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

Abstract

本研究主要針對多場站之收送貨問題(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.