應用變數產生法求解有時間窗限制的收送貨問題

A Column Generation Approach for the Pickup and Delivery Problem with Time Windows

葉珮婷(Pei-Ting Yeh)

指導教授 ： 王晉元

國立交通大學/管理學院/運輸科技與管理學系/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00373

摘要

本研究目的為替貨運業之預先派遣作業產生具有效率的路線，除了須考量路徑成本外，尚需考量貨運業收送貨之特性，包含優先限制、聯結限制、時間窗限制與車容量限制。本研究將有時間窗限制的收送貨問題(Pickup and Delivery Problem with Time Windows, PDPTW)建構為一集合分割問題，並提出兩套以變數產生法(Column Generation)為基礎的演算法求解。此兩套演算法皆以變數產生法、分支定限法與解決重覆涵蓋問題之啟發式解法三大部分所組成，兩套演算法不同之處在於變數產生法之求解子問題演算法。本研究將子問題設計為考慮有時間窗限制收送貨特性之最短路徑問題，第一套演算法之子問題使用修正後的Dijkstra’s 演算法與啟發式解法求解；第二套演算法之子問題使用修正後之Label Correcting 演算法求解。
測試結果發現第一套演算法與第二套演算法於小例題測試範例之求解績效誤差在5%內，但使用第一套演算法之求解時間遠較第二套演算法快。本研究將第一套演算法求解子問題時之啟發式演算法分為三種組合方式，測試結果發現三種組合方式對於平均旅行成本在小範圍時間窗客戶群與同一客戶大小有顯著差異；三種組合方式對於平均車輛數僅在LR2客戶類型無顯著差異，在其餘客戶類型與同一客戶大小皆有顯著差異；三種組合方式對於不包含分支定限法之平均求解時間皆為第三種組合最快。由測試結果可知使用第一套演算法且子問題啟發式演算法使用第二種組合方式能在較快速之運算時間內求得不錯的路徑組合。

關鍵字

有時間窗限制的收送貨問題 ； 集合分割問題 ； 變數產生法

並列摘要

Pickup and delivery problem with time windows (PDPTW) is an important and fundamental problem for many logistic service providers. We first formulate this problem as a set-partitioning problem. Two column generation based algorithms are proposed for solving this model. Both algorithms consist of three phases: column generation, branch-and-bound, and heuristic local search. The column generation subproblem is formulated as a shortest path problem with multiple side constraints. The major differences between these two algorithms are the adopted solution techniques. The first algorithm is based on the traditional Dijkstra’s algorithm and the second algorithm is basically a modified Label Correcting.
We use benchmark testing problems to evaluate the performance of these two algorithms. Numerical experiments show that the proposed algorithms can find near optimal solution for smaller test problems, and the second algorithm could get better solutions efficiently on large test problems generalized from benchmark problems in the literature.

並列關鍵字

PDPTW ； set-partitioning problem ； Column Generation

參考文獻

[1] Bell, J. E. and McMullen, P. R., “Ant colony optimization techniques for the vehicle routing problem”, Advanced Engineering Informatics, 18, pp. 41-48, 2004.

[2] Bent, R. and Hentenryck, P.V.,“A Two-stage Hybrid Algorithm for Pickup and Delivery Vehicle Routing Problems with Time Windows” , Computers and Operations Research, Vol. 33, No. 4, pp. 875-893 ,2006.

[3] Berbeglia, G., Cordeau, J., Gribkovskaia, I. and Laporte, G., “Static pickup and delivery problems: a classification scheme and survey”, TOP, Vol 15, No. 1, pp. 1-31, July 2007.

[4] Dantig, G.B. and Wolfe, P., “The Decomposition Algorithm for Linear Programming”, Operations Reserch, Vol. 8, pp.101-111, 1960.

[7] Dumas, Y., Desrosiers J. and Soumis, F., “The Pickup and Delivery Problem with Time Windows” , European Journal of Operational Research, Vol. 54, No. 1, pp. 7-22, 1991.