Improving the efficiency of stochastic vehicle routing: A partial Lagrange multiplier method
Publication Type
Journal Article
Publication Date
9-2015
Abstract
More realistic than deterministic vehicle routing, stochastic vehicle routing considers uncertainties in traffic. Its two representative optimization models are the probability tail (PT) and the stochastic shortest path problem with delay excess penalty (SSPD), which can be approximately solved by expressing them as mixed-integer linear programming (MILP) problems. The traditional method to solve these two MILP problems, i.e., branch and bound (B&B), suffers from exponential computation complexity because of integer constraints. To overcome this computation inefficiency, we propose a partial Lagrange multiplier method. It benefits from the total unimodularity of the incidence matrix in the models, which guarantees an optimal integer solution by only solving a linear programming (LP) problem. Thus, this partial Lagrange multiplier problem can be further solved using the subgradient method, and the proposed method can guarantee polynomial computation complexity. Moreover, we theoretically prove the convergence and the efficiency, which are also assessed by the experiments on three different scales of graphs (road networks): small scale, medium scale, and large scale. More importantly, the experimental results on the Beijing road network with real traffic data show that our method can efficiently solve the time-dependent routing problem. Additionally, the implementation on the navigation system based on the Singapore road network further confirms that our method can be applied to efficiently solve the real-world stochastic vehicle routing problem.
Keywords
mixed-integer linear programming (MILP), partial Lagrange multiplier, stochastic vehicle routing, total unimodularity
Discipline
Dynamical Systems | Electrical and Computer Engineering | Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms
Research Areas
Intelligent Systems and Optimization
Publication
IEEE Transactions on Vehicular Technology
Volume
65
Issue
6
First Page
3993
Last Page
4005
ISSN
0018-9545
Identifier
10.1109/TVT.2015.2480964
Publisher
Institute of Electrical and Electronics Engineers
Citation
CAO, Zhiguang; GUO Hongliang; ZHANG Jie; NIYATO Dusit; and FASTENRATH Ulrich.
Improving the efficiency of stochastic vehicle routing: A partial Lagrange multiplier method. (2015). IEEE Transactions on Vehicular Technology. 65, (6), 3993-4005.
Available at: https://ink.library.smu.edu.sg/sis_research/8183
Copyright Owner and License
Authors