Skip to Main content Skip to Navigation
Journal articles

Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem

Abstract : The cumulative capacitated vehicle routing problem (CCVRP) is a relatively new version of the classical capacitated vehicle routing problem, and it is equivalent to a traveling repairman problem with capacity constraints and a homogeneous vehicle fleet, which aims to minimize the total arrival time at customers. Many real-world applications can be modeled by this problem, such as the important application resulting from the humanitarian aid following a natural disaster. In this paper, two heuristics are proposed. The first one is a constructive heuristic to generate an initial solution and the second is the skewed variable neighborhood search (SVNS) heuristic. The SVNS algorithm starts with the initial solution. At each iteration, the perturbation phase and the local search phase are used to improve the solution of the CCVRP, and the distance function in acceptance criteria phase is used to improve the exploration of faraway valleys. This algorithm is applied to a set of benchmarks, and the comparison results show that the proposed algorithms provide better solutions than those reported in the previous literature on memetic algorithms and adaptive large neighborhood search heuristics.
Document type :
Journal articles
Complete list of metadata
Contributor : Mylène Delrue Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 8:40:49 AM
Last modification on : Friday, June 17, 2022 - 4:04:08 PM




Noura Smiti, Mohamed Mahjoub Dhiaf, Bassem Jarboui, Said Hanafi. Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem. International Transactions in Operational Research, Wiley, 2020, 27 (1), pp.651-664. ⟨10.1111/itor.12513⟩. ⟨hal-03400354⟩



Record views