A new hybrid metaheuristics for the vehicle routing problem with simultaneous pick-up and delivery

The vehicle routing problem with simultaneous pickup and delivery is the problem of optimally integrating goods distribution and waste collection. We analyze the vehicle routing problem in which, a single depot can offer service to many customers that may both receive and send good by multiple vehicles, customers strictly require that their delivery and pickup is to be served in a single visit by a vehicle simultaneously. The objective of the problem is to minimize the total distance to service all customers, each with a single stop, without violating the capacity of each vehicle. Firstly, the revised tour-partitioning algorithm is used to get the initial solution of the vehicle routing problem with simultaneous pick-up and delivery In the reactive tabu search phase, variable neighborhood search modules are also proposed to improve the results. Finally, computational experiments show that the proposed hybrid heuristic is able to obtaining optimal solutions very efficiently.