Large neighborhood search for multi-trip vehicle routing

Véronique François; Yasemin Arda; Yves Crama; Gilbert Laporte

doi:10.1016/j.ejor.2016.04.065

Large neighborhood search for multi-trip vehicle routing

Véronique François, Yasemin Arda, Yves Crama, Gilbert Laporte

Research output: Contribution to journal › Article › peer-review

60 Citations (SciVal)

Abstract

We consider the multi-trip vehicle routing problem, in which each vehicle can perform several routes during the same working shift to serve a set of customers. The problem arises when customers are close to each other or when their demands are large. A common approach consists of solving this problem by combining vehicle routing heuristics with bin packing routines in order to assign routes to vehicles. We compare this approach with a heuristic that makes use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. Two large neighborhood search heuristics are proposed to perform the comparison. We provide insights into the configuration of the proposed algorithms by analyzing the behavior of several of their components. In particular, we question the impact of the roulette wheel mechanism. We also observe that guiding the search with an objective function designed for the multi-trip case is crucial even when exploring the solution space of the vehicle routing problem. We provide several best known solutions for benchmark instances.

Original language	English
Pages (from-to)	422-441
Number of pages	20
Journal	European Journal of Operational Research
Volume	255
Issue number	2
DOIs	https://doi.org/10.1016/j.ejor.2016.04.065
Publication status	Published - 1 Dec 2016

Funding

This work has benefited from several discussions with the Institut de Recherches Interdisciplinaires et de Développements en Intelligence Artificielle (IRIDIA), and in particular with Franco Mascia who granted support with irace . Computational resources were provided by the Consortium des Equipements de Calcul Intensif (CECI), funded by the Fonds de la Recherche Scientifique de Belgique (F.R.S.-FNRS) under Grant no. 2.5020.11 . The project leading to these results was partially supported by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office , Grant P7/36 . Gilbert Laporte was funded by the Canadian National Sciences and Engineering Research Council under Grant 2015–06189 . Thanks are due to the referees for their valuable comments.

Keywords

Automatic algorithm configuration
Large neighborhood search
Multi-trip
Transportation
Vehicle routing

ASJC Scopus subject areas

General Computer Science
Modelling and Simulation
Management Science and Operations Research
Information Systems and Management

Access to Document

10.1016/j.ejor.2016.04.065

Cite this

@article{968389b6e4cd4770b2e82eb7d87fdf2d,

title = "Large neighborhood search for multi-trip vehicle routing",

abstract = "We consider the multi-trip vehicle routing problem, in which each vehicle can perform several routes during the same working shift to serve a set of customers. The problem arises when customers are close to each other or when their demands are large. A common approach consists of solving this problem by combining vehicle routing heuristics with bin packing routines in order to assign routes to vehicles. We compare this approach with a heuristic that makes use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. Two large neighborhood search heuristics are proposed to perform the comparison. We provide insights into the configuration of the proposed algorithms by analyzing the behavior of several of their components. In particular, we question the impact of the roulette wheel mechanism. We also observe that guiding the search with an objective function designed for the multi-trip case is crucial even when exploring the solution space of the vehicle routing problem. We provide several best known solutions for benchmark instances.",

keywords = "Automatic algorithm configuration, Large neighborhood search, Multi-trip, Transportation, Vehicle routing",

author = "V{\'e}ronique Fran{\c c}ois and Yasemin Arda and Yves Crama and Gilbert Laporte",

year = "2016",

month = dec,

day = "1",

doi = "10.1016/j.ejor.2016.04.065",

language = "English",

volume = "255",

pages = "422--441",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Large neighborhood search for multi-trip vehicle routing

AU - François, Véronique

AU - Arda, Yasemin

AU - Crama, Yves

AU - Laporte, Gilbert

PY - 2016/12/1

Y1 - 2016/12/1

N2 - We consider the multi-trip vehicle routing problem, in which each vehicle can perform several routes during the same working shift to serve a set of customers. The problem arises when customers are close to each other or when their demands are large. A common approach consists of solving this problem by combining vehicle routing heuristics with bin packing routines in order to assign routes to vehicles. We compare this approach with a heuristic that makes use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. Two large neighborhood search heuristics are proposed to perform the comparison. We provide insights into the configuration of the proposed algorithms by analyzing the behavior of several of their components. In particular, we question the impact of the roulette wheel mechanism. We also observe that guiding the search with an objective function designed for the multi-trip case is crucial even when exploring the solution space of the vehicle routing problem. We provide several best known solutions for benchmark instances.

AB - We consider the multi-trip vehicle routing problem, in which each vehicle can perform several routes during the same working shift to serve a set of customers. The problem arises when customers are close to each other or when their demands are large. A common approach consists of solving this problem by combining vehicle routing heuristics with bin packing routines in order to assign routes to vehicles. We compare this approach with a heuristic that makes use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. Two large neighborhood search heuristics are proposed to perform the comparison. We provide insights into the configuration of the proposed algorithms by analyzing the behavior of several of their components. In particular, we question the impact of the roulette wheel mechanism. We also observe that guiding the search with an objective function designed for the multi-trip case is crucial even when exploring the solution space of the vehicle routing problem. We provide several best known solutions for benchmark instances.

KW - Automatic algorithm configuration

KW - Large neighborhood search

KW - Multi-trip

KW - Transportation

KW - Vehicle routing

UR - http://www.scopus.com/inward/record.url?scp=84969924840&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2016.04.065

DO - 10.1016/j.ejor.2016.04.065

M3 - Article

AN - SCOPUS:84969924840

SN - 0377-2217

VL - 255

SP - 422

EP - 441

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

Large neighborhood search for multi-trip vehicle routing

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this