Local search in two-fold EMO algorithm to enhance solution similarity for multi-objective vehicle routing problems

In this paper, we propose a memetic EMO algorithm that enhances the similarity of two sets of non-dominated solutions. We employ our algorithm in vehicle routing problems (VRPs) where the demand of customers varies. We consider two periods of different demand in a problem that are Normal Demand Period (NDP) and High Demand Period (HDP). In each period, we can find a set of non-dominated solutions with respect to several objectives such as minimizing total cost for delivery, minimizing maximum cost, minimizing the number of vehicles, minimizing total delay to the date of delivery and so on. Although a set of non-dominated solutions can be searched independently in each period, drivers of vehicles prefer to have similar routes in NDP and HDP in order to reduce their fatigue to drive on a different route. In this paper, we propose a local search that enhance the similarity of routes in NDP and HDP. Simulation results show that the proposed memetic EMO algorithm can find a similar set of non-dominated solutions in HDP to the one in NDP.