Abstract
In open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version of the well-known capacitated vehicle routing problem (CVRP). The algorithm is based on branch-and-cut. We show that, even though the open CVRP initially looks like a minor variation of the standard CVRP, the integer programming formulation and cutting planes need to be modified in subtle ways. Computational results are given for several standard test instances, which enables us for the first time to assess the quality of existing heuristic methods, and to compare the relative difficulty of open and closed versions of the same problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aksen D, Özyurt Z and Aras N (2006). The open vehicle routing problem with driver nodes and time deadlines. J Opl Res Soc, AOP 9/8/06 doi: 10.1057/palgrave.jors.2602249.
Augerat P (1995). Approche Polyèdrale du Problème de Tournées de Véhicules. PhD thesis, Institut National Polytechnique de Grenoble.
Bodin LD, Golden BL, Assad AA and Ball MO (1983). Routing and scheduling of vehicles and crews: The state of the art. Comput Opns Res 10: 63–211.
Brandão J (2004). A tabu search algorithm for the open vehicle routing problem. Eur J Opl Res 157: 552–564.
Christofides N and Eilon S (1969). An algorithm for the vehicle-dispatching problem. Opns Res Quart 20: 309–318.
Edmonds J (1965). Maximum matching and a polyhedron with 0–1 vertices. J Res Nat Bur Standards 69B: 125–130.
Fischetti M, Toth P and Vigo D (1994). A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Opns Res 42: 846–859.
Ford L and Fulkerson D (1962). Flows in Networks. Princeton University Press: New Jersey.
Fu Z, Eglese R and Li LYO (2005). A new tabu search heuristic for the open vehicle routing problem. J Opl Res Soc 56: 267–274.
Fu Z, Eglese R and Li LYO (2006). Corrigendum to ‘A new tabu search heuristic for the open vehicle routing problem'. J Opl Res Soc 57: 1018.
Fukasawa R et al (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math Program 106: 491–511.
Goldberg AV and Tarjan RE (1988). A new approach to the maximum flow problem. J ACM 35: 921–940.
Laporte G, Nobert Y and Desrochers M (1985). Optimal routing under capacity and distance restrictions. Opns Res 33: 1050–1073.
Letchford AN, Eglese RW and Lysgaard J (2002). Multistars, partial multistars and the capacitated vehicle routing problem. Math Program 94: 21–40.
Li F, Golden B and Wasil E (2006). The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Comput Opns Res, doi: 10.1016/j.cor.2005.11.018.
Lysgaard J (2003). CVRPSEP: A Package of Separation Routines for the Capacitated Vehicle Routing Problem. Working Paper 03-04, Department of Management Science and Logistics, Aarhus School of Business. www.asb.dk/~lys/.
Lysgaard J, Letchford AN and Eglese RW (2004). A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math Program 100: 423–445.
Naddef D and Rinaldi G (2002). Branch-and-cut algorithms for the capacitated VRP. In: Toth and Vigo (Eds). The Vehicle Routing Problem. Chapter 3. SIAM Monographs on Discrete Mathematics and Applications: Philadelphia PA.
Nobert Y and Picard J-C (1996). An optimal algorithm for the mixed Chinese postman problem. Networks 27: 95–108.
Padberg MW and Rao MR (1982). Odd minimum cut-sets and b-matchings. Math Opns Res 7: 67–80.
Pisinger D and Ropke S (2006). A general heuristic for vehicle routing problems. Comput Opns Res, doi: 10.1016/j.cor.2005.09.012.
Reinelt G (1991). TSPLIB—A traveling salesman problem library. ORSA J Comput 3: 376–384.
Repoussis PP, Tarantilis CD and Ioannou G (2006). The open vehicle routing problem with time windows. J Opl Res Soc, AOP 1/2/06 doi: 10.1057/palgrave.jors.2602143.
Sariklis D and Powell S (2000). A heuristic method for the open vehicle routing problem. J Opl Res Soc 51: 564–573.
Schrage L (1981). Formulation and structure of more complex/realistic routing and scheduling problems. Networks 11: 229–232.
Tarantilis CD, Diakoulaki D and Kiranoudis CT (2004). Combination of geographical information system and efficient routing algorithms for real life distribution operations. Eur J Opl Res 152: 437–453.
Tarantilis CD, Ioannou G, Kiranoudis CT and Prastacos GP (2005). Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm. J Opl Res Soc 56: 588–596.
Toth P and Vigo D (eds). The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications: Philadelphia PA.
Author information
Authors and Affiliations
Corresponding author
Appendix A
Appendix A
To show validity of the mixed comb inequalities, it is helpful to prove the following lemma.
Lemma 1
-
For any set S such that 0∈S, the following three inequalities are valid.
Proof
-
Owing to the degree equations, the inequality (A.1) is equivalent to the capacity inequality on V\S and the inequalities (A.2) and (A.3) are equivalent to the balancing inequalities on V\S and S\{0}, respectively. □
Proof of Theorem 1
-
We follow the standard Chvátal–Gomory integer rounding argument. If we sum together the following inequalities:
-
the degree equations for all i∈H,
-
the inequality (6) on H∩T i for 1⩽i⩽t,
-
the inequality (6) on T i and T i \H for i∈𝒩,
-
the inequalities (A.1) for T i and T i \H, for i∈𝒟,
-
the inequalities (A.2) for T i and T i \H, for i∈𝒮, and
-
the inequalities (A.3) for T i and T i \H, for i∈ℛ,
we obtain (after some re-arranging):
Dividing this inequality by two and rounding down yields the result. □
-
Rights and permissions
About this article
Cite this article
Letchford, A., Lysgaard, J. & Eglese, R. A branch-and-cut algorithm for the capacitated open vehicle routing problem. J Oper Res Soc 58, 1642–1651 (2007). https://doi.org/10.1057/palgrave.jors.2602345
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/palgrave.jors.2602345