:::

詳目顯示

回上一頁
題名:線上型車輛巡迴路線問題:混合型啟發式演算法之應用
書刊名:運輸學刊
作者:廖彩雲 引用關係王翔正胡大瀛 引用關係
作者(外文):Liao, Tsai-yunWang, Shiang-jengHu, Ta-yin
出版日期:2012
卷期:24:4
頁次:頁497-528
主題關鍵詞:線上型車輛巡迴路線問題混合型啟發式演算法都市物流On-line vehicle routing problemHybrid heuristic algorithmsCity logisticsDynaTAIWAN
原始連結:連回原系統網址new window
相關次數:
  • 被引用次數被引用次數:期刊(0) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:0
  • 共同引用共同引用:1
  • 點閱點閱:157
在實際的運輸系統環境下,都市物流配送(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.
期刊論文
1.梅明德、謝浩明(20010600)。時窗限制動態車輛路線問題之線上型路線建立啟發式解法。運輸學刊,13(2),73-111。new window  延伸查詢new window
其他
1.毛皖亭(2007)。線上動態車輛巡迴路線演算法之發展:滾動平面法之應用。  延伸查詢new window
2.Ball, M. O., Magnanti, T. L., Monma, C. L., and Nemhauser, G. L.(1995)。Network Routing。  new window
3.Barceló, J., Grzybowska, H., and Pardo, S.(2007)。Vehicle Routing and Scheduling Models, Simulation and City Logistics。  new window
4.Fink, I., Krumke, S. O., and Westphal, S.(2009)。New Lower Bounds for Online K-server Routing Problems。  new window
5.Garey, M. and Johnson, D.(1979)。Computers and Intracta-bility: A Guide to the Theory of NP-completeness。  new window
6.Ghiani, G., Guerriero, F., Laporte, G., and Musmanno, R.(2003)。Real-time Vehic1e Routing: Solution Concepts, Algorithms and Parallel Computing Strategies。  new window
7.Glover, F., Kelly, J. P., and Laguna, M.(1995)。Genetic Algorithms and Tabu Search: Hybrids for Optimization。  new window
8.Golden, B., Magnanti, T., and Nguyen, H.(1977)。Implementing Vehic1e Routing Algorithms。  new window
9.Ho, W., Hob, G., Jib, P., and Laub, H.(2008)。A Hybrid Genetic Algorithm for the Multi-depot Vehic1e Routing Problem。  new window
10.Hom, M. E. T.(2006)。On-line Vehic1e Routing and Scheduling with Time-varying Travel Speeds。  new window
11.Jaillet, P. and Wagner, M.(2008)。Online Vehic1e Routing Problems: A Survey。  new window
12.Jeon, G., Leep, H. R., and Shim, J. Y.(2007)。A Vehic1e Routing Problem Solved by Using a Hybrid Genetic Algorithm。  new window
13.Juan, A., Faulin, J., Ruiz, R., Barrios, B., and Caballé, S.(2010)。The SR-GCWS Hybrid Algorithm for Solving the Capacitated Vehic1e Routing Problem。  new window
14.Karlin, A., Manasse, M., Rudolph, L., and Sleator, D.(1988)。Competitive Snoopy Catching。  new window
15.Krumke, S., Paepe, W., Poensgen, D., and Stougie, L.(2003)。News from the Online Traveling Repairman。  new window
16.Lin, S., Lee, Z., Ying, K., and Lee, C.(2009)。Applying Hybrid Meta-heuristics for Capacitated Vehic1e Routing Problem。  new window
17.Ma, W., Dong, D., and Wang, K.(2010)。Competitive Analysis for the On-line Vehic1e Routing Problem。  new window
18.Malandraki, C. and Daskin, M. S.(1992)。Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms。  new window
19.Marinakis, Y., Marinaki, M., and Dounias, G.(2010)。A Hybrid Partic1e Swarm Optimization Algorithm for the Vehic1e Routing Problem。  new window
20.Mauri, G and Lorena, L.(2007)。A New Hybrid Heuristic for Driver Scheduling。  new window
21.Bibeiro, C., Noronha, T., Rocha, C., and Urrutia, S.(2005)。A Heuristic for a Real-life Car Sequencing Problem with Multiple Requirements。  new window
22.Savelessbergh, M.(1985)。Local Search in Routing Problems with Times。  new window
23.Shih, W. and Ou, Y. H.(2007)。The Development of a Web-based System to Solve the Multi-depot Vehicle Routing Problem of Fixed-route Trucking Carriers。  new window
24.SINTEF(2002)。Vehicle Routing and Travelling Salesperson Problems。  new window
25.Solomon, M.(1987)。Algorithms for the Vehic1e Routing and Scheduling Problems with Time Window Constraints。  new window
26.Taniguchi, E., Thompson, R. O., Yamada, T., and van Duin, R.(2001)。City Logistics: Network Modelling and Intelligent Transport Systems。  new window
27.Thangiah, S., Osman, I., and Sun, T.(1994)。Hybrid Genetic Algorithm, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Windows。  new window
28.Ting, C., Li, S., and Lee, C.(2001)。TGA: A New Integrated Approach to Evolutionary Algorithms。  new window
29.Wang, C., and Lu, J.(2009)。A Hybrid Genetic Algorithm that Optimizes Capacitated Vehicle Routing Problems。  new window
圖書論文
1.Christofides, N.、Mingozzi, A.、Toth, P.(1979)。The Vehicle Routing Problem。Combinatorial Optimization。Chichester:Wiley。  new window
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top
QR Code
QRCODE