蟻群最佳化演算法於時窗限制之車輛途程問題的研究

A Study of Ant Colony Optimization on Vehicle Routing Problem with Time Window

高秀梅(Hsiu-Mei Kao)

指導教授 ： 梁韵嘉

元智大學/工程學院/工業工程與管理學系/碩士(2003年)

摘要

蟻群最佳化演算法於時窗限制之車輛途程問題的研究
學生：高秀梅 指導教授：梁韵嘉 博士
元智大學工業工程與管理研究所
摘要
物流配送系統中，物流中心必須在最適當的時間內將正確數量的產品運送到正確的地點以滿足顧客的需求。但隨著客製化需求愈來愈受重視，顧客對於貨品交期時間之要求也愈嚴苛，因此在車輛途程問題中導入時窗因子，即VRPTW(Vehicle Routing Problem with Time Window)，將使得車輛途程問題之應用更符合實際需要。
車輛途程問題之求解複雜度很高，屬於NP-Hard問題，以傳統數學模式求解時，須花費冗長的運算時間，因此為了于合理計算時間內獲得理想的解，啟發式方法便成為一較可行之途徑。基於此特性，本研究針對硬性時窗之VRPTW問題，建構蟻群最佳化演算法(ACO)為解題架構，將影響演算成效的因子作測試與分析，例如費洛蒙起始濃度( τ0 )、螞蟻數( N )、局部啟發式函數( η )、區域改善、區域更新、全域更新、以及ACO參數，其中又包括規則決定參數 (q0)、費洛蒙殘留比例(ρ)、及參數α與β等，並透過Solomon(1987)標準題庫的六類題型進行測試與驗證，測試50及100個顧客點之測試結果，以C類的表現為最好，其中在50個顧客點的題型中，又以R112及RC104的表現最佳，與文獻最佳解的距離誤差僅有0.04﹪及0.00﹪；而100個顧客點的題型中，則以R211及RC202的表現較文獻最佳解好，改善率達9.22﹪及5.5﹪。
關鍵字：時窗限制車輛途程問題、蟻群最佳化演算法

關鍵字

時窗限制車輛途程問題 ； 蟻群最佳化演算法

並列摘要

A Study of Ant Colony Optimization on Vehicle Routing Problem with Time Window
Student： Hsiu-Mei Kao Advisors：Dr. Yun-Chia Liang
Department of Industrial Engineering and Management
YUAN-ZE University
ABSTRACT
In a logistic distribution system, the right amount of products has to be shipped to the right place from the depot to meet customers’ needs. With customized requirement being valued more, customers are more demanding on merchandise’s on-time delivery. Thus, in order to meet practical needs, time window constraint is considered in this research and, therefore, the focus of this research is VRPTW (Vehicle Routing Problem with Time Window).
Solving vehicle routing problems involves with high complexity. Since the VRPTW is a NP-Hard problem, traditional mathematical programming approach needs lengthy computational time to find the optimal solution. In order to obtain good solutions within acceptable computing time in practice, metaheuristics becomes a better option. In this research, we employ one of metaheuristics - Ant Colony Optimization (ACO) — for VRPTW problem. To investigate the characteristic of ACO on VRPTW, a thorough parameter design are conducted, and then the optimal parameter and algorithm structure is suggested. Based on 56 benchmark problems by Solomon, we test and verify all six categories and test different customer sizes including 50 and 100. The result shows that in C category problem ACO performs the best. In addition, in two of 50-customer problems, R112 and RC104, the proposed algorithm provides the best percentage deviation from the best solution in the literature that is 0.04% and 0.00%, respectively. In two of 100-customer problems, R211 and RC202, ACO improves the known best results in the literature by 9.22% and 5.5%, respectively.
Keywords: Vehicle Routing Problem with Time Window, Ant Colony Optimization.

並列關鍵字

Vehicle Routing Problem with Time Window ； Ant Colony Optimization

參考文獻

陳百傑，「以啟發式演算法求解時窗限制車輛途程問題」，中原大學工業工程研究所，碩士論文，2002.

陳契伸，「硬性/軟性時窗限制之車輛途程問題研究」，中原大學工業工程研究所，碩士論文，2001.

韓復華、楊智凱、卓裕仁，「應用門檻接受法求解車輛路線問題之研究」，運輸計劃季刊，第26卷，第二期，253-280，1998.

曾維豪，「軟性時間與回程撿收之車輛途程問題」，元智大學工業工程與管理研究所，碩士論文，2000.

顏成佑，「基因演算法解算軟性時窗車輛途程問題之研究」，元智大學工業工程研究所，碩士論文，2000.