Paper Info
Title
A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints
Abstract
This paper introduces a special vehicle routing problem, i.e. the cumulative capacitated vehicle routing problem with time-window constraints (Cum-CVRPTW). The problem can be defined as designing least-cost delivery routes from a depot to a set of geographically-scattered customers, subject to the constraint that each customer has to be served within a time window; accordingly, the objective costs are computed as the sum of arrival times at all the customers. The Cum-CVRPTW finds practical utility in many situations, e.g. the provision of humanitarian aids in the context of natural disasters. The Cum-CVRPTW can be viewed as a combination of two NP-hard problems, i.e. the vehicle routing problem with time windows and the cumulative vehicle routing problem. To effectively address this problem, an effective algorithm is designed, which is based on the frameworks of Large Neighborhood Search Algorithm and hybridizes with Genetic Algorithm. The proposed algorithm adopts a constraint-relaxation scheme to extend the search space, enabling the iterative exploration of both the feasible and infeasible neighborhood solutions of an incumbent solution. Furthermore, some speed-up techniques are designed to reduce the computational complexity. To elucidate its effectiveness, the proposed algorithm is examined on the benchmark instances from the literature. The resultant numerical findings show that the algorithm is able to improve and obtain some best-known solutions found by existing state-of-the-art methods.
Year
DOI
Venue
2019
10.1016/j.asoc.2019.03.008
Applied Soft Computing
Keywords
Field
DocType
Vehicle routing problem,Cumulative,Large neighborhood search algorithm,Genetic algorithm
Mathematical optimization,Vehicle routing problem,Algorithm,Genetic algorithm,Mathematics,Computational complexity theory,Large neighborhood search
Journal
Volume
ISSN
Citations 
80
1568-4946
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Ran Liu1417.64
Z. B. Jiang224236.08