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