An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation

References

• Achuthan N. R., Caccetta L., Hill S. P. Capacitated vehicle routing problem: Some new cutting planes. Asia-Pacific J. Oper. Res. (1998) 15:109–123Google Scholar
• Applegate D., Bixby R., Chvátal V., Cook W. Special session on TSP. 15th Internat. Sympos. Math. Programming (1994) (University of Michigan, Ann Arbor, MI) Google Scholar
• Araque J. R., Hall L. A., Magnanti T. L. Capacitated trees, capacitated routing and associated polyhedra. (1990) . Discussion paper 90-61, Center for Operations Research and Econometrics, Catholic University of Louvain, Louvain, BelgiumGoogle Scholar
• Araque J. R., Kudva G., Morin T. L., Pekny J. F. A branch and cut algorithm for the vehicle routing problem. Ann. Oper. Res. (1994) 50:37–59Crossref, Google Scholar
• Augerat P., Belenguer J. M., Benavent E., Corberán A., Naddef D. Separating capacity constraints in the CVRP using tabu search. Eur. J. Oper. Res. (1998) 106:546–557Crossref, Google Scholar
• Augerat P., Belenguer J. M., Benavent E., Corberán A., Naddef D., Rinaldi G. Computational results with a branch and cut code for the capacitated vehicle routing problem. (1995) . Rapport de recherche 1 RR949-M, ARTEMIS-IMAG, Grenoble, FranceGoogle Scholar
• Baldacci R., Hadjiconstantinou E., Mingozzi A. An exact algorithm for the traveling salesman problem with deliveries and collections. Networks (2003) 42(1):26–41Crossref, Google Scholar
• Balinski M., Quandt R. On an integer program for a delivery problem. Oper. Res. (1964) 12:300–304Link, Google Scholar
• Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L.Network Routing. Handbooks in Operations Research and Management Science (1995) 8(Elsevier Science, Amsterdam, The Netherlands) Google Scholar
• Bodin L., Mingozzi A., Maniezzo V., Hall R. Street routing and scheduling problems. Handbook on Transportation Science (1999) (Kluwer Academic Publishers)Crossref, Google Scholar
• Bodin L., Golden B. L., Assad A. A., Ball M. O. Routing and scheduling of vehicles and crews: The state of the art. Comput. Oper. Res. (1983) 10:69–211Google Scholar
• Bramel J., Simchi-Levi D., Toth P., Vigo D. Set-covering-based algorithms for the capacitated VRP. The Vehicle Routing Problem (2000) (SIAM, Philadelphia, PA) Google Scholar
• Christofides N., Lenstra J. K., Lawler E. L., Rinnooy Kan A. H. G., Shmoys D. B. Vehicle routing. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985) (John Wiley and Sons, Chichester, U.K.) 431–448Google Scholar
• Christofides N., Eilon S. An algorithm for the vehicle dispatching problem. Oper. Res. Quart (1969) 20:309–318Crossref, Google Scholar
• Christofides N., Mingozzi A. Vehicle routing: Practical and algorithm aspects. LOGISTICS: Where Ends Have to Meet (1990) (Pergamon Press, Oxford, U.K.) Google Scholar
• Christofides N., Mingozzi A., Toth P., Christofides N., Mingozzi A., Toth P., Sandi L. The vehicle routing problem. Combinatorial Optimization (1979) (Wiley, Chichester, U.K.) 315–338Google Scholar
• Christofides N., Mingozzi A., Toth P. Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation. Math. Programming (1981a) 10:255–280Crossref, Google Scholar
• Christofides N., Mingozzi A., Toth P. State space relaxation procedures for the computation of bounds to routing problems. Networks (1981b) 11:145–164Crossref, Google Scholar
• Chvátal V. Edmonds polytopes and weakly Hamiltonian graphs. Math. Programming (1973) 5:29–40Crossref, Google Scholar
• Cornuéjols G., Harche F. Polyhedral study of the capacitated vehicle routing. Math. Programming (1993) 60:21–52Crossref, Google Scholar
• CPLEX ILOG CPLEX 6.5 callable library. (2001) (ILOG, Incline Village, NV) Google Scholar
• Finke G., Claus A., Gunn E. A two-commodity network flow approach to the traveling salesman problem. Congress. Numerantium (1984) 41:167–178Google Scholar
• Fischetti M., Toth P., Vigo D. A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Oper. Res. (1994) 42:846–859Link, Google Scholar
• Fisher M. L. Optimal solution of vehicle routing problems using minimum K-Trees. Oper. Res. (1994) 42:626–642Link, Google Scholar
• Fisher M. L., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. Vehicle routing. Network Routing Handbooks in Operations Research and Management Science (1995) Vol. 8(North-Holland, Amsterdam, The Netherlands) 1–33Google Scholar
• Garvin W. W., Crandall H. W., John J. B., Spellman R. A. Applications of vehicle routing in the oil industry. Management Sci. (1957) 3:407–430Link, Google Scholar
• Gavish B., Graves S. C. The travelling salesman problem and related problems. (1979) . Working paper 7905, Graduate School of Management, University of Rochester, Rochester, NYGoogle Scholar
• Gavish B., Graves S. C. Scheduling and routing in transportation and distribution systems: Formulations and new relaxations. (1982) . Working paper, Graduate School of Management, University of Rochester, Rochester, NYGoogle Scholar
• Gendreau M., Hertz A., Laporte G. A tabu search heuristic for the vehicle routing problem. Management Sci. (1994) 40:1276–1290Link, Google Scholar
• Gendreau M., Laporte G., Potvin J.-Y., Toth P., Vigo D. Metaheuristics for the capacitated VRP. The Vehicle Routing Problem (2000) (SIAM, Philadelphia, PA) Google Scholar
• Golden B. L., Magnanti T. L., Nguyen H. Q. Implementing vehicle routing algorithms. Networks (1977) 7:113–148Crossref, Google Scholar
• Golden B. L., Wasil E. A., Kelly J. P., Chao I.-M. Metaheuristics in vehicle routing. Fleet Management and Logistics (1998) (Kluwer, Boston, MA) Crossref, Google Scholar
• Gouveia L. A result on projection for the vehicle routing problem. J. Oper. Res. (1995) 85:610–624Crossref, Google Scholar
• Grötschel M., Padberg M. W. On the symmetric traveling salesman problem: I and II. Math. Programming (1979) 16:265–280Crossref, Google Scholar
• Grötschel M., Padberg M. W., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. Polyhedral theory. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985) (John Wiley and Sons, Chichester, U.K.) 251–305Google Scholar
• Hadjiconstantinou E., Christofides N., Mingozzi A. A new exact algorithm for the vehicle routing problem based on q-paths and K-shortest paths relaxations. Ann. Oper. Res. (1995) 61:21–43Crossref, Google Scholar
• Hill S. P. Branch and cut methods for the symmetric capacitated vehicle routing problem. (1995) . Ph.D. thesis, School of Mathematics and Statistics, Curtin University of Technology, Perth, AustraliaGoogle Scholar
• Langevin A., Desrochers M., Desrosiers J., Gélinas S., Soumis F. A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows. Networks23:631–640Crossref, Google Scholar
• Laporte G. The vehicle routing problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. (1992) 59:345–358Crossref, Google Scholar
• Laporte G. Vehicle routing. M. Dell'Amico. Annotated Bibliographies in Combinatorial Optimization (1997) (Wiley, Chichester, U.K.) Google Scholar
• Laporte G., Nobert Y. Comb inequalities for the vehicle routing problem. Methods Oper. Res. (1984) 51:271–276Google Scholar
• Laporte G., Nobert Y. Exact algorithms for the vehicle routing problem. Ann. Discrete Math. (1987) 31:147–184Google Scholar
• Laporte G., Osman I. H. Routing problems: A bibliography. Ann. Oper. Res. (1995) 61:227–262Crossref, Google Scholar
• Laporte G., Semet F., Toth P., Vigo D. Classical heuristics for the capacitated VRP. The Vehicle Routing Problem (2000) (SIAM, Philadelphia, PA) Google Scholar
• Laporte G., Mercure H., Nobert Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks (1986) 16:1050–1073Crossref, Google Scholar
• Laporte G., Nobert Y., Desrochers M. Optimal routing under capacity and distance restrictions. Oper. Res. (1985) 33:1058–1073Link, Google Scholar
• Laporte G., Gendreau M., Potvin J.-Y., Semet F. Classical and modern heuristics for the vehicle routing problem. Internat. Trans. Oper. Res. (2000) 7:285–300Crossref, Google Scholar
• Letchford A. N., Eglese R. W., Lysgaard J. Multistars, partial multistars and the capacitated vehicle routing problem. Math. Programming (2002) 94:21–40Crossref, Google Scholar
• Lucena A. Exact solution approaches for the vehicle routing problem. (1986) . Ph.D. thesis, Department of Management Science, Imperial College, London, U.K.Google Scholar
• Magnanti T. L. Combinatorial optimization and vehicle fleet planning: Perspectives and prospects. Networks (1981) 11:179–213Crossref, Google Scholar
• Miller D. L. A matching based exact algorithm for capacitated vehicle routing problems. ORSA J. Comput. (1995) 7(1):1–9Link, Google Scholar
• Mingozzi A., Christofides N., Hadjiconstantinou E. An exact algorithm for the vehicle routing problem based on the set partitioning formulation. (1994) . Internal report, Department of Mathematics, University of Bologna, Bologna, ItalyGoogle Scholar
• Naddef D., Rinaldi G. Branch-and cut algorithms for the capacitated VRP. The Vehicle Routing Problem (2000) (SIAM, Philadelphia, PA) Google Scholar
• Petersen N. C. The embedding of flow formulations of the TSP and some of its extensions into Benders' decomposition algorithm. (2000) . Doctoral mercatural thesis, University of Odense, Odense, DenmarkGoogle Scholar
• Ralphs T. K., Kopman L., Pulleyblank W. R., Trotter L. E. On the capacitated vehicle routing problem. Math. Programming (2003) 94:343–359Crossref, Google Scholar
• Reinelt G. TSPLIB—A traveling salesman problem library. ORSA J. Comp. (1991) 3:376–384Link, Google Scholar
• Toth P., Vigo D., Crainic T. G., Laporte G. Exact algorithms for vehicle routing. Fleet Management and Logistics (1998) (Kluwer, Boston, MA) 1–31Crossref, Google Scholar
• Toth P., Vigo D. The vehicle routing problem. Monographs on Discrete Mathematics and Applications (2000a) (SIAM, Philadelphia, PA) Google Scholar
• Toth P., Vigo D., Toth P., Vigo D. An overview of vehicle routing problems. The Vehicle Routing Problem (2000b) (SIAM, Philadelphia, PA) Google Scholar
• Toth P., Vigo D., Toth P., Vigo D. Branch-and-bound algorithms for the capacitated VRP. (2000c) (SIAM, Philadelphia, PA) Google Scholar