Routing Optimization Under Uncertainty

• 成果类型: Article; Proceedings Paper
• 署名作者: Jaillet, Patrick; Qi, Jin; Sim, Melvyn
• 署名单位: Massachusetts Institute of Technology (MIT); Hong Kong University of Science & Technology; National University of Singapore
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2015.1462
• 发表日期: 2016
• 页码: 186-200
• 关键词: traveling salesman problem; soft time windows; shortest-path problem; stochastic travel; INTERVAL DATA; Demand uncertainty; generation; algorithm; deadlines; price

摘要

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.