跳到主要內容

臺灣博碩士論文加值系統

(44.200.27.215) 您好!臺灣時間:2024/04/20 09:23
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:周偉禮
研究生(外文):Wei-Li Chou
論文名稱:以啟發式演算法求解單一場站多車種同時收送貨之車輛途程問題
論文名稱(外文):A Heuristic Algorithm for Single Depot Vehicle Routing Problem with Simultaneous Pickup and Delivery
指導教授:朱經武朱經武引用關係
指導教授(外文):Ching-Wu Chu
學位類別:碩士
校院名稱:國立臺灣海洋大學
系所名稱:航運管理學系
學門:運輸服務學門
學類:運輸管理學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:52
中文關鍵詞:同時收送貨車輛途程問題0-1整數規劃啟發式演算法
外文關鍵詞:Vehicle routing problem with simultaneous pickup and delivery0-1 integer programmingheuristic algorithm
相關次數:
  • 被引用被引用:4
  • 點閱點閱:327
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
由配送中心運送貨物給顧客是配銷管理者每日所面臨的決策問題,如何有效率將貨物運送給顧客對配銷管理而言,是一項很重要的決策,因為運輸成本在配銷各項成本中所佔之比例很高,除此之外,速度也是一完善物流系統不可或缺的服務。
本研究中以單一配送中心為研究對象,並以實務中多車種同時收送貨車輛途程問題(Vehicle Routing Problem with Simultaneous Pickup and Delivery: VRPSPD)為探討情境,由於車輛途程問題的計算複雜度屬於NP-Hard的問題,若以數學規劃求解,不可能在合理時間內獲得結果,因此在可接受時間內,求得ㄧ高精準度的演算法協助配銷管理者解決上述問題有其必要性。
本研究之主要目的為在於滿足顧客需求及考慮公司成本下,發展一演算法,幫助配銷管理者解決規劃運送路線問題。研究中建構數學規劃模式與發展啟發式演算法,其中數學規劃模式僅適合小型問題求解與驗證演算法精確度之用。經測試比較後顯示啟發式演算法之效率與準確度均十分良好。
How to efficiently delivery goods to customers from a depot is a daily and an important decision for the logistics managers, because the transportation cost accounts for a large portion of the distribution cost. Furthermore, the speed of delivery is also an indispensable element of a sound logistics system.
A single-depot vehicle routing problem with simultaneous pickup and delivery is studied in this thesis. Since the complexity of vehicle routing problem is NP hard, it is impossible to solve this type of problem within a reasonable time with a mathematical model. So it is necessary to develop a high accuracy algorithm helping the logistics managers dealing with the above mentioned problem.
The main purpose of this thesis is to develop a heuristic algorithm facilitating the logistics managers in planning the delivery routes under the consideration of customers’ demands and operating costs. Both the mathematical model and heuristic algorithm are developed in this thesis. The mathematical model is suitable for small size problem and developed fro comparing the accuracy with the heuristic algorithm. From the empirical results, we know that the heuristic algorithm performs well in terms of efficiency and accuracy.
第 一 章 緒論
1.1研究動機與目的
1.2研究範圍與基本假設
1.3研究流程與方法
第 二 章 文獻回顧
2.1車輛途程問題的基本概念
2.1.1車輛途程問題的基本假設
2.1.2各類型車輛途程問題
2.1.3回程收貨的車輛途程問題
2.2車輛途程問題相關演算法
2.2.1節省法
2.2.2途程改良
2.2.3禁忌搜尋法
2.3考慮收貨與送貨之車輛途程問題
第 三 章 整數規劃模式
3.1整數規劃模式
3.2啟發式演算法
3.2.1建構起初解程序
3.2.1.1 Clarke-Wright節省法
3.2.1.2搬移與插入程序
3.2.1.3檢查與重新安排程序
3.2.2最佳化程序
3.2.2.1路線內改善
3.2.2.2路線間改善
3.2.2.3搜尋
第 四 章 範例說明與分析
4.1 測試例題之蒐集與說明
4.2求解結果
第 五 章 結論與建議
5.1 結論
5.2 建議
參考文獻
附錄
一、中文部份
1.夏承永(2003),「以遺傳演算法求解多車種多倉庫之車輛途程問題」,國立清華大學碩士論文。
2.陳建良(2002),「以啟發式演算法求解時窗限制車輛途程問題」,私立中原大學碩士論文。
3.鄧宇佑(2002),「求解醫院運輸部門運輸中心個數最佳化之研究」,國立成功大學碩士論文。
4.劉曄(2005),「整合同時收送貨與選擇貨運公司服務之車輛途程問題」,國立台灣海洋大學碩士論文。
5.謝伯昂(2002),「考慮收送貨與選擇貨運公司服務的車輛途程問題」,國立台灣海洋大學碩士論文。
二、英文部份
1.Ball, M.O., Golden, A, Assad, A. and Bodin, L.D. (1983), “Planning for Truck Fleet Size in the Presence of a Common-Carrier Option,” Decision Sciences, 14, pp. 103-120.
2.Bodin, L., B. Golden, A. Assad and M. Ball (1983),“ Routing and Scheduling of Vehicle and crews: The State of the Art,” Computers & Operations Research, 10, pp. 62-212.
3.Casco, D. and Golden, B. and Wasil, E. (1988), “Vehicle Routing with Backhauls: Models Algorithm and Case-studies. In Vehicle Routing: Methods and Studies,” Studies in management Science and Systems, North Holland, Amsterdam, wd. B. Golden, A. Assad, Vol. 16.
4.Christofides, N. and Eilon, S. (1969), “An Algorithm for the Vehicle Dispatching Problems,” Operational Research Quarterly, 20, pp. 309-318.
5.Christofides, N., (1981),“Exact Algorithms for the Vehicles Routing Problems, Based on Spanning Tree and Shortest Path Relaxations,” Math. Prog., Vol. 20, pp. 255-282.
6.Christofides, N., Mingozzi, A., and Toth, P., (1979), “The Vehicle Routing Problem,” Combinatorial Optimization, Wiley, Chichester, pp. 315-338.
7.Chu, C. W., (2005), “A Heuristic Algorithm for The Truckload and Less_than_truckoad Problem,” European Journal of Operational Research , 113, pp. 528-543.
8.Clarke, G. and Wright, J. (1964), “ Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operational Research ,12, pp. 568-581.
9.Gaskell, T.J., (1967), “Basis for Vehicle Fleet Scheduling,” Operational Research Quarterly, 18, pp. 281-295.
10.Golden, E. B. and Alfaro, J. and Schagger, J., (1985), “The Vehicle Routing Problem with Backhauling: Two Approache,” Proceedings of the XII Annual Meeting of S.E.TIMS, Myrtle Beach, S.C, pp. 90-92.
11.Gillett, B. and Miller, L., (1974), “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operational Research, 22, pp. 340-349.
12.Glover, F., (1977) “Heuristic for Integer Programming Using Surrogate constraints,” Decision Science, 8, pp. 156-166.
13.Golden, B., Assad, A., and Arjang, A., (1988), Vehicle Routing: Methods and Studies, North-Holland, pp. 7-45.
14.Held, M. and Karp, R., (1962),“A Dynamic Programming Approach to Sequencing Problem,” SIAM Journal Applied mathematics, 10, pp. 196-210.
15.Jacques Renaud, Gilbert Laporte and Fayez F. Boctor., (1996), “A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem,” Computers & Operations research, 23, pp. 229-235
16.Kindervater, G.A.P., and Savelsbergh, M.W.P., (1997), “Vehicle Routing: Handling Edge Exchanges. In: Aarts, E.H., Lenstra, J.K. (Eds.),” Local Search in Combinatorial Optimization. Wiley, Chichester, 1997.
17.Laporte, G., Nobert, Y. and Desrochers, M., (1985), “Optimal Routing Under Capacity and Distance Restriction,” CACM, 33, pp. 1015-1073
18.Laporte, G., Gendreau, M., Potvin, J-Y, and Semet, F., (2000), “Classical and Modern Heuristics for the Vehicle Routing Problem,” International Transactions in Operational Research, 7, pp. 285-300.
19.Lin, S., (1965), “Computer Solution of the Traveling Salesman Problem,” Bell System Technology Journal, 44, pp. 2245-2269.
20.Lin, S. and Kernighan, B., (1973), “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operational Research, 21, pp. 498-516.
21.Miller, C. E., (1960), “Integer Programming Formulation of Traveling Salemen Problems,” Journal of Association for Computing Machinery, 7, pp. 326-329.
22.Min, H., (1989), “The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-up Points,” 23, pp. 377-386.
23.Mole, R. and Jameson, S., (1976), “A Sequential Route-Building Algorithm Employing A Generalized Savings Criterion,” Operational Research Q., 27, pp. 498-516.
24.Nagy, G. and Salhi, S. (2005), “Heuristic Algorithms for Single and Multiple and Depot Vehicle Routing Problem with Pickups and Deliveries,” European Journal of Operational Research, 162, pp. 126-141.
25.Psaraftis, H.N., (1980), “A Dynamic Programming Solution to the Single Vehicle Many-to-many Immediate Request Dial-a-ride Problem,” Transportation Science, 14, pp. 130-154.
26.Salhi, S., Nagy, G., (1999), “A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problem with Backhauling,” Journal of the Operational Research Society, 50, pp. 1034-1042.
27.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, pp. 854-867.
28.Stewart, W. and Golden, B., 1979,“A Vehicle Routing Algorithm Based on Generalized Lagrane Mutipliers,” Proceedings of the AIDS 1979 Annual Convention, Moore, L., Monore, K., Taylor B. Eds.,
29.Van Breedam, A. (2001), “Comparing Descent Heuristics and Metaheuristics for the Vehicle Routing Problem,” Computers & Operations Research, 28, pp. 289-315.
30.Yellow, P., (1970), “A Computational Modification to the Savings Method of Vehicle Scheduling,” Operational Research Quarterly, 21, pp. 281-283.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top