A biased-randomised large neighbourhood search for the two-dimensional vehicle routing problem with backhauls

Oscar Dominguez, Daniel Guimarans, Angel A. Juan, Ignacio de la Nuez

Research output: Contribution to journalArticleResearchpeer-review

48 Citations (Scopus)

Abstract

The two-dimensional loading vehicle routing problem with clustered backhauls (2L-VRPB) is a realistic extension of the classical vehicle routing problem where both delivery and pickup demands are composed of non-stackable items. Despite the fact that the 2L-VRPB can be frequently found in real-life transportation activities, it has not been analysed so far in the literature. This paper presents a hybrid algorithm that integrates biased-randomised versions of vehicle routing and packing heuristics within a Large Neighbourhood Search metaheuristic framework. The use of biased randomisation techniques allows to better guide the local search process. The proposed approach for solving the 2L-VRPB is tested on an extensive set of instances, which have been adapted from existing benchmarks for the two-dimensional loading vehicle routing problem (2L-VRP). Additionally, when no backhauls are considered our algorithm is able to find new best solutions for several 2L-VRP benchmark instances with sequential oriented loading, both with and without items rotation.

Original languageEnglish
Pages (from-to)442-462
Number of pages21
JournalEuropean Journal of Operational Research
Volume255
Issue number2
DOIs
Publication statusPublished - 2016
Externally publishedYes

Keywords

  • Metaheuristics
  • Packing
  • Routing
  • Transportation
  • Vehicle routing problem

Cite this