文章詳目資料

運輸學刊 TSSCI

  • 加入收藏
  • 下載文章
篇名 線上型車輛巡迴路線問題:混合型啟發式演算法之應用
卷期 24:4
並列篇名 A Solution Algorithm for On-line Vehicle Routing Problems: A Hybrid Meta-heuristic Algorithm Approach
作者 廖彩雲王翔正胡大瀛
頁次 497-528
關鍵字 線上型車輛巡迴路線問題混合型啟發式演算法都市物流DynaTAIWANOn-line vehicle routing problemHybrid heuristic algorithmsCity logisticsDynaTAIWANTSSCI
出刊日期 201212

中文摘要

在實際的運輸系統環境下,都市物流配送 (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-time information and real-time 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 environmen , 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.

相關文獻