以蟻群最佳化演算法求解動態車輛途程問題

Ant Colony Optimization for the Dynamic Vehicle Routing Problem

"隨著電子商務的快速發展，以及物流業將資通訊技術運用於營運作業上，使得車輛途程問題（vehicle routing problem, VRP）的相關研究不再侷限於傳統的靜態問題，而是逐漸走向利用即時資訊的動態車輛途程問題（dynamic vehicle routing problem, DVRP）。本研究首先建立數學模式，在滾動平面法架構下，提出三種途程更新時機策略：時間間隔策略、批次需求策略、及混合策略，發展蟻群最佳化演算法（ant colony optimization, ACO），以及加入路徑重劃法（path-relinking, PR）機制之蟻群最佳化演算法（ACOPR）的兩種演算法。本研究測試文獻標竿例題，並與文獻結果進行比較，驗證本研究演算法所提出的求解績效及結果，且進一步分析動態度對結果的影響。從結果發現本研究所提的ACOPR對於求解動態車輛途程問題具有效果與可行性，未來可以做為物流業者使用。"

In recent years, the real-time information has been applied in fleet management and route assignment. The research topic is changed from static vehicle routing problem (SVRP) to dynamic vehicle routing problem (DVRP), where new orders are received during the working day. The DVRP is concerned with the updating information of customer demand on a rolling horizon so as to minimize the total travelled distance. In this research, three rolling horizon planning strategies are proposed: fixed time interval, fixed number of new arrival, and mixed strategy. We focus on developing the ant colony optimization (ACO) and ant colony optimization with path-relinking (ACOPR) algorithm, to improve both diversity and the capability to escape from local optima. Experiments were conducted by testing the benchmark instances from literatures. In addition, we compared our ACOPR to the existing algorithms in the literature. Furthermore, different degrees of dynamism were tested. The experimental results show that ACOPR is effective and comparable to solve DVRP. Apply path-relinking can further improve the solution quality. Our proposed algorithms could be applied to the logistics provider for their daily operations.