A hybrid multi-objective genetic local search algorithm for the prize-collecting vehicle routing problem

This paper studies the prize-collecting vehicle routing problem (PCVRP), which is a new variant of the vehicle routing problem. In the PCVRP, besides the vehicle assignment and visiting sequencing, customer selection also must be determined because the available vehicles are insufficient to visit all the customers. Two types of PCVRP are often encountered in the real world, namely the PCVRP in which the number of vehicles is predetermined (PCVRP-P) and that in which the number of vehicles is not predetermined (PCVRP-NP). In general, multiple optimization objectives are required to be considered in both the PCVRP-P and PCVRP-NP. Unlike the commonly used weighted-sum method, a Pareto-based evolutionary algorithm featuring a genetic algorithm combined with a local search strategy (denoted as HGLS) is proposed for solving the multi-objective PCVRP-P. Subsequently, based on the proposed HGLS, a decomposition strategy is designed to solve the multi-objective PCVRP-NP problem by decomposing it into multiple PCVRP-P problems. In order to determine the number of PCVRP-P problems in the decomposition strategy, a vehicle-number range determination approach is proposed to obtain a tight upper bound and lower bound of the number of vehicles. The superiority of the proposed algorithm is demonstrated by conducting several experiments on the benchmark problems. (C) 2018 Elsevier Inc. All rights reserved.