研究生: |
鄒育銓 Yu-cyuan Zou |
---|---|
論文名稱: |
可調式多載具的車輛途程問題之研究 Adjustable Compartments Vehicle Routing Problem |
指導教授: |
喻奉天
Vincent F. Yu |
口試委員: |
郭人介
Ren-Jieh Kuo 林詩偉 Shih-Wei Lin |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2010 |
畢業學年度: | 98 |
語文別: | 中文 |
論文頁數: | 77 |
中文關鍵詞: | 車輛途程問題 、禁忌搜尋法 、多載具車輛途程問題 |
外文關鍵詞: | MC-VRP, AC-VRP, VRP |
相關次數: | 點閱:1854 下載:4 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
冷凍車及油罐車在配送產品時,通常是使用兩個載具以上的車輛來儲存不同的特定產品,與一般常見之配送模式不同,因此衍生出多載具車輛途程問題(Multi-Compartment Vehicle Routing Problem; MC-VRP)。由於實務上,某些配送業者使用可調整車輛上載具空間之車輛,以期能夠節省更多的途程成本,本研究進一步延伸MC-VRP問題,定義可調式多載具的車輛途程問題(Adjustable Compartments Vehicle Routing Problem; AC-VRP),並且建構AC-VRP的數學模型。因為最佳化軟體無法求解大型AC-VRP問題,不能滿足實際營運上之需求所以本研究亦發展了一套符合AC-VRP特性的演算法,以期能在一定時限內,求得不錯之解。此演算法以禁忌搜尋法為基礎,結合了若干特色,包括縮小搜尋的鄰近結構空間及加入指導策略來尋找最佳解,經過實驗的測試之後,結果顯示本研究所提出之演算法不但能夠找到不錯的AC-VRP解,在求解MC-VRP問題上,也略優於過去研究所提出之演算法。
Cold logistics and oil distributers often use special vehicles with multiple compartments to ship different products to customers. This special transportation mode results in a new type of vehicle routing problem, namely the multi-compartment vehicle routing problem (MC-VRP). In practice, some of these carriers adopted vehicles with adjustable compartments to further reduce transportation costs. Therefore, in this research, we extended the MC-VRP and defined the adjustable compartments vehicle routing problem (AC-VRP). We also developed a mathmatical programming model for this new problem. Since large-scale AC-VRP instances in practice are difficult to solve by commercial optimization software, we developed a heuristics algorithm based on tabu search for the AC-VRP so that quality solutions may be obtained within a reasonable amount of time. The proposed algorithm integrates certain problem specific features such as solution space reduction and guided search strategies. Results of computational experiments indicate that the proposed heuristic is capable of solving the AC-VRP efficiently. Moreover, it's performance on solving MC-VRP is slightly better than previous approaches in the literature.
Archetti, C., Speranza, M. G., & Hertz, A. (2006). A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, 40(1), 64-71.
Avella, P., Boccia, M., & Sforza, A. (2004). Solving a fuel delivery problem by heuristic and exact approaches. European Journal of Operational Research, 152(1), 170-179.
Beasley, J. (1983). Route first--Cluster second methods for vehicle routing. Omega, 11(4), 403-408.
Beullens, P., Muyldermans, L., Cattrysse, D., & Oudheusden, D. V. (2003). A guided local search heuristic for the capacitated arc routing problem European Journal of Operational Research, 147(3), 629-643.
Brandão, J., & Eglese, R. (2008). A deterministic tabu search algorithm for the capacitated arc routing problem Computers & Operations Research, 35(4), 1112-1125.
Brown, G. G., Ellis, C. J., Graves, G. W., & Ronen, D. (1987). Real-time, wide area dispatch of mobil tank trucks. Interfaces, 17(1), 107-120.
Brown, G. G., & Graves, G. W. (1981). Real-time dispatch of petroleum tank trucks. Management Science, 27(1), 19-32.
Chajakis, E. D., & Guignard, M. (2003). Scheduling Deliveries in Vehicles with Multiple Compartments Journal of Global Optimization, 26, 43-78.
Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle-dispatching problem. Operations Research, 20(3), 309-318.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 88-99.
Dror, M., & Trudeau, P. (1989). Savings by split delivery routing. Transportation Science, 23(2), 141-146.
Fallahi, A. E., Prins, C., & Calvo, R. W. (2008). A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers & Operations Research, 35(5), 1725-1741.
Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Gendreau, M., Hertz, A., & Laporte, G. (1992). New insertion and postoptimization procedures for the traveling salesman problem. Operations Research, 40(6), 1086-1094.
Gendreau, M., Hertz, A., & Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276-1285.
Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2), 340-349.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13(5), 533-549.
Golden, B. L., & Wong, R. T. (1981). Capacitated arc routing problems. Networks, 11(3), 305-315.
Haouari, M. (2002). Arc routing: theory, solutions and applications Moshe Dror (editor) Kluwer Academic Publishers. IIE Transactions, 34(3), 331-333.
Hertz, A., Laporte, G., & Mittaz, M. (2000). A tabu search heuristic for the capacitated arc routing problem. Operations Research, 48, 129-135.
Muyldermans, L., & Pang, G. (2010). On the benefits of co-collection: experiments with a multi compartment vehicle routing algorithm. European Journal of Operational Research, 206(1), 93-103.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(2), 1985-2002.
Rochat, Y., & Taillard, É. D. (1995). Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1(1), 147-167.
Ruiz, R., Maroto, C., & Alcaraz, J. (2004). A decision support system for a real vehicle routing problem. European Journal of Operational Research, 153(3), 593-606.
Taillard, É. (1993). Parallel iterative search methods for vehicle routing problems. Networks, 23(8), 661-674.
Toth, P., & Vigo, D. (2003). The granular tabu search and Its application to the vehicle-routing problem. Informs Journal on Computing, 15(4), 333-346.
Xu, J., & Kelly, J. P. (1996). A network flow-nased tabu search heuristic for the vehicle routing problem. Transportation Science, 30(4), 379-393.
Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2009). A guided tabu search for the vehicle routing problem with two-dimensional loading constraints European Journal of Operational Research, 195(3), 729-743.