Improving neighborhood exploration into MOEA/D framework to solve a bi-objective routing problem

Local search (LS) algorithms are efficient metaheuristics to solve combinatorial problems. The performance of LS highly depends on the neighborhood exploration of solutions. Many methods have been developed over the years to improve the efficiency of LS on different problems of operations research. In particular, the exploration strategy of the neighborhood and the exclusion of irrelevant neighboring solutions are design mechanisms that have to be carefully considered when tackling NP-hard optimization problems. An MOEA/D framework including an LS-based mutation and knowledge discovery mechanisms is the core algorithm used to solve a bi-objective vehicle routing problem with time windows (bVRPTW) where the total traveling cost and the total waiting time of drivers have to be minimized. We enhance the classical LS exploration strategy of the neighborhood from the literature of scheduling and propose new metrics based on customer distances and waiting times to reduce the neighborhood size. We conduct a deep analysis of the parameters to give a fine tuning of the MOEA/D framework adapted to the LS variants and to the bVRPTW. Experiments show that the proposed neighborhood strategies lead to better performance on both Solomon's and Gehring and Homberger's benchmarks.