Large neighborhood search for multi-trip vehicle routing

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

Research output: Contribution to journalArticlepeer-review

26 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 languageEnglish
Pages (from-to)422-441
Number of pages20
JournalEuropean Journal of Operational Research
Volume255
Issue number2
DOIs
Publication statusPublished - 1 Dec 2016

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'Large neighborhood search for multi-trip vehicle routing'. Together they form a unique fingerprint.

Cite this