運用粒子群最佳化解決多場站之收送貨問題

A Particle Swarm Optimization Approach for the Multi-depot Vehicle Routing Problem with Pickup and Delivery

李忠憲(Chung-Hsien Li)

指導教授 ： 王晉元

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

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

摘要

本研究主要針對多場站之收送貨問題(Multi-depot Vehicle Routing Problem with Pickup and Delivery, MDPDP)定式數學模式與發展一套有效的解法。在數學模式部分，本研究參考過去所發表過MDVRP與PDPTW之數學模式，加入考量收送貨的優先限制，建構一個MDPDP之數學模式。優先限制為收送貨問題特性之一，對於每個顧客而言，必須先服務該顧客之收貨後才能服務該顧客之送貨。在演算法部分，本研究以粒子群最佳化(PSO)為基礎，設計一般PSO與GLNPSO兩種演算法來求解MDPDP，比較兩種演算法之求解績效，並提出兩種新的慣性權重更新法則。在編碼方式的設計上，參考Wu and Wang[28]，產生適合於本研究之編碼方式。最後本研究參考Ropke and Pisinger[15]之測試例題，加以修改作為本研究之測試範例。測試結果指出本研究之兩種演算法在求解小範例之績效沒有顯著差異，求解較大規模之問題時，GLNPSO求解績效較優。

關鍵字

多場站收送貨問題 ； 粒子群最佳化 ； 優先限制

並列摘要

The goals of this research are to develop a mathematical model and an effective solution technique for the Multi-depot vehicle routing problem with pickup and delivery(MDPDP). Our model is based on the published MDVRP and PDPTW formulations plus the proposed precedence constraints. The precedence constraints mean the pickup tasks must be fulfilled prior to the delivery tasks for each customer. Two particle swarm Optimization based heuristic algorithms, general PSO and GLNPSO, are developed for solving MDPDP. The uniqueness of our solution techniques is the mechanism of encoding and decoding of a solution, which is a modification of that of Wu and Wang [28]. Testing examples are generated from the existing benchmark instances. Numerical experiments show that these two algorithms perform equally well for small problems. However, GLNPSO is more effective for solving larger problems.

並列關鍵字

MDPDP ； Particle Swarm Optimization ； precedence constraints

參考文獻

[32] 林至康,「汽車客運多場站車輛排程問題之研究」，國立交通大學運輸科技與管理學系博士論文，民國九十八年三月。

[35] 葉珮婷,「應用變數產生法求解有時間窗限制的收送貨問題」，國立交通大學運輸科技與管理學系碩士論文，民國九十八年七月。

[2] Catay, B., “A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery”, EXPERT SYSREMS WITH APPLICATION, Vol.37, No. 10, pp. 6809-6817, OCT 2010.

[3] Cortes, C.E., Saez, D., Nunez, A., et al., “Hybrid Adaptive Predictive Control for a Dynamic Pickup and Delivery Problem”, Transportation Science, Vol. 43, No. 1, pp. 27-42, 2009.

[4] Goksal, F.P., Altiparmak, F., Karaoglan, I., “A hybrid particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery”, 40th International Conference on Computers and Industrial Engineering(CIE), pp. 1-6, Awaji, JUL 25-28, 2010.