A simple metaheuristic for the fleetsize and mix problem with TimeWindows

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

doi:10.1007/978-3-319-54490-8_4

A simple metaheuristic for the fleetsize and mix problem with TimeWindows

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

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Chapter › Academic › peer-review

36 Downloads (Pure)

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 language	English
Title of host publication	Computational Methods and Models for Transport
Subtitle of host publication	New Challenges for the Greening of Transport Systems
Publisher	Springer Netherland
Chapter	4
Pages	57-70
Number of pages	14
Volume	45
ISBN (Electronic)	9783319544908
ISBN (Print)	9783319544892, 9783319854052
DOIs	https://doi.org/10.1007/978-3-319-54490-8_4
Publication status	Published - 2018

Publication series

Name	Computational Methods in Applied Sciences
Volume	45
ISSN (Print)	1871-3033

Access to Document

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

Bräysy2018_Chapter_ASimpleMetaheuristicForTheFleetSizeFinal published version, 250 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Copy link address

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. https://doi.org/10.1007/978-3-319-54490-8_4

@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",

}

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 proceeding › Chapter › Academic › peer-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

AN - SCOPUS:85021833644

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 -

A simple metaheuristic for the fleetsize and mix problem with TimeWindows

Abstract

Publication series

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this