Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers

Prasanna Balaprakash; Mauro Birattari; Thomas Stützle; Marco Dorigo

doi:10.1007/s10589-014-9719-z

Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers

Prasanna Balaprakash, Mauro Birattari, Thomas Stützle, Marco Dorigo

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

20 Scopus citations

Abstract

The vehicle routing problem with stochastic demands and customers (VRPSDC) requires finding the optimal route for a capacitated vehicle that delivers goods to a set of customers, where each customer has a fixed probability of requiring being visited and a stochastic demand. For large instances, the evaluation of the cost function is a primary bottleneck when searching for high quality solutions within a limited computation time. We tackle this issue by using an empirical estimation approach. Moreover, we adopt a recently developed state-of-the-art iterative improvement algorithm for the closely related probabilistic traveling salesman problem. We integrate these two components into several metaheuristics and we show that they outperform substantially the current best algorithm for this problem.

Original language	English
Article number	9719
Pages (from-to)	463-487
Number of pages	25
Journal	Computational Optimization and Applications
Volume	61
Issue number	2
DOIs	https://doi.org/10.1007/s10589-014-9719-z
State	Published - Dec 13 2015
Externally published	Yes

Funding

This research has been supported by \u201CE-SWARM \u2013 Engineering Swarm Intelligence Systems\u201D, an European Research Council Advanced Grant awarded to Marco Dorigo (Grant Number 246939). The authors acknowledge support from the Fonds de la Recherche Scientifique, F.R.S.-FNRS of the French Community of Belgium.

Keywords

Empirical estimation
Metaheuristics
Vehicle routing with stochastic demands and customers

Access to Document

10.1007/s10589-014-9719-z

Cite this

@article{a49d1e527c934047aa34b76a3f17bacc,

title = "Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers",

abstract = "The vehicle routing problem with stochastic demands and customers (VRPSDC) requires finding the optimal route for a capacitated vehicle that delivers goods to a set of customers, where each customer has a fixed probability of requiring being visited and a stochastic demand. For large instances, the evaluation of the cost function is a primary bottleneck when searching for high quality solutions within a limited computation time. We tackle this issue by using an empirical estimation approach. Moreover, we adopt a recently developed state-of-the-art iterative improvement algorithm for the closely related probabilistic traveling salesman problem. We integrate these two components into several metaheuristics and we show that they outperform substantially the current best algorithm for this problem.",

keywords = "Empirical estimation, Metaheuristics, Vehicle routing with stochastic demands and customers",

author = "Prasanna Balaprakash and Mauro Birattari and Thomas St{\"u}tzle and Marco Dorigo",

note = "Publisher Copyright: {\textcopyright} 2014, Springer Science+Business Media New York.",

year = "2015",

month = dec,

day = "13",

doi = "10.1007/s10589-014-9719-z",

language = "English",

volume = "61",

pages = "463--487",

journal = "Computational Optimization and Applications",

issn = "0926-6003",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers

AU - Balaprakash, Prasanna

AU - Birattari, Mauro

AU - Stützle, Thomas

AU - Dorigo, Marco

PY - 2015/12/13

Y1 - 2015/12/13

N2 - The vehicle routing problem with stochastic demands and customers (VRPSDC) requires finding the optimal route for a capacitated vehicle that delivers goods to a set of customers, where each customer has a fixed probability of requiring being visited and a stochastic demand. For large instances, the evaluation of the cost function is a primary bottleneck when searching for high quality solutions within a limited computation time. We tackle this issue by using an empirical estimation approach. Moreover, we adopt a recently developed state-of-the-art iterative improvement algorithm for the closely related probabilistic traveling salesman problem. We integrate these two components into several metaheuristics and we show that they outperform substantially the current best algorithm for this problem.

AB - The vehicle routing problem with stochastic demands and customers (VRPSDC) requires finding the optimal route for a capacitated vehicle that delivers goods to a set of customers, where each customer has a fixed probability of requiring being visited and a stochastic demand. For large instances, the evaluation of the cost function is a primary bottleneck when searching for high quality solutions within a limited computation time. We tackle this issue by using an empirical estimation approach. Moreover, we adopt a recently developed state-of-the-art iterative improvement algorithm for the closely related probabilistic traveling salesman problem. We integrate these two components into several metaheuristics and we show that they outperform substantially the current best algorithm for this problem.

KW - Empirical estimation

KW - Metaheuristics

KW - Vehicle routing with stochastic demands and customers

UR - https://www.scopus.com/pages/publications/84929703232

U2 - 10.1007/s10589-014-9719-z

DO - 10.1007/s10589-014-9719-z

M3 - Article

AN - SCOPUS:84929703232

SN - 0926-6003

VL - 61

SP - 463

EP - 487

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

IS - 2

M1 - 9719

ER -

Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this