A simple metaheuristic for the fleetsize and mix problem with TimeWindows

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

Research output: Chapter in Book / Report / Conference proceedingChapterAcademicpeer-review

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.

LanguageEnglish
Title of host publicationComputational Methods and Models for Transport
Subtitle of host publicationNew Challenges for the Greening of Transport Systems
PublisherSpringer Netherland
Chapter4
Pages57-70
Number of pages14
Volume45
ISBN (Electronic)9783319544908
ISBN (Print)9783319544892, 9783319854052
DOIs
StatePublished - 2018

Publication series

NameComputational Methods in Applied Sciences
Volume45
ISSN (Print)1871-3033

Fingerprint

Vehicle routing
Metaheuristics
Testing
Vehicle Routing Problem with Time Windows
Random number
Local Search
Jump
Customers
Linearly
Benchmark
Operator

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 and Models for Transport: New Challenges for the Greening of Transport Systems (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 and Models for Transport: New Challenges for the Greening of Transport Systems. Vol. 45 Springer Netherland, 2018. pp. 57-70 (Computational Methods in Applied Sciences).
@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{\"a}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{\"a}ysy and Wout Dullaert and Porkka, {Pasi P.}",
year = "2018",
doi = "10.1007/978-3-319-54490-8_4",
language = "English",
isbn = "9783319544892",
volume = "45",
series = "Computational Methods in Applied Sciences",
publisher = "Springer Netherland",
pages = "57--70",
booktitle = "Computational Methods and Models for Transport",

}

Bräysy, O, Dullaert, W & Porkka, PP 2018, A simple metaheuristic for the fleetsize and mix problem with TimeWindows. in Computational Methods and Models for Transport: New Challenges for the Greening of Transport Systems. 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 and Models for Transport: New Challenges for the Greening of Transport Systems. Vol. 45 Springer Netherland, 2018. p. 57-70 (Computational Methods in Applied Sciences; Vol. 45).

Research output: Chapter in Book / Report / Conference proceedingChapterAcademicpeer-review

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

UR - https://www.springer.com/gp/book/9783319544892

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

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

M3 - Chapter

SN - 9783319544892

SN - 9783319854052

VL - 45

T3 - Computational Methods in Applied Sciences

SP - 57

EP - 70

BT - Computational Methods and Models for Transport

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 and Models for Transport: New Challenges for the Greening of Transport Systems. Vol. 45. Springer Netherland. 2018. p. 57-70. (Computational Methods in Applied Sciences). Available from, DOI: 10.1007/978-3-319-54490-8_4