A memetic algorithm for the Multi Trip Vehicle Routing Problem

作者：Cattaruzza Diego^*; Absi Nabil; Feillet Dominique; Vidal Thibaut

来源：European Journal of Operational Research, 2014, 236(3): 833-848.

DOI：10.1016/j.ejor.2013.06.012

• Multi Trip Vehicle Routing Problem
• Memetic algorithm
• City logistics

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.

• 出版日期2014-8-1