Journal
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
Volume 61, Issue 1, Pages 159-187Publisher
SPRINGER
DOI: 10.1007/s10589-014-9713-5
Keywords
Multitrip cumulative capacitated vehicle routing problem; Disaster logistics; Iterated local search; Variable neighborhood descent
Ask authors/readers for more resources
The multitrip cumulative capacitated vehicle routing problem (mt-CCVRP) is a non-trivial extension of the classical CVRP: the goal is to minimize the sum of arrival times at demand nodes and each vehicle may perform several trips. Applications of this NP-hard problem can be found in disaster logistics and maintenance operations. Contrary to the CVRP, the cost of a solution varies if a trip is reversed or if its rank in a multitrip is changed. Moreover, evaluating local search moves in constant time is not obvious. This article presents a mixed integer linear program (MILP), a dominance rule, and a hybrid metaheuristic: a multi-start iterated local search (MS-ILS) calling a variable neighborhood descent with move evaluations. On three sets of instances, MS-ILS obtains good solutions, not only on the mt-CCVRP, but also on the cumulative CVRP where it competes with four existing algorithms. Moreover, the metaheuristic retrieves the optimal solutions of the MILP, which can be computed for small instances using a commercial solver.
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