A Memetic Algorithm for an External Depot Production Routing Problem

Abstract

This study aims to compare the results of a memetic algorithm with those of the two-phase decomposition heuristic on the external depot production routing problem in a supply chain. We have modified the classical scheme of a genetic algorithm by replacing the mutation operator by three local search algorithms. The first local search consists in exchanging two customers visited the same day. The second consists in trying an exchange between two customers visited at consecutive periods and the third consists in removing a customer from his current tour for a better insertion in any tour of the same period. The tests that were carried out on 128 instances of the literature have highlighted the effectiveness of the memetic algorithm developed in this work compared to the two-phase decomposition heuristic. This is reflected by the fact that the results obtained by the memetic algorithm lead to a reduction in the overall average cost of production, inventory, and transport, ranging from 3.65% to 16.73% with an overall rate of 11.07% with regard to the results obtained with the two-phase decomposition heuristic. The outcomes will be beneficial to researchers and supply chain managers in the choice and development of heuristics and metaheuristics for the resolution of production routing problem.

Keywords

• supply chain
• production
• distribution
• memetic algorithm
• decomposition heuristic