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

Ant Colony Optimization for the Dynamic Vehicle Routing Problem

陳冠宇(Guan-Yu Chen) ； 丁慶榮(Ching-Jung Ting)

《運輸學刊》 33卷2期 (2021/06) Pp. 135-163

https://doi.org/10.6383/JCIT.202106_33(2).0001

摘要

隨著電子商務的快速發展，以及物流業將資通訊技術運用於營運作業上，使得車輛途程問題（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.

並列關鍵字

Dynamic vehicle routing problem ； Rolling horizon planning ； Ant colony optimization ； Path-relinking ； Degrees of dynamism

參考文獻

陳家和、丁慶榮 (2005)，「應用螞蟻演算法於時窗限制車輛途程問題之研究」，運輸學刊，第十七卷第三期，頁 261-280。

喻奉天、林宗漢、盧宗成 (2001)，「應用蟻群系統求解卡車與拖車途程問題」，運輸學刊，第二十三卷第二期，頁 199-218。

蘇純繒、翁瑞聰 (2004)，「以螞蟻群聚最佳化整合基因演算法求解無資源限制單一指派中位轉接點問題」，運輸學刊，第十六卷第二期，頁 99-114。

Abbatecola, L., Fanti, M. P., and Ukovich, W. (2016), “A Review of New Approaches for Dynamic Vehicle Routing Problem,” In 2016 IEEE International Conference on Automation Science and Engineering, pp. 361-366.

AbdAllah, A. M. F., Essam, D. L., and Sarker, R. A. (2017), “On Solving Periodic Re-optimization Dynamic Vehicle Routing Problems,” Applied Soft Computing, Vol. 55, No.1, pp. 1-12.