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

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

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