A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem - Archive ouverte HAL Access content directly
Journal Articles Computational Optimization and Applications Year : 2015

A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem

(1) , (1) , (1)
1

Abstract

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 O(1) 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.

Dates and versions

hal-02478659 , version 1 (14-02-2020)

Identifiers

Cite

Juan Carlos Rivera, Hasan Murat Afsar, Christian Prins. A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem. Computational Optimization and Applications, 2015, 61 (1), pp.159-187. ⟨10.1007/s10589-014-9713-5⟩. ⟨hal-02478659⟩

Collections

CNRS UTT LOSI
10 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More