跳到主要內容

臺灣博碩士論文加值系統

(34.204.198.73) 您好!臺灣時間:2024/07/19 15:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:朱雅禎
研究生(外文):CHU,YA-CHEN
論文名稱:應用非支配排序遺傳演算法求解具時間窗限制之多目標車輛路徑問題
論文名稱(外文):Application of Non-dominated Sorting Genetic Algorithm to Solve Multi-objective Vehicle Routing Problem with Time Window Constraints
指導教授:康鶴耀康鶴耀引用關係
指導教授(外文):KANG,HE-YAU
口試委員:康鶴耀李欣怡陳貴琳
口試委員(外文):KANG,HE-YAULEE,HSIN-ICHEN,KUEI-LIN
口試日期:2023-06-27
學位類別:碩士
校院名稱:國立勤益科技大學
系所名稱:工業工程與管理系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2023
畢業學年度:111
語文別:中文
論文頁數:85
中文關鍵詞:車輛路徑問題時間窗多目標優化問題數學規劃非支配排序遺傳演算法
外文關鍵詞:vehicle routing problemtime windowmulti-objective optimization problemmathematical programmingnon-dominated sorting genetic algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:36
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
運輸業發展快速,如今利用交通工具進行貨運運輸已是社會常態,生活中最息息相關的就是汽車貨運,我們可以這麼輕易且方便就能得到所需的商品,都是因為運輸的關係,然而在商品的供應鏈中,也有空間和時間上的限制,須考慮車輛的負載限制以及各需求點的需求量,生活周遭時常遇到多目標優化問題,對於運輸業來說不外乎就是希望車輛的行駛距離最短、派出的車輛最少、花費總成本最低等等,在這麼多的限制條件下,同時又要盡可能地達到所期望的目標,這是個複雜的規劃問題,因此本研究在基礎的車輛路徑問題加上各項限制如車輛負載、時間等因素,將相關數據帶入數學規劃軟體,計算出最佳解。
本研究進行多目標優化,最終目的是以最低成本、最低車輛數、最短距離為理想成果,並能符合所設定的時間窗,建立配送中心與車輛路徑的模組,提供符合多目標的車輛行駛路徑,進而取代耗時又耗力的人工規劃路徑方式,使用Matlab軟體執行非支配排序遺傳演算法建構模型,帶入相關的成本與時間窗限制,使其在一定時間內求得區域最佳解。
The transportation industry is developing rapidly, and nowadays, using vehicles for cargo transportation has become a social norm. The most closely related aspect of our lives is automobile freight transport, which allows us to easily and conveniently obtain the goods we need. This convenience is all thanks to transportation. However, in the supply chain of goods, there are also limitations in terms of space and time. It is necessary to consider the load restrictions of vehicles and the demand at various points.
In daily life, we often encounter multi-objective optimization problems, which, for the transportation industry, typically involve minimizing the distance traveled by vehicles, minimizing the number of dispatched vehicles, minimizing the total cost, and so on. With so many constraints, the goal is to achieve the desired objectives as much as possible. This is a complex planning problem. Therefore, this study incorporates various constraints such as vehicle load and time factors into the basic vehicle routing problem and uses mathematical optimization software to calculate the optimal solution.
In this study, multi-objective optimization is performed with the ultimate goal of achieving the lowest cost, the fewest number of vehicles, and the shortest distance. The solution should also meet the specified time windows. A module for the distribution center and vehicle routing is established to provide vehicle routes that satisfy multiple objectives, thereby replacing time-consuming and labor-intensive manual route planning methods. Matlab software is used to execute a non-dominated sorting genetic algorithm and construct a model. By incorporating relevant cost and time window constraints, the algorithm finds the regional optimal solution within a specified time frame.

摘要 i
ABSTRACT ii
致謝 iii
目錄 iv
表目錄 vi
圖目錄 ix
第一章 緒論 1
1-1、研究背景與動機 1
1-2、研究目的 2
1-3、研究流程與架構 2
第二章 文獻探討 5
2-1、車輛路徑問題 5
2-2、時間窗 9
2-2-1 硬時間窗 9
2-2-2 軟時間窗 10
2-3、具時間窗限制之車輛路徑問題 11
2-4、多目標車輛路徑問題 16
2-5、非支配排序遺傳演算法 17
第三章 問題描述與模式建構 21
3-1、問題定義與假設 21
3-2、數學模式建構 21
3-3、非支配排序遺傳演算法於具時間窗限制之多目標車輛路徑問題的應用 25
第四章 案例分析 27
4-1、案例介紹 27
4-2、解題結果:小問題 27
4-2-1案例一:五個需求點 27
4-2-2案例二:十個需求點 32
4-3、解題結果:中問題 37
4-3-1案例三:二十個需求點 37
4-3-2案例四:三十個需求點 45
4-4、解題結果:大問題 54
4-4-1案例五:六十個需求點 54
4-4-2案例六:一百個需求點 62
第五章 結論 74
參考文獻 76
中文參考文獻 76
英文參考文獻 77
中文參考文獻
[1]李洪鑫 (2000),含時間窗車輛途程問題各演算法適用範圍之探討,東海大學工業工程研究所碩士論文
[2]李美儀 (2015),車輛路線相關問題之回顧與國內發展之分析,國立交通大學運輸與物流管理學系碩士班碩士論文
[3]卓裕仁、朱佑旌 (2008)兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究,運輸計劃季刊,第三十七卷第四期,405-430
[4]郭佳林 (2005),求解具時間窗之多趟次車輛途程問題,國立交通大學運輸科技與管理學系碩士論文
[5]張哲旗 (2009),以混合啟發式演算法求解具模糊時窗限制車輛途程問題,龍華科技大學商學與管理研究所碩士學位論文
[6]張承裕 (2016),考慮物流士作業能力與服務時間相似度之車輛路徑問題,國立臺北科技大學工業工程與管理研究所碩士學位論文
[7]陳文賢 (2021),配對交易最佳化研究-非支配排序基因演算法III,國立高雄科技大學商業智慧學院博士論文
[8]楊雅媜 (2022),軟時間窗與多艙種之車輛路徑問題之研究,國立雲林科技大學工業工程與管理系碩士論文
[9]劉文義 (2010),以k-opt為基礎之分支切面法求解旅行銷售員問題,國立成功大學工業與資訊管理學系碩士論文
[10]劉依晴 (2016),利用迭代區域搜尋法求解綠能車輛路線問題之研究,國立交通大學運輸與物流管理學系碩士論文
[11]賴志豪 (2006),宅配路線規劃應用禁制搜尋法之研究,逢甲大學交通工程與管理學系碩士班碩士論文
[12]賴敬棠 (2010),螞蟻記憶系統應用於車輛途程問題,逢甲大學運輸科技與管理學系碩士班碩士論文
[13]蔣宗翰 (2013),以禁忌搜尋法求解具時間窗限制之開放式存貨途程問題,國立台灣科技大學工業管理系碩士學位論文
英文參考文獻
[1]Abdullahi, H., Reyes-Rubiano, L., Ouelhadj, D., Faulin, J., Juan, A.A., 2021, “Modelling and multi-criteria analysis of the sustainability dimensions for the green vehicle routing problem”, European Journal of Operational Research, 292(1), pp. 143-154
[2]Ballou, R.H., 1992, “Business logistics management”, 3rd Edition, Prentice-Hall, Inc., Englewood Cliffs.
[3]Bederina, H., Hifi, M., 2018, “A hybrid multi-objective evolutionary optimization approach for the robust vehicle routing problem”, Applied Soft Computing Journal, 71, pp. 980-993
[4]Belhor, M., El-Amraoui, A., Jemai, A., Delmotte, F., 2023, “Multi-objective evolutionary approach based on K-means clustering for home health care routing and scheduling problem”, Expert Systems with Applications, 213, 119035
[5]Bodin, L., Golden, B., 1981, “Classification in vehicle routing and scheduling” , Networks, 11(2), pp. 97-108
[6]Bodin, L., Golden, B., Assad, A., and Ball, M., 1983, “Routing and scheduling of vehicle and crews: the state of the art”, Computer & Operations Research, Vo1. 10, No. 2, pp. 63-211
[7]Bula, G.A., Murat Afsar, H., González, F.A., Prodhon, C., Velasco, N., 2019, “Bi-objective vehicle routing problem for hazardous materials transportation”, Journal of Cleaner Production, 206, pp. 976-986
[8]Cai, Y., Cheng, M., Zhou, Y., Liu, P., Guo, J.-M., 2022, “A hybrid evolutionary multitask algorithm for the multiobjective vehicle routing problem with time windows”, Information Sciences, 612, pp. 168-187
[9]Chen, C., Demir, E., Huang, Y., 2021, “An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots”, European Journal of Operational Research, 294(3), pp. 1164-1180
[10]Clarke, G., Wright, J. W., 1964, ”Scheduling of vehicles from a central depot to a number of delivery points”, Operations research, Vol.12, pp. 568-581
[11]Dantzig, G.B., Ramser, J.H., 1959, “Optimum routing of gasoline delivery trucks”, World Petroleum Congress Proceedings, 1959-May, pp. 229-238
[12]Deb, K., Pratap, A., Agarwal, S., Meyarivan, T., 2002, “A fast and elitist multiobjective genetic algorithm: NSGA-II”, IEEE Transactions on Evolutionary Computation, 6(2), pp. 182-197
[13]Dueck, G., Scheuer, T., 1990, “Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing”, Journal of Computational Physics, 90(1), pp. 161-175
[14]El-Sherbeny, N.A., 2010, “Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods”, Journal of King Saud University - Science, 22(3), pp. 123-131
[15]Fisher, M.L., Jaikumar, R., 1981, “A generalized assignment heuristic for vehicle routing”, Networks, 11(2), pp. 109-124
[16]Fisher,M., 1995, “Vehicle routing”, Chapter 1, Handbooks in Operations Research and Management Science
[17]Gan, X., Wang, Y., Li, S., Niu, B., 2012, “Vehicle routing problem with time windows and simultaneous delivery and pick-up service based on MCPSO”, Mathematical Problems in Engineering, 2012, 104279
[18]Garcia-Najera, A., Bullinaria, J.A., 2011, “An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows”, Computers and Operations Research, 38(1), pp. 287–300
[19]Ghannadpour, S.F., Zarrabi, A., 2019, “Multi-objective heterogeneous vehicle routing and scheduling problem with energy minimizing”, Swarm and Evolutionary Computation, 44, pp. 728-747
[20]Ghoseiri, K., Ghannadpour, S.F., 2010, “Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm”, Applied Soft Computing Journal, 10(4), pp. 1096-1107
[21]Glover, F., 1977, “Heuristic for integer programming using surrogate constraints”, Decision Sciences, 8(1), pp. 156-166
[22]Guo, K., Hu, S., Zhu, H., Tan, W., 2022, “Industrial information integration method to vehicle routing optimization using grey target decision”, Journal of Industrial Information Integration, 27, 100336
[23]Gupta, P., Govindan, K., Mehlawat, M.K., Khaitan, A., 2022, “Multiobjective capacitated green vehicle routing problem with fuzzy time-distances and demands split into bags”, International Journal of Production Research, 60(8), pp. 2369-2385
[24]Haddadene, S.R.A., Labadie, N., Prodhon, C., 2016, “NSGAII enhanced with a local search for the vehicle routing problem with time windows and synchronization constraints”, IFAC-PapersOnLine, 49(12), pp. 1198-1203
[25]Homberger, J., Gehring, H., 2005, “A two-phase hybrid metaheuristic for the vehicle routing problem with time windows”, European Journal of Operational Research, 162(1), pp. 220-238
[26]Hou, Y., Wu, Y., Han, H., 2021, “Solution evaluation-oriented multi-objective differential evolution algorithm for MOVRPTW”, 2021 International Conference on Information, Cybernetics, and Computational Social Systems, ICCSS 2021, pp. 50-55
[27]Hussain Ahmed, Z., Yousefikhoshbakht, M., 2023, “An improved tabu search algorithm for solving heterogeneous fixed fleet open vehicle routing problem with time windows”, Alexandria Engineering Journal, 64, pp. 349-363
[28]Jia, Y., Ren, Z., 2010, “Hybrid genetic algorithm for multi-objective vehicle routing problem based on human-computer interaction”, Proceedings - 3rd International Conference on Information Management, Innovation Management and Industrial Engineering, ICIII 2010, 1, 5694430, pp. 393-396
[29]Jiang, P., Men, J., Xu, H., Kong, Y., Zhang, L., 2020, “A variable neighborhood search-based hybrid multiobjective evolutionary algorithm for HazMat heterogeneous vehicle routing problem with time windows” , IEEE Systems Journal, 14(3), PP. 4344-4355, 8978793
[30]John H. Holland, 1975, “Genetic algorithms and adaptation”, Adaptive Control of Ill-Defined Systems, pp. 317-333
[31]Jozefowiez, N., Semet, F., Talbi, E.-G., 2006, “Enhancements of NSGA II and its application to the vehicle routing problem with route balancing”, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3871 LNCS, pp. 131-142
[32]Kang, H.-Y., Lee, A.H.I., 2018, “An enhanced approach for the multiple vehicle routing problem with heterogeneous vehicles and a soft time window”, Symmetry, 10(11), 650
[33]Kang, H.-Y., Lee, A.H.I., Yeh, Y.-F., 2020, “An optimization approach for traveling purchaser problem with environmental impact of transportation cost”, Kybernetes, 50(8), pp. 2289-2317
[34]Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P., 1983, “Optimization by simulated annealing”, Science, 220(4598), pp. 671-680
[35]Kolen, A.W.J., Rinnooy Kan, A.H.G., Trienekens, H.W.J.M., 1987, “Vehicle routing with time windows”, Operations Research, 35(2), pp. 266-273
[36]Koskosidis, Yiannis, Powell, Warren, Solomon, Marius, 1992, “Optimization-based heuristic for vehicle routing and scheduling with soft time window constraints”, Transportation Science, 26(2), pp. 69-85
[37]Laporte, G., Nobert, Y., 1987, “Exact algorithms for the vehicle routing problem”, North-Holland Mathematics Studies, 132(C), pp. 147-184
[38]Le Bouthillier, A., Crainic, T.G., 2005, “A cooperative parallel meta-heuristic for the vehicle routing problem with time windows”, Computers and Operations Research, 32(7), pp. 1685-1708
[39]Li, J.-Q., Han, Y.-Q., Duan, P.-Y., Zheng, Z.-X., 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
[40]Lin,S., 1965, “Computer solutions of traveling salesman problem”, Bell System Technical Journal, 44(10), pp. 2245-2269
[41]Liu, F.-H.F., Shen, S.-Y., 1999, “A route-neighborhood-based metaheuristic for vehicle routing problem with time windows”, European Journal of Operational Research, 118(3), pp. 485-504
[42]Li, J., Fang, Y., Tang, N., 2022, “A cluster-based optimization framework for vehicle routing problem with workload balance”, Computers and Industrial Engineering, 169,108221
[43]Mazdarani, F., Ghannadpour, S.F., Zandieh, F., 2023, “Bi-objective overlapped links vehicle routing problem for risk minimizing valuables transportation”, Computers & Operations Research, 153, 106177
[44]Miranda, D.M., Branke, J., Conceição, S.V., 2018, “Algorithms for the multi-objective vehicle routing problem with hard time windows and stochastic travel time and service time”, Applied Soft Computing Journal, 70, pp. 66-79
[45]Mnasri, S., Abbes, F., Zidi, K., Ghedira, K., “A multi-objective hybrid BCRC-NSGAII algorithm to solve the VRPTW”, 13th International Conference on Hybrid Intelligent Systems, HIS 2013, 6920455, pp. 60-65
[46]Mojtahedi, M., Fathollahi-Fard, A.M., Tavakkoli-Moghaddam, R., Newton, S., 2021, “Sustainable vehicle routing problem for coordinated solid waste management”, Journal of Industrial Information Integration, 23, 100220
[47]Mole, R. H., Jameson, S. R., 1976, “A sequential route-building algorithm employing a generalized savings criterion”, Journal of the Operational Research Society, 27(2), pp. 503-511
[48]Moradi, B., 2020, “The new optimization algorithm for the vehicle routing problem with time windows using multi-objective discrete learnable evolution model”, Soft Computing, 24(9), pp. 6741-6769
[49]Niu, Y., Zhang, Y., Cao, Z., Song, W., Zhang, F., 2021 “MIMOA: A membrane-inspired multi-objective algorithm for green vehicle routing problem with stochastic demands”, Swarm and Evolutionary Computation, 60, 100767
[50]Ombuki, B., Ross, B.J., Hanshar, F., 2006, “Multi-objective genetic algorithms for vehicle routing problem with time windows”, Applied Intelligence, 24(1), pp. 17-30
[51]Potvin, J. Y., Rousseau,J. M., 1993, “A parallel route building algorithm for the vehicle routing and scheduling problem with time windows”, European Journal of Operational Research, Vol.66, pp. 331-341
[52]Qi, R., Li, J.-Q., Wang, J., Jin, H., Han, Y.-Y., 2022, “QMOEA: A Q-learning-based multiobjective evolutionary algorithm for solving time-dependent green vehicle routing problems with time windows”, Information Sciences, 608, pp. 178-201
[53]Rabbani, M., Heidari, R., Farrokhi-Asl, H., Rahimi, N., 2018, “Using metaheuristic algorithms to solve a multi-objective industrial hazardous waste location-routing problem considering incompatible waste types”, Journal of Cleaner Production, 170, pp. 227-241
[54]Rabbani, M., Heidari, R., Yazdanparast, R., 2019, “A stochastic multi-period industrial hazardous waste location-routing problem: Integrating NSGA-II and Monte Carlo simulation”, European Journal of Operational Research, 272(3), pp. 945-961
[55]Sánchez-Oro, J., López-Sánchez, A.D., Colmenar, J.M., 2020, “A general variable neighborhood search for solving the multi-objective open vehicle routing problem”, Journal of Heuristics, 26(3), pp. 423-452
[56]Solomon, Marius M., 1983, “Vehicle routing and scheduling with time window constraints: models and algorithms”, Ph.D. Dissertation, Dept. of Decision Sciences, University of Pennsylvania
[57]Solomon, M. M., & Desrosiers, J., 1988, “Survey paper—time window constrained routing and scheduling problems”, Transportation science, 22(1), pp.1-13
[58]Song, M.-X., Li, J.-Q., Han, Y.-Q., Liu, L.-L., Sun, Q., 2020, “Metaheuristics for solving the vehicle routing problem with the time windows and energy consumption in cold chain logistics”, Applied Soft Computing Journal, 95, 106561
[59]Srivastava, G., Singh, A., Mallipeddi, R., 2021, “NSGA-II with objective-specific variation operators for multiobjective vehicle routing problem with time windows”, Expert Systems with Applications, 176, 114779
[60]Taillard, É.,Badeau, P.,Gendreau, M.,Guertin, F. ,Potvin, J. Y., 1997, “A tabu search heuristic for the vehicle routing problem with soft time windows”, Transportation science, Vol.31(2), pp. 170-186
[61]Tan, K.C., Chew, Y.H., Lee, L.H., 2006, “A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows”, Computational Optimization and Applications, 34(1), pp. 115-151
[62]Wang, J., Zhou, Y., Wang, Y., Chen, C.L.P., Zheng, Z., 2016, “Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: formulation, instances, and algorithms”, IEEE Transactions on Cybernetics, 46(3), 7062012, pp. 582-594
[63]Wang, J., Weng, T., Zhang, Q., 2019, “A two-stage multiobjective evolutionary algorithm for multiobjective multidepot vehicle routing problem with time windows”, IEEE Transactions on Cybernetics, 49(7), pp. 2467-2478, 8338097
[64]Wang, J., Ren, W., Zhang, Z., Huang, H., Zhou, Y., 2020, “A hybrid multiobjective memetic algorithm for multiobjective periodic vehicle routing problem with time windows”, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 50(11), 8438859, pp. 4732-4745
[65]Xu, X., Lin, Z., Zhu, J., 2022, “DVRP with limited supply and variable neighborhood region in refined oil distribution”, Annals of Operations Research, 309(2), pp. 663-687
[66]Zhang, Z., Qin, H., Li, Y., 2020, “Multi-objective optimization for the vehicle routing problem with outsourcing and profit balancing”, IEEE Transactions on Intelligent Transportation Systems, 21(5), pp. 1987-2001, 8694960
[67]Zhou, Y., Wang, J., 2015, “A local search-based multiobjective optimization algorithm for multiobjective vehicle routing problem with time windows”, IEEE Systems Journal, 9(3), 6730953, pp. 1100-1113
電子全文 電子全文(網際網路公開日期:20280727)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊