Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
The Revolutionary Internet of Things Read chapter Read first chapter

2018 | OriginalPaper | Chapter

4. A Simple Metaheuristic for the FleetSize and Mix Problem with TimeWindows

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

Published in: Computational Methods and Models for Transport

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Agile Deep Learning UAVs Operating in Smart Spaces: Collective Intelligence Versus “Mission-Impossible”
next chapter Green Route Allocation in a Transportation Network
Appendix
Available only for authorised users
Literature
Baldacci R, Battarra M, Vigo D (2008) Routing a heterogeneous fleet of vehicles. In: The vehicle routing problem: latest advances and new challenges. Springer, Heidelberg, pp 3–27
Bräysy O (2003) A reactive variable neighborhood search for the vehicle-routing problem with time windows. INFORMS J Comput 15(4):347–368MathSciNetCrossRefMATH
Bräysy O, Dullaert W, Hasle G, Mester D, Gendreau M (2008) An effective multirestart deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows. Transp Sci 42(3):371–386CrossRef
Bräysy O, Porkka PP, Dullaert W, Repoussis PP, Tarantilis CD (2009) A well-scalable metaheuristic for the fleet size and mix vehicle routing problem with time windows. Expert Syst Appl 36(4):8460–8475CrossRef
Campbell AM, Savelsbergh M (2004) Efficient insertion heuristics for vehicle routing and scheduling problems. Transp sci 38(3):369–378CrossRef
Clarke GU, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12(4):568–581CrossRef
Gehring H, Homberger J (1999) A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Proceedings of EUROGEN99, vol. 2. Citeseer
Gendreau M, Potvin J-Y, Bräumlaysy O, Hasle G, Løkketangen A (2008) Metaheuristics for the vehicle routing problem and its extensions: a categorized bibliography. In: The vehicle routing problem: latest advances and new challenges. Springer, Heidelberg, pp 143–169
Kytöjoki J, Nuortio T, Bräysy O, Gendreau M (2007) An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Comput Oper Res 34(9):2743–2757CrossRefMATH
Liu F-H, Shen S-Y (1999) The fleet size and mix vehicle routing problem with time windows. J Oper Res Soc 50(7):721–732CrossRefMATH
Or I (1976) Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Xerox University Microfilms
Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265MathSciNetCrossRefMATH
Metadata
Title
A Simple Metaheuristic for the FleetSize and Mix Problem with TimeWindows
Authors
Olli Bräysy
Wout Dullaert
Pasi P. Porkka
Copyright Year
2018
Book
Computational Methods and Models for Transport

Print ISBN: 978-3-319-54489-2

Electronic ISBN: 978-3-319-54490-8

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-54490-8_4

Premium Partner

    Image Credits