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

• Date: 01 January 2020
• Author: Bassem Jarboui,Noura Smiti,Saïd Hanafi,Mohamed Mahjoub Dhiaf
• Published date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12513

Intl. Trans. in Op. Res. 27 (2020) 651–664

DOI: 10.1111/itor.12513

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Skewed general variable neighborhood search

for the cumulative capacitated vehicle routing problem

Noura Smitia, Mohamed Mahjoub Dhiafb, Bassem Jarbouiband Sa¨

ıd Hanafic

aMODILS, Facult´

e des Sciences Economiques et de Gestion, Universit´

e de Sfax, Sfax, Tunisia

bEmirates College of Technology, Sheikh Hamdan Street, Abu Dhabi, UAE

cLAMIH UMR CNRS 8201, Universit´

e de Valenciennes,Famars, France

E-mail: smiti_noura@hotmail.fr [Smiti]; dhiafmohamed@yahoo.fr [Dhiaf]; bassem_jarboui@yahoo.fr [Jarboui];

said.hanafi@univ-valenciennes.fr [Hanafi]

Received 5 February2017; received in revised form 29 November 2017; accepted 30 December 2017

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, whichaims to minimiz e the total arrivaltime at customers. Many

real-world applicationscan 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 generatean 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 appliedto

a set of benchmarks, and the comparison results show that the proposed algorithms provide better solutions

than those reported in the previous literatureon memetic algorithms and adaptive large neighborhood search

heuristics.

Keywords:cumulative objective; neighborhood structures; variableneighborhood descent; skewed variable neighborhood

search

1. Introduction

The cumulativecapacitated vehicle routing problem(CCVRP) is a variant of the classical capacitated

vehicle routing problem (CVRP). Its objective is to minimize the sum of arrival times at customers

instead of the total routing time, subject to vehicle capacity constraints. More specifically, the

CCVRP is defined on a graph G=(V,A), where V={0, 1, . . . , n} denotes the vertex set, 0

represents the depot, V=V−{0} represents the set of customers, and A={(i,j): i,jࢠV,i<j}is

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.