A simple metaheuristic for the fleetsize and mix problem with TimeWindows

Olli Bräysy, Wout Dullaert, Pasi P. Porkka

Abstract

This paper presents a powerful new single-parameter metaheuristic to solve the Fleet Size and Mix Vehicle Routing Problem with Time Windows. The key idea of the new metaheuristic is to perform a random number of random-sized jumps in random order through four well-known local search operators. Computational testing on the 600 large-scale benchmarks of Bräysy et al. (Expert Syst Appl 36(4):8460–8475, 2009) show that the new metaheuristic outperforms previous best approaches, finding 533 new best-known solutions. Despite the significant number of random components, it is demonstrated that the variance of the results is rather low. Moreover, the suggested metaheuristic is shown to scale almost linearly up to 1000 customers.

Original languageEnglish
Title of host publicationComputational Methods in Applied Sciences
PublisherSpringer Netherland
Pages57-70
Number of pages14
Volume45
DOIs
StatePublished - 2018

Publication series

NameComputational Methods in Applied Sciences
Volume45
ISSN (Print)18713033

Cite this

Bräysy, O., Dullaert, W., & Porkka, P. P. (2018). A simple metaheuristic for the fleetsize and mix problem with TimeWindows. In Computational Methods in Applied Sciences (Vol. 45, pp. 57-70). (Computational Methods in Applied Sciences; Vol. 45). Springer Netherland. DOI: 10.1007/978-3-319-54490-8_4

Bräysy, Olli; Dullaert, Wout; Porkka, Pasi P. / A simple metaheuristic for the fleetsize and mix problem with TimeWindows.

Computational Methods in Applied Sciences. Vol. 45 Springer Netherland, 2018. p. 57-70 (Computational Methods in Applied Sciences; Vol. 45).

Research output: Scientific - peer-reviewChapter

@inbook{14a64da852b64fa89a33385b2391e7c8,
title = "A simple metaheuristic for the fleetsize and mix problem with TimeWindows",
abstract = "This paper presents a powerful new single-parameter metaheuristic to solve the Fleet Size and Mix Vehicle Routing Problem with Time Windows. The key idea of the new metaheuristic is to perform a random number of random-sized jumps in random order through four well-known local search operators. Computational testing on the 600 large-scale benchmarks of Bräysy et al. (Expert Syst Appl 36(4):8460–8475, 2009) show that the new metaheuristic outperforms previous best approaches, finding 533 new best-known solutions. Despite the significant number of random components, it is demonstrated that the variance of the results is rather low. Moreover, the suggested metaheuristic is shown to scale almost linearly up to 1000 customers.",
author = "Olli Bräysy and Wout Dullaert and Porkka, {Pasi P.}",
year = "2018",
doi = "10.1007/978-3-319-54490-8_4",
volume = "45",
series = "Computational Methods in Applied Sciences",
publisher = "Springer Netherland",
pages = "57--70",
booktitle = "Computational Methods in Applied Sciences",

}

Bräysy, O, Dullaert, W & Porkka, PP 2018, A simple metaheuristic for the fleetsize and mix problem with TimeWindows. in Computational Methods in Applied Sciences. vol. 45, Computational Methods in Applied Sciences, vol. 45, Springer Netherland, pp. 57-70. DOI: 10.1007/978-3-319-54490-8_4

A simple metaheuristic for the fleetsize and mix problem with TimeWindows. / Bräysy, Olli; Dullaert, Wout; Porkka, Pasi P.

Computational Methods in Applied Sciences. Vol. 45 Springer Netherland, 2018. p. 57-70 (Computational Methods in Applied Sciences; Vol. 45).

Research output: Scientific - peer-reviewChapter

TY - CHAP

T1 - A simple metaheuristic for the fleetsize and mix problem with TimeWindows

AU - Bräysy,Olli

AU - Dullaert,Wout

AU - Porkka,Pasi P.

PY - 2018

Y1 - 2018

N2 - This paper presents a powerful new single-parameter metaheuristic to solve the Fleet Size and Mix Vehicle Routing Problem with Time Windows. The key idea of the new metaheuristic is to perform a random number of random-sized jumps in random order through four well-known local search operators. Computational testing on the 600 large-scale benchmarks of Bräysy et al. (Expert Syst Appl 36(4):8460–8475, 2009) show that the new metaheuristic outperforms previous best approaches, finding 533 new best-known solutions. Despite the significant number of random components, it is demonstrated that the variance of the results is rather low. Moreover, the suggested metaheuristic is shown to scale almost linearly up to 1000 customers.

AB - This paper presents a powerful new single-parameter metaheuristic to solve the Fleet Size and Mix Vehicle Routing Problem with Time Windows. The key idea of the new metaheuristic is to perform a random number of random-sized jumps in random order through four well-known local search operators. Computational testing on the 600 large-scale benchmarks of Bräysy et al. (Expert Syst Appl 36(4):8460–8475, 2009) show that the new metaheuristic outperforms previous best approaches, finding 533 new best-known solutions. Despite the significant number of random components, it is demonstrated that the variance of the results is rather low. Moreover, the suggested metaheuristic is shown to scale almost linearly up to 1000 customers.

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

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

U2 - 10.1007/978-3-319-54490-8_4

DO - 10.1007/978-3-319-54490-8_4

M3 - Chapter

VL - 45

T3 - Computational Methods in Applied Sciences

SP - 57

EP - 70

BT - Computational Methods in Applied Sciences

PB - Springer Netherland

ER -

Bräysy O, Dullaert W, Porkka PP. A simple metaheuristic for the fleetsize and mix problem with TimeWindows. In Computational Methods in Applied Sciences. Vol. 45. Springer Netherland. 2018. p. 57-70. (Computational Methods in Applied Sciences). Available from, DOI: 10.1007/978-3-319-54490-8_4