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 proceedingChapterAcademicpeer-review

18 Downloads (Pure)


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 and Models for Transport
Subtitle of host publicationNew Challenges for the Greening of Transport Systems
PublisherSpringer Netherland
Number of pages14
ISBN (Electronic)9783319544908
ISBN (Print)9783319544892, 9783319854052
Publication statusPublished - 2018

Publication series

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


Dive into the research topics of 'A simple metaheuristic for the fleetsize and mix problem with TimeWindows'. Together they form a unique fingerprint.

Cite this