A memetic algorithm for the Multi Trip Vehicle Routing Problem

• A split procedure for the mutli trip vehicle routing problem is proposed.
• A new tailored local search operator is introduced.
• Results outperform previous works with respect to solution quality.

We consider the Multi Trip Vehicle Routing Problem, in which a set of geographically scattered customers have to be served by a fleet of vehicles. Each vehicle can perform several trips during the working day. The objective is to minimize the total travel time while respecting temporal and capacity constraints.The problem is particularly interesting in the city logistics context, where customers are located in city centers. Road and law restrictions favor the use of small capacity vehicles to perform deliveries. This leads to trips much briefer than the working day. A vehicle can then go back to the depot and be re-loaded before starting another service trip.We propose an hybrid genetic algorithm for the problem. Especially, we introduce a new local search operator based on the combination of standard VRP moves and swaps between trips. Our procedure is compared with those in the literature and it outperforms previous algorithms with respect to average solution quality. Moreover, a new feasible solution and many best known solutions are found.