A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times

Daniel Guimarans, Oscar Dominguez, Javier Panadero, Angel A. Juan

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

The two-dimensional vehicle routing problem (2L-VRP) is a realistic extension of the classical vehicle routing problem in which customers’ demands are composed by sets of non-stackable items. Examples can be found in real-life applications such as the transportation of furniture or industrial machinery. Often, it is necessary to consider stochastic travel times due to traffic conditions or customers availability. However, there is a lack of works discussing stochastic versions of the 2L-VRP. This paper offers a model of the 2L-VRP with stochastic travel times that also includes penalty costs generated by overtime. To solve this stochastic and non-smooth version of the 2L-VRP, a hybrid simheuristic algorithm is proposed. Our approach combines Monte Carlo simulation, an iterated local search framework, and biased-randomised routing and packing heuristics. Our algorithm is tested on an extensive benchmark, which extends the deterministic one for the 2L-VRP with unrestricted and non-oriented loading.

Original languageEnglish
Pages (from-to)1-14
Number of pages14
JournalSimulation Modelling Practice and Theory
Volume89
DOIs
Publication statusPublished - 2018
Externally publishedYes

Keywords

  • Biased-randomised heuristics
  • Packing problem
  • Simheuristics
  • Simulation-optimisation
  • Transportation
  • Vehicle routing problem

Cite this

@article{94c6f9233b63488f8d87e36fc5c1a455,
title = "A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times",
abstract = "The two-dimensional vehicle routing problem (2L-VRP) is a realistic extension of the classical vehicle routing problem in which customers’ demands are composed by sets of non-stackable items. Examples can be found in real-life applications such as the transportation of furniture or industrial machinery. Often, it is necessary to consider stochastic travel times due to traffic conditions or customers availability. However, there is a lack of works discussing stochastic versions of the 2L-VRP. This paper offers a model of the 2L-VRP with stochastic travel times that also includes penalty costs generated by overtime. To solve this stochastic and non-smooth version of the 2L-VRP, a hybrid simheuristic algorithm is proposed. Our approach combines Monte Carlo simulation, an iterated local search framework, and biased-randomised routing and packing heuristics. Our algorithm is tested on an extensive benchmark, which extends the deterministic one for the 2L-VRP with unrestricted and non-oriented loading.",
keywords = "Biased-randomised heuristics, Packing problem, Simheuristics, Simulation-optimisation, Transportation, Vehicle routing problem",
author = "Daniel Guimarans and Oscar Dominguez and Javier Panadero and Juan, {Angel A.}",
year = "2018",
doi = "10.1016/j.simpat.2018.09.004",
language = "English",
volume = "89",
pages = "1--14",
journal = "Simulation Modelling Practice and Theory",
issn = "1569-190X",
publisher = "Elsevier",

}

A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times. / Guimarans, Daniel; Dominguez, Oscar; Panadero, Javier; Juan, Angel A.

In: Simulation Modelling Practice and Theory, Vol. 89, 2018, p. 1-14.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times

AU - Guimarans, Daniel

AU - Dominguez, Oscar

AU - Panadero, Javier

AU - Juan, Angel A.

PY - 2018

Y1 - 2018

N2 - The two-dimensional vehicle routing problem (2L-VRP) is a realistic extension of the classical vehicle routing problem in which customers’ demands are composed by sets of non-stackable items. Examples can be found in real-life applications such as the transportation of furniture or industrial machinery. Often, it is necessary to consider stochastic travel times due to traffic conditions or customers availability. However, there is a lack of works discussing stochastic versions of the 2L-VRP. This paper offers a model of the 2L-VRP with stochastic travel times that also includes penalty costs generated by overtime. To solve this stochastic and non-smooth version of the 2L-VRP, a hybrid simheuristic algorithm is proposed. Our approach combines Monte Carlo simulation, an iterated local search framework, and biased-randomised routing and packing heuristics. Our algorithm is tested on an extensive benchmark, which extends the deterministic one for the 2L-VRP with unrestricted and non-oriented loading.

AB - The two-dimensional vehicle routing problem (2L-VRP) is a realistic extension of the classical vehicle routing problem in which customers’ demands are composed by sets of non-stackable items. Examples can be found in real-life applications such as the transportation of furniture or industrial machinery. Often, it is necessary to consider stochastic travel times due to traffic conditions or customers availability. However, there is a lack of works discussing stochastic versions of the 2L-VRP. This paper offers a model of the 2L-VRP with stochastic travel times that also includes penalty costs generated by overtime. To solve this stochastic and non-smooth version of the 2L-VRP, a hybrid simheuristic algorithm is proposed. Our approach combines Monte Carlo simulation, an iterated local search framework, and biased-randomised routing and packing heuristics. Our algorithm is tested on an extensive benchmark, which extends the deterministic one for the 2L-VRP with unrestricted and non-oriented loading.

KW - Biased-randomised heuristics

KW - Packing problem

KW - Simheuristics

KW - Simulation-optimisation

KW - Transportation

KW - Vehicle routing problem

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

U2 - 10.1016/j.simpat.2018.09.004

DO - 10.1016/j.simpat.2018.09.004

M3 - Article

VL - 89

SP - 1

EP - 14

JO - Simulation Modelling Practice and Theory

JF - Simulation Modelling Practice and Theory

SN - 1569-190X

ER -