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

Computational Approaches to Stochastic Vehicle Routing Problems

Author

Listed:
  • Dimitris Bertsimas

    (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Philippe Chervi

    (Service Technique des Systèmes Navals, 75015 Paris, France)

  • Michael Peterson

    (School of Public and Environmental Affairs, Indiana University, Bloomington, Indiana 47405)

Abstract

We report computational test results for several graph-based a priori heuristics for the Euclidean plane versions of two well-known stochastic optimization problems, the probabilistic traveling salesman problem (PTSP) and the probabilistic (or stochastic) vehicle routing problem (PVRP). These heuristics are termed a priori because they design vehicle routes prior to realization of demands. Our tests compare the quality of such solutions to sample averages of a posteriori solutions of the deterministic realizations---the underlying TSPs and VRPs. Our results indicate that the simplest implementations give average cost performance within 5% of the latter, while the best implementations show a gap of only about 1%. Since running times are modest, we conclude that the a priori approaches offer a large potential benefit to the practitioner seeking to obtain good performance in a situation where solving repeated deterministic instances of the TSP or VRP is impractical or otherwise undesirable.

Suggested Citation

  • Dimitris Bertsimas & Philippe Chervi & Michael Peterson, 1995. "Computational Approaches to Stochastic Vehicle Routing Problems," Transportation Science, INFORMS, vol. 29(4), pages 342-352, November.
    • Handle: RePEc:inm:ortrsc:v:29:y:1995:i:4:p:342-352
    DOI: 10.1287/trsc.29.4.342
    as

    Download full text from publisher

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

    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:29:y:1995:i:4:p:342-352. 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.