Routing Optimization Under Uncertainty

Patrick Jaillet (), Jin Qi () and Melvyn Sim ()
Additional contact information
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

Operations Research, 2016, vol. 64, issue 1, 186-200

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

Keywords: vehicle routing; uncertain travel time; robust optimization (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (37)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1462 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:1:p:186-200

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().