期刊
TRANSPORTATION SCIENCE
卷 50, 期 2, 页码 608-626出版社
INFORMS
DOI: 10.1287/trsc.2014.0581
关键词
vehicle routing; travel time uncertainty; stochastic programming; robust optimization; branch-and-cut
资金
- Singapore-MIT Alliance for Research and Technology (SMART) Center for Future Mobility (FM)
We consider the vehicle routing problem with deadlines under travel time uncertainty in the contexts of stochastic and robust optimization. The problem is defined on a directed graph where a fleet of vehicles is required to visit a given set of nodes and deadlines are imposed at a subset of nodes. In the stochastic vehicle routing problem with deadlines (SVRP-D), the probability distribution of the travel times is assumed to be known and the problem is solved to minimize the sum of probability of deadline violations. In the robust vehicle routing problem with deadlines (RVRP-D), however, the exact probability distribution is unknown but it belongs to a certain family of distributions. The objective of the problem is to optimize a performance measure, called lateness index, which represents the risk of violating the deadlines. Although novel mathematical frameworks have been proposed to solve these problems, the size of the problem that those approaches can handle is relatively small. Our focus in this paper is the computational aspects of the two solution schemes. We introduce formulations that can be applied for the problems with multiple capacitated vehicles and discuss the extensions to the cases of incorporating service times and soft time windows. Furthermore, we develop an algorithm based on a branch-and-cut framework to solve the problems. The experiments show that these approaches provide substantial improvements in computational efficiency compared to the approaches in the literature. Finally, we provide a computational comparison to evaluate the solution quality of the SVRP-D and the RVRP-D. The results show that the RVRP-D produces solutions that are very competitive to those obtained by the SVRP-D with a large number of scenarios, whereas much less sensitive to the distributional uncertainty.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据