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

Citations Over TimeTop 10% of 2023 papers

Abstract

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.

Related Papers

• → Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints(2011)455 cited
• → Emerging Research Fields in Vehicle Routing Problem: A Short Review(2022)29 cited
• → A Contemporary Recapitulation of Major Findings on Vehicle Routing Problems : Models and Methodologies(2019)5 cited
• → Applying Simulated Annealing Approach for Capacitated Vehicle Routing Problems(2006)14 cited
• → The vehicle routing problem with Time Window and Stochastic Demands(VRPTW-SD): Review(2020)4 cited