含時窗限制的動態車輛途程問題之研究

A Study of The Dynamic Vehicle Routing Problem With Time Windows

周蘇江(Chou Su-Chiang)

指導教授 ： 杜志挺

中原大學/工學院/工業工程研究所/碩士(2001年)

https://doi.org/10.6840/cycu200100129

摘要

傳統上解決靜態的車輛途程問題的方法，無法應用於B2C (Business to Customer)的物流環境中，主要的因素是在於顧客需求及位置是即時而且不確定的，因此有動態的車輛途程問題的產生。
本研究在有容量及時窗的限制條件下，探討動態的車輛途程問題，並提出了利用解決靜態問題的啟發式演算法加以調整及修改，利用初始路線建構的方式，配合路線改善的方法，以雙向連結串列的資料結構，及反覆循序式的方法，並且強調求解時間的長短，使其適合於動態的問題，解決顧客需求及位置的不確定性的車輛途程問題。對於各種不同的演算法，利用實驗設計的方法，進行模擬結果的討論，探討各因子的不同水準間對不同績效指標的影響，針對插單的顧客，探討演算法對此類型的顧客的反應能力及其影響，並且分析模擬的結果。最後提出本研究的結論及未來可繼續發展的方向。

關鍵字

即時反應 ； 啟發示解法 ； 動態車輛途程

並列摘要

Dynamic vehicle routing problems arise when customers’ demands occur in real-time without knowing the information in advance. The conventional static model can’t apply to the dynamic environment. In this study, we consider the dynamically vehicle routing problem that deliver to customers with both capacity and time windows constraints. This research proposes a two-step algorithm that is modified from the heuristic approach of static problems. The first step constructs initial routes, and the second step improves the routes. The data structure of proposed algorithm is a double link list with re-optimization method. It focuses on how fast the system can solve the dynamic problem. This study also uses experimental design to simulate the model and the analysis of different indexes will be covered.

並列關鍵字

real-time reaction ； heuristic solution ； dynamic vehicle routing

參考文獻

(Bertsimas and Ryzin 1993) Bertsimas D. J., Van Ryzin G., 1993, Stochastic and dynamic vehicle routing in the Euclidian plane with multiple capacitated vehicles, Operations Research, 41, 60-76.

(Clarke and Wright 1964) Clarke, G., and Wright, J.W., 1964, Scheduling of vehicles from a central depot to a number of delivery points, Operation Research, 12, 568-581.

(Garey and Johnson 1979) Garey M.R., and Johnson, D.S., 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco.

(Gillett and Miller 1974) Gillett, B., and Miller, L., 1974, A heuristic algorithm for the vehicle dispatch problem, Operation Research, 22, 340-349.

(Ichoua, et. al. 2000) Ichoua S., Gendreau M., Potvin J-Y., 2000, Diversion issues in Real-Time vehicle dispatching, Transportation Science, 34, No. 4, 426-438.