IDEAS home Printed from
   My bibliography  Save this article

Routing Optimization Under Uncertainty


  • Patrick Jaillet

    () (Department of Electrical Engineering and Computer Science, Laboratory for Information and Decision Systems, Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Jin Qi

    () (Department of Industrial Engineering and Logistics Management, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong)

  • Melvyn Sim

    () (Department of Decision Sciences, NUS Business School, National University of Singapore, Singapore 119077)


We consider a class of routing optimization problems under uncertainty in which all decisions are made before the uncertainty is realized. The objective is to obtain optimal routing solutions that would, as much as possible, adhere to a set of specified requirements after the uncertainty is realized. These problems include finding an optimal routing solution to meet the soft time window requirements at a subset of nodes when the travel time is uncertain, and sending multiple capacitated vehicles to different nodes to meet the customers’ uncertain demands. We introduce a precise mathematical framework for defining and solving such routing problems. In particular, we propose a new decision criterion, called the Requirements Violation (RV) Index , which quantifies the risk associated with the violation of requirements taking into account both the frequency of violations and their magnitudes whenever they occur. The criterion can handle instances when probability distributions are known, and ambiguity when distributions are partially characterized through descriptive statistics such as moments. We develop practically efficient algorithms involving Benders decomposition to find the exact optimal routing solution in which the RV Index criterion is minimized, and we give numerical results from several computational studies that show the attractive performance of the solutions.

Suggested Citation

  • Patrick Jaillet & Jin Qi & Melvyn Sim, 2016. "Routing Optimization Under Uncertainty," Operations Research, INFORMS, vol. 64(1), pages 186-200, February.
  • Handle: RePEc:inm:oropre:v:64:y:2016:i:1:p:186-200

    Download full text from publisher

    File URL:
    Download Restriction: no


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

    Cited by:

    1. repec:eee:ejores:v:267:y:2018:i:1:p:288-303 is not listed on IDEAS


    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:64:y:2016:i:1:p:186-200. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc). General contact details of provider: .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.