A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows

A two-stage hybrid meta-heuristic for pickup and delivery vehiclerouting problem with time windows and multiple vehicles isconsidered in this paper. The first stage uses simulated annealingalgorithm to decrease the number of used vehicles, the second stageuses tabu search to decrease the total travel cost. Experimentalresults show the effectiveness of the algorithm which has producedmany new best solutions on problems within 600 customers. Inparticular, it has improved 45% and 81.7% of the best solutions onthe 200 and 600-customer benchmarks, sometimes by as much as 3vehicles. These results further confirm the benefits of two-stageapproaches in vehicle routing problems.