線上型車輛巡迴路線問題：混合型啟發式演算法之應用

A Solution Algorithm for On-line Vehicle Routing Problems: A Hybrid Meta-heuristic Algorithm Approach

廖彩雲(Tsai-Yun Liao) ； 王翔正(Shiang-Jeng Wang) ； 胡大瀛(Ta-Yin Hu)

《運輸學刊》 24卷4期 (2012/12) Pp. 497-528

https://doi.org/10.6383/JCIT.201212.0497

摘要

在實際的運輸系統環境下，都市物流配送（city logistics）的靜態車輛巡迴路線問題（Vehicle Routing Problems, VRP）之規劃，已不能滿足多樣化的客戶需求與複雜的交通情況。因此，都市物流配送問題必須考量能反應真實資訊的動態車輛巡迴路線問題。線上型車輛巡迴路線問題（On-line VRP）需考慮運算的效率性與精確性，相關的研究指出巨集啟發式演算法為一種可行的方式。本研究發展一混合型啟發式演算法求解線上型車輛巡迴路線問題，此演算法結合對於求解VRP效果佳的禁制搜尋法與有良好全域搜尋機制的基因演算法。為測試演算法之效能，本研究結合DynaTAIWAN交通模擬指派模式在一真實路網中進行求解實驗與分析。數值分析中以演算法間的比較與演算法內的比較進行分析，演算法間的比較以基因演算法與混合型啟發式演算法進行比較，演算法內的比較考慮演算法的參數對於問題求解的影響。結果顯示此混合型啟發式演算法可在真實路網中求解線上型車輛巡迴路線問題，其效率較基因演算法為佳。

關鍵字

線上型車輛巡迴路線問題 ； 混合型啟發式演算法 ； 都市物流 ； DynaTAIWAN

並列摘要

Due to the dynamic characteristics, traditional vehicle routing problems (VRP) cannot be directly applied under varied customer demand and complicated traffic situations for the logistics industry. Therefore, dynamic vehicle routing algorithms need to be developed to consider real time information for city logistics. On-line VRP problems consider real-lime information and real-lime updating, and efficiency and accuracy are major concerns. Previous researches show that hybrid meta-heuristic approaches might be able to provide efficiency and accuracy simultaneously. This research proposes a hybrid meta-heuristic algorithm based on Tabu Search (TS) and Genetic Algorithm (GA) for solving dynamic VRP for on-line operations, i.e., new requests are revealed on-line. Basically TS with adaptive memory search mechanism could generate good VRP solution and GA provides good global search mechanism. In order to illustrate the proposed algorithm, the hybrid algorithm is numerically experimented in a simulation environment, DynaTAIWAN, for a city network. Within the simulation environment, network characteristics and real-time traffic information can be described. Numerical analyses, including comparisons among different algorithms and sensitivity analysis based on different parameter values, are conducted to illustrate the performance of the proposed algorithm. For the comparisons among different algorithms, the GA algorithm and the hybrid algorithm are compared under the same simulation conditions. In the sensitivity analysis, different parameter values, including the length of candidate list, the elimination cycle, and the mutation rate, are experimented to achieve better performance. The numerical results show that the hybrid heuristic algorithm provides better performance for generating on-line VRP solutions.

並列關鍵字

On-line vehicle routing problem ； Hybrid heuristic algorithms ； City logistics ； DynaTAIWAN

參考文獻

毛皖亭(2007)。線上動態車輛巡迴路線演算法之發展：滾動平面法之應用(碩士論文)。成功大學交通管理科學系。

梅明德、謝浩明(2001)。時窗限制動態車輛路線問題之線上型路線建立啟發式解法。運輸學刊。十三(二)，73-111。

Fisher, M.(ed.)(1995).Handbooks in Operations Research and Management Science.Netherlands:North-Holland.

Barceló, J.,Grzybowska, H.,Pardo, S.(2007).Vehicle Routing and Scheduling Models, Simulation and City Logistics.Operations Research/Computer Science Interfaces Series.38,163-195.

Christofides, N.(ed.)(1979).Combinatorial Optimization.Chichester:Wiley.