臺灣博碩士論文加值系統

近年來隨著顧客生活水準的提升，顧客對貨品準時送達的要求越來越講究，因此延伸出考慮顧客服務時窗巡迴路線問題，即為時窗限制下車輛巡迴路線問題(Vehicle routing problem with time windows, VRPTW)。然而物流配送如何降低成本跟準時送到顧客手中，透過時窗限制下的車輛路線規劃能夠解決跟滿足顧客要求，因此時間視窗車輛途程問題也更加重視。
本研究運用模擬退火法結合區域搜尋法求解時窗限制車輛巡迴路線問題。模擬退火法具有跳脫區域最佳解之特性，搭配區域搜尋法中的插入法跟交換法，使得交換能更有效率去找出最佳解和檢查是否有更好的解決辦法。
所發展之法，以Solomon所提出之標準例題來作測試，顧客數從25個、50個和100個開始來測試，例題中場站一個、車子有載重限制和時窗限制，基於車輛數需求和旅行距離成本,顧客數在25個、50個中有不錯的成果，在顧客數100個中最佳解的找尋上C類型均找到先前學者所發表之已知最佳解，R類型跟RC類型找出4組已知最佳解，在各類組中部份例題與最佳解比較上相差甚小，在平均車輛數相同時，我們所得距離成本少於先前學者的解，顯示本研究所提方法可有效的求解時窗限制之車輛途程問題。

In recent years, the customer request for sending time of the goods more strictly, it can be solved with customer's request in the vehicle routing problem with time windows (VRPTW). Because the constraints of VRPTW include the length of each route, loading capacity of vehicle and the available time window for each customer, it is more complex than travel salesperson problem and vehicle routing problem (VRP).
This research applied the simulated annealing (SA) combined with local search for solving the VRPTW. The developed approach can escape from the local optimal traps, and the use of exchange and insertion local search can find out the (near) optimal solution quickly and efficiently.
The Solomon’s benchmark instances are used for verifying the developed approach. All problems have 25, 50 and 100 customers, a delivery depot, constraints of loading capacity and time window. Based on the number of vehicles required and the traveling distance, good results are obtained when the number of customers equal to 25 and 50. In 100 customers, the developed approach finds all the best results in the C set, and find out 4 solutions which are equal to the best solutions found so far in R set and RC set at reasonable computational time. Our developed approach finds the average number of vehicles and route costs in most classes are better than or equal to those of previous researches. Therefore, the developed approach can be used to solve the VRPTW effectively.

誌謝 Ⅰ
摘要 Ⅱ
Abstract Ⅲ
目錄 Ⅳ
表錄 Ⅵ
圖錄 Ⅶ
ㄧ、緒論 1
1.1 研究背景和動機 1
1.2 研究目的 1
1.3 研究流程 2
二、文獻探討 5
2.1 傳統車輛途程路線問題理論 5
2.1.1 含時間視窗限制的車輛途程路線問題理論 6
2.1.2 其它車輛途程問題 6
2.2 車輛群迴路線問題求解方式 9
2.2.1 精確演算法 9
2.2.2 啟發式初始解法 10
2.3 通用啟發式演算法及文獻彙整 14
三、模式構建與研究方法 20
3.1 VRPTW的問題定義 20
3.2 所發展之演算法 23
3.2.1 模擬退火法參數設定 23
3.2.2 建構可行初始解 25
3.2.3 編碼方式 25
3.2.4 區域搜尋法 26
3.3 模擬退火法步驟 28
四、實驗結果 31
4.1 開發環境與測試例題 31
4.2 參數設定實驗 32
4.3 目標函數 33
4.4 實驗數據 33
4.4.1 Solomon題庫25個顧客例題 33
4.4.2 Solomon題庫50個顧客例題 36
4.4.3 Solomon題庫100個顧客例題 38
五、結論 42
5.1 結論 42
5.2 未來研究 43
參考文獻 44
附錄一 49

[1] Savelsbergh, M.,“Local Search for Routing Problems with Time Windows,” Annals of Operations Research, Vol. 4, 1985, pp. 285-305.
[2]Bodin, L., Golden, B., Assad, A.,and Ball, M., “Routing and Scheduling of Vehicles and Crews,” Computers and Operations Research, Vol. 10, No.2, 1983, pp. 63-211.
[3]Miller, C. E., et al, “Integer Programming Formulation and Travelling Salesman Problem,” J.ACM. , vol. 7, 1960, pp. 326-329.
[4]Eilon, S., Watson-Grandy, C. D. T., and Chrsitofides, N. , “ Distribution Management: Mathematical Modeling and Practical Analysis,” Hafner, New York, N. Y, 1971.
[5]Kolen, A. W. J., Kan, A. H. G. R., and Trienekens, H. W. J. M., “Vehicle Routing with Time Windows,” Operations Research, Vol.35, 1987,pp.266-273.
[6]Desrochers, M., Desrosiers, J., and Solomon, M., “A New Optimization Algorithm for The Vehicle Routing Problem with Time Windows,” Operations Research, Vol. 40, 1992, pp. 342-354.
[7]Fisher, M., Jörnsten, K., and Madsen, O., “Vehicle Routing with Time Windows: Two Optimization Algorithms,” Operations Research, Vol. 45, 1997, pp. 488-492.
[8]Clarke, G. and Wright, J. W., “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, 1964, pp. 568-581.
[9]Gillett, B. and Miller, L., “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operations Research, Vol. 22, 1974, pp. 340-349.
[10]Solomon, M. M., “Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows Constraints,” Operations Research, Vol. 35, 1987, pp. 254-265.
[11]Kirkpatrick, S., Gelatt, C. D. and Vecchi, J. M. P., “Optimization by Simulated Annealing,” Science, Vol. 220, 1983, pp. 671-680.
[12]Chiang, W., and Russell, R., “Simulated annealing Meta-heuristics for the Vehicle Routing Problem with Time Windows,” Annals of Operations Research, Vol. 63, 1996, pp. 3-27.
[13]Osman, I. H., “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problems,” Annals of Operations Research, Vol. 42, 1993b, pp. 421-451.
[14]Haibing, L. and Andrew, L., “Local Search with Annealing-Like Restarts to Solve the VRPTW,” European Journal of Operational Research, Vol. 150, 2003, pp. 115-127.
[15]Glover, F., “Tabu Search-Part I”, ORSA Journal on Computing, Vol 13, 1989, pp. 190-206.
[16]Taillard, E., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J. Y., “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows,” Transportation Science, Vol. 31, 1997, pp.170-186.
[17]Potvin, J. Y., Kervahut, T., Garcia, B. L. and Rousseau, J. M., “The Vehicle Routing Problem with Time Windows Part I: Tabu Search,” Informs Journal on Computing, Vol. 8, 1996, pp. 158-164.
[18]Gehring, H. and Homberger, J., “A Parallel Hybrid Evolutionary Meta-heuristic for the Vehicle Routing Problem with Time Windows,” In Proc. of EUROGEN99, University of Jyväskylä, Jyväskylä, Finland, pp. 57-64.
[19]Gehring, H. and Homberger, J., “Parallelization of A Two Phase Meta-heuristic for Routing Problems with Time Windows,” Asia-Pacific Journal of Operational Research, Vol. 18, 2001, 35-47.
[20]Blanton, J. and Wainwright, R., “Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms,” In Proc. 5th International Conf. Genetic Algorithms, San Francisco, Morgan Kaufmann, 1993, pp. 452-459.
[21]Bräysy, O., Berger, J. and Barkaoui, M., “A New Hybrid Evolutionary Algorithm for the Vehicle Routing Problem with Time Windows,” Presented in Route 2000 Workshop, Skodsborg, Denmark, 2000.
[22]Dorigo,M., “Optimization Learning and Natural Algorithms ”, Ph.D. Thesis, Politecnico di Milano, Italy, 1992.
[23]Gambardella, L., Taillard, E. and Agazzi, G., “MACSVRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows,” IDSIA, Lugano, Switzerland, Tech. Rep. IDSIA-06-99, 1999.
[24]Potvin, J. Y. and Bengio, S., “The Vehicle Routing Problem with Time Windows PartⅡ: Genetic Search,” Informs Journal on Computing, Vol. 8, 1996, pp.165-172.
[25]Tan, K. C., Lee, L.H. and Ou, K., “Artificial Intelligence Heuristics in Solving Vehicle Routing Problems with Time Window Constraints,” Engineering Applications of Artificial Intelligence, Vol. 14, 2001, pp. 825–837.
[26]Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. and Teller, E., “Equations of State Calculations by Fast Computing Machines, ” Journal of Chemical Physics, Vol.21, 1953, pp. 1087-1092.
[27]Russell, R. A., “An effective heuristic for the m-tour traveling salesman problem with some side conditions,” Operations Research, vol. 25, 1977, pp. 517-524.
[28]Cook, T. and Russell, R. A., “A Simulation and Statistical Analysis of Stochastic Vehicle Routing with Timing Constraints,” Decision Science, Vol. 9, 1978, pp. 673-687.
[29]Baker, E. and Schaffer, J., “Computational Experience with Branch Exchange Heuristics for Vehicle Routing Problems with time window constraints,” American Journal of Mathematical and Management Sciences, Vol. 6, 1986, pp. 261-300.
[30]Kohl, N., Desrosiers, J., Madsen, O. B. G., Solomon, M. and Soumis, F., “2-Path Cuts for the Vehicle Routing Problem with Time Windows,” Transportation Science, Vol. 33, 1999, pp. 101-116.
[31]Chabrier, A., “Vehicle Routing Problem with Elementary Shortest Path Based Column Generation.” Forthcoming in: Computers and Operations Research, 2005.
[32]Cook, W. and Rich,J. L., “A Parallel Cutting Plane Algorithm for the Vehicle Routing Problem with Time Windows, ” Technical Report, TR99-04, Department of Computational and Applied Mathematics, Rice University, Houston, TX, 1999.
[33]Kallehauge, B., Larsen, J., and Madsen, O.B.G. “Lagrangean Duality and Non-differentiable Optimization Applied on Routing with Time Windows - Experimental Eesults,” Internal report IMM-REP-2000-8, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 2000.
[34]Irnich, S. and Villeneuve, D., “The Shortest Path Problem with K-cycle Elimination (k≦3): Improving a Branch-and-price Algorithm for the VRPTW.” Forthcoming in: INFORMS Journal of Computing, 2005.
[35]Larsen, J., “Parallelization of the Vehicle Routing Problem with Time Windows ” Ph.D. Thesis IMM-PHD-1999-62, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 1999.
[36]Danna, E. and Le Pape, C., “Accelerating Branch-and-price with Local Search: A Case Study on the Vehicle Routing Problem with Time Windows,” In: Column Generation, G. Desaulniers, J. Desrosiers, and M. M. Solomon (eds.),2005, Kluwer Academic Publishers, pp.99-130.
[37]Bent, R. and Hentenryck, P. V., “A Two-stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows,” Department of Computer Science, Brown University, Tech. Rep. CS-01-06, 2001.
[38]Berger, J., Barkaoui, M., and Bräysy, O., “A Route-directed Hybrid Genetic Approach for the Vehicle Routing Problem with Time Windows,” Information Systems and Operations Research, Vol. 41, 2003, pp. 179-194.
[39]Czech, Z. J. and Czarnas, P., “A Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows,” in Proc. 10th Euromicro Workshop on Parallel, 2002, pp. 376-383.
[40]Cordeau, J. F., Larporte, G., and Mercier, A., “A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows,” Journal of the Operational Research Society, Vol. 52, 2001, pp. 928-936.
[41]Homberger, J. and Gehring, H., “Two Evolutionary Meta-heuristics for the Vehicle Routing Problem with Time Windows,” INFOR, Vol. 37, 1999, pp. 297-318.
[42]Homberger, J., “Verteilt-parallele Metaheuristiken Zur Tourenplanung,” Gaber, Wiesbaden, 2000.
[43]Ibaraki, T., Imahori, S., Kubo, M., Masuda, T., Uno, T., and Yagiura, M., “Effective Local Search Algorithms for Routing and Scheduling Problems with General Time Window Constraints,” Transportation Science, Vol. 39, 2005, pp. 206-232.
[44]Mester, D., “An Evolutionary Strategies Algorithm for Large Scale Vehicle Routing Problem with Capacitate and Time Windows Restrictions,” In Conf. Mathematical and Population Genetics, Univ. of Haifa, Israel, 2002.
[45]Rochat, Y. and Taillard, E.D., “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing” Journal of Heuristics, Vol. 1, 1995, pp. 147-167.
[46]Rousseau, L.-M., Gendreau, M., and Pesant, G., “Using Constraint-based Operators to Solve the Vehicle Routing Problem with Time Windows,” Journal of Heuristics, Vol. 8, 2002, pp. 43-58.
[47]Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H. and Dueck, G., “Record Breaking Optimization Results Using the Ruin and Recreate Principle,” Journal of Computational Physics, Vol. 159, 2000, pp.139-171.
[48]Shaw, P., “A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems,” Department of Computer Sciences, University of Strathclyde, Glasgow, Scottland, Tech. Rep, APES group, 1997.
[49]Shaw, P., “Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems,” in Proc. of the Fourth International Conf. Principles and Practice of Constraint Programming, New York, 1998, pp. 417-431.
[50]Thangiah, S.R., Osman, I.H., and Sun, T., “Meta-heuristics for Vehicle Routing Problems with Time Windows,” Technical Report,SRU-CpSc-TR-95-32, Artificial Intelligence and Robotics Laboratory, Computer Science Department, Slippery Rock University, Pennsylvania, 1995.
[51]Berger, J., Barkaoui, M. and Bräysy, O., “A Route-directed Hybrid Genetic Approach for the Vehicle Routing Problem with Time Windows,” Information Systems and Operations Research, Vol. 41, 2003, pp. 179-194.
[52]Cordone, R. and Wolfler, R., “A Note on Time Windows Constraints in Routing Problems”, Internal Report, Department of Electronics and Information, Polytechnic of Milan, 1997, Milan, Italy.
[53]Thangiah, S.R., “A Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems with Time Windows,” in Practical Handbook of Genetic Algorithms, Volume III: Complex Structures, edited by L. Chambers, CRC Press, 1999, pp. 347–381.
[54]Braysy, O., “A New Genetic Algorithms for Vehicle Routing Problem with Time Windows Based on Hybridization of a Genetic Algorithm and Route Construction Heuristics,” in Proceedings of the University of Vaasa, Research Papers, 1999, pp. 227.
[55]Tan, K.C., Hay, L. L., and Ke, O., “A Hybrid Genetic Algorithm for Solving Vehicle Routing Problems with Time Window Constraints,” Asia-Pacific Journal of Operational Research, Vol. 18, No. 1, 2001, pp. 121–130.
[56]Tan, K.C., Lee,L.H., Zhu, Q. L. and Ou, K., “Heuristic Methods for Vehicle Routing Problem with Time Windows,” Artificial Intelligent in Engineering, 2001, pp. 281–295.
[57]Kit, H.W., Chin, J. and Lim, A., “A Hybrid Genetic Algorithm for the Vehicle Routing Problem,” International Journal on Artificial Intelligence Tools (to appear).
[58]Zhu, K.Q., “A Diversity-controlling Adaptive Genetic Algorithm for the Vehicle Routing Problem with Time Windows,” in Proceedings of the 15th IEEE International Conference on Tools for Artificial Intelligence , 2003, pp. 176–183.
[59]Beatrice, O., Brian, J. R. and Hanshar,F., “Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows,” Springer Science Business Media, Inc. Manufactured in The Netherlands. Applied Intelligence 24, 2006, pp. 17–30.