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

Probabilistic Analysis of the Capacitated Vehicle Routing Problem with Unsplit Demands

Author

Listed:
  • Julien Bramel

    (Columbia University, New York, New York)

  • Edward G. Coffman

    (AT&T Bell Laboratories, Murray Hill, New Jersey)

  • Peter W. Shor

    (AT&T Bell Laboratories, Murray Hill, New Jersey)

  • David Simchi-Levi

    (Columbia University, New York, New York)

Abstract

In the capacitated vehicle routing problem with unsplit demands, the demand of a customer may not be divided over more than one vehicle. The objective is to find tours for the vehicles such that the amount delivered by a vehicle does not exceed its capacity, each customer receives its demand, and the total distance traveled is as small as possible. We find the asymptotic optimal solution value of the capacitated vehicle routing problem with unsplit demands for any distribution of the demands when customers are independently and identically distributed in a given region. We also develop polynomial-time heuristics for the problem and show that, under certain assumptions on the distribution of customer locations and demands, the heuristics produce solutions that are asymptotically optimal. In addition, we give a tight bound on the rate of convergence for the case when customers are uniformly distributed in a rectangular region.

Suggested Citation

  • Julien Bramel & Edward G. Coffman & Peter W. Shor & David Simchi-Levi, 1992. "Probabilistic Analysis of the Capacitated Vehicle Routing Problem with Unsplit Demands," Operations Research, INFORMS, vol. 40(6), pages 1095-1106, December.
    • Handle: RePEc:inm:oropre:v:40:y:1992:i:6:p:1095-1106
    DOI: 10.1287/opre.40.6.1095
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.40.6.1095
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.40.6.1095?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. 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.
    2. Patrick Jaillet & Michael R. Wagner, 2008. "Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses," Operations Research, INFORMS, vol. 56(3), pages 745-757, June.
    3. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    4. 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.
    5. Langevin, André & Mbaraga, Pontien & Campbell, James F., 1996. "Continuous approximation models in freight distribution: An overview," Transportation Research Part B: Methodological, Elsevier, vol. 30(3), pages 163-188, June.

    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:40:y:1992:i:6:p:1095-1106. 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.