Skip to main content
SpringerLink
Log in

A branch and bound algorithm for the capacitated vehicle routing problem

  • Theoretical Papers
  • Published:
Operations-Research-Spektrum Aims and scope Submit manuscript

Summary

This paper considers a version of the vehicle routing problem in which a non-negative weight is assigned to each city to be visited and where all vehicles are identical and have the same capacityD. The weight assigned to a vehicle on a given route may not exceed this capacity. The problem is formulated as an integer program: integrality is obtained by means of a branch and bound procedure; capacity constraints are first relaxed, and introduced only when they are found to be violated. Three variants of this basic algorithm are examined. Exact solutions are obtained for problems ranging from 15 to 50 cities.

Zusammenfassung

Diese Arbeit befaßt sich mit einer Variante des Fahrzeugroutenproblems, bei der jeder zu besuchenden Stadt ein nichtnegatives Gewicht zugeordnet ist und bei der alle Fahrzeuge gleich sind und die gleiche KapazitätD haben. Das Problem wird als ganzzahliges lineares Programm formuliert: Ganzzahligkeit wird über ein Branch und Bound-Verfahren erreicht. Dabei werden die Kapazitätsbeschränkungen zunächst relaxiert und nur dann wieder einbezogen, wenn sie verletzt werden. Drei Varianten dieses Basisverfahrens werden untersucht. Exakte Lösungen werden für Probleme mit 15 bis 50 Städten erhalten.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Balas E, Christofides N (1981) A restricted lagrangean approach to the travelling salesman problem. Math Programming 21:19–46

    Article  Google Scholar 

  2. Balinski M, Quandt R (1964) On an integer program for a delivery problem. Oper Res 12:300–304

    Article  Google Scholar 

  3. Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4:238–252

    Article  Google Scholar 

  4. Bodin LD, Golden BL, Assad A, Ball M (1981) The state of the art in routing and scheduling of vehicles and crews. Report No. UMTA/BMGT/MSS # 81-001, US Department of Trasnportation, Washington, DC

    Google Scholar 

  5. Christofides N (1976) The vehicle routing problem. RAIRO (Rech Operat) 10:55–70

    Google Scholar 

  6. Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. In: Combinatorial optimization. Wiley, New York London, pp 315–338

    Google Scholar 

  7. Christofides N, Mingozzi A, Toth P (1981) Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxations. Math Programming 20:255–282

    Article  Google Scholar 

  8. Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11:145–164

    Article  Google Scholar 

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

    Article  Google Scholar 

  10. Dantzig GB, Fulkerson R, Johnson S (1954) Solution of a large-scale travelling-salesman problem. Oper Res 2:393–410

    Google Scholar 

  11. Fisher M, Jaikumar R (1981) A generalized assignment heuristic for vehicle routing. Networks 11:109–124

    Article  Google Scholar 

  12. Fleischmann B (1982) Linear programming approaches to traveling salesman and vehicle scheduling problems. Paper presented at the XI. International Symposium on Mathematical Programming, Bonn

  13. Foster BA, Ryan DM (1976) An integer programming approach to the vehicle scheduling problem. Oper Res Qu 27:367–384

    Article  Google Scholar 

  14. Garvin WM, Crandall HW, John JB, Spellman RA (1957) Applications of linear programming in the oil industry. Manag Sci 3:407–430

    Article  Google Scholar 

  15. Gavish B, Graves SC (1979) The travelling salesman problem and related problems. Working Paper No. 7905, Graduate School of Management, University of Rochester

  16. Gavish B, Srikanth K (1982) An optimal solution method for the multiple travelling salesman problem. Working Paper No. 8027. Graduate School of Management, University of Rochester

  17. Golden B, Magnanti TL, Nguyen HQ (1977) Implementing vehicle routing algorithms. Networks 7:113–148

    Article  Google Scholar 

  18. Gomory R (1963) An algorithm for integer solutions to linear programs. Recent Advances in Mathematical Programming, McGraw-Hill, New York, pp 269–302

    Google Scholar 

  19. Grötschel M (1980) On the symmetric travelling salesman problem: solution of a 120-city problem. Math Programming Study 12:61–77

    Article  Google Scholar 

  20. Held M, Karp RM (1971) The travelling salesman problem and minimum spanning trees: part II. Math Programming 1:6–25

    Article  Google Scholar 

  21. Land AH, Powell S (1973) FORTRAN codes for mathematical programming: linear, quadratic and discrete. Wiley, London

    Google Scholar 

  22. Laporte G (1975) Permutation programming: problems, methods and applications. Ph.D. Thesis, University of London

  23. Laporte G, Nobert Y (1981) An exact algorithms for minimizing routing and operating costs in depot location. Eur J Oper Res 6:224–226

    Article  Google Scholar 

  24. Laporte G, Nobert Y, Desrochers M (1982) Two exact algorithms for the distance constrained vehicle routing problem. Cahiers du GERAD G-82-05. Ecole des Hautes Etudes Commerciales de Montréal

  25. Miliotis P (1976) Integer programming approaches to the travelling salesman problem. Math Programming 10:367–378

    Article  Google Scholar 

  26. Miliotis P, Laporte G, Nobert Y (1981) Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph. RAIRO (Rech Opérat) 15:233–239

    Google Scholar 

  27. Nobert Y (1982) Construciton d'algorithmes optimaux pour des extensions au problème du voyageur de commerce. Thèse de doctorat, Département d'Informatique et de Recherche Opérationnelle, Université de Montréal

Download references

Author information

Authors and Affiliations

  1. Ecole des Hautes Etudes Commerciales de Montréal, 5255 avenue Decelles, H3T 1V6, Montréal, Canada

    G. Laporte

  2. Département des Sciences Administratives, Université du Québec à Montréal, H3C 3P8, Montréal, Canada

    Y. Nobert

Authors
  1. G. Laporte
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Y. Nobert
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Laporte, G., Nobert, Y. A branch and bound algorithm for the capacitated vehicle routing problem. OR Spektrum 5, 77–85 (1983). https://doi.org/10.1007/BF01720015

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01720015

Keywords

Search

Navigation