Memetic algorithm for a multi-objective vehicle routing problem with multiple trips

This paper considers a variant of the vehicle routing problem where vehicles are allowed to take more than one route during the working day. A restricted fleet size is used in order to serve customers' demand. Therefore, vehicles could exceed the time horizon. The objective is to optimize both maximum overtime and routing cost. A mathematical model has been proposed for the VRPM. A memetic algorithm has been developed to solve it by combining a genetic algorithm based on suitable encoding and genetic operators, with a local search procedure. The algorithm is run over a benchmark of the VRPM. Comparing with seven existing algorithms, our approach shows competitive performance and contributes many new best solutions. © Technomathematics Research Foundation.