The Bi-Objective k-Dissimilar Vehicle Routing Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

The Bi-Objective k-Dissimilar Vehicle Routing Problem

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

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

Included in the following conference series:

Abstract

This paper deals with the k-dissimilar vehicle routing problem in which a set of k dissimilar alternatives for a Capacitated Vehicle Routing Problem (CVRP) has to be determined for a single instance. The tradeoff between minimizing the longest routing alternative and maximizing the minimum dissimilarity between two routing alternatives is investigated. Since short vehicle routings tend to be similar to each other, a conflict of objectives arises. The developed heuristic approach approximates the Pareto set with respect to this tradeoff using a dissimilarity metric based on a grid. The method is tested on benchmark instances of the CVRP and findings are reported.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • 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

Similar content being viewed by others

References

  1. Akgün, V., Erkut, E., Batta, R.: On finding dissimilar paths. Eur. J. Oper. Res. 121(2), 232–246 (2000)

    Article  MATH  Google Scholar 

  2. Bock, F.: An algorithm for solving ‘Traveling Salesman’ and related network optimization problems. Technical report, 14th National Meeting of the Operations Research Society of America (ORSA), St Louis (1958)

    Google Scholar 

  3. Christofides, N.: Combinatorial optimization. Wiley, Chichester and New York (1979)

    MATH  Google Scholar 

  4. Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4), 568–581 (1964)

    Article  Google Scholar 

  5. Croes, G.A.: A method for solving traveling salesman problems. Oper. Res. 6, 791–812 (1958)

    Article  MathSciNet  Google Scholar 

  6. Dell’Olmo, P., Gentili, M., Scozzari, A.: On finding dissimilar Pareto-optimal paths. Eur. J. Oper. Res. 162(1), 70–82 (2005)

    Article  MATH  Google Scholar 

  7. Geiger, M.J.: Fast approximation heuristics for multi-objective vehicle routing problems. In: Chio, C., et al. (eds.) EvoApplications 2010, Part II. LNCS, vol. 6025, pp. 441–450. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  8. Glover, F.: Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discrete Appl. Math. 65(1–3), 223–253 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  9. Johnson, P., Joy, D., Clarke, D.: HIGHWAY 3.01, an enhancement routing model: program, description, methodology and revised user’s manual. Technical report, Oak Ridge National Laboratories, Washington, D.C. (1992)

    Google Scholar 

  10. Kuby, M., Zhongyi, X., Xiaodong, X.: A minimax method for finding the k best “differentiated” paths. Geogr. Anal. 29(4), 298–313 (1997)

    Article  Google Scholar 

  11. Laporte, G.: The vehicle routing problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(3), 345–358 (1992)

    Article  MATH  Google Scholar 

  12. Lombard, K., Church, R.L.: The gateway shortest path problem: generating alternative routes for a corridor location problem. Geogr. Syst. 1, 25–45 (1993)

    Google Scholar 

  13. Martí, R., González Velarde, J.L., Duarte, A.: Heuristics for the bi-objective path dissimilarity problem. Comput. Oper. Res. 36(11), 2905–2912 (2009)

    Article  MATH  Google Scholar 

  14. Ngueveu, S.U., Prins, C., Wolfler Calvo, R.: A hybrid tabu search for the m-peripatetic vehicle routing problem. In: Maniezzo, V., Stützle, T., Voß, S. (eds.) Matheuristics. Annals of Information Systems, vol. 10, pp. 253–266. Springer, Boston (2010)

    Chapter  Google Scholar 

  15. Savelsbergh, M.W.P.: The vehicle routing problem with time windows: minimizing route duration. INFORMS J. Comput. 4, 146–154 (1992)

    Article  MATH  Google Scholar 

  16. Sörensen, K.: Route stability in vehicle routing decisions: a bi-objective approach using metaheuristics. CEJOR 14(2), 193–207 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  17. Suurballe, J.W.: Disjoint paths in a network. Networks 4(2), 125–145 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  18. Talarico, L., Sörensen, K., Springael, J.: The k-dissimilar vehicle routing problem. Eur. J. Oper. Res. 244(1), 129–140 (2015)

    Article  MathSciNet  Google Scholar 

  19. Yen, J.Y.: Finding the k shortest loopless paths in a network. Manage. Sci. 17(11), 712–716 (1971)

    Article  MATH  MathSciNet  Google Scholar 

  20. Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999)

    Article  Google Scholar 

  21. Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms - a comparative case study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 292–301. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Logistics Management Department, Helmut-Schmidt-University, Holstenhofweg 85, 22043, Hamburg, Germany

    Sandra Zajac

Authors
  1. Sandra Zajac
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sandra Zajac .

Editor information

Editors and Affiliations

  1. Faculdade de Ciências da Universidade de Lisboa, Lisbon, Portugal

    Ana Paias

  2. University of Vienna , Vienna, Austria

    Mario Ruthmair

  3. University of Hamburg , Hamburg, Hamburg, Germany

    Stefan Voß

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Zajac, S. (2016). The Bi-Objective k-Dissimilar Vehicle Routing Problem. In: Paias, A., Ruthmair, M., Voß, S. (eds) Computational Logistics. ICCL 2016. Lecture Notes in Computer Science(), vol 9855. Springer, Cham. https://doi.org/10.1007/978-3-319-44896-1_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-44896-1_20

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-44895-4

  • Online ISBN: 978-3-319-44896-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics