進階搜尋


下載電子全文  
系統識別號 U0026-1102201402353000
論文名稱(中文) 多桶格車輛配送問題之三階段啟發式解法
論文名稱(英文) A Three-phase Efficient Heuristic for Solving the Multi-compartment Vehicle Routing Problem
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系
系所名稱(英) Department of Industrial and Information Management
學年度 102
學期 1
出版年 103
研究生(中文) 姚逸羣
研究生(英文) Yi-Chun Yao
學號 R36014113
學位類別 碩士
語文別 中文
論文頁數 69頁
口試委員 指導教授-李賢得
口試委員-利德江
口試委員-王清正
中文關鍵字 車輛配送問題  多桶格配送  整數規劃模式  三階段啟發式解法 
英文關鍵字 vehicle routing problem  multi-compartment  integer programming  three-phase heuristic 
學科別分類
中文摘要 隨著物流業競爭日益劇烈,在多樣化產品的配送需求下,為了高效率運作而將多樣產品裝載於同一配送車輛,同時為了避免不相容產品的混裝問題,即不同產品存放之隔間不可相同,實務上發展出配送車輛上裝設之桶格與隔間設計以同時運送不相容產品。但在進行物流配送作業時,便面臨一高度複雜之組合最佳化問題,包含配送車輛之選擇與路線規劃,以及不同訂單如何分配於最適車輛中桶格之決策。
本研究首先建構一多桶格車輛配送問題之數學模式,但在求解此整數規劃模式時發現,由於模式過於複雜,導致求解時間過長,無法滿足實務上即時或快速之需求,故發展一三階段啟發式解法以快速求得良好品質之決策,首先第一階段以權重法、最大配送成本法與累計配送成本法,挑選優先顧客後分配至不同車輛,第二階段以優先顧客為基準求解一般化指派問題,將每一顧客之每一筆訂單指派至每一台車輛上之合適桶格進行裝載,完成顧客分群與桶格指派作業,第三階段則以每一台車輛之分群結果,求解其對應之旅行銷售員問題,可得到全部車輛之路線與其總配運成本。
依據演算實驗發現,最佳化解法與數學模式過於複雜,僅能求解小型問題,故針對顧客數較小型之派車問題採用最佳解法與三階段啟發式解法之求解品質進行絕對比較,發現累計配送成本法所求得之品質出色,其總配送成本與最佳解之平均誤差小於4%,平均求解時間亦小於10秒,十分快速;當顧客數變大時,則以三種不同啟發式解法進行相對比較,實驗發現累計配送成本法其求解品質穩定,且整體表現較其他二種為佳,求解時間平均小於1分半鐘,可有助應用在實際上求解多桶格車輛配送問題。
英文摘要 The vehicle routing problem (VRP) with multiple compartments in each vehicle is considered in this thesis. The problem is to determine an optimal delivery route which leaves from a distribution center, visits customers and returns, subject to constraints of vehicle and compartment capacity and to meet customer’s demand. Compartments are installed and used in each vehicle to improve delivery efficiency and avoid the incompatibility between products.
An integer programming model is formulated for this multi-compartment VRP. Due to the computational complexity of the mathematical model, a three-phase heuristic is developed to find the optimal delivery route with minimal cost. The heuristic includes three methods to assign seed customer to each vehicle.
Computational experiments and results have demonstrated that the three-phase heuristic performs very well. For the small data set, the deviation of total delivery cost from the best three-phase heuristic to the optimization model is less than 4%. The average computational time is less than 10 seconds. For the large data set, the three-phase heuristic with accumulated delivery cost criterion to assign seed customer performs the best. Overall, the three-phase heuristic with accumulated delivery cost criterion has the best solution quality, and is computationally the most efficient.
論文目次 目錄
摘要 I
Abstract II
誌謝 V
目錄 VI
表目錄 VIII
圖目錄 IX
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 1
1.3 研究目的 2
1.4 研究流程 2
第二章 文獻探討 4
2.1 傳統車輛配送問題 4
2.2 多桶格車輛配送問題 7
2.3 海運船舶多艙裝載問題 8
第三章 多桶格車輛配送數學模式與啟發式解法發展 12
3.1 問題描述 12
3.2 多桶格車輛配送數學規劃模式 13
3.3 三階段啟發式解法之發展 15
第四章 範例說明與演算實驗 19
4.1 範例說明 19
4.2 演算實驗 30
4.3 演算實驗比較與分析 31
4.3.1 絕對比較 31
4.3.2 相對比較 33
第五章 研究成果與未來研究議題 40
5.1 研究成果 40
5.2 未來研究議題 40
參考文獻 42
參考文獻 1. Al-Khayyal, F., and Hwang, S.J., (2007). Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk, part I: applications and model. European Journal of Operational Research, Vol. 176, pp. 106-130.
2. Appelgren, L.H., (1969). A column generation algorithm for a ship scheduling problem. Transportation Science, Vol. 3, pp. 53-68.
3. Appelgren, L.H., (1971). Integer programming methods for a vessel scheduling problem. Transportation Science, Vol. 5, pp. 64-78.
4. Avella, P., Boccia, M., and Sforza, A., (2004). Solving a fuel delivery problem by heuristic and exact approaches. European Journal of Operational Research, Vol. 152, pp. 170-179.
5. Baldacci, R., Hadjiconstantinou, E.A., and Mingozzi, A., (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations Research, Vol. 52, pp. 723-738.
6. Baldacci, R., Toth, P., and Vigo, D., (2007). Recent advances in vehicle routing exact algorithms. A Quarterly Journal of Operations Research, Vol. 5, pp. 269-298.
7. Berger, J., and Barkaoui, M., (2003). A new hybrid algorithm for the capacitated vehicle routing problem. The Journal of the Operational Research Society, Vol. 54, pp. 1254-1262.
8. Brown, G.G., and Graves, G.W., (1981). Real-time dispatch of petroleum tank trucks. Management Science, Vol. 27, pp. 19-32.
9. Brown, G.G., Graves, G.W., and Ronen, D., (1987). Scheduling ocean transportation of crude oil. Management Science, Vol. 33, pp. 335-346.
10. Bruggen, L.V.D., Gruson, R., and Salomon, M., (1995). Reconsidering the distribution structure of gasoline products for a large oil company. European Journal of Operational Research, Vol. 81, pp. 460-473.
11. Bukchin, J., and Sarin, S.C., (2004). A cyclic policy for the loading of multiple products on a vehicle with different compartment sizes. IIE transactions, Vol. 36, pp. 641-653.
12. Chajakis, E.D., and Guignard, M., (2003). Scheduling deliveries in vehicle with multiple compartments. Journal of Global Optimization, Vol. 26, pp. 43-78.
13. Christiansen, M., and Nygreen, B., (1998). A method for solving ship routing problems with inventory constraints. Annals of Operations Research, Vol. 81, pp. 357-378.
14. Christiansen, M., Fagerholt, K., Flatberg, T., Haugen, O., Kloster, O., and Lund, E.H., (2011). Maritime inventory routing with multiple products: a case study from the cement industry. European Journal of Operational Research, Vol. 208, pp. 86-94.
15. Christofides, N., Mingozzi, A., and Toth, P., (1981). Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Mathematical Programming, Vol. 20, pp. 255-282.
16. Clark, G., and Wright, J.W., (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, Vol. 12, pp. 568-581.
17. Cornillier, F., Boctor, F.F., Laporte, G., and Renaud, J., (2008). An exact algorithm for the petrol station replenishment problem. The Journal of the Operational Research Society, Vol. 59, pp. 607-615.
18. Dantzig, G.B., and Ramser, J.H., (1959). The truck dispatching problem. Management Science, Vol. 6, pp. 80-91.
19. Derigs, U., Gottlieb, J., Kalkoff, J., Piesche, M., Rothlauf, F., and Vogel, U., (2011). Vehicle routing with compartments: applications, modeling and heuristics. OR Spectrum, Vol. 33, pp. 885-914.
20. Fagerholt, K., and Christiansen M., (2000). A combined ship scheduling and allocation problem. The Journal of the Operational Research Society, Vol. 51, pp. 834-842.
21. Fallahi, A.E., Prins, C., and Calvo, R.W., (2008). A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers and Operations Research, Vol. 35, pp. 1725-1741.
22. Fisher, M.L., and Jaikumar, R., (1981). A generalized assignment heuristic for vehicle routing. Networks, Vol. 11, pp. 109-124.
23. Garey, M.R., and Johnson, D.S., (1979). Computers and intractability: a guide to the theory of NP-completeness.W. H. Freeman, ISBN 0-7167-1045-5.
24. Gillett, B.E., and Miller, L.R., (1974). A heuristic algorithm for the vehicle-dispatching problem. Operations Research, Vol. 22, pp. 340-349.
25. Glover, F., (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, Vol. 13, pp. 533-549.
26. Golden, B., Assad, A., Levy, L., and Gheysens, F., (1984). The fleet size and mix vehicle routing problem. Computers and Operations Research, Vol. 11, pp. 49-66.
27. Gunnarsson, H., Rönnqvist, M., and Carlsson, D., (2006). A combined terminal location and ship routing problem. The Journal of the Operational Research Society, Vol. 57, pp. 928-938.
28. Jetlund, A.S., and Karimi, I.A., (2004). Improving the logistics of multi-compartment chemical tankers. Computers and Chemical Engineering, Vol. 28, pp. 1267-1283.
29. Karp, R.M., (1972). Reducibility among combinatorial problems. In Miller, R.E. and Thatcher, J.W.(Editors). Complexity of Computer Computations. New York: Plenum, pp. 85-103.
30. Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P., (1983). Optimization by simulated annealing. Science, New Series, Vol. 220, pp. 671-680.
31. Laporte, G., (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, Vol. 59, pp. 345-358.
32. Laporte, G., Mercure, H., and Nobert, Y., (1992). A branch and bound algorithm for a class of asymmetrical vehicle routing problems. The Journal of the Operational Research Society, Vol. 43, pp. 469-481.
33. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B., (1985). The traveling salesman problem. John Wiley & Sons Ltd.
34. Lawrence, S.A., (1972). International sea transport: the years ahead. Lexington Books, Lexington, MA.
35. Mendoza, J.E., Castanier, B., Guéret, C., Medaglia, A.L., and Velasco, N., (2010). A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Computers and Operations Research, Vol. 37, pp. 1886-1898.
36. Mendoza, J.E., Castanier, B., Guéret, C., Medaglia, A.L., and Velasco, N., (2011). Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands. Transportation Science, Vol. 45, pp. 346-363.
37. Miller, D.M., (1987). An interactive, computer-aided ship scheduling system. European Journal of Operational Research, Vol. 32, pp. 363-379.
38. Psaraftis, H.N., (1999). Forward to the focused issue on maritime transportation. Transportation Science, Vol. 33, pp. 1-2.
39. Robusté, F., Daganzo, C.F., and Souleyrette II, R.R., (1990). Implementing vehicle routing models. Transportation Research Part B: Methodological, Vol. 24B, pp. 263-286.
40. Ronen, D., (1983). Cargo ships routing and scheduling: survey of models and problems. European Journal of Operational Research, Vol. 12, pp. 119-126.
41. Ronen, D., (1986). Short-term scheduling of vessels for shipping bulk or semi-bulk commodities originating in a single area. Operations Research, Vol. 34, pp. 164-173.
42. Ronen, D., (2002). Marine inventory routing: shipments planning. The Journal of the Operational Research Society, Vol. 53, pp. 108-114.
43. Savelsbergh, M.W.P., (1985). Local search in routing problems with time windows. Annals of Operations Research, Vol. 4, pp. 285-305.
44. Sherali, H.D., Al-Yakoob, S.M., and Hassan, M.M., (1999). Fleet management models and algorithms for an oil-tanker routing and scheduling problem. IIE transactions, Vol. 31, pp. 395-406.
45. Tarantilis, C.D., Zachariadis, E.E., and Kiranoudis, C.T., (2008). A guided tabu search for the heterogeneous vehicle routing problem. The Journal of the Operational Research Society, Vol. 59, pp. 1659-1673.
46. Van Breedam, A., (1995). Improvement heuristics for the vehicle routing problem based on simulated annealing. European Journal of Operational Research, Vol. 86, pp.480-490.
47. Voudouris, C., and Tsang, E., (1995). Partial constraint satisfaction problems and guided local search. Technical Report CSM 250, Department of Computer Science, University of Essex: UK, pp. 337-356.
48. Wren, A., and Holliday, A., (1972). Computer scheduling of vehicles from one or more depots to a number of delivery points. Operational Research Quarterly, Vol. 23, pp. 333-344.
49. Yuceer, U., (1996). A multi-product loading problem: a model and solution method. European Journal of Operational Research, Vol. 101, pp. 519-531.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2019-02-14起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2019-02-14起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw