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

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

本研究探討同時具有隨機旅行時間與服務時窗限制特性之車輛途程問題（簡稱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.