A Local Search-Based Multiobjective Optimization Algorithm for Multiobjective Vehicle Routing Problem With Time Windows

Vehicle routing problem with time windows (VRPTW) is an important logistics problem, which appears to be multiobjective in real world. Recently, a general multiobjective VRPTW (MOVRPTW) with five objectives has been defined, and a set of MOVRPTW problem instances based on data from real world have been proposed. These instances indicate more truly multiobjective nature and represent more realistic and challenging MOVRPTW cases. In this paper, a local search-based multiobjective optimization algorithm is proposed for the real-world MOVRPTW instances. Considering the problem structure of MOVRPTW, we design different local search methods for different objectives. These simple but effective local search methods cooperate to optimize different objectives simultaneously. More problem-specific knowledge can be extracted by using objective-wise local search components, and thus, high-quality solutions are expected to be generated. The proposed algorithm is tested on 45 realistic and challenging MOVRPTW benchmark instances from real world. Experimental results show that the proposed algorithm can obtain better solutions than the previous evolutionary algorithm-based multiobjective algorithm on new MOVRPTW cases. Additional results on 56 Solomon instances show the stability of the proposed algorithm across data sets.