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

Probabilistic Analyses and Practical Algorithms for the Vehicle Routing Problem with Time Windows

Author

Listed:
  • Julien Bramel

    (Columbia University, New York, New York)

  • David Simchi-Levi

    (Columbia University, New York, New York and Northwestern University, Evanston, Illinois)

Abstract

In the Vehicle Routing Problem with Time Windows, a set of customers are served by a fleet of vehicles of limited capacity, initially located at a central depot. Each customer provides a period of time in which they require service, which may consist of repair work or loading/unloading the vehicle. The objective is to find tours for the vehicles, such that each customer is served in its time window, the total load on any vehicle is no more than the vehicle capacity, and the total distance traveled is as small as possible. In this paper, we present a characterization of the asymptotic optimal solution value for general distributions of service times, time windows, customer loads and locations. This characterization leads to the development of a new algorithm based on formulating the problem as a stylized location problem. Computational results show that the algorithm is very effective on a set of standard test problems.

Suggested Citation

  • Julien Bramel & David Simchi-Levi, 1996. "Probabilistic Analyses and Practical Algorithms for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 44(3), pages 501-509, June.
    • Handle: RePEc:inm:oropre:v:44:y:1996:i:3:p:501-509
    DOI: 10.1287/opre.44.3.501
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.44.3.501
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.44.3.501?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. 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.
    2. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    3. Koorush Ziarati & François Soumis & Jacques Desrosiers & Marius M. Solomon, 1999. "A Branch-First, Cut-Second Approach for Locomotive Assignment," Management Science, INFORMS, vol. 45(8), pages 1156-1168, August.
    4. Braysy, Olli & Hasle, Geir & Dullaert, Wout, 2004. "A multi-start local search algorithm for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 159(3), pages 586-605, December.
    5. Adamo, Tommaso & Gendreau, Michel & Ghiani, Gianpaolo & Guerriero, Emanuela, 2024. "A review of recent advances in time-dependent vehicle routing," European Journal of Operational Research, Elsevier, vol. 319(1), pages 1-15.
    6. Figliozzi, Miguel Andres, 2009. "Planning approximations to the average length of vehicle routing problems with time window constraints," Transportation Research Part B: Methodological, Elsevier, vol. 43(4), pages 438-447, May.
    7. Steven I. Chien * & Zhaoqiong Qin, 2004. "Optimization of bus stop locations for improving transit accessibility," Transportation Planning and Technology, Taylor & Francis Journals, vol. 27(3), pages 211-227, June.
    8. Chen, Yen-Liang & Yang, Hsu-Hao, 2000. "Shortest paths in traffic-light networks," Transportation Research Part B: Methodological, Elsevier, vol. 34(4), pages 241-253, May.
    9. Carrese, Stefano & Cuneo, Valerio & Nigro, Marialisa & Pizzuti, Raffaele & Ardito, Cosimo Federico & Marseglia, Guido, 2022. "Optimization of downstream fuel logistics based on road infrastructure conditions and exposure to accident events," Transport Policy, Elsevier, vol. 124(C), pages 96-105.
    10. 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.
    11. David Simchi-Levi, 2014. "OM Forum —OM Research: From Problem-Driven to Data-Driven Research," Manufacturing & Service Operations Management, INFORMS, vol. 16(1), pages 2-10, February.
    12. Chen, Yen-Liang & Yang, Hsu-Hao, 2003. "Minimization of travel time and weighted number of stops in a traffic-light network," European Journal of Operational Research, Elsevier, vol. 144(3), pages 565-580, February.
    13. Hideki Hashimoto & Mutsunori Yagiura & Shinji Imahori & Toshihide Ibaraki, 2013. "Recent progress of local search in handling the time window constraints of the vehicle routing problem," Annals of Operations Research, Springer, vol. 204(1), pages 171-187, April.
    14. Zhu, Xiaoyan & Wilhelm, Wilbert E., 2007. "Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context," European Journal of Operational Research, Elsevier, vol. 183(2), pages 564-577, December.

    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:44:y:1996:i:3:p:501-509. 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.