Computer Science ›› 2015, Vol. 42 ›› Issue (4): 230-234.doi: 10.11896/j.issn.1002-137X.2015.04.047

Previous Articles     Next Articles

Hybrid Tabu Search Algorithm for Solving Incident Vehicle Routing Problem

CAI Yan-guang, TANG Ya-lian and ZHU Jun   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Considering these factors that vehicles have the departure time limit and road conditions affect the transportation cost,etc,we established the incident vehicle routing problem (IVRP) mathematical model based on clients’ soft time windows,depots’ time windows,heterogeneous vehicles,road conditions constraints,etc.Making full use of the advantages of genetic algorithm (GA) and tabu search (TS),hybrid tabu search algorithm (HTSA) was constructed.Search space was increased by constructing multiple initial solutions,and two kinds of tabu list:local tabu list and global tabu list were designed,which not only can speed up the optimization,but also can get rid of the reliance on initial solution.Adjusting the tabu list length adaptively can avoid premature convergence,extracting core routes is conducive to late optimization and the relocate operator can reduce route number.Experiments show that IVRP is superior to the general VRP,which can save cost greatly.Moreover,HTSA is better than GA and TS in convergence speed and optimal results,and the stability of HTSA is better by comparing the standard deviation of total cost,total distance and convergence time.

Key words: Incident vehicle routing problem,Tabu search,Genetic algorithm,Core route,Adaptive crossover,Chaotic mutation

[1] Reed M,Yiannakou A,Evering R.An ant colony algorithm for the multi-compartment vehicle routing problem[J].Applied Soft Computing,2014,15:169-176
[2] Azi N,Gendreau M,Potvin J Y.An adaptive large neighborhood search for a vehicle routing problem with multiple routes[J].Computers & Operations Research,2014,41:167-173
[3] Michallet J,Prins C,Amodeo L,et al.Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services[J].Computers & Operations Research,2014,41:196-207
[4] Archetti C,Guastaroba G,Speranza M G.An ILP-refined tabu search for the directed profitable rural postman problem [J].Discrete Applied Mathematics,2014,163:3-16
[5] Gómez J R,Pacheco J,Gonzalo-Orden H.A Tabu Search Methodfor a Bi-Objective Urban Waste Collection Problem[J].Compu-ter-Aided Civil and Infrastructure Engineering,2013,30(1):1-18
[6] Cai Y,Zhang Z,Guo S,et al.A tree-based tabu search algorithm for the manpower allocation problem with time windows and job-teaming constraints[C]∥Proceedings of the Twenty-Third international joint conference on Artificial Intelligence.AAAI Press,2013:496-502
[7] Jia H,Li Y,Dong B,et al.An Improved Tabu Search Approach to Vehicle Routing Problem[J].Procedia-Social and Behavioral Sciences,2013,96:1208-1217
[8] 朱玲玲,杨爱琴,吴宽仁.基于协同自适应禁忌的多时窗VRP算法实现[J].计算机应用研究,2012,29(12):4542-4545
[9] Nguyen P K,Crainic T G,Toulouse M.A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows [J].European Journal of Operational Research,2013,231(1):43-56
[10] Tarantilis C D.Adaptive multi-restart Tabu Search algorithmfor the vehicle routing problem with cross-docking [J].Optimization letters,2013,7(7):1583-1596
[11] Jair J,Paternina-Arboleda C D,Cantillo V,et al.A two-pheromone trail ant colony system—tabu search approach for the he-terogeneous vehicle routing problem with time windows and multiple products[J].Journal of Heuristics,2013,19(2):233-252
[12] 余明珠,李建斌,雷东.装卸一体化的车辆路径问题及基于插入法的新禁忌算法[J].中国管理科学,2010,18(4):89-95
[13] 胡大伟,陈诚.遗传算法 (GA) 和禁忌搜索算法 (TS) 在配送中心选址和路线问题中的应用[J].系统工程理论与实践,2007,27(9):171-176
[14] 郎茂祥,胡思继.车辆路径问题的禁忌搜索算法研究[J].管理工程学报,2004,18(1):81-84
[15] 邵春福,熊志华,姚智胜.道路网短时交通需求预测理论、方法及应用[M].北京:清华大学出版社,2011
[16] 钟石泉.物流配送车辆路径优化方法研究[D].天津:天津大学,2007
[17] 汤雅连,蔡延光,赵学才.关联物流运输调度问题的改进遗传算法[J].微型机与应用,2012,31(17):69-71
[18] 张建林.MATLAB&Excel 定量预测与决策-运作案例精编[M].北京:电子工业出版社,2012
[19] Gendreau M,Hertz A,Laporte G.New insertion and postoptimization procedures for the traveling salesman problem[J].Ope-rations Research,1992,40(6):1086-1094

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!