IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v45y1997i2p295-301.html
   My bibliography  Save this article

On the Effectiveness of Set Covering Formulations for the Vehicle Routing Problem with Time Windows

Author

Listed:
  • Julien Bramel

    (Columbia University, New York)

  • David Simchi-Levi

    (Northwestern University, Evanston, Illinois)

Abstract

The Vehicle Routing Problem with Time Windows (VRPTW) is one of the most important problems in distribution and transportation. A classical and recently popular technique that has proven effective for solving these problems is based on formulating them as a set covering problem . The method starts by solving its linear programming relaxation , via column generation, and then uses a branch and bound strategy to find an integer solution to the set covering problem: a solution to the VRPTW. An empirically observed property is that the optimal solution value of the set covering problem is very close to its linear programming relaxation which makes the branch and bound step extremely efficient. In this paper we explain this behavior by demonstrating that for any distribution of service times, time windows, customer loads, and locations, the relative gap between fractional and integer solutions of the set covering problem becomes arbitrarily small as the number of customers increases.

Suggested Citation

  • Julien Bramel & David Simchi-Levi, 1997. "On the Effectiveness of Set Covering Formulations for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 45(2), pages 295-301, April.
    • Handle: RePEc:inm:oropre:v:45:y:1997:i:2:p:295-301
    DOI: 10.1287/opre.45.2.295
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.45.2.295
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.45.2.295?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
    ---><---

    Citations

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


    Cited by:

    1. 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.
    2. Nizar Hachemi & Issmail Hallaoui & Michel Gendreau & Louis-Martin Rousseau, 2015. "Flow-based integer linear programs to solve the weekly log-truck scheduling problem," Annals of Operations Research, Springer, vol. 232(1), pages 87-97, September.
    3. Jütte, Silke & Thonemann, Ulrich W., 2012. "Divide-and-price: A decomposition algorithm for solving large railway crew scheduling problems," European Journal of Operational Research, Elsevier, vol. 219(2), pages 214-223.
    4. Lap Mui Ann Chan & Ana Muriel & David Simchi-Levi, 1998. "Parallel Machine Scheduling, Linear Programming, and Parameter List Scheduling Heuristics," Operations Research, INFORMS, vol. 46(5), pages 729-741, October.
    5. Song, Jiongjiong & Regan, Amelia, 2005. "Approximation algorithms for the bid construction problem in combinatorial auctions for the procurement of freight transportation contracts," Transportation Research Part B: Methodological, Elsevier, vol. 39(10), pages 914-933, December.
    6. Oktay Günlük & Tracy Kimbrel & Laszlo Ladanyi & Baruch Schieber & Gregory B. Sorkin, 2006. "Vehicle Routing and Staffing for Sedan Service," Transportation Science, INFORMS, vol. 40(3), pages 313-326, August.
    7. L Tansini & O Viera, 2006. "New measures of proximity for the assignment algorithms in the MDVRPTW," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(3), pages 241-249, March.
    8. Cochran, Jeffery K. & Marquez Uribe, Alberto, 2005. "A set covering formulation for agile capacity planning within supply chains," International Journal of Production Economics, Elsevier, vol. 95(2), pages 139-149, February.
    9. Irnich, Stefan, 2000. "A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles," European Journal of Operational Research, Elsevier, vol. 122(2), pages 310-328, April.
    10. Stephan Westphal & Sven Krumke, 2008. "Pruning in column generation for service vehicle dispatching," Annals of Operations Research, Springer, vol. 159(1), pages 355-371, March.
    11. Victor Reyes & Ignacio Araya, 2021. "A GRASP-based scheme for the set covering problem," Operational Research, Springer, vol. 21(4), pages 2391-2408, December.
    12. Du, Jia Yan & Brunner, Jens O. & Kolisch, Rainer, 2014. "Planning towing processes at airports more efficiently," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 293-304.
    13. Jian Yang & Patrick Jaillet & Hani Mahmassani, 2004. "Real-Time Multivehicle Truckload Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 38(2), pages 135-148, May.
    14. Song, Jiongjiong & Regan, A C, 2003. "Approximation Algorithms for the Bid Construction Problem in Combinatorial Auctions for the Procurement of Freight Transportation Contracts," University of California Transportation Center, Working Papers qt3j7034z2, University of California Transportation Center.
    15. 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.

    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:oropre:v:45:y:1997:i:2:p:295-301. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.