本文研究具有多個時間窗的冰淇淋配送問題(DICMTW)，此問題為傳統車輛路徑問題 (VRP) 的擴展，並被歸類為 NP-hard問題。此DICMTW問題假設顧客有不同的喜好時間窗可以補貨，即上午、下午、上午/下午，為冰淇淋配送問題中的重要實務假設，此多個時間窗的DICMTW問題比傳統只有一個時間窗的VRP問題更加複雜。本研究DICMTW的問題目標為最小化總貨車行駛距離和服務時間。
本文提出了一種新的編碼方式，將任何隨機整數序列直接轉換為 DICMTW 問題的可行解，並將此新的編碼方式結合免疫算法 (IA) 和基因演算法 (GA) 求解 DICMTW問題。本文以印尼知名冰淇淋公司真實案例進行實驗，利用IA和GA分別求解，以探討研究方法的性能。數值結果顯示，提出的IA和GA可以有效地解決DICMTW問題，除此之外，統計測試檢定結果顯示，對於測試問題， IA表現優於GA。本研究結果有助於進一步研究在提供冰淇淋方面具有多個時間窗的車輛路徑問題。

This research addresses the delivery of ice cream with multiple vehicle and time windows (DICMVTW) which is an extension of the classical vehicle routing problem (VRP). Based on the preference of customers, the DICMVTW assumes that each customer has different practical time windows of delivery for ice cream, namely, AM, PM, AM/PM. Therefore, the DICMVTW is classified as an NP-hard problem and it is more complex to solve compared to the classical VRP with only a single time window. In the DICMVTW, the demand of ice cream of each customer has to be delivered based on their time windows by using heterogeneous vehicles with various capacities. The objective of the considered DICMVTW is to determine the best assignment of vehicle for customers and to minimize the total traveling distance and service times of all vehicles.
In this study, a novel coding scheme has been developed to directly convert a sequence of random integers into a feasible solution of the DICMVTW which simultaneously determines the sequence of the route trip for vehicles into various time windows, and then it is embedded into two artificial intelligence algorithms including an immune algorithm (IA) and genetic algorithm (GA) to solve the DICMVTW. This thesis also compares the performance between the immune algorithm and the genetic algorithm to solve the delivery of ice cream with multiple vehicles and time windows. A real case of ice cream delivery in Indonesia is experimented with by using the two proposed algorithms. Numerical results of test problems in Indonesia show that the proposed immune algorithm and genetic algorithm can be used to effectively solve the DICMVTW, and the statistical test results show that the proposed immune algorithm is superior to that of genetic algorithm. This research also could contribute for further research in vehicle routing problem with multiple time windows in term of delivering an ice cream.

Abstract........................................................ i
摘要............................................................ iii
Acknowledgments................................................. iv
Table of Contents................................................. v
List of Table................................................. vii
List of Figure................................................. ix
Chapter 1 Introduction................................................. 1
1.1 Background and Motivation.............................................. 1
1.2 The objective of the Research................................................. 2
1.3 Outline of the Research................................................. 3
1.4 Structure of the Thesis................................................. 6
Chapter 2 Literature Review and Research Method................................................. 8
2.1 Literature Review of Vehicle Routing Problem................................................. 8
2.1.1 Vehicle Routing Problem ................................................. 8
2.1.2 Vehicle Routing Problem with Multiple Time Windows................................................. 11
2.2 Literature Review of Research Method................................................. 13
2.2.1 Genetic Algorithm................................................. 13
2.2.2 Immune Algorithm................................................. 19
2.2.3 Taguchi Method................................................. 25
Chapter 3 Illustration Encoding of Test Problem................................................. 30
3.2 Problem Assumption................................................. 31
3.3 Coding Method................................................. 31
3.4 Parameter Setting................................................. 37
Chapter 4 Results and Analysis................................................. 40
4.1 Equipment Environment and Parameter Setting................................................. 40
4.2 The Problem Test in Indonesia................................................. 41
4.3 Analysis of the Numerical Result of DICMVTW................................................. 44
4.5 Analysis of Penalty................................................. 52
4.6 Statistical Test of Adopted Algorithms................................................. 55
Chapter 5 Conclusion................................................. 57
5.1 Conclusions................................................. 57
5.2 Contribution of this Research................................................. 58
5.3 Limitation and Further Research................................................. 58
References................................................. 59
Appendix I................................................. 66
Extended Abstract................................................. 70

[1]E. Calixto, Gas and Oil Reliability Engineering: Modeling and Analysis. Gulf Professional Publishing, 2016.
[2]R. Casado-Vara, A. González-Briones, J. Prieto, and J. M. Corchado, “Smart Contract for Monitoring and Control of Logistics Activities: Pharmaceutical Utilities Case Study,” in The 13th International Conference on Soft Computing Models in Industrial and Environmental Applications, 2018, pp. 509–517.
[3]Y. Tseng, W. L. Yue, and M. A. P. Taylor, “The Role of Transportation in Logistics Chain,” 2005.
[4]A. Rong, R. Akkerman, and M. Grunow, “An Optimization Approach for Managing Fresh Food Quality throughout the Supply Chain,” Int. J. Prod. Econ., vol. 131, no. 1, pp. 421–429, 2011.
[5]G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Manage. Sci., vol. 6, no. 1, pp. 80–91, 1959.
[6]M. Asghari and S. M. J. M. Al-e, “Green Vehicle Routing Problem: A State-of-the-Art Review,” Int. J. Prod. Econ., p. 107899, 2020.
[7]P. Toth and D. Vigo, “An Overview of Vehicle Routing Problems,” Veh. routing Probl., pp. 1–26, 2002.
[8]V. K. Sandhya, “Issues in Solving Vehicle Routing Problem with Time Window and its Variants using Meta Heuristics-A Survey,” Int. J. Eng. Technol., vol. 3, no. 6, pp. 668–672, 2013.
[9]U. Klanšek, “Using the TSP Solution for Optimal Route Scheduling in Construction Management,” Organ. Technol. Manag. Constr. an Int. J., vol. 3, no. 1, pp. 243–249, 2011.
[10]T. Bektas, “The Multiple Traveling Salesman Problem: an Overview of Formulations and Solution Procedures,” Omega, vol. 34, no. 3, pp. 209–219, 2006.
[11]M. A. H. Akhand, Z. J. Peya, and T. Sultana, “Solving Capacitated Vehicle Routing Problem with Route Optimization using Swarm Intelligence,” in 2015 2nd International Conference on Electrical Information and Communication Technologies (EICT), 2015, pp. 112–117.
[12]A. V Donati, R. Montemanni, N. Casagrande, A. E. Rizzoli, and L. M. Gambardella, “Time Dependent Vehicle Routing Problem with a Multi Ant Colony System,” Eur. J. Oper. Res., vol. 185, no. 3, pp. 1174–1191, 2008.
[13]C. Archetti and M. G. Speranza, “The Split Delivery Vehicle Routing Problem: A Survey,” in The Vehicle Routing Problem: Latest Advances and New Challenges, Springer, 2008, pp. 103–122.
[14]P. Toth and D. Vigo, “VRP with Backhauls,” in The Vehicle Routing Problem, SIAM, 2002, pp. 195–224.
[15]J. Ruiz-Meza, A. T. Espinosa, D. M. Ayala, and G. M. Ortega, “Vehicle Routing Problem with Simultaneous Pickup and Delivery for Milk Collection in Galeras, Sucre,” EasyChair, 2020.
[16]M. Desrochers, J. Desrosiers, and M. Solomon, “A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows,” Oper. Res., vol. 40, no. 2, pp. 342–354, 1992.
[17]S. R. Thangiah, J.-Y. Potvin, and T. Sun, “Heuristic Approaches to Vehicle Routing with Backhauls and Time Windows,” Comput. Oper. Res., vol. 23, no. 11, pp. 1043–1057, 1996.
[18]L. Grandinetti, F. Guerriero, F. Pezzella, and O. Pisacane, “A Pick-up and Delivery Problem with Time Windows by Electric Vehicles,” Int. J. Product. Qual. Manag., vol. 18, no. 2–3, pp. 403–423, 2016.
[19]S. Belhaiza, R. M’Hallah, and G. Ben Brahim, “A New Hybrid Genetic Variable Neighborhood Search Heuristic for the Vehicle Routing Problem with Multiple Time Windows,” in 2017 IEEE Congress on Evolutionary Computation (CEC), 2017, pp. 1319–1326.
[20]S. Belhaiza, P. Hansen, and G. Laporte, “A Hybrid Variable Neighborhood Tabu Search Heuristic for the Vehicle Routing Problem with Multiple Time Windows,” Comput. Oper. Res., vol. 52, pp. 269–281, 2014.
[21]G. Pesant, M. Gendreau, J.-Y. Potvin, and J.-M. Rousseau, “On the Flexibility of Constraint Programming Models: From Single to Multiple Time Windows for the Traveling Salesman Problem,” Eur. J. Oper. Res., vol. 117, no. 2, pp. 253–263, 1999.
[22]A. Goel, “The Minimum Duration Truck Driver Scheduling Problem,” EURO J. Transp. Logist., vol. 1, no. 4, pp. 285–306, 2012.
[23]A. Goel and L. Kok, “Truck Driver Scheduling in the United States,” Transp. Sci., vol. 46, no. 3, pp. 317–326, 2012.
[24]F. Tricoire, M. Romauch, K. F. Doerner, and R. F. Hartl, “Heuristics for the Multi-period Orienteering Problem with Multiple Time Windows,” Comput. Oper. Res., vol. 37, no. 2, pp. 351–367, 2010.
[25]W. Souffriau, P. Vansteenwegen, G. Vanden Berghe, and D. Van Oudheusden, “The Multiconstraint Team Orienteering Problem with Multiple Time Windows,” Transp. Sci., vol. 47, no. 1, pp. 53–63, 2013.
[26]D. Favaretto, E. Moretti, and P. Pellegrini, “Ant Colony System for a VRP with Multiple Time Windows and Multiple Visits,” J. Interdiscip. Math., vol. 10, no. 2, pp. 263–284, 2007.
[27]A. K. Beheshti, S. R. Hejazi, and M. Alinaghian, “The Vehicle Routing Problem with Multiple Prioritized Time Windows: A case study,” Comput. Ind. Eng., vol. 90, pp. 402–413, 2015.
[28]S. Belhaiza, “A Game Theoretic Approach for the Real-Life Multiple-Criterion Vehicle Routing Problem with Multiple Time Windows,” IEEE Syst. J., vol. 12, no. 2, pp. 1251–1262, 2016.
[29]M. Hoogeboom, W. Dullaert, D. Lai, and D. Vigo, “Efficient Neighborhood Evaluations for the Vehicle Routing Problem with Multiple Time Windows,” Transp. Sci., vol. 54, no. 2, pp. 400–416, 2020, doi: https://doi.org/10.1007/s12351-019-00521-0.
[30]K. Wang, “Computational Intelligence in Agile Manufacturing Engineering,” Agil. Manuf. 21st Century Compet. Strateg. Oxford, UK Elsevier Sci. Ltd, pp. 297–315, 2001.
[31]K. Ghoseiri and S. F. Ghannadpour, “Multi-Objective Vehicle Routing Problem with Time Windows using Goal Programming and Genetic Algorithm,” Appl. Soft Comput., vol. 10, no. 4, pp. 1096–1107, 2010.
[32]Y. Chang and L. Chen, “Solve the Vehicle Routing Problem with Time Windows Via a Genetic Algorithm,” in Conference Publications, 2007, vol. 2007, no. Special, p. 240.
[33]Y. P. Anggodo, A. K. Ariyani, M. K. Ardi, and W. F. Mahmudy, “Optimization of Multi-Trip Vehicle Routing Problem with Time Windows using Genetic Algorithm,” J. Environ. Eng. Sustain. Technol., vol. 3, no. 2, pp. 92–97, 2017.
[34]X. Wang, C. Xu, and X. Hu, “Genetic Algorithm for Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles,” in 2008 International Conference on Management Science and Engineering 15th Annual Conference Proceedings, 2008, pp. 128–133.
[35]P. K. Nguyen, T. G. Crainic, and M. Toulouse, “A Hybrid Generational Genetic Algorithm for the Periodic Vehicle Routing Problem with Time Windows,” J. Heuristics, vol. 20, no. 4, pp. 383–416, 2014.
[36]P. Li, J. He, D. Zheng, Y. Huang, and C. Fan, “Vehicle Routing Problem with Soft Time Windows Based on Improved Genetic Algorithm for Fruits and Vegetables Distribution,” Discret. Dyn. Nat. Soc., vol. 2015, 2015.
[37]G. Zhenfeng, L. Yang, J. Xiaodan, and G. Sheng, “The Electric Vehicle Routing Problem with Time Windows using Genetic Algorithm,” in 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), 2017, pp. 635–639.
[38]J. Zhong, X. Hu, J. Zhang, and M. Gu, “Comparison of Performance between Different Selection Strategies on Simple Genetic Algorithms,” in International conference on computational intelligence for modelling, control and automation and international conference on intelligent agents, web technologies and internet commerce (CIMCA-IAWTIC’06), 2005, vol. 2, pp. 1115–1121.
[39]C. J. Shingadiya, “Genetic Algorithm for Test Suite Optimization: An Experimental Investigation of Different Selection Methods,” Turkish J. Comput. Math. Educ., vol. 12, no. 3, pp. 3778–3787, 2021.
[40]C.-W. Chu, M.-D. Lin, G.-F. Liu, and Y.-H. Sung, “Application of Immune Algorithms on Solving Minimum-Cost Problem of Water Distribution Network,” Math. Comput. Model., vol. 48, no. 11–12, pp. 1888–1900, 2008.
[41]M. Gong, L. Jiao, and L. Zhang, “Baldwinian Learning in Clonal Selection Algorithm for Optimization,” Inf. Sci. (Ny)., vol. 180, no. 8, pp. 1218–1236, 2010.
[42]X. Zhao, G. Liu, H. Liu, G. Zhao, and S. Niu, “A New Clonal Selection Immune Algorithm with Perturbation Guiding Search and Non-Uniform Hypermutation,” Int. J. Comput. Intell. Syst., vol. 3, no. sup01, pp. 1–17, 2010.
[43]R. Zeng and Y. Wang, “A Chaotic Simulated Annealing and Particle Swarm Improved Artificial Immune Algorithm for Flexible Job Shop Scheduling Problem,” EURASIP J. Wirel. Commun. Netw., vol. 2018, no. 1, pp. 1–10, 2018.
[44]E. Y. C. Wong, H. S. C. Yeung, and H. Y. K. Lau, “Immunity-Based Hybrid Evolutionary Algorithm for Multi-Objective Optimization in Global Container Repositioning,” Eng. Appl. Artif. Intell., vol. 22, no. 6, pp. 842–854, 2009.
[45]X. Jiangang and F. Jianhua, “The Vehicle Routing Problem Based on the Immune Algorithm,” 2009.
[46]Y. S. Tan, “An Improved Immune Clone Algorithm Logistics Delivery Strategy,” J. Adv. Comput. Intell. Intell. Informatics, vol. 23, no. 2, pp. 309–312, 2019.
[47]Y.-C. Hsieh, P.-S. You, and Y.-C. Lee, “An Application of Immune Algorithm for the Periodic Delivery Planning of Vending Machines.,” J. Comput., vol. 9, no. 7, pp. 1525–1529, 2014.
[48]J.-S. Chun, H.-K. Jung, and S.-Y. Hahn, “A Study on Comparison of Optimization Performances between Immune Algorithm and Other Heuristic Algorithms,” IEEE Trans. Magn., vol. 34, no. 5, pp. 2972–2975, 1998.
[49]A. R. Yıldız, “A New Design Optimization Framework Based on Immune Algorithm and Taguchi’s Method,” Comput. Ind., vol. 60, no. 8, pp. 613–620, 2009.
[50]A. Mozdgir, I. Mahdavi, I. S. Badeleh, and M. Solimanpur, “Using the Taguchi Method to Optimize the Differential Evolution Algorithm Parameters for Minimizing the Workload Smoothness Index in Simple Assembly Line Balancing,” Math. Comput. Model., vol. 57, no. 1–2, pp. 137–151, 2013.
[51]A. R. Khoei, I. Masters, and D. T. Gethin, “Design Optimisation of Aluminium Recycling Processes using Taguchi Technique,” J. Mater. Process. Technol., vol. 127, no. 1, pp. 96–106, 2002.
[52]G. Taguchi, “Introduction to Quality Engineering, White Plains: UNIPUB.” Kraus International Publications, 1987.
[53]M. S. Phadke, Quality Engineering Using Robust Design. Prentice Hall PTR, 1995.
[54]C.-D. Yang, C.-C. Luo, S.-J. Liu, and Y.-H. Chang, “Applications of Genetic-Taguchi Algorithm in Flight Control Designs,” J. Aerosp. Eng., vol. 18, no. 4, pp. 232–241, 2005.
[55]R. Ranjit, “A Primer on the Taguchi Method: Society of Manufacturing Engineers,” Estados Unidos Soc. Manuf. Eng., pp. 172–174, 2010.
[56]H. N. AV, P. R. S. Pillai, and Y. Rao, “Optimization for Temperature and Time in Co-Composting Municipal Solid Waste and Brewery Sludge,” Int. J. Environ. Eng. Manag., vol. 7, no. 1, pp. 1–23, 2016.
[57]J.-T. Tsai, W.-H. Ho, T.-K. Liu, and J.-H. Chou, “Improved Immune Algorithm for Global Numerical Optimization and Job-Shop Scheduling Problems,” Appl. Math. Comput., vol. 194, no. 2, pp. 406–424, 2007.
[58]Z. Yang, Q. Zhao, S. Zhao, L. Jin, and Y. Mao, “Optimization of Bus Scheduling Based on Artificial Immune Algorithm,” in Logistics: The Emerging Frontiers of Transportation and Development in China, 2009, pp. 3648–3655.