多車種接駁補貨車輛途程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：27

、訪客IP：3.139.239.157

姓名

何宗育(Tsung-yu Ho) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

多車種接駁補貨車輛途程問題
(A Study of the Feeder Vehicle Routing Problem)

相關論文

★ 圖書館系統通閱移送書籍之車輛途程問題	★ 起迄對旅行時間目標下高速公路匝道儀控之研究
★ 結合限制規劃法與螞蟻演算法求解運動排程問題	★ 共同邊界資料包絡分析法在運輸業之應用-以國內航線之經營效率為例
★ 雙北市公車乘客知覺服務品質、知覺價值、滿意度、行為意向路線與乘客之跨層次中介效果與調節式中介效果	★ Investigating the influential factors of public bicycle system and cyclist heterogeneity
★ A Mixed Integer Programming Formulation for the Three-Dimensional Unit Load Device Packing Problem	★ 高速公路旅行時間預測之研究--函數資料分析之應用
★ Behavior Intention and its Influential Factors for Motorcycle Express Service	★ Inferring transportation modes (bus or vehicle) from mobile phone data using support vector machine and deep neural network.
★ 混合羅吉特模型於運具選擇之應用-以中央大學到桃園高鐵站為例	★ Preprocessing of mobile phone signal data for vehicle mode identification using map-matching technique
★ 含額外限制式動態用路人均衡模型之研究	★ 動態起迄旅次矩陣推估模型之研究
★ 動態號誌時制控制模型求解演算法之研究	★ 不同決策變數下動態用路人均衡路徑選擇模型之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

台灣都市地區部分巷道狹窄，致使大型貨車進出、臨時停車皆不容易；為因應此問題，物流業者使用機動性高但載貨量較小之輕便車輛(如機車)進行貨物配送，然而此舉可能造成車輛往返配送場站中心之次數與距離增加。近年來已有部分業者利用載貨量大但機動性較低之大車(如貨車)搭配機動性高但載貨量較小之小車(如機車)進行聯合貨物配送，亦即大車、小車各自進行貨物配送，當小車送貨完畢時，除了返回場站補貨亦可選擇直接前往大車所在位置補貨，補貨完畢小車即可再進行送貨服務，節省小車往返場站之次數、距離與時間。
針對上述問題，本研究提出「接駁補貨車輛途程問題」(Feeder Vehicle Routing Problem, FVRP)，根據問題特性建構數學模型，並提出預估平均法、門檻法兩種啟發式求解架構，再根據測試題庫The VRP Web為基礎，從中挑選出17題設計為FVRP之測試例題並作測試結果分析。經由測試結果比較，發現在測試例題的改善解當中，預估平均法的表現較良好，其最重要之原因為求解過程中預估平均法選擇較多補貨點，使小車補貨選擇更有彈性；而將測試例題補貨候選點由4點增為8點時，小車補貨選擇增加，可改善目標值約5.8%；最後提出本問題後續研究方向與建議。

摘要(英)

Due to scarcity of land resources, urban streets in Taiwan, especially those at local street level, are often not wide enough for big cars performing temporary parking and home delivery services. To solve this problem, few home delivery companies have invented a new type of vehicle routing and operations which involves two types of vehicles. During the operation, a big vehicle departs from the depot and travels along several “legitimate” stops whereas a set of small vehicles performs delivery to customers and, if necessary, reloads the commodity either from the depot or from the big vehicle at stops and then continues their work. The objective of the operation is to minimize the total travel cost. This new service not only overcomes the difficulty of accessing “narrowed” local streets with high-capacity big cars but also saves the low-capacity small vehicles a number of times to and from the depot to reload the commodities.
This problem can be regarded as an extension of the Vehicle Routing Problem and for easy of reference is named as the Feeder Vehicle Routing Problem (FVRP). In this research, the FVRP problem is formally formulated as a mixed integer programming problem and two heuristics, namely the method of average and the threshold method, are proposed for solving it. 17 test problems modified from a set of classical VRP benchmark instances were extensively examined. The results show that the method of average outperforms the threshold method in terms of the objective value, though the latter does have some nice features from the algorithmic point of view. In addition, we also observed that more candidates of stops allowed for the big car, the better objective value would be obtained. To conclude the research, a few remarks were made in the end.

關鍵字(中)

★ 啟發式解法
★ 多車種
★ 接駁補貨
★ 車輛途程問題

關鍵字(英)

★ Heuristic Algorithm.
★ Heterogeneous Fleet
★ Feeder
★ Vehicle Routing Problem

論文目次

摘要 I
Abstract II
致謝 III
目錄 V
圖目錄 VII
表目錄 IX
第一章緒論 1
1.1 研究動機與目的 1
1.2 研究範圍與假設 4
1.2.1 研究內容 4
1.2.2問題特性 5
1.3 研究步驟與流程 5
第二章文獻回顧 8
2.1 車輛途程問題相關文獻 8
2.1.1 車輛途程問題 8
2.1.2 VRP求解方法 11
2.2 垃圾回收車輛途程問題相關文獻 16
2.4 指定點接駁車輛途程問題相關文獻 22
第三章模型建構 28
3.1 FVRP問題的特性 28
3.2 研究假設 29
3.3 符號說明 30
3.4 數學模型 32
第四章求解演算法 36
4.1 整體解題架構 36
4.2 起始解建構 37
4.2.1 第一階段初始路徑建構 38
4.2.2 第二階段初始路徑建構 45
4.2.3 第三階段起始解建構 50
4.3 鄰域搜尋改善 54
第五章範例測試與分析 56
5.1 測試例題建立 56
5.2 範例測試 57
5.3 敏感度分析 63
5.4 小結 65
第六章結論與建議 66
6.1 結論 66
6.2 建議 66
參考文獻 68

參考文獻

1. 池昆霖(2006)，區位途程與易腐性商品排程之研究，國立中央大學土木工程研究所碩士論文，中壢。
2. 吳志仁(2003)，一般化卡車拖車路線問題，國立交通大學運輸科技與管理學系碩士論文，新竹。
3. 卓裕仁(2001)，以巨集啟發式方法求解多車種與週期性車輛路線問題之研究，國立交通大學運輸工程與管理學系所博士論文，新竹。
4. 凃紓瑜、賴淑娟、黎燕萍(2001)，時間限制VRP之應用研究－以網路訂購便當之配送車隊排程為例，中華大學交通與物流管理學系畢業專題報告，新竹。
5. 張靖、卓裕仁、黃勇智(2001)，「時間限制車輛途程模式應用於網路訂購便當車隊途程規劃之探討」，發表於中國工業工程學會九十年度年會暨學術研討會，高雄。
6. 陳惠國、王宣(2006)，「垃圾車輛途程問題之研究」，發表於中華民國運輸學會第21屆論文研討會，新竹。
7. 張耘翠(2006)，指定點接駁車輛路線問題之建構與解法研究，中華大學科技管理研究所碩士論文，新竹。
8. 劉建宏(2005)，含時窗限制式卡車與拖車途程問題之研究，國立中央大學土木工程研究所碩士論文，中壢。
9. Bodin, L., Golden, B.L., Assad, A., and Ball, M. (1983), “Routing and Schedule of Vehicle and Crew: the State of Art,” Computers & Operations Research, Vol. 10, No. 2, pp.63-211.
10. Chao, I. (2002), “A Tabu Search Method for the Truck and Trailer Routing Problem,” Computers & Operations Research, Vol.29, pp.33-51.
11. Christofides, N., and Eilon, S. (1969), “An Algorithm for Vehicle Dispatching Problem,” Operational Research Quarterly, Vol.20, pp.309-318.
12. Christofides, N., Mingozzi, A., and Toth, P. (1979), Combinatorial Optimization, John Wiley & Sons (Asia) Pte. Ltd., Singapore.
13. Clarke, G., and Wright, J.W. (1964), “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, pp. 568-581.
14. Dorigo, M., Maniezzo, V., and Colorni, A. (1996), “The Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26, pp. 29-41.
15. Dueck, G., and Scheuer, T. （1990）,“Threshold Accepting: a General Purpose Optimization Algorithm Appeared Superior to Simulated Annealing,” Journal of Computational Physics, Vol. 90, pp. 161-175.
16. Dueck, G. (1993), “New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel,” Journal of Computational Physics, Vol. 104, pp. 86-92.
17. Gerdessen, J. (1996), “Vehicle Routing Problem with Trailers,” European Journal of Operational Research, Vol.93, pp.135-147.
18. Gillett, B., and Miller, L. (1974), “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operations Research, Vol. 22, pp. 340-349.
19. Glover, F. (1989), “Tabu Search-Part I,” ORSA Journal on Computing, Vol. 1, No. 3, pp. 190-206.
20. Golden, B.L., Magnanti, T.L., and Nguyen, H.Q. (1977), “Implement Vehicle Routing Algorithms,” Networks, Vol. 7, pp. 113-148.
21. Holland, J. H. (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Michigan, USA.
22. Hsueh, C.F., Chen H.K., and Chou, H.W. (2007), Vehicle Routing for Relief Logistics in Natural Disasters, Working Paper at National Central University, Jungli, Taiwan.
23. Kim B.I., Kim S., and Sahoo S. (2006), “Waste Collection Vehicle Routing Problem with Time Windows,” Computers & Operations Research, Vol. 33, pp. 3624-3642.
24. Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P. (1983), “Optimization by Simulated Annealing,” Science 220, 671-680.
25. Lin, S., and Kernighan, B. (1973), “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operations Research, Vol. 21, pp. 498-516.
26. Nemhauser, G.L., and Rinnooy Kan, A.H.G. (1995), Handbooks in Operations Research and Management Science, North-Holland, Inc. Netherlands.
27. Or, I. (1976), Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Blood Banking, Ph.D. Thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, USA.
28. Psaraftis, H.N. (1995), “Dynamic Vehicle Routing: Status and Prospect,” Annals of Operations Research, Vol. 61, pp.143-164.
29. Sahoo, S., Kim, S., Kim, B.I., Kraas, B., and Popov, Jr. A. (2005), “Routing optimization for waste management,” Interfaces, Vol. 35, No. 1, pp. 24-36.
30. Scheuerer, S. (2006), “A Tabu Search Heuristic for the Truck and Trailer Routing Problem,” Computers & Operations Research, Vol.33, pp.894-909.
31. Solomon, M. M. (1983), Vehicle Routing and Scheduling with Time Windows Constraints: Models and Algorithms, Ph.D. Dissertation, Dept. of Decision Sciences, University of Pennsylvania, Pennsylvania, USA.
32. Solomon, M. M. (1986), “On the Worst-case Performance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Time Windows Constraints,” Networks, Vol. 16, pp. 161-174.
33. Solomon, M. M. (1987), “Algorithm for the Vehicle Routing and Scheduling Problems with Time Windows Constraints,” Operations Research, Vol.35, pp. 254-265.
34. Solomon, M. M., and Desrosiers, J. (1988), “Time Windows Constrained Routing and Scheduling Problems,” Transportation Science, Vol.22, pp. 1-13.
35. Toth, P., and Vigo, D. (2002), The Vehicle Routing Problem, SIAM, Philadelphia, USA.
36. The VRP Web, http://neo.lcc.uma.es/radi-aeb/WebVRP/, Collaboration between AUREN and the Languages and Computation Sciences department of the University of Malaga.

指導教授

陳惠國(Huey-kuo Chen)

審核日期

2007-7-23

推文