Journal
INFORMATION SCIENCES
Volume 478, Issue -, Pages 40-61Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2018.11.006
Keywords
Vehicle routing problem; Prize collecting; Multi-objective optimization; Genetic algorithm; Local search
Categories
Funding
- National Natural Science Foundation of China [51775112, 71801046, 51605406]
- Natural Science Foundation of Guangdong Province [2018A030310029]
- Paul and Heidi Brown Preeminent Professorship at ISE, University of Florida
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available