Skip to main content
SpringerLink
Log in

Metaheuristic Approaches for the Fleet Size and Mix Vehicle Routing Problem with Time Windows and Step Cost Functions

  • Conference paper
  • First Online:
Computational Logistics (ICCL 2020)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12433))

Included in the following conference series:

Abstract

The vehicle routing problem is a traditional combinatorial problem with practical relevance for a wide range of industries. In the literature, several attributes have been tackled by dedicated methods in order to better reflect real-life situations. This article addresses the fleet size and mix vehicle routing problem with time windows in which companies hire a third-party logistics company. The shipping charges considered in this work are calculated using step cost functions, in which values are determined according to the type of vehicle and the total distance traveled, with fixed values for predefined distance ranges. The problem is solved with three different metaheuristic methods: Variable Neighborhood Search (VNS), Greed Randomized Adaptive Search Procedure (GRASP) and a hybrid proposition that combines both. The methods are examined through a computational comparative analysis in 168 benchmark instances from the literature, small-sized instances with known optimal solution, and 3 instances based on a real problem from the civil construction industry. The numerical experiments show that the proposed methods are efficient and show strong performance in different scenarios.

Supported by FAPESP (grants 2016/01860-1 and 2013/07375-0) and CNPq (grant 306083/2016-7).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Arnold, F., Sörensen, K.: What makes a VRP solution good? The generation of problem-specific knowledge for heuristics. Comput. Oper. Res. 106, 280–288 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  2. Ball, M.O., Golden, B., Assad, A., Bodin, L.: Planning for truck fleet size in the presence of a common-carrier option. Decis. Sci. 14(1), 103–120 (1983)

    Article  Google Scholar 

  3. Braekers, K., Ramaekers, K., Van Nieuwenhuyse, I.: The vehicle routing problem: state of the art classification and review. Comput. Ind. Eng. 99, 300–313 (2016)

    Article  Google Scholar 

  4. Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manag. Sci. 6(1), 80–91 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  5. Feo, T.A., Resende, M.G.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8(2), 67–71 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  6. Feo, T.A., Resende, M.G.: Greedy randomized adaptive search procedures. J. Global Optimiz. 6(2), 109–133 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  7. Festa, P., Resende, M.G.C.: Hybrid GRASP heuristics. In: Abraham, A., Hassanien, A.E., Siarry, P., Engelbrecht, A. (eds.) Foundations of Computational Intelligence Volume 3. SCI, vol. 203, pp. 75–100. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01085-9_4

    Chapter  Google Scholar 

  8. Golden, B., Assad, A., Levy, L., Gheysens, F.: The fleet size and mix vehicle routing problem. Comput. Oper. Res. 11(1), 49–66 (1984)

    Article  MATH  Google Scholar 

  9. Hansen, P., Mladenovic, N.: A tutorial on variable neighborhood search. Groupe d’Études et de Recherche en Analyse des Décisions, HEC Montréal (2003)

    Google Scholar 

  10. Hansen, P., Mladenović, N., Pérez, J.A.M.: Variable neighbourhood search: methods and applications. Ann. Oper. Res. 175(1), 367–407 (2010). https://doi.org/10.1007/s10479-009-0657-6

    Article  MathSciNet  MATH  Google Scholar 

  11. Koç, Ç., Bektaş, T., Jabali, O., Laporte, G.: A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows. Comput. Oper. Res. 64, 11–27 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Laporte, G.: Fifty years of vehicle routing. Transp. Sci. 43(4), 408–416 (2009)

    Article  Google Scholar 

  13. Lieb, R.C., Lieb, K.J.: The north American third-party logistics industry in 2013: the provider CEO perspective. Transp. J. 54(1), 104–121 (2015)

    Article  MathSciNet  Google Scholar 

  14. Liu, F.H., Shen, S.Y.: The fleet size and mix vehicle routing problem with time windows. J. Oper. Res. Soc. 50(7), 721–732 (1999)

    Article  MATH  Google Scholar 

  15. Manguino, J.L.V.: Heuristic methods applied to the mixed fleet vehicle routing problem with time windows and step costs per distance range. Ph.D. Thesis, Escola Politécnica, Universidade de São Paulo, São Paulo (2020). www.teses.usp.br

  16. Manguino, J.L.V., Ronconi, D.P.: Step cost functions in a fleet size and mix vehicle routing problem with time windows. Ann. Opera. Res. (2020, submitted)

    Google Scholar 

  17. Marasco, A.: Third-party logistics: a literature review. Int. J. Prod. Econ. 113(1), 127–147 (2008)

    Article  Google Scholar 

  18. Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  19. Palomo-Martínez, P.J., Salazar-Aguilar, M.A., Laporte, G., Langevin, A.: A hybrid variable neighborhood search for the orienteering problem with mandatory visits and exclusionary constraints. Comput. Oper. Res. 78, 408–419 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  20. Potvin, J.Y., Rousseau, J.M.: An exchange heuristic for routeing problems with time windows. J. Oper. Res. Soc. 46(12), 1433–1446 (1995). https://doi.org/10.1057/jors.1995.204

    Article  MATH  Google Scholar 

  21. Resende, M.G., Ribeiro, C.C.: Greedy randomized adaptive search procedures: advances, hybridizations, and applications. In: Gendreau, M., Potvin, J.Y. (eds.) Handbook of Metaheuristics. ISOR, vol. 146, pp. 283–319. Springer, Boston (2010). https://doi.org/10.1007/978-1-4419-1665-5_10

    Chapter  Google Scholar 

  22. Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254–265 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  23. Taillard, É., Badeau, P., Gendreau, M., Guertin, F., Potvin, J.Y.: A tabu search heuristic for the vehicle routing problem with soft time windows. Transp. Sci. 31(2), 170–186 (1997)

    Article  MATH  Google Scholar 

  24. Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. Eur. J. Oper. Res. 231(1), 1–21 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  25. Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. 234(3), 658–673 (2014)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Production Engineering, University of São Paulo, Av. Luciano Gualberto, 1380, Cidade Universitária, São Paulo, SP, 05508-010, Brazil

    João L. V. Manguino & Débora P. Ronconi

Authors
  1. João L. V. Manguino
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Débora P. Ronconi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to João L. V. Manguino .

Editor information

Editors and Affiliations

  1. University of Twente, Enschede, The Netherlands

    Eduardo Lalla-Ruiz

  2. University of Twente, Enschede, The Netherlands

    Martijn Mes

  3. University of Hamburg, Hamburg, Germany

    Stefan Voß

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Manguino, J.L.V., Ronconi, D.P. (2020). Metaheuristic Approaches for the Fleet Size and Mix Vehicle Routing Problem with Time Windows and Step Cost Functions. In: Lalla-Ruiz, E., Mes, M., Voß, S. (eds) Computational Logistics. ICCL 2020. Lecture Notes in Computer Science(), vol 12433. Springer, Cham. https://doi.org/10.1007/978-3-030-59747-4_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-59747-4_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-59746-7

  • Online ISBN: 978-3-030-59747-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation