時窗限制虛擬場站接駁補貨車輛途程問題之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：13

、訪客IP：3.144.145.38

姓名

許家筠(Chia-yuan Hsu) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

時窗限制虛擬場站接駁補貨車輛途程問題之研究
(Linehaul-Feeder Vehicle Routing Problem with Virtual Depots and Time Windows)

相關論文

★ 圖書館系統通閱移送書籍之車輛途程問題	★ 起迄對旅行時間目標下高速公路匝道儀控之研究
★ 結合限制規劃法與螞蟻演算法求解運動排程問題	★ 共同邊界資料包絡分析法在運輸業之應用-以國內航線之經營效率為例
★ 雙北市公車乘客知覺服務品質、知覺價值、滿意度、行為意向路線與乘客之跨層次中介效果與調節式中介效果	★ 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 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

台灣都市地區部分巷道狹窄，致使大型貨車進出、臨時停車皆不容易；為因應此問題，已有部分物流業者利用載貨量大但機動性較低之大車(如貨車)搭配機動性高但載貨量較小之小車(如機車)進行接駁補貨的配送服務，針對配送方式，本研究提出「時窗限制之虛擬場站接駁補貨車輛途程問題」(linehaul-feeder vehicle routing problem with virtual depots and time windows, LFVRP-VD-TW)，即大車、小車須在客戶預期收取貨物的時段內各自完成每一客戶的貨物配送，當小車送貨完畢時，除了返回實際場站(physical depot, PD)補貨亦可選擇直接前往大車所在之虛擬場站(virtual depot)進行補貨，補貨完畢小車即可再進行配送服務，節省小車往返場站之次數、距離與時間。
本研究根據其問題特性建構數學模型，並發展出一套建構初始途程模組與途程改善模組之兩階段啟發式演算法，其中，途程改善模組以禁制搜尋法為主軸，並結合路線間節點1-1交換法。根據LFVRP-VD(何宗育，2007)研究，從The VRP Web題庫裡所挑選出的17題範例，作為本研究的範例基礎，並針對本研究之問題特性設計為LFVRP-VD-TW之測試例題並作測試結果分析。測試結果可知，17題範例的平均目標函數值為2673.15，平均運算時間54.61秒，改善率達10.59%。

摘要(英)

Due to the scarcity of land resources for the access limitations of local streets for accommodating large vehicles in urban areas, some home delivery companies have invented a new type of vehicle routing and operations which involves two types of vehicles. This problem can be regarded as an extension of the vehicle routing problem and is named as the linehaul-feeder vehicle routing problem with virtual depots and time windows (LFVRP-VD-TW). It means that a big vehicle departs from the physical depot (PD) and traverses all virtual depots (VD), whereas a set of small vehicles performs delivery to customers and, if necessary, reloads the commodity either from the PD or from the big vehicle at a VD before continuing their work. During the operation, all of vehicles must perform delivery during the time window of the customers.
In this research, the LFVRP-VD-TW is formally formulated as a mixed integer programming problem. In addition, a meta-heuristics which includes tour construction and tour improvement procedure which consists of the tabu search and the exchange method is proposed for solving it. Seventeen test problems modified from the LFVRP-VD (Chen et al., 2007) benchmark instances were extensively examined. The results show that the average objective value of the seventeen test problems is 2673.15, and it could be reduced 10.59% by the tour improvement procedure.

關鍵字(中)

★ 接駁補貨
★ 實際場站
★ 虛擬場站
★ 禁制搜尋法

關鍵字(英)

★ Linehaul-feeder
★ Tabu search
★ Virtual depot
★ Physical depot

論文目次

摘要 I
ABSTRACT II
致謝 III
目錄 V
圖目錄 VII
表目錄 IX
第一章緒論 1
1.1 研究動機與目的 1
1.2 研究內容 3
1.3 研究方法與流程 4
第二章文獻回顧 7
2.1 車輛途程問題之相關文獻 7
2.1.1車輛途程問題 7
2.1.2車輛途程問題的分類 8
2.1.3車輛途程問題的求解方法 11
2.2 指定點接駁車輛途程問題之相關文獻 22
2.3 虛擬場站接駁補貨車輛途程問題之相關文獻 25
2.4 文獻回顧之結論 28
第三章模型建構 30
3.1 問題特性 30
3.2 研究假設 33
3.3符號說明 35
3.4 數學模型 37
第四章求解演算法 44
4.1 演算法架構 44
4.2 建構初始途程模組 45
4.2.1 建構單一小車的超時容路線 47
4.2.2 建構多小車之超容量路線 51
4.2.3 選擇虛擬場站 59
4.2.4 建構初始可行路線 63
4.3 改善途程模組 67
4.3.1 禁制搜尋法 68
4.3.2 鄰近解 71
4.3.3 傳統區域搜尋法 72
第五章範例測試與分析 75
5.1測試例題之建立 75
5.2 範例測試 79
5.2.1範例測試之初始路線 79
5.2.2 改善路線之範例測試 82
5.2.3 範例測試結果之比較分析 84
第六章結論與建議 91
6.1 結論 91
6.2 建議 92
參考文獻 94
附錄一測試例題5之小車初始路線 98

參考文獻

1. 王元鵬(2006)，仿水流離散優化演算法，國立台灣大學工業工程學研究所碩士論文，台北。
2. 毛皖亭(2007)，線上動態車輛巡迴路線演算法之發展：滾動平面法之應用，國立成功大學交通管理科學研究所碩士論文，台南。
3. 陳惠國、王宣(2006)，垃圾車輛途程問題之研究，中華民國運輸學會第21屆論文研討會，新竹。
4. 張耘翠(2006)，指定點接駁車輛路線問題之建構與解法研究，中華大學科技管理研究所碩士論文，新竹。
5. 劉建宏(2005)，含時窗限制式卡車與拖車途程問題之研究，國立中央大學土木工程研究所碩士論文，中壢。
6. Brandao, J. and Mercer, A. (1997), “A tabu search algorithm for the multi-trip vehicle routing and scheduling problem,” European Journal of Operational Research, Vol. 100, No. 1, pp. 180-191.
7. Bräysy, O. and Gendreau, M. (2005a), “Vehicle routing problem with time windows, part I: route construction and local search algorithms,” Transportation Science, Vol. 39, No. 1, pp. 104-118.
8. Bräysy, O. and Gendreau, M. (2005b), “Vehicle routing problem with time windows, part II: metaheuristics,” Transportation Science, Vol. 39, No. 1, pp. 119-139.
9. Chiang, W.C. and Russel, R.A. (1997), “A reactive tabu search metaheuristic for the vehicle routing problem with time windows,” INFORM Journal of Computing, Vol. 9, No. 4, pp. 417-430.
10. Chen, H.K., Hsueh, C.F. and Chang, M.S. (2006), “The real-time time-dependent vehicle routing problem,” Transportation Research Part E., Vol. 42, pp. 383-408.
11. Chen, H.K. and Chou, H.W. Hsueh, C.F and Ho, T.Y. (2007), “The linehaul-feeder vehicle routing problem with virtual depots,” Submitted to IEEE Transactions on Automation Science and Engineering.
12. 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.
13. 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.
14. Dorigo, M., Maniezzo, V., and Colorni, A. (1996), “The ant system: Optimization by a colony of cooperating agents,” IEEE Transaction on System, Man, and Cybernetics-Part B, Vol. 26-1, pp. 29-41.
15. Dorigo, M. and Gambardella, L.M. (1997), “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evoluationaty Computation, Vol. 1-1, pp. 53-66.
16. Glover, F. (1989), “Tabu Search-Part I,” ORSA Journal on Computing, Vol. 1, No. 3, pp. 190-206.
17. Glover, F. (1990), “Tabu Search-Part II,” ORSA Journal on Computing, Vol. 2, No. 1, pp. 4-32.
18. Gendreau, M., Laporte, G., Musaraganyi, C., and Taillard, E.D. (1999), “A tabu search heuristic for the heterogeneous fleet vehicle routing problem,” Computers & Operations Research, Vol. 26, pp. 1153-1173.
19. Holland, J.H. (1975), Adapation in natural and artificial system, Univ. of Michigan Press, Ann Arbor, Mich.
20. 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.
21. Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P. (1983), “optimization by simulated annealing,” Science 220, pp. 671-680.
22. Lin, S. (1965), “Computer solutions of the traveling salesman problem,” Bell Syst. Tech. J., Vol. 44, pp. 2245-2269.
23. Lin, S., and Kernighan, B.W. (1973), “An effective heuristic algorithm for the traveling salesman problem,” Operations Research, Vol. 21, pp. 498-516.
24. Osman, I.H. (1991), “Metastrategy Simulated Annealing and Tabu Search Algorithms for Combinatorial Optimization Problem,” Ph.D. Dissertation, The Management School, Imperial Collage, London.
25. Osman, I.H. (1993), “Metastrategy simulated annealing and tabu search algorithms for vehicle routing problem,” Annals of Operations Research, Vol. 41, pp. 421-451.
26. 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.
27. Solomon, M.M. (1987), “Algorithm for the vehicle routing and scheduling problems with time windows constraints,” Operations Research, Vol. 35, pp. 254-265.
28. Solomon, M.M. and Desrosiers, J. (1988), “Time windows constrained routing and scheduling problems,” Transportation Science, Vol. 22, pp. 1-13.
29. Scheuerer, S. (2006), “A tabu search heuristic for the truck and trailer routing problem,” Computers & Operations Research, Vol. 33, pp. 894-909.
30. Stutzle, T. (1997), MAX-MIN ant system for quadratic assignment problem, Technical Report AIDA-97-04, Intellectics Group, Department of Computer Science, Darmstadt University of Technology, Germany, July.
31. Stutzle, T. and Hoos, H.H. (1997), “The MAX-MIN ant system and local search for traveling salesman problem,” In T. baeck, Z. Michalewicz, and X. Yao, editors, Proceedings of the IEEE International Conference on Evolutionary Computation(ICEC’97), pp. 309-314.
32. Taillard, E.D. and Gambardella, L.M. (1997), Adaptive memories for quadratic assignment problem, Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland.

指導教授

陳惠國(Huey-kuo Chen)

審核日期

2008-6-26

推文