IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v36y2002i2p250-269.html
   My bibliography  Save this article

A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows

Author

Listed:
  • Jonathan F. Bard

    (Graduate Program in Operations Research, Department of Mechanical Engineering, The University of Texas, Austin, Texas 78712-1063)

  • George Kontoravdis

    (Graduate Program in Operations Research, Department of Mechanical Engineering, The University of Texas, Austin, Texas 78712-1063)

  • Gang Yu

    (Management Science and Information Systems, College of Business Administration, The University of Texas, Austin, Texas 78712)

Abstract

This paper addresses the problem of finding the minimum number of vehicles required to visit a set of nodes subject to time window and capacity constraints. The fleet is homogeneous and is located at a common depot. Each node requires the same type of service. An exact method is introduced based on branch and cut. In the computations, ever increasing lower bounds on the optimal solution are obtained by solving a series of relaxed problems that incorporate newly found valid inequalities. Feasible solutions or upper bounds are obtained with the help of greedy randomized adaptive search procedure (GRASP). A wide variety of cuts is introduced to tighten the linear programming (LP) relaxation of the original mixed-integer program. To find violated cuts, it is necessary to solve a separation problem. A substantial portion of the paper is aimed at describing the heuristics developed for this purpose. A new approach for obtaining feasible solutions from the LP relaxation is also discussed. Numerical results for standard 50- and 100-node benchmark problems are reported.

Suggested Citation

  • Jonathan F. Bard & George Kontoravdis & Gang Yu, 2002. "A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 36(2), pages 250-269, May.
    • Handle: RePEc:inm:ortrsc:v:36:y:2002:i:2:p:250-269
    DOI: 10.1287/trsc.36.2.250.565
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.36.2.250.565
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.36.2.250.565?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    2. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    3. Matteo Fischetti & Paolo Toth, 1997. "A Polyhedral Approach to the Asymmetric Traveling Salesman Problem," Management Science, INFORMS, vol. 43(11), pages 1520-1536, November.
    4. Marius M. Solomon & Jacques Desrosiers, 1988. "Survey Paper---Time Window Constrained Routing and Scheduling Problems," Transportation Science, INFORMS, vol. 22(1), pages 1-13, February.
    5. Matteo Fischetti & Juan José Salazar González & Paolo Toth, 1998. "Solving the Orienteering Problem through Branch-and-Cut," INFORMS Journal on Computing, INFORMS, vol. 10(2), pages 133-148, May.
    6. Niklas Kohl & Oli B. G. Madsen, 1997. "An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation," Operations Research, INFORMS, vol. 45(3), pages 395-406, June.
    7. Karla L. Hoffman & Manfred Padberg, 1993. "Solving Airline Crew Scheduling Problems by Branch-and-Cut," Management Science, INFORMS, vol. 39(6), pages 657-682, June.
    8. George Kontoravdis & Jonathan F. Bard, 1995. "A GRASP for the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 7(1), pages 10-23, February.
    9. Niklas Kohl & Jacques Desrosiers & Oli B. G. Madsen & Marius M. Solomon & François Soumis, 1999. "2-Path Cuts for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 33(1), pages 101-116, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Martin Durbin & Karla Hoffman, 2008. "OR PRACTICE---The Dance of the Thirty-Ton Trucks: Dispatching and Scheduling in a Dynamic Environment," Operations Research, INFORMS, vol. 56(1), pages 3-19, February.
    2. Yibo Dang & Manjeet Singh & Theodore T. Allen, 2021. "Network Mode Optimization for the DHL Supply Chain," Interfaces, INFORMS, vol. 51(3), pages 179-199, May.
    3. Ran Liu & Zhibin Jiang, 2019. "A constraint relaxation-based algorithm for the load-dependent vehicle routing problem with time windows," Flexible Services and Manufacturing Journal, Springer, vol. 31(2), pages 331-353, June.
    4. Jourdan, L. & Basseur, M. & Talbi, E.-G., 2009. "Hybridizing exact methods and metaheuristics: A taxonomy," European Journal of Operational Research, Elsevier, vol. 199(3), pages 620-629, December.
    5. Jeng-Shyang Pan & Qing-yong Yang & Shu-Chuan Chu & Kuo-Chi Chang, 2021. "Compact Sine Cosine Algorithm applied in vehicle routing problem with time window," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 78(4), pages 609-628, December.
    6. Yuan Qu & Jonathan F. Bard, 2015. "A Branch-and-Price-and-Cut Algorithm for Heterogeneous Pickup and Delivery Problems with Configurable Vehicle Capacity," Transportation Science, INFORMS, vol. 49(2), pages 254-270, May.
    7. Pureza, Vitória & Morabito, Reinaldo & Reimann, Marc, 2012. "Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW," European Journal of Operational Research, Elsevier, vol. 218(3), pages 636-647.
    8. Calvete, Herminia I. & Gale, Carmen & Oliveros, Maria-Jose & Sanchez-Valverde, Belen, 2007. "A goal programming approach to vehicle routing problems with soft time windows," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1720-1733, March.
    9. Guy Desaulniers & François Lessard & Ahmed Hadjar, 2008. "Tabu Search, Partial Elementarity, and Generalized k -Path Inequalities for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 42(3), pages 387-404, August.
    10. Jonathan F. Bard & Siwate Rojanasoonthon, 2006. "A branch‐and‐price algorithm for parallel machine scheduling with time windows and job priorities," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 24-44, February.
    11. Tan, K.C. & Chew, Y.H. & Lee, L.H., 2006. "A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 172(3), pages 855-885, August.
    12. Pedro Munari & Reinaldo Morabito, 2018. "A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(3), pages 437-464, October.
    13. D. G. N. D. Jayarathna, 2024. "Survey on Thirty Years of Vehicle Routing Problems: Mathematical Models, Solution Methods, and Real-Life Applications," International Journal of Research and Scientific Innovation, International Journal of Research and Scientific Innovation (IJRSI), vol. 11(7), pages 435-449, July.
    14. Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
    15. Junfang Yu & Randy Hoff, 2013. "Optimal Routing and Assignment of Consultants for Energy Education, Inc," Interfaces, INFORMS, vol. 43(2), pages 142-151, April.
    16. Lysgaard, Jens, 2006. "Reachability cuts for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 175(1), pages 210-223, November.
    17. Manuel Iori & Juan-José Salazar-González & Daniele Vigo, 2007. "An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints," Transportation Science, INFORMS, vol. 41(2), pages 253-264, May.
    18. G Zhu & J F Bard & G Yu, 2005. "Disruption management for resource-constrained project scheduling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(4), pages 365-381, April.
    19. Ann Melissa Campbell & Dieter Vandenbussche & William Hermann, 2008. "Routing for Relief Efforts," Transportation Science, INFORMS, vol. 42(2), pages 127-145, May.
    20. Lysgaard, Jens, 2004. "Reachability cuts for the vehicle routing problem with time windows," CORAL Working Papers L-2004-01, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    21. Guidong Zhu & Jonathan F. Bard & Gang Yu, 2006. "A Branch-and-Cut Procedure for the Multimode Resource-Constrained Project-Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 377-390, August.
    22. Theodore Athanasopoulos & Ioannis Minis, 2013. "Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework," Annals of Operations Research, Springer, vol. 206(1), pages 1-22, July.
    23. Zhi-Long Chen & Hang Xu, 2006. "Dynamic Column Generation for Dynamic Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 40(1), pages 74-88, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Vicky Mak & Andreas Ernst, 2007. "New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 66(1), pages 69-98, August.
    2. Wanpracha Chaovalitwongse & Dukwon Kim & Panos M. Pardalos, 2003. "GRASP with a New Local Search Scheme for Vehicle Routing Problems with Time Windows," Journal of Combinatorial Optimization, Springer, vol. 7(2), pages 179-207, June.
    3. Olli Bräysy, 2003. "A Reactive Variable Neighborhood Search for the Vehicle-Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 15(4), pages 347-368, November.
    4. Liu, Fuh-Hwa Franklin & Shen, Sheng-Yuan, 1999. "A route-neighborhood-based metaheuristic for vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 118(3), pages 485-504, November.
    5. Müller, Juliane, 2010. "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 202(1), pages 223-231, April.
    6. Hong, Sung-Chul & Park, Yang-Byung, 1999. "A heuristic for bi-objective vehicle routing with time window constraints," International Journal of Production Economics, Elsevier, vol. 62(3), pages 249-258, September.
    7. Rosemary T. Berger & Collette R. Coullard & Mark S. Daskin, 2007. "Location-Routing Problems with Distance Constraints," Transportation Science, INFORMS, vol. 41(1), pages 29-43, February.
    8. Zamorano, Emilio & Stolletz, Raik, 2017. "Branch-and-price approaches for the Multiperiod Technician Routing and Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 257(1), pages 55-68.
    9. Vis, Iris F.A., 2006. "Survey of research in the design and control of automated guided vehicle systems," European Journal of Operational Research, Elsevier, vol. 170(3), pages 677-709, May.
    10. Bhusiri, Narath & Qureshi, Ali Gul & Taniguchi, Eiichi, 2014. "The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 1-22.
    11. Guy Desaulniers & François Lessard & Ahmed Hadjar, 2008. "Tabu Search, Partial Elementarity, and Generalized k -Path Inequalities for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 42(3), pages 387-404, August.
    12. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    13. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    14. Calvete, Herminia I. & Gale, Carmen & Oliveros, Maria-Jose & Sanchez-Valverde, Belen, 2007. "A goal programming approach to vehicle routing problems with soft time windows," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1720-1733, March.
    15. Russell Bent & Pascal Van Hentenryck, 2004. "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 515-530, November.
    16. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    17. Yao, Yu & Zhu, Xiaoning & Dong, Hongyu & Wu, Shengnan & Wu, Hailong & Carol Tong, Lu & Zhou, Xuesong, 2019. "ADMM-based problem decomposition scheme for vehicle routing problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 156-174.
    18. Andrew Lim & Xingwen Zhang, 2007. "A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 443-457, August.
    19. Diego Pecin & Claudio Contardo & Guy Desaulniers & Eduardo Uchoa, 2017. "New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 489-502, August.
    20. Russell, Robert A. & Chiang, Wen-Chyuan, 2006. "Scatter search for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 169(2), pages 606-622, March.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:36:y:2002:i:2:p:250-269. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.