具時窗限制的載具排程問題係解決在給定需求及服務時間限制的前提下，以有限容量的載具組合，從基地出發服務散佈於地理上的各個需求點。要解決並符合所有限制條件的載具最佳化路徑問題，其目標不但載具數量需最少化，而且傳送距離成本亦須達到最低。本研究提出一個混合演化的搜尋策略演算法，以漸進搜尋和專業的基因運算為特色的局部探索，來求解具時窗限制的載具排程問題。其中並分別應用以路程總距離為倒數的適應函數和輪轉盤法來做基因突變的操作，以求解此路徑排程問題的連續最佳化；不同於折衷函數往往需要多樣的參數和限制的先期研究，所提出的混合演化搜尋的演算法，期望能簡化所有路徑的限制和目標，從路徑成本的降低和更好的群聚路徑及廣域的分散區域搜尋，進而提升為路徑排程的最佳解。最後藉由Solomon (1987)提出之56題國際標竿試題測試演算法績效，並和文獻已知的最佳解作驗證與比較；而模擬結果顯示，所提出的混合演化搜尋的演算法有多個結果超越或接近已知最佳解，可以是載具路徑排程理想的解決方案。

The vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with finite capacity from a depot to a set of geographically scattered nodes with known demands and predefined time windows. This problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of number of vehicles and delivering distance. This thesis proposes a hybrid evolutionary search strategy algorithm (HESSA) that incorporates heuristics solution of the local exploration in the evolutionary search with specialized genetic operators. The fitness function and mutation of the sequence-oriented optimization in VRPTW are realized by the inverse of the total distance and the roulette wheel, respectively. Different existing VRPTW researches often aggregate multiple criteria and constraints into a compromise function, the proposed HESSA simultaneously optimizes all routing constraints and objectives, and improves the routing solutions in many appearances, such as lower routing cost, better cluster trace, and wider scattering area search. The HESSA can obtain the optimal solution by balancing the exploring and developing ability. Finally, the proposed HESSA is applied to solve the benchmark problem, Solomon’s 56 VRPTW 100-customer instances. Simulation results demonstrate that 17 routing solutions are better than or competitive as compared to the best solutions published in the literature.

[1] A. W. J. Kolen, A. H. G. R. Kan, and H. W. J. M. Trienekens, “Vehicle routing with time windows,” Oper. Res., vol. 35, no. 2, pp. 266–273, 1987.
[2] N. Kohl, J. Desrosiers, O. B. G. Madsen, M. M. Solomon, and F. Soumis, “2-path cuts for the vehicle routing problem with time windows,” Transp. Sci., vol. 33, no. 1, pp. 101–116, 1999.
[3] Y. Rochat and E. D. Taillard, “Probabilistic diversification and intensification in local search for vehicle routing,” J. Heuristics, vol. 1, no. 1, pp. 147–167, 1995.
[4] M. M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Oper. Res., vol. 35, no. 2, pp. 254–265, 1987.
[5] M. Gendreau, A. Hertz, and G. Laporte, “A tabu search heuristic for the vehicle routing problem,” Manage. Sci., vol. 40, pp. 1276–1290, 1994.
[6] E. Taillard, P. Badeau, M. Gendreau, F. Geurtin, and J-Y. Potvin. “A tabu search heuristic for the vehicle routing problem with soft time windows,” Transp. Sci., vol. 31, no. 2, pp. 170–186, 1997.
[7] J. F. Cordeau, G. Laporte, and A. Mercier, “A unified tabu search heuristic for vehicle routing problems with time windows,” J. Oper. Res. Soc., vol. 52, No. 8, pp. 928–936, Aug. 2001.
[8] L. H. Lee, K. C. Tan, K. Ou, and Y. H. Chew, “Vehicle capacity planning system: A case study on vehicle routing problem with time windows,” IEEE Trans. Syst., Man Cybern. Pt. A-Syst., Humans, vol. 33, no. 2, pp. 169–178, Mar. 2003.
[9] R. Bent and P. V. Hentenryck, “A two-stage hybrid local search for the vehicle routing problem with time windows,” Transp. Sci., vol. 38, no. 4, pp. 515–530, 2004.
[10] W. C. Chiang and R. A. Russell, “Simulated annealing metaheuristics for the vehicle routing problem with time windows,” Ann. Oper. Res., vol. 63, no. 1, pp. 3–27, 1996.
[11] Z. J. Czech and P. Czarnas, “Parallel simulated annealing for the vehicle routing problem with time windows,” in Proc. 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands, Spain, pp. 376–383, 2002.
[12] A. Debudaj-Grabysz and Z. Czech, “Theoretical and practical issues of parallel simulated annealing,” Parallel Process. Appl. Math., pp. 189–198, 2008.
[13] G. B. Alvarenga, G. R. Mateus, and G. D. Tomi, “A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows,” Comput. Oper. Res., vol. 34, no. 6, pp. 1561–1584, 2007.
[14] K. Ghoseiri and S. F. Ghannadpour, “Hybrid genetic algorithm for vehicle routing and scheduling problem,” J. Appl. Sci., vol. 9, no. 1, pp. 79–87, 2009.
[15] H. Nazif and L. S. Lee, “Optimized crossover genetic algorithm for vehicle routing problem with time windows,” Amer. J. Appl. Sci., vol. 7, no. 1, pp. 95–101, 2010.
[16] G. Jeon, H. R. Leep, and J. Y. Shim, “A vehicle routing problem solved by using a hybrid genetic algorithm,” Comput. Ind. Eng., vol. 53, no. 4, pp. 680–692, 2007.
[17] M. Dorigo, V. Maniezzo, and A. Colorni, “The Ant System: An Autocatalytic Optimizing Process.” Tech. Rep., no. 91–016 Revised, Politecnico di Milano, Milan, Italy, 1991.
[18] J. E. Bell and P. R. McMullen. “Ant colony optimization techniques for the vehicle routing problem.” Adv. Eng. Inform., vol. 18, pp. 41–48, 2004.
[19] L. M. Gambardella, E. Taillard, and G. Agazzi, “MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows,” New. Ideas. Optimization, New York: McGraw-Hill, pp. 63–76, 1999.
[20] X. Tan, X. Zhuo, and J. Zhang, “Ant colony system for optimizing vehicle routing problem with time windows,” Lect. Notes Comput. Sci., vol. 4115, pp. 33–38, 2006.
[21] C. H. Chen and C. J. Ting, “A hybrid ant colony system for vehicle routing problem with time windows,” J. Eastern Asia Soc. Transp. Stud., vol. 6, pp. 2822–2836, 2005.
[22] B. Yu, Z. Z. Yang, and B. Z. Yao, “A hybrid algorithm for vehicle routing problem with time windows,” Expert Syst. Appl., vol. 38, no. 1, pp. 435–441, 2011.
[23] P. P. Repoussis, C. D. Tarantilis, and G. Ioannou, “Arc-guided evolutionary algorithm for the vehicle routing problem with time windows,” IEEE Trans. Evol. Comput., vol. 13, no. 3, pp. 624–647, Jun. 2009.
[24] J. Berger and M. Barkaoui, “A parallel hybrid genetic algorithm for the vehicle routing problem with time windows,” Comput. Oper. Res., vol. 31, no. 12, pp. 2037–2053, 2004.
[25] A. L. Bouthillier and T. G. Crainic, “A cooperative parallel meta-heuristic for the vehicle routing problem with time windows,” Comput. Oper. Res., vol. 32, no. 7, pp. 1685–1708, 2005.
[26] B. Ombuki, B. J. Ross, and F. Hanshar, “Multi-objective genetic algorithms for vehicle routing problem with time windows,” Appl. Intell., vol. 24, no. 1, pp. 17–30, 2006
[27] J.Kennedy and R. Eberhart, “Particle swarm optimization,” in Proc. IEEE Int. Conf. Neural Netw., vol. 4, pp. 1942–1948, 1995.
[28] R. Poli, J. Kennedy, and T. Blackwell, “Particle swarm optimization: An overview,” Swarm Intell., vol. 1, no. 1, pp. 33–57, 2007.
[29] J. Kennedy and R. Mendes, “Neighborhood topologies in fully informed and best-of-neighborhood particle swarms,” IEEE Trans. Syst., Man, Cybern. Pt. C-Appl. Rev., vol. 36, no. 4, pp. 515–519, Jul. 2006.
[30] Z. H. Zhan, J. Zhang,Y. Li, and H. S.-H. Chung, “Adaptive particle swarm optimization,” IEEE Trans. Syst., Man, and Cybern. Pt. B-Cybern., vol. 39, no. 6, pp. 1362–1381, Dec. 2009.
[31] J. J. Liang, A. K. Qin, P. N. Suganthan, and S. Baskar, “Comprehensive learning particle swarm optimizer for global optimization of multimodal functions,” IEEE Trans. Evol. Comput., vol. 10, no. 3, pp. 281–295, Jun. 2006.
[32] K. Veeramachaneni, L. A. Osadciw, and P. K. Varshney, “An adaptive multimodal biometric management algorithm,” IEEE Trans. Syst., Man, and Cybern. Pt. C-Appl. Rev., vol. 35, no. 3, pp. 344–356, Aug. 2005.
[33] C. J. Lin, C. H. Chen, and C. T. Lin, “A hybrid of cooperative particle swarm optimization and cultural algorithm for neural fuzzy networks and its prediction applications,” IEEE Trans. Syst., Man, Cybern. Pt. C-Appl. Rev., vol. 39, no. 1, pp. 55–68, Jan. 2009.
[34] R. V. Kulkarni and G. K. Venayagamoorthy, “Bio-inspired algorithms for autonomous deployment and localization of sensor nodes,” IEEE Trans. Syst., Man, Cybern. Pt. C-Appl. Rev., vol. 40, no. 6, pp. 663–675, Nov. 2010.
[35] P. Kanakasabapathy and K. S. Swarup, “Evolutionary tristate PSO for strategic bidding of pumped-storage hydroelectric plant,” IEEE Trans. Syst., Man, Cybern. Pt. C-Appl. Rev., vol. 40, no. 4, pp. 460–471, Jul. 2010.
[36] R. V. Kulkarni and G. K. Venayagamoorthy, “Particle swarm optimization in wireless-sensor networks: A brief survey,” IEEE Trans. Syst., Man, Cybern. Pt. C-Appl. Rev., vol. 41, no. 2, pp. 262–267, 2011.
[37] Q. Zhu, L. M. Qian, Y. C. Li, and S. J. Zhu, “An improved particle swarm optimization algorithm for vehicle routing problem with time windows,” IEEE Congr. Evol. Comput., pp. 1386–1390, 2006.
[38] T. J. Ai and V. Kachitvichyanukul, “A particle swarm optimization for vehicle routing problem with time windows,” Int. J. Oper. Res., vol. 6, no. 4, pp. 519–537, 2009.
[39] S. Amini, H. Javanshir, and R. Tavakkoli-Moghaddam, “A PSO approach for solving VRPTW with real case study,” Int. J. Res. Rev. Appl. Sci., vol. 4, no. 3, pp. 118–126, 2010.
[40] J. P. Castro, D. Landa-Silva, and J. A. M. P´erez, “Exploring feasible and infeasible regions in the vehicle routing problem with time windows using a multi-objective particle swarm optimization approach,” Nat. Inspired Cooperative Strategies Optim., vol. 236, pp. 103–114, 2009.
[41] Y. J. Gong, J. Zhang, O. Liu, R. Z. Huang, H. S. H. Chung and Y. H. Shi, “Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach,” IEEE Trans. Syst., Man, Cybern. Pt. C-Appl. Rev., vol. 42, no. 2, pp. 254–267, Mar. 2012.
[42] J. Homberger and H. Gehring, “A two-phase hybrid metaheuristic for the vehicle routing problem with time windows,” Eur. J. Oper. Res., vol. 162, no.3, pp. 220–238, 2005.
[43] R. Tavakkoli-Moghaddam, N. Safaei, and Y. Gholipour, “A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length,” Appl. Math. Comput, vol. 176, pp. 445–454, Aug., 2006.
[44] B. Golden, T. Magnanti, and H. Nguyen, “Implementing vehicle routing algorithms,” Networks, vol. 7, pp 113-148, 1977.
[45] Lin, S., “Computer solutions to the travelling salesman problem,” Bell. Syst. Tech. J., vol. 44, pp. 2245-2269, 1965.
[46] J. Homberger, Verteilt-parallele Metaheuristiken zur Tourenplanung. Wiesbaden, Germany: Gaber, 2000.
[47] H. Li, A. Lim, and J. Huang, “Local search with annealing-like restarts to solve the VRPTW,” Working Paper, Eur. J. Oper. Res., vol. 150, no.1, pp. 115–127, 2003.
[48] D. Mester, “An evolutionary strategies algorithm for large scale vehicle routing problem with capacitate and time windows restrictions,” Working Paper, Inst. Evol., Univ. Haifa, Israel, 2002.
[49] P. Shaw, “A new local search algorithm providing high quality solutions to vehicle routing problems,” Working Paper, Dept. of Comput. Sci., Univ. Strathclyde, Glasgow, Scotland, 1997.
[50] J. Homberger and H. Gehring, “Two evolutionary metaheuristics for the vehicle routing problem with time windows,” Inf. Syst. Oper. Res., vol. 37, pp. 297–318, 1999.
[51] L. M. Rousseau, M. Gendreau, and G. Pesant, “Using constraint-based operators to solve the vehicle routing problem with time windows,” J. Heuristics, vol. 8, no. 1, pp. 43–58, 2002.
[52] P. Shaw, “Using constraint programming and local search methods to solve vehicle routing problems,” Proc. Principles Pract. Constraint Program., LNCS 1520, vol. 1, pp. 417–431, 1998.
[53] G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, and G. Dueck, “Record breaking optimization results using the ruin and recreate principle,” J. Comput. Phys., vol. 159, no. 2, pp. 139–171, 2000.
[54] T. Ibaraki, M. Kubo, T. Masuda, T. Uno, and M. Yagiura, “Effective local search algorithms for the vehicle routing problem with general time windows,” Working Paper, Dept. Appl. Math. Phys., Kyoto Univ., Japan, 2001.
[55] R. A. Russell and W. C. Chiang, “Scatter search for the vehicle routing problem with time windows,” Eur. J. Oper. Res., vol. 169, no.3, pp. 606–622, 2006.