6533b82efe1ef96bd12929b4

RESEARCH PRODUCT

A Simple Metaheuristic for the FleetSize and Mix Problem with TimeWindows

Wout DullaertOlli BräysyPasi P. Porkka

subject

Mathematical optimizationComputer scienceSimple (abstract algebra)business.industryVehicle routing problemKey (cryptography)Scale (descriptive set theory)Local search (optimization)Variance (accounting)businessMetaheuristicParallel metaheuristic

description

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.

yearjournalcountryeditionlanguage
2017-06-30
https://doi.org/10.1007/978-3-319-54490-8_4