智慧物流管理一直是一門很熱門的話題，並且這個課題已經研究了很長一段時間，由於目前尚未有一個最佳的演算法來解決所有「路徑最佳化」的問題，故仍然是一個值得深入探討的議題。高效率、低成本一直是許多公司所追求的目標，因此「路徑最佳化」對於公司以及政府有著十分重要的影響。路徑最佳化可以幫助政府提高服務民眾的效率，尤其在全世界新冠病毒(COVID-19)疫情爆發的時候更為重要，提升效率對於預防疫情大肆蔓延並最大程度減少對公眾的負面影響有著極大的幫助。
本論文主要研究最佳化車輛載重限制之車輛運途問題(CVRP)，研究重點是開發兩個混和模型，包含增強版的基因演算法(GA)和增強版的人工免疫系統(AIS)兩種演算法之比較。研究方法是先以增強版本的掃描法做分群，再通過最佳化演算法進行優化，而分群的方式是基於車輛容量和客戶需求進行分群。研究的目標是最小化運輸成本，即在滿足所有限制條件下，為所有客戶提供服務所需的行駛路徑最小。通過在20個基準問題中，使用GA和AIS兩種演算法進行了實驗，然後將倉庫位置改變後，再次進行測試標竿問題。從實驗數據說明，這兩種演算法的結果在大多數情況下都是很接近的，但是在處理小於70個需求點的問題時，AIS比GA相對更好；反之大規模問題時，GA則會比AIS的最佳解較低。而在時間方面，GA的表現更優於AIS，GA的運行速度比AIS快約30%。由於兩種演算法都可以提供良好的結果，因此它們都可以很好的解決具有不同目的的問題。

Intelligent logistics management has always been a hot topic that has been under research for a long period of time. Nonetheless, the topic of route optimization is similarly important since there is no best algorithm to solve all problems. However, the results produced from route optimization have a very huge impact on businesses and even the government. For instance, businesses are able to lower its logistic costs and reduce delivery time when they are able to deliver products to customers through the best way. Route optimization also helps to add efficiency for the government to serve the citizens especially when pandemics, such as COVID-19, strike the world where efficiency is required to prevent further disaster and to minimize negative impacts on the public.
This thesis focuses on route optimization for the Capacitated Vehicle Routing Problem (CVRP). Two hybrid algorithms, enhanced Genetic Algorithm (GA) and enhanced Artificial Immune System (AIS), are developed by cluster-first approach with the help of enhanced sweep algorithm. Both hybrid algorithms begin with grouping customers based on the vehicle capacity and their demands, then optimized through the optimization algorithms. The objective of the research is to minimize the cost of delivery, which is associated with the distance travelled to serve at all the customers under all constraints. We conduct the experiment with two hybrid algorithms in 20 benchmark problems, along with two different direction of movement for depot to a total of 60 testing problems. From experimental results, near-optimal solutions for both hybrid algorithms in most cases are close to each other. However, the hybrid algorithms of AIS works relatively better than the hybrid algorithm of GA for smaller scale problems with lower than or equal to 70 nodes in most cases. On the other hand, hybrid model by GA works relatively better than the hybrid model by AIS for larger scale problems. On the computational time, the GA relatively works faster than the AIS with the speed of approximately 30% faster. Therefore, since both hybrid algorithms are able to provide good results, they are both good to solve problems with varying purposes.

Augerat, P., Belenguer, J. M., Benavent, E., Corberán, A., Naddef, D., & Rinaldi, G. (1995). Computational results with a branch and cut code for the capacitated vehicle routing problem (Vol. 34). IMAG.
Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800. (DOI: 10.1016/S0305-0548(02)00051-5)
Baldacci, R., Mingozzi, A., & Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1), 1-6. (DOI: 10.1016/j.ejor.2011.07.037)
Baldacci, R., Hadjiconstantinou, E., & Mingozzi, A. (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations Research, 52(5), 723-738. (DOI: 10.1287/opre.1040.0111)
Balinski, M. L., & Quandt, R. E. (1964). On an integer program for a delivery problem. Operations Research, 12(2), 300-304. (DOI: 10.1287/opre.12.2.300)
Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1), 41-48. (DOI: 10.1016/j.aei.2004.07.001)
Bergstrom, R. Y. (1993). An annotated essay: environmental affairs. Production, 105(4), 36-41.
Bersini, H., & Varela, F. J. (1990). Hints for adaptive problem solving gleaned from immune networks. In International Conference on Parallel Problem Solving from Nature (343-354). Springer, Berlin, Heidelberg. (DOI: 10.1007/BFb0029775)
Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research, 89, 319-328. (DOI: 10.1023/A:1018940026670)
Chen, A. L., Yang, G. K., & Wu, Z. M. (2006). Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University-Science A, 7(4), 607-614. (DOI: 10.1631/jzus.2006.A0607)
Chen, J. C., Wu, C. C., Chen, C. W., & Chen, K. H. (2012). Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm. Expert Systems with Applications, 39(11), 10016-10021. (DOI: 10.1016/j.eswa.2012.01.211)
Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20(3), 309-318.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581. (DOI: 10.1287/opre.12.4.568)
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. (DOI: 10.1287/mnsc.6.1.80)
Deaven, D. M., & Ho, K. M. (1995). Molecular geometry optimization with a genetic algorithm. Physical Review Letters, 75(2), 288. (DOI: 10.1103/PhysRevLett.75.288)
De Castro, L. N., & Timmis, J. (2002, May). An artificial immune network for multimodal function optimization. In Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No. 02TH8600) (Vol. 1, 699-704). IEEE. (DOI: 10.1109/CEC.2002.1007011)
Diabat, A., Kannan, D., Kaliyan, M., & Svetinovic, D. (2013). An optimization model for product returns using genetic algorithms and artificial immune system. Resources, Conservation and Recycling, 74, 156-169. (DOI: 10.1016/j.resconrec.2012.12.010)
Faulin, J., Lera-López, F., & Juan A. A. (2011). Optimizing routes with safety and environmental criteria in transportation management in Spain: A case study, International Journal of Information Systems and Supply Chain Management, 4(3), 38-59. (DOI: 10.4018/jisscm.2011070103)
Forrest, S., Perelson, A. S., Allen, L., & Cherukuri, R. (1994). Self-nonself discrimination in a computer. In Proceedings of 1994 IEEE Computer Society Symposium on Research in Security and Privacy (202-212). Ieee. (DOI: 10.1109/RISP.1994.296580)
Ghoseiri, K., & Ghannadpour, S. F. (2009). An efficient heuristic method for capacitated p-median problem. International Journal of Management Science and Engineering Management, 4(1), 72-80. (DOI: 10.1080/17509653.2009.10671064)
Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2), 340-349. (DOI: 10.1287/opre.22.2.340)
Golden, B. L., Magnanti, T. L., & Nguyen, H. Q. (1975). Implementing Vehicle Routing Algorithms. Massachusetts Institute of Technology Cambridge Operations Research Center.
Grefenstette, J. J. (1986). Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 16(1), 122-128. (DOI: 10.1109/TSMC.1986.289288)
Harmer, P. K., Williams, P. D., Gunsch, G. H., & Lamont, G. B. (2002). An artificial immune system architecture for computer security applications. IEEE Transactions on Evolutionary Computation, 6(3), 252-280. (DOI: 10.1109/TEVC.2002.1011540)
Hatata, A. Y., Osman, M. G., & Aladl, M. M. (2017). A review of the clonal selection algorithm as an optimization method. Leonardo Journal of Sciences, 16(30), 1-14.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University of Michigan Press.
Ishida, T., & Goldfarb, R. B. (1990). Fundamental and harmonic susceptibilities of YBa 2 Cu 3 O 7− δ. Physical Review B, 41(13), 8937. (DOI: 10.1103/PhysRevB.41.8937)
Jerne, N. K. (1973). The immune system. Scientific American, 229(1), 52-63.
Jordehi, A. R. (2015). A chaotic artificial immune system optimisation algorithm for solving global continuous optimisation problems. Neural Computing and Applications, 26(4), 827-833. (DOI: 10.1007/s00521-014-1751-5)
Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43(4), 408-416. (DOI: 10.1287/trsc.1090.0301)
Laporte, G., Gendreau, M., Potvin, J. Y., & Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7(4‐5), 285-300. (DOI: 10.1111/j.1475-3995.2000.tb00200.x)
Lei, H., Laporte, G., & Guo, B. (2011). The capacitated vehicle routing problem with stochastic demands and time windows. Computers & Operations Research, 38(12), 1775-1783. (DOI: 10.1016/j.cor.2011.02.007)
Liu, R., & Jiang, Z. (2019). A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints. Applied Soft Computing, 80, 18-30. (DOI: 10.1016/j.asoc.2019.03.008)
Maxie, E. (1994). Supplier performance and the environment. In Proceedings of 1994 IEEE International Symposium on Electronics and The Environment (323-327). IEEE. (DOI: 10.1109/ISEE.1994.337238)
Mohammed, M. A., Abd Ghani, M. K., Hamed, R. I., Mostafa, S. A., Ahmad, M. S., & Ibrahim, D. A. (2017). Solving vehicle routing problem by using improved genetic algorithm for optimal solution. Journal of Computational Science, 21, 255-262. (DOI: 10.1016/j.jocs.2017.04.003)
Na, B., Jun, Y., & Kim, B. I. (2011). Some extensions to the sweep algorithm. The International Journal of Advanced Manufacturing Technology, 56(9-12), 1057-1067. (DOI: 10.1007/s00170-011-3240-7)
Nazif, H., & Lee, L. S. (2012). Optimised crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling, 36(5), 2110-2117. (DOI: 10.1016/j.apm.2011.08.010)
Nurcahyo, G. W., Alias, R. A., Shamsuddin, S. M., & Sap, M. N. M. (2002). Sweep algorithm in vehicle routing problem for public transport. Jurnal Antarabangsa Teknologi Maklumat, 2, 51-64.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(4), 421-451. (DOI: 10.1007/BF02023004)
Perelson, A. S. (1989). Immune network theory. Immunol. Rev, 110(5). (DOI: 10.1111/j.1600-065x.1989.tb00025.x)
Ramachandran, K. N., Belding-Royer, E. M., Almeroth, K. C., & Buddhikot, M. M. (2006). Interference-Aware Channel Assignment in Multi-Radio Wireless Mesh Networks. Infocom (Vol. 6, pp. 1-12).
Ralphs, T. K., Kopman, L., Pulleyblank, W. R., & Trotter, L. E. (2003). On the capacitated vehicle routing problem. Mathematical Programming, 94(2-3), 343-359. (DOI: 10.1007/s10107-002-0323-0)
Read, M., Andrews, P. S., Timmis, J., & Kumar, V. (2012). Techniques for grounding agent-based simulations in the real domain: a case study in experimental autoimmune encephalomyelitis. Mathematical and Computer Modelling of Dynamical Systems, 18(1), 67-86. (DOI: 10.1080/13873954.2011.601419)
Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers & Operations Research, 22(1), 5-13. (DOI: 10.1016/0305-0548(93)E0014-K)
Sariklis, D., & Powell, S. (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 51(5), 564-573. (DOI: 10.1057/palgrave.jors.2600924)
Schaffer, J. D., Caruana, R., Eshelman, L. J., & Das, R. (1989). A study of control parameters affecting online performance of genetic algorithms for function optimization. In Proceedings of the 3rd international conference on genetic algorithms (pp. 51-60).
Shi, G., & Jing, Y. (2009, May). Research of improved immune clonal algorithms and its applications. In 2009 IEEE International Conference on Computational Intelligence for Measurement Systems and Applications (212-215). IEEE. (DOI: 10.1109/CIMSA.2009.5069950)
Szeto, W. Y., Wu, Y., & Ho, S. C. (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215(1), 126-135. (DOI: 10.1016/j.ejor.2011.06.006)
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285. (DOI: 10.1016/0377-2217(93)90182-M)
Tarantilis, C. D., & Kiranoudis, C. T. (2002). Distribution of fresh meat. Journal of Food Engineering, 51(1), 85-91. (DOI: 10.1016/S0260-8774(01)00040-1)
Timmis, J., & Neal, M. (2001). A resource limited artificial immune system for data analysis. In Research and Development in Intelligent Systems XVII (19-32). Springer, London. (DOI: 10.1007/978-1-4471-0269-4_2)
Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123(1-3), 487-512. (DOI: 10.1016/S0166-218X(01)00351-1)
Wang, C. H., & Lu, J. Z. (2009). A hybrid genetic algorithm that optimizes capacitated vehicle routing problems. Expert Systems with Applications, 36(2), 2921-2936. (DOI: 10.1016/j.eswa.2008.01.072)
Weise, T., Podlich, A., & Gorldt, C. (2009). Solving real-world vehicle routing problems with evolutionary algorithms. In Natural Intelligence for Scheduling, Planning and Packing Problems (29-53). Springer, Berlin, Heidelberg. (DOI: 10.1007/978-3-642-04039-9_2)
Wikarek, J., Sitek, P., & Zawarczyński, Ł. (2019). An integer programming model for the capacitated vehicle routing problem with drones. In International Conference on Computational Collective Intelligence (511-520), Springer, Cham.
Wren, A., & Holliday, A. (1972). Computer scheduling of vehicles from one or more depots to a number of delivery points. Journal of the Operational Research Society, 23(3), 333-344. (DOI: 10.1057/jors.1972.53)
Xiao, Y., Zhao, Q., Kaku, I., & Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers & Operations Research, 39(7), 1419-1431. (DOI: 10.1016/j.cor.2011.08.013)