Improving the Efficiency of Stochastic Vehicle Routing: A Partial Lagrange Multiplier Method

被引:50
作者
Cao, Zhiguang [1 ]
Guo, Hongliang [2 ]
Zhang, Jie [2 ]
Niyato, Dusit [2 ]
Fastenrath, Ulrich [3 ]
机构
[1] Nanyang Technol Univ, Future Mobil Res Lab, Singapore 639798, Singapore
[2] Nanyang Technol Univ, Sch Comp Engn, Singapore 639798, Singapore
[3] BMW Grp, D-85748 Munich, Germany
关键词
Mixed-integer linear programming (MILP); partial Lagrange multiplier; stochastic vehicle routing; total unimodularity; TIME; PATH;
D O I
10.1109/TVT.2015.2480964
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
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.
引用
收藏
页码:3993 / 4005
页数:13
相关论文
共 45 条
[1]  
Abraham I, 2012, LECT NOTES COMPUT SC, V7501, P24, DOI 10.1007/978-3-642-33090-2_4
[2]  
[Anonymous], 2012, Yahoo News
[3]  
[Anonymous], 2012, 1 7 BILLION CARS ROA
[4]  
[Anonymous], 2007, LECT NOTES EE364B
[5]  
[Anonymous], 2009, CONVEX OPTIMIZATION
[6]  
[Anonymous], 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13)
[7]   The volume algorithm: producing primal solutions with a subgradient method [J].
Barahona, F ;
Anbil, R .
MATHEMATICAL PROGRAMMING, 2000, 87 (03) :385-399
[8]  
Cao Z, 2014, 2014 IEEE 17TH INTERNATIONAL CONFERENCE ON INTELLIGENT TRANSPORTATION SYSTEMS (ITSC), P1045, DOI 10.1109/ITSC.2014.6957826
[9]   Optimal routing for maximizing the travel time reliability [J].
Fan, Yueyue ;
Nie, Yu .
NETWORKS & SPATIAL ECONOMICS, 2006, 6 (3-4) :333-344
[10]   Arriving on time [J].
Fan, YY ;
Kalaba, RE ;
Moore, JE .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2005, 127 (03) :497-513