Solving Multi-Objective Vehicle Routing Problems with Time Windows: A Decomposition-Based Multiform Optimization Approach

In solving multi-objective vehicle routing problems with time windows (MOVRPTW), most existing algorithms focus on the optimization of a single problem formulation. However, little effort has been devoted to exploiting valuable knowledge from the alternate formulations of MOVRPTW for better optimization performance. Aiming at this insufficiency, this study proposes a decomposition-based multi-objective multiform evolutionary algorithm (MMFEA/D), which performs the evolutionary search on multiple alternate formulations of MOVRPTW simultaneously to complement each other. In particular, the main characteristics of MMFEA/D are three folds. First, a multiform construction (MFC) strategy is adopted to construct multiple alternate formulations, each of which is formulated by grouping several adjacent subproblems based on the decomposition of MOVRPTW. Second, a transfer reproduction (TFR) mechanism is designed to generate offspring for each formulation via transferring promising solutions from other formulations, making that the useful traits captured from different formulations can be shared and leveraged to guide the evolutionary search. Third, an adaptive local search (ALS) strategy is developed to invest search effort on different alternate formulations as per their usefulness for MOVRPTW, thus facilitating the efficient allocation of computational resources. Experimental studies have demonstrated the superior performance of MMFEA/D on the classical Solomon instances and the real-world instances.