含取貨之車輛途程問題解法之研究

Solving Vehicle Routing Problem with Backhauls

吳泰熙(Tai-Hsi Wu) ； 陳正芳(Jeng-Fung Chen) ； 徐俊誠

《工業工程學刊》 20卷6期 (2003/11) Pp. 651-665

摘要

本研究針對傳統車輛途程含回程取貨問題(vehicle routing problem with backhauls,VRPB)加以研究並修改其某些不合理之假設。傳統型VRPB問題並不允許對某一需求點同時送貨與取貨，而且取貨點一定要安排在送貨點之後處理。但如此之假設恐將造成路線行駛距離與所需車輛數之增加，且與某些產業之貨物運送實況不合。基於此想法，我們將取貨需求點必需放在送貨需求點之後的限制予以放寬，而且允許同一需求點可以同時為送貨點與取貨點，接著將此修正後之VRPB與服務時窗(time windows)結合以更接近實務現況。文內針對上述兩類型之問題分別建構對應之數學模式，並發展以模擬退火法為基之啓發式演算法，再以國際網路例題做測試。測試結果顯示，在和傳統型VRPB/VRPBTW測試例題比較方面，本研究所得之運輸距離大多優於文獻的結果，顯示修正後之VRPB/VRPBTW模式不僅具備處理實際狀況之彈性（允許需求點同時有送、取貨之需求），並較傳統之VRPB/VRPBTW模式節省運輸成本。

關鍵字

車輛途程問題 ； 取貨問題 ； 模擬退火法

並列摘要

This paper modifies the definition of the traditional vehicle routing problems with backhaul (VRPB) and presents a simulated annealing-based heuristic algorithm. Computational results demonstrate that the proposed algorithm not only has the capability of handling situations encountered in practice, but also consumes less transportation costs the traditional algorithms.

並列關鍵字

vehicle routing problem with backhaul ； simulated annealing ； VRPB ； SA

參考文獻

Casco, D. O.,Golden, B. L.,Wasil, E. A.(1988).Vehicle Routing: Methods and Studies.North-Holland, Amsterdam:

Clarke, G.,Wright, J. W.(1964).Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.Operations Research.12(4)

Deif, I.,Bodin, L.(1984).Proceedings of the Babson College Conference on Software Uses in Transportation and Logistic Management.Babson Prak, MA:

Duhamel, C.,Potvin, J. Y.,Rousseau, J. M.(1997).A tabu search heuristic for the vehicle routing problem with backhauls and time windows.Transportation Science.31

Gillett, B. E.,Miller, L. R.(1974).A heuristic algorithm for the vehicle dispatch problem.Operations Research.22(2)