臺灣博碩士論文加值系統

本研究乃是在探討同時具有收貨、送貨與時窗限制的多場站車輛途程問題。考量n個顧客點與m個場站，每一個顧客點由一部車子服務，每部車子服務完途程上的所有需求點後須返回原場站，車子服務需求點的時間必須符合時窗的限制且不能違反車子容量的限制，目標是使總運輸成本最小化。
由於多場站車輛途程與規劃問題是屬於尚未定論是多項式難度（NP-hard）的問題，本研究的目的乃是要發展一個能在合理時間內找出近似最佳或好解的啟發式解法，以使運輸成本最小化，我們並對發展的啟發式解法就解的品質和計算效率與Cplex 7.0最佳化軟體作比較。

The classical vehicle routing problem is thought of as a single depot with pure delivery or pickup problem. In many practical situations, however, the fleet of vehicles is stationed at more than one depot and the vehicle is required to mix drop off goods and pick up goods to the depot at the same stop. This paper recognizes the possibility of mixed routes with pickup and delivery customers allowed. The objective of the problem is to design a set of routs for the vehicles stationed at each depot so that all customers are serviced, each vehicle departs from and returns to the same depot, and the total distance traveled by the fleet is minimized.

The purpose of this paper is to develop a heuristic for this type of vehicle routing problems. Computational characteristics of the developed heuristic will be evaluated through extensive computational experiments and comparisons will be made with optimal solutions.

中文摘要…………………………………………………….….……i
英文摘要…………………………………………………….………ii
目錄…………………………………………………………………iii
圖目錄………………………………………………………………vi
表目錄…………………………………………………...…………vii
1.緒論………………………………………………….……………1
1.1前言………………………………………………………...1
1.2研究動機與目的…………………………………………...3
1.3研究範圍………………………………………………...…6
1.4研究步驟………………………………………...…………6
2.文獻探討………………………………………………………….8
2.1 傳統車輛途程問題(VRP)...………………………………...8
2.1.1 傳統VRP的基本假設...……………………………9
2.1.2 車輛途程問題發展…………………………………10
2.1.3 傳統求解車輛途程的方法…………………………13
2.2 具時窗限制的車輛途程問題(VRPTW)…………………...15
2.3 包含回程取貨和具時窗限制及回程取貨的車輛途程問題(VRPB and VRPBTW)………………………….…………18
2.4 多場站的車輛途程問題(MDVRP)...……………………….21
3.MDVRPSDPTW數學模式……………………………………….30
3.1MDVRPSDPTW基本假設………………………………...30
3.2MDVRPSDPTW數學模式………………………………...30
3.3MDVRPSDPTW數學模式求解…………………………...35
4.考量時窗限制與同時送貨與收貨之多場站車輛途程問題(MDVRPSDPTW)的改善啟發式方法….………………………..40
4.1 啟發式解法發展概念……………………………………….40
4.2 起始途程建構……………………………………………….43
4.2.1第一階段 : 對需求點分群……………………………44
4.2.2 第二階段 : 界限內需求點的途程安排……………...46
4.2.3 第三階段 : 安排界限外需求點到途程中…………...50
4.3 搜尋鄰近解的改善方法…………………………………….51
4.3.1 場站間的途程交換改善……………………………..52
4.3.2 場站內的途程交換改善…………………………..…56
4.3.3 途程內的交換改善..……………………………..…..57
4.4 改善程序……………………………………………….……58
5.評估啟發式解法……………………………………………….….65
5.1 基本資料設定………………………………………….……65
5.2 MDVRPSDPTW實驗結果…………………………………67
5.3 MDVRP實驗結果…………..………………………...……68
6.結論與未來方向………………………………………………….70
6.1 結論…………………………………………………………70
6.2 2未來研究方向………………………………………...……70
參考文獻………………………………………………………..….71

圖目錄
圖1.1 傳統的物流配送模式………………….………………….2
圖1.2 經由物流中心的物流配送模式…………………………..2
圖1.3 研究步驟流程圖………………………….……………….7
圖2.1 TSP……………………………………………..…………..8
圖2.2 VRP…………………………………………….…………..8
圖3.1 MDVRPSDPTW結果示意圖…………………………….39
圖4.1 起始途程建構流程圖…………………………...………..44
圖4.2 傳統節省法……………………………………………….48
圖 4.3 1-0節點交換法…………………………..………………53
圖 4.4 1-1節點交換法………………………………..…………54
圖 4.5 2-Opt節線交換法……………………………………..…58
圖 4.6 3-Opt 節線交換法…………………………………….…58
圖 4.7 改善流程圖…………………………………………..….59
圖 4.8 梯形門檻數列示意圖………………...…………………60
圖 4.9 Inter-depot improvement 交換模組……………………..62
圖 4.10 Intra-depot improvement 交換模組…………………....63
圖 4.11 Intra-rout improvement 交換模組………………….…..64

表目錄
表1.1 研究範圍……………………………………………….….6
表2.1 VRP的相關研究……………………………………….…12
表2.2 MDVRP 相關文獻……………………………………….29
表3.1 場站1距離矩陣…………………………………...…….37
表3.2 場站2距離矩陣………………………………………....38
表3.3 需求與時窗矩陣………………………………………....39
表5.1 測試結果數據表…………………………………………67
表5.2 MDVRP的實驗結果……………………………………..69

1.Alfa, A.S., Heragu, S.S., and Chen.M. 1991. A 3-opt based simulated annealing algorism for vehicle routing problems. Computers and Industrial Engineering 21, 635-639.2.Assad, A., 1988. Modeling and implementation issues. In: Golden, L. and Assad, A. (eds). Vehicle Routing: Methods and Studies. North-Holland, Amsterdam, 127-147.3.Baker, B. M., and Sheasby, J. 1999. Extensions to the generalized assignment heuristic for vehicle routing. European Journal of Operational Research, 119, 147-157.4.Barbarosoglu, G., and Ozgur, D. 1999. A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 26, 255-270.5.Bjorndal, M.H., Caprara, A., Cowling, P.I., Croce, F.D., Lourenco, H., Malucelli, F., Orman, A.J., Pisinger, D., Rego, C. and Salazar, J.J., 1995. Some thoughts on combinatorial optimization. European Journal of Operational Research, 83, 253-270.6.Bramel, J., Simchi-levi, D. 1996. Probabilistic analysis and practical algorithms for the vehicle routing problem with time windows. Operations Research, 44, 501-509.7.Bramel, J., Simchi-levi, D. 1997. On the effectiveness of set covering formulations for the vehicle routing problem with time windows. Operations Research, 45, 295-301.8.Casco, D.O, Golden, B.L., and Wasil, E.A., 1988. Vehicle routing with backhauls: models, algorithms, and case studies. In: Golden, L. and Assad, A. (eds). Vehicle Routing: Methods and Studies, North-Holland, Amsterdam, 127-147.9.Chen, T. K., Hay, L. L., and Ke, O. U. 2001. Hybrid genetic algorithms in solving vehicle routing problems with time window constraints. Asia-Pacific Journal of Operational Research, 18, 121-130.10.Chiang, W., Russell, R. 1996. Simulated annealing methaheuristics for the vehicle routing problem with time windows. Annals of Operations Research, 63, 3-27.11.Chiang, W., Russell, R. 1997. A reactive tabu search methaheuristics for the vehicle routing problem with time windows. INFORMS Journal of on Computing, 9, 417-430.12.Chin, A. 1999. A new GA approach for the vehicle routing problem. Proceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence, 307-310.13.Chao, I.M., Golden, B.L., and Wasil, E. 1993. A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. American Journal of Mathematical & Management Sciences, 13, 371-401.14.Christofides, N., Mingozi, A., and Toth, P. 1978. The vehicle routing problem. Combinational Optimization, John Wiley & Sons, New York, p318-338. 15.Christofides, N., and Eilon, S., 1969. An algorithm for the vehicle dispatching problem. Operational Research Quarterly, 20, 309-318.16.Christofides, N., 1985. Vehicle routing, In: Lawler, E. L., J. K. Lenstra, A. H. G. Rinnooy Kan, and Shmoys, D. B. (eds). The traveling Salesman Problem, John Wiley and Sons Ltd., New York, 431-448.17.Clarke, G., and Wright, J., 1964. Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581.18.Cordeau, J-F, Laporte, G., and Mercier, A, 2001. A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational research society, 52(8), 928-936.19.Cordone, R., and Calvo, R., 2001. A heuristic for the vehicle routing problem with time windows. Journal of Heuristics, 7(2), 107-129.20.De Backer, B, Furmon, V, Shaw, P, Kilby, P, and Prosser, P. 2000. Solving vehicle routing problems using constraint programming and metaheuristics. Journal of Heuristics, 6(4), 501-523.21.Deif, I., and Bodin, L., 1984. Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling. Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management, Babson Park, MA, 75-96.22.Desrochers, M., Desrosiers, J. Solomon, M. 1992. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40, 342-354.23.Dueck, G., 1993. New optimization heuristics: the great deluge algorithm and the record-to-record travel. Journal of computational physics, 104, 86-92.24.Duhamel, C, Potvin, Jean-Yves, and Rousseau, Jean-Marc, 1997. A tabu search heuristic for the vehicle routing problem with backhauls and time windows. Institute for Operations Research and Management Sciences, 49-59.25.Fisher, M. L., and Jaikumar, R., 1981. A generalized assignment heuristics for vehicle routing, Networks, 11, 109-124.26.Fisher, M., Vehicle routing, in: Ball, M., Magnanti, T., Monma, M., Nemhauser(Eds.), G. 1995. Handbooks in Operations Research and Management Science, vol. 8: Network Routing, North-Holland, Amsterdam, pp.1-33.27.Fisher, M., Jornsten, K.O., Madsen, O.B.G. 1997. Vehicle routing with time windows: two optimization algorithms. Operations Research, 45, 488-492.28.Garcia, B.L., Potvin, J.Y., Rousseau, J.M. 1994. A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraint. Computers & Operations Research, 21, 1025-1033.29.Gelinas, S., Desrochers, M., and Desrosiers, J., 1995. A new branching strategy for time constrained routing problems with application to backhauling. Annals of Operations Research, 61, 91-109.30.Gendreau, M., Hertz, A., and Laporte, G., 1994. A tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276-1290.31.Gendreau, M., Hertz, A., and Laporte, G. 1992. A tabu search heuristic for the vehicle routing problem. Working Paper, ORWP 92/14. Department de Mathematiques. Ecole Polytechnique Fe’de’rale de Lausanne.32.Gillett, B. E., and Miller, L. R., 1974. A heuristic algorithm for the vehicle dispatch problem. Operations Research, 22, 340-349.33.Gillett, B. E., and Johnson, J. W. 1976. Multi-terminal vehicle-dispatching algorithm. Omega, 4, 711-718.34.Glover, F., 1977. Heuristic for integer programming using surrogate constrains. Decision Science 8, 156-166.35.Glover, F., 1986.’Future paths for inter programming and links to artificial intelligence. Computers and Operation Research, 13, 533-54936.Glover, F., 1990. Tabu search: a tutorial, Interfaces, 20, 74-94.37.Glover, F., 1989, Tabu search-PartⅠ, ORSA Journal on Computing, 1(3), 190-206.38.Golden, B., Baker, E., Alfaro, J., and Schaffer, J., 1985. The vehicle routing problem with backhauling: two approaches. Proceedings of the Twenty-First Annual Meeting of S.E.TIMS, Myrtle Beach, Sc, 90-92.39.Golden, B.L., Magnanti, T.L., and Nguyen, H.Q. 1977. Implementing vehicle routing algorithms. Networks, 7, 113-148. 40.Goetschalckx, M., and Jacobs-Blecha, C., 1989. The vehicle routing problem with backhauls. European Journal of Operational Research, 42, 39-51.41.Goetschalckx, M., and Horsley, C., 1986. The vehicle routing problem with backhauls. Working Paper, Material Handling Research Center, Dept. of Industrial and System Engineering, Georgia Institute of Technology.42.Held, M. and R. Karp, 1970. The Travelling Salesman Problem and Minimum Spanning Tree, Operations Research, 18, 1138-1162.43.Homberger, J., and Gehring, H. 1999. Two evolutional metaheuristics for the vehicle routing problem with time windows. INFOR Journal, 37(3), 297-318.44.Kindervater, G.A.P., Savelsbergh, M.W.P. 1997. Vehicle Routing: Handling Edge Exchanges. In Local Search in Combinatorial Optimization, Chichester: Wiley, pp. 337-360.45.Kohl, N., Madsen, O.B.G. 1997. An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation. Operations Research, 45, 395-406.46.Kolen, A.W.J., Rinnooy Kan, A.H.G., Trienkens, H.W.J.M. 1987. Vehicle routing with time windows. Operations Research, 35, 266-273.47.Konskosidis, A., Powell, W.B., Solomon, M.M. 1992. An optimization-based heuristic for vehicle routing and scheduling with soft time window constrains. Transportation Science, 26, 69-85.48.Kontoravdis, G., and Bard, J., 1992. Improved heuristics for the vehicle routing problem with time windows. Working Paper, Operations Research Group, Department of Mechanical Engineering, The University of Texas, Austin.49.Laporte, G. and Osman, I. H., 1996. Metaheuristics in combinatorial optimization. Annals of Operations Research, Vol. 63, Baltzer Science Publications, The Netherlands.50.Laporte, G., Nobert, Y., and Arpin, D. 1984. Optimal solutions to capacitated multi-depot vehicle routing problem. Congressus Numerantium, 44, 283-292.51.Lenstra, J. and Rinnooy K.,1981, Complexity of vehicle routing and scheduling problem, Network, 11(2),221-227.52.Liu, F-H., and Shen, S-Y. 1999. A route-neighborhood-based metaheuristic for vehicle routing problem with time windows. European Journal of Operational Research, 118, 485-504.53.Min, H., 1989. The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportaion research. Part A, 23, 377-386.54.Min, H., Gurrent, J., and Schilling, D., 1992. The multiple depot vehicle routing problem with backhauling. Journal of Business Logistics, 13, 259-287.55.Mibaraga, P, Langevin, A, and Laporte, G, 1999. Two exact algorithms for the vehicle routing problem on tree. Naval Research Logistics, 46(1), 75-89.56.Mingozzi, A., Giorgi, S., and Baldacci, R. 1999. Exact method for the vehicle routing problem with backhauls. Transportation Science, 33(3), 315-329.57.Osman, I.H. 1991. Metastrategy simulated annealing and tabu search algorithms for combinatorial optimization problem. Ph.D. Dissertation, The Management School, Imperial Collage, London.58.Osman, I.H. 1993a. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operational Research, 41, 421-451.59.Osman, I. H. 1993b. Vehicle routing and scheduling: application, algorithms and developments, Proceedings of International Conference on Industrial Logistics, Rennes, France.60.Potvin, J., Bengo, S. 1996. The vehicle routing problem with time windows: Part II: Genetic search. INFORMS Journal on Computing, 8, 165-172.61.Potvin, J., and Rousseau J., 1997. A tabu search heuristic for the vehicle routing problem with backhauls and time windows. Transportation Science, 32(1), 49-59.62.Potvin, J., Rousseau, J. 1995. An exchange heuristic for routing problems with time windows. Journal of the Operational Research Society, 46, 1433-1446.63.Rochat, Y., Taillard, E.D. 1995. Probabilistic diversification and intensification in local search for vehicle routing. Journal of heuristic, 1, 147-167.64.Potvin, J., Rousseau, J. 1993. A parallel route building algorithms for the vehicle routing and scheduling problem with time windows. European Journal of Operational Research, 66, 331-340.65.Potvin, J., Duhamel, C., and Guertin, F., 1996. A genetic algorithm for vehicle routing with backhauling. Applied Intelligence, 6, 345-355.66.Potvin, J-Y, Kervahut, T, Garcia, B-L, and Rousscau J-M. 1996. The vehicle routing problem with time windows part I: tabu search. INFORMS Journal on Computing, 8(2), 158-164.67.Pureza, V.M., and Franca, P.M. 1991. Vehicle routing problem via tabu search metaheuristic. Publication CRT-747, Centre de recherché sur les transports, Montreal.68.Raft, O.M. 1982. A modular algorithm for an extended scheduling problem. European Journal of Operational Research, 11, 67-76.69.Reeves, C. R., 1993. Modern Heuristic Techniques for Combinatorial Problems. John Wiley & Sons, Inc., New York.70.Rego, C’esar 2001. Node-ejection chains for the vehicle routing problem: sequential and parallel algorithms. Parallel Computing, 27, 201-222.71.Renaud, J., Laporte, G., and Boctor, F. 1996. A tabu search heuristic for the multi-depot vehicle routing problem. Computers Operational Research, v23, 3, 229-235.72.Renaud, J., Boctor, F.F., and Laporte, G. 1996. An improved petal heuristic for the vehicle routing problem. Journal of the Operational Research Society, v47, 2, 329-336.73.Rochat, Y., Semet, F. 1994. A tabu search approach for delivering pet food and flour in Switzerland. Journal of Operational Research Society, 45, 1233-1246.74.Rosenkrantz, D., Sterns, R., and Lewis, P., 1977 An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6, 563-581.75.Russell, R.A. 1995. Hybrid heuristics for the vehicle routing problem with time windows. Transportation Science, 29, 156-166.76.Savelsbergh, M.W.P. 1985. Local search in routing problems with time windows. Annals of Operations Research, 4, 285-305.77.Savelsbergh, M.W.P. 1992. The vehicle routing problem with time windows: minimizing route duration. ORSA Journal of Computing, 4, 146-154.78.Salhi, S., and Nagy, G., 1999. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. Journal of the Operational Research Society, 50, 1034-1042.79.Salhi, S., and Sari, M,, 1997. A multi-level composite heuristic for the multi-depot vehicle fleet mix problem. European Journal of Operational Research, 103, 95-112.80.Schruben, L., and Clifton, R., 1968. The lockset method of sequential programming applied to routing delivery and pickup trucks. American Journal of Agricultural Economics, 50, 854-867.81.Solomon, M., 1987. Algorithm for the vehicle routing and scheduling problem with time window constrain. Operations Research, 35, 254-265.82.Taillard, E., Badeau, P., Gendreau, M.M., Guertin, F., Potvin, J. 1997. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31, 170-186.83.Taillard, E. 1992. Parallel iterative search methods for vehicle routing problems. Working Paper ORWP 92/03, Department de Mathematiques, Ecole Polytechnique Fe’de’rale de Lausanne.84.Tillman, F.A., and Cain, T.M. 1972. An upper bound algorithm for the single and multiple terminal delivery problem. Management Science, 18, 664-682. 85.Tan, K. C. 2001. A messy genetic algorithm for the vehicle routing problem with time window constraints. Proceedings of the IEEE Conference on Evolutionary Computation, May 27-30, Soul, p679-686.86.Thangiah S., Osman I., and Sun, T. 1994 Hybrid genetic algorithm simulated annealing and tabu search methods for vehicle routing problem with time windows. Technical Report SRU-CpSc-TR-94-27, Computer Science Department , Slippery Rock University, Slippery Rock, PA.87.Thangiah, S., Potvin, J., and Sun, T., 1996. Heuristic approaches to vehicle routing with backhauls and time windows. Computers Operational Research, 23(11), 1043-105788.Thompson, P.M., Psaraftis, H.N. 1993. Cyclic transfer algorithms for multivehicle routing and scheduling problems. Operations Research, 41, 935-946.89.Toth, P., and Vigo, D., 1999. A heuristic algorithm for the symmetric and asymmetric vehicle routing problem with backhauls. European Journal of Operational Research, 113, 528-543.90.Toth, P., and Vigo, D., 1997. An exact algorithm for the vehicle routing problem with backhauls. Transportation science, 31(4), 372-385.91.Van Breedam, A. 1995. Improvement heuristics for the vehicle routing problem based on simulated snnealing. European Journal of Operational Research 86, 480-490.92.Van Breedam, A. 2001. Comparing descent heuristics and metaheuristics for the vehicle routing problem. Computers & Operations Research, 28, 289-315.93.Xu, J. and Kelly, J.P., 1996. A network flow-based tabu search heuristic for vehicle routing problem. Transportation Science, 30(4), 379-393.94.Yano, C., Chan, T., Richter, L., Cutler, T., Murty, K., and McGettigan, D., 1987. Vehicle routing at quality stores. Interfaces, 17(2), 52-63.