近年來，隨著企業競爭愈加劇烈，「物流管理」在企業營運中逐漸受到重視，而車輛配送路徑的安排對於物流管理的成本具有極大的影響，車輛途程問題 (vehicle routing problems, VRP)相關研究因應而生，對應不同的配送條件、作業特性、及實務限制，至今已發展出許多 VRP 相關的延伸問題。本研究為了更全面分析台灣企業面臨到的問題，在車隊數量有限的情況下，同時考量多車種問題、時窗限制問題、車輛停放限制問題以及多趟次配送問題的具時窗限制之多趟次車輛途程問題(multi-trip vehicle routing problem with time windows, MTVRPTW)，並建構數學規劃最佳化模型，以總配送車數最小化為主要目標，降低總配送距離與減少每趟次的花費時間為次要目標，以求得最佳的車輛使用與配送路徑配置。車輛途程問題在文獻上已被證明為 NP-hard 問題，為了提高求解效率，本研究發展適應性基因演算法(adaptive genetic algorithm)，並透過台灣生鮮食品物流配送實務案例，比較與分析案例公司的規劃現況、標準基因演算法(genetic algorithm)以及本研究提出的演算法之規劃結果，最後進行參數敏感度分析，探討不同參數水準下對規劃結果造成之影響，提供給公司決策者作為參考依據。

This study explored a multi-trip vehicle routing problem with time windows. Through mathematical programming, an optimization model was established to identify the optimal arrangement for vehicle selection and route allocation. The model set minimizing the number of trips as its primary objective, and the reduction of travel distance and time per trip as its secondary objective. Given that VRP have been recognized as a type of NP-hard problems, an adaptive genetic algorithm was developed to enhance problem-solving efficiency. Actual fresh food distribution operations in Taiwan were investigated, and the results of the proposed optimization model were compared with the results obtained using a normal genetic algorithm and the plans implemented by case companies. Finally, a parameter sensitivity analysis was performed to determine the effects of different parameter settings on the planning results. The findings of this study are expected to provide reference for business decision-making.

摘要............i
Abstract........ii
誌謝............iii
目錄............iv
表目錄..........vii
圖目錄..........xiii
第一章 緒論.....1
1.1 研究背景與動機....1
1.2 研究目的....2
1.3研究範圍與假設.....2
1.4 研究流程.........3
第二章 文獻探討.......5
2.1 車輛途程問題......5
2.2 具時窗限制車輛途程問題.........8
2.3 具時窗限制之多趟次問題.........12
2.4 基因演算法....................13
2.5 實驗設計-反應曲面法............17
第三章、問題定義...................19
3.1 定義問題......................19
3.2 數學規劃模型..................19
3.3 測試問題......................23
第四章、演算法測試與開發...........27
4.1適應性基因演算法...............27
4.1.1 初始化參數設定..............29
4.1.2 編碼.......................29
4.1.3 建構初始群體................29
4.1.4 適應性基因演算法............30
4.2 基因演算法...................34
4.3 演算法參數設定...............34
4.3.1 適應性基因演算法...........35
4.3.2 標準基因演算法.............44
4.4問題測試與驗證................47
4.4.1 測試環境與測試問題..........47
4.4.2 適應性基因演算法與標準基因演算法結果與驗證...47
第五章、實務案例.................52
5.1 案例說明....................52
5.1.1夜間配送案例...............53
5.1.2日間配送案例...............59
5.2 適應性基因演算法規劃結果.....66
5.2.1 演算法夜間配送規劃結果.....67
5.2.2演算法日間配送規劃結果......70
5.2.3演算法與現況比較............73
5.2.4案例結果小結................74
5.3參數敏感度分析................75
5.3.1門市需求量之影響.............75
5.3.2車輛固定成本之影響...........78
5.3.3子目標比重之影響.............79
5.3.4 單趟次與多趟次結果之比較.....83
第六章 結論及建議.................85
6.1 結論.........................85
6.2 建議.........................86
參考文獻.........................87
附錄A............................93
附錄B............................114
Extended Abstract................152

[1].林李旺. (2013). 突破品質水準: 實驗設計與田口方法之實務應用: 全華圖書.
[2].陳家和, & 丁慶榮. (2005). 應用螞蟻演算法於時窗限制車輛途程問題之研究. [Solving the Vehicle Routing Problem with Time Windows Using Ant Algorithm]. 運輸學刊, 17(3), 261-280. doi:10.6383/jcit.200509.0261
[3].葉怡成 (2005)，實驗設計法-製程與產品最佳化，五南圖書，台北市。
[4].劉騏賢. (2020). 以啟發式演算法求解具有時窗限制之群眾運輸問題. 成功大學工業與資訊管理學系學位論文, 1-67.
[5].龔昱銘. (2018). 週期性之混合車隊車輛途程問題-考量時窗限制. 國立雲林科技大學工業工程與管理系碩士論文.
[6].Afshar-Nadjafi, B., & Afshar-Nadjafi, A. (2017). A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet. Journal of king saud university-Engineering sciences, 29(1), 29-34.
[7].Andreatta, G., Casula, M., De Francesco, C., & De Giovanni, L. (2016). A branch-and-price based heuristic for the stochastic vehicle routing problem with hard time windows. Electronic Notes in Discrete Mathematics, 52, 325-332.
[8].Azi, N., Gendreau, M., & Potvin, J.-Y. (2007). An exact algorithm for a single-vehicle routing problem with time windows and multiple routes. European Journal of Operational Research, 178(3), 755-766.
[9].Babaee Tirkolaee, E., Abbasian, P., Soltani, M., & Ghaffarian, S. A. (2019). Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban waste collection: A case study. Waste Management & Research, 37(1_suppl), 4-13. doi:10.1177/0734242X18807001
[10].Ben Ticha, H., Absi, N., Feillet, D., & Quilliot, A. (2019). Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows. Computers & Operations Research, 104, 113-126. doi:https://doi.org/10.1016/j.cor.2018.11.001
[11].Bezerra, M. A., Santelli, R. E., Oliveira, E. P., Villar, L. S., & Escaleira, L. A. (2008). Response surface methodology (RSM) as a tool for optimization in analytical chemistry. Talanta, 76(5), 965-977. doi:https://doi.org/10.1016/j.talanta.2008.05.019
[12].Breig, S. J. M., & Luti, K. J. K. (2021). Response surface methodology: A review on its applications and challenges in microbial cultures. Materials Today: Proceedings, 42, 2277-2284. doi:https://doi.org/10.1016/j.matpr.2020.12.316
[13].Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
[14].Desrochers, M., & Soumis, F. (1988). A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR: Information Systems and Operational Research, 26(3), 191-212.
[15].Dumitrescu, D., Lazzerini, B., Jain, L. C., & Dumitrescu, A. (2000). Evolutionary computation: CRC press.
[16].Fermín Cueto, P., Gjeroska, I., Solà Vilalta, A., & Anjos, M. F. (2021). A solution approach for multi-trip vehicle routing problems with time windows, fleet sizing, and depot location. Networks, n/a(n/a). doi:https://doi.org/10.1002/net.22028
[17].Fisher, R. A. (1920). 012: A Mathematical Examination of the Methods of Determining the Accuracy of an Observation by the Mean Error, and by the Mean Square Error.
[18].Fleischmann, B. (1990). The vehicle routing problem with multiple use of vehicles. Forschungsbericht Fachbereich Wirtschaftswissenschaften, Universität Hamburg.
[19].Fraser, A. S. (1960). Simulation of genetic systems by automatic digital computers vi. epistasis. Australian Journal of Biological Sciences, 13(2), 150-162.
[20].Gendreau, M., Ghiani, G., & Guerriero, E. (2015). Time-dependent routing problems: A review. Computers & Operations Research, 64, 189-197.
[21].Ghani, N. E. A., Shariff, S. S. R., & Zahari, S. M. (2016). An Alternative Algorithm for Vehicle Routing Problem with Time Windows for Daily Deliveries. Advances in Pure Mathematics, 6(5), 342-350. doi:10.4236/apm.2016.65025
[22].Ghannadpour, S. F., & Zandiyeh, F. (2020). An adapted multi-objective genetic algorithm for solving the cash in transit vehicle routing problem with vulnerability estimation for risk quantification. Engineering Applications of Artificial Intelligence, 96, 103964. doi:https://doi.org/10.1016/j.engappai.2020.103964
[23].Goldberg, D. E., Korb, B., & Deb, K. (1989). Messy genetic algorithms: Motivation, analysis, and first results. Complex systems, 3(5), 493-530.
[24].Gutierrez, A., Dieulle, L., Labadie, N., & Velasco, N. (2016). A multi population memetic algorithm for the vehicle routing problem with time windows and stochastic travel and service times. IFAC-PapersOnLine, 49(12), 1204-1209.
[25].HAN, Y., PENG, Y., WEI, H., & SHI, B. (2019). Hyper-heuristic genetic algorithm for vehicle routing problem with soft time windows. Computer Integrated Manufacturing Systems.
[26].Hassanat, A., Almohammadi, K., Alkafaween, E., Abunawas, E., Hammouri, A., & Prasath, V. (2019). Choosing mutation and crossover ratios for genetic algorithms—a review with a new dynamic approach. Information, 10(12), 390.
[27].Hernandez, F., Feillet, D., Giroudeau, R., & Naud, O. J. E. J. o. O. R. (2016). Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows. 249(2), 551-559.
[28].Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
[29].Jebari, K., & Madiafi, M. (2013). Selection methods for genetic algorithms. International Journal of Emerging Sciences, 3(4), 333-344.
[30].Khoukhi, S., Yaakoubi, O. E., Bojji, C., & Bensouda, Y. (2019). A genetic algorithm for solving a multi-trip vehicle routing problem with time windows and simultaneous pick-up and delivery in a hospital complex. Paper presented at the Proceedings of the 3rd International Conference on Machine Learning and Soft Computing, Da Lat, Viet Nam. https://doi.org/10.1145/3310986.3311031
[31].Kolen, A. W., Rinnooy Kan, A., & Trienekens, H. W. (1987). Vehicle routing with time windows. Operations Research, 35(2), 266-273.
[32].Kumar, S. N., & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants.
[33].Li, J.-q., Han, Y.-q., Duan, P.-y., Han, Y.-y., Niu, B., Li, C.-d., . . . Liu, Y.-p. (2020). Meta-heuristic algorithm for solving vehicle routing problems with time windows and synchronized visit constraints in prefabricated systems. Journal of Cleaner Production, 250, 119464. doi:https://doi.org/10.1016/j.jclepro.2019.119464
[34].Liu, Y., Ji, S., Su, Z., & Guo, D. (2019). Multi-objective AGV scheduling in an automatic sorting system of an unmanned (intelligent) warehouse by using two adaptive genetic algorithms and a multi-adaptive genetic algorithm. PloS one, 14(12), e0226161.
[35].Marinakis, Y., Marinaki, M., & Migdalas, A. (2019). A multi-adaptive particle swarm optimization for the vehicle routing problem with time windows. Information Sciences, 481, 311-329.
[36].Mejjaouli, S., & Babiceanu, R. F. (2018). Cold supply chain logistics: System optimization for real-time rerouting transportation solutions. Computers in Industry, 95, 68-80.
[37].Nguyen, P. K., Crainic, T. G., & Toulouse, M. (2013). A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows. European Journal of Operational Research, 231(1), 43-56.
[38].Pan, B., Zhang, Z., & Lim, A. (2021). Multi-trip time-dependent vehicle routing problem with time windows. European Journal of Operational Research, 291(1), 218-231. doi:https://doi.org/10.1016/j.ejor.2020.09.022
[39].Pratiwi, A. B., Sasmito, A., Istiqomah, Q. S., Kurniawan, M. R., & Suprajitno, H. (2019). Metaheuristic Algorithms for Solving Multiple-Trips Vehicle Routing Problem with Time Windows (MTVRPTW). Journal of Physics: Conference Series, 1306, 012021. doi:10.1088/1742-6596/1306/1/012021
[40].Pureza, V., Morabito, R., & Reimann, M. (2012). Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW. European Journal of Operational Research, 218(3), 636-647.
[41].Rabbouch, B., Saâdaoui, F., & Mraihi, R. (2019). Efficient implementation of the genetic algorithm to solve rich vehicle routing problems. Operational Research. doi:10.1007/s12351-019-00521-0
[42].Rizzoli, A. E., Montemanni, R., Lucibello, E., & Gambardella, L. M. (2007). Ant colony optimization for real-world vehicle routing problems. Swarm Intelligence, 1(2), 135-151.
[43].Sbai, I., Limem, O., & Krichen, S. (2017). An adaptive genetic algorithm for the capacitated vehicle routing problem with time windows and two-dimensional loading constraints. Paper presented at the 2017 IEEE/ACS 14th International Conference on Computer Systems and Applications (AICCSA).
[44].Shi, Y., Boudouh, T., & Grunder, O. (2018). An efficient tabu search based procedure for simultaneous delivery and pick-up problem with time window. IFAC-PapersOnLine, 51(11), 241-246.
[45].Sinthamrongruk, T., Dahal, K., Satiya, O., Vudhironarit, T., & Yodmongkol, P. (2017, 1-4 March 2017). Healthcare Staff Routing Problem using adaptive Genetic Algorithms with Adaptive Local Search and Immigrant Scheme. Paper presented at the 2017 International Conference on Digital Arts, Media and Technology (ICDAMT).
[46].Solomon, M. M., & Desrosiers, J. (1988). Survey paper—time window constrained routing and scheduling problems. Transportation science, 22(1), 1-13.
[47].Sastry, K., Goldberg, D., & Kendall, G. (2005). Genetic Algorithms. In E. K. Burke & G. Kendall (Eds.), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (pp. 97-125). Boston, MA: Springer US.
[48].Ticha, H. B., Absi, N., Feillet, D., & Quilliot, A. (2017). Empirical analysis for the VRPTW with a multigraph representation for the road network. Computers & Operations Research, 88, 103-116.
[49].Wang, F., Liao, F., Li, Y., Yan, X., & Chen, X. (2021). An ensemble learning based multi-objective evolutionary algorithm for the dynamic vehicle routing problem with time windows. Computers & Industrial Engineering, 154, 107131. doi:https://doi.org/10.1016/j.cie.2021.107131
[50].Wang, S., Lu, Z., Wei, L., Ji, G., & Yang, J. (2016). Fitness-scaling adaptive genetic algorithm with local search for solving the Multiple Depot Vehicle Routing Problem. Simulation, 92(7), 601-616.
[51].Wang, Y., Wang, L., Peng, Z., Chen, G., Cai, Z., & Xing, L. (2019). A Multi Ant System based hybrid heuristic algorithm for Vehicle Routing Problem with Service Time Customization. Swarm and Evolutionary Computation, 50, 100563. doi:https://doi.org/10.1016/j.swevo.2019.100563
[52].Wei, Q., Guo, Z., Lau, H. C., & He, Z. (2019). An artificial bee colony-based hybrid approach for waste collection problem with midway disposal pattern. Applied Soft Computing, 76, 629-637.
[53].Xu, Z., Elomri, A., Pokharel, S., & Mutlu, F. (2019). A model for capacitated green vehicle routing problem with the time-varying vehicle speed and soft time windows. Computers & Industrial Engineering, 137, 106011.
[54].Zhang, J. (2020). An Improved Genetic Algorithm for Vehicle Routing Problem. Paper presented at the International Conference on Machine Learning and Big Data Analytics for IoT Security and Privacy.
[55].Zhang, J., Lam, W. H., & Chen, B. Y. (2016). On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows. European Journal of Operational Research, 249(1), 144-154.
[56].Zhen, L. M., Chengle & Wang, Kai & Xiao, Liyang & Zhang, Wei. (2020). Multi-depot multi-trip vehicle routing problem with time windows and release dates. Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 135.
[57].Zhenfeng, G., Yang, L., Xiaodan, J., & Sheng, G. (2017). The electric vehicle routing problem with time windows using genetic algorithm. Paper presented at the 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC).