An Exact Algorithm for Vehicle Routing Problem with Time Windows and Stochastic Travel Times

含時窗限制暨機率型旅行時間車輛途程問題之真正解演算法探討

陳惠國(Huey-Kuo Chen) ； 薛哲夫(Che-Fu Hsueh) ； 張美香(Mei-Shiang Chang)

《運輸學刊》 23卷4期 (2011/12) Pp. 437-476

https://doi.org/10.6383/JCIT.201112.0028

摘要

本研究探討同時具有隨機旅行時間與服務時窗限制特性之車輛途程問題（簡稱VRPTW－ST），其主要內容為藉由妥善安排車輛路線以及離開服務顧客的時間，來達成一般化總成本期望值最小化的目標。VRPTW－ST問題可以建構為隨機規劃問題，然後利用分枝與切割法求解。本研究所研提之切割可以做為原目標函數之下限，因此所得結果為真正解。為提升演算法之效率，本研究亦探討加速收斂速度之求解技巧，經由測試結果顯示，25個節點規模之問題在Intel PIII 550 CPU及128MB RAM的環境下均可在10分鐘之內求得真正解。

關鍵字

車輛途程問題 ； 隨機旅行時間 ； 時窗限制 ； 隨機規劃

並列摘要

This paper considers the vehicle routing problem with time windows and stochastic travel times (VRPTW-ST), in which the expected total general cost is minimized by optimally determining the vehicle routes as well as departure times from each node/customer. The VRPTW-ST is mathematically formulated as a stochastic programming model and solved by a branch-and-cut solution algorithm which involves a brand new class of cuts. These cuts serve as the lower bounds of the original objective and hence make the obtained solution to be exact. Some skills to accelerate the rate of convergence are also discussed. Computational results indicate that problems with 25 nodes can be solved to optimality within 10 minutes under the environment of Intel PIII 550 CPU and 128MB RAM.

並列關鍵字

Vehicle routing problem ； Stochastic travel times ； Time windows ； Stochastic programming

參考文獻

Benders, J. F.(1962).Partitioning Procedures for Solving Mixed-variables Programming Problems.Numerische Mathematik.4(1),238-252.

Birge, J. R.,Louveaux, F.(1997).Introduction to Stochastic Programming.New York:Springer-Verlag.

Carraway, R. L.,Morin, T. L.,Moskowitz, H.(1989).Generalized Dynamic Programming for Stochastic Combinatorial Optimization.Operations Research.37(5),819-829.

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

Gendreau, M.,Laporte, G.,Séguin, R.(1996).Stochastic Vehicle Routing.European Journal of Operational Research.88(1),3-12.