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

Copyright Owner and License

Authors

This document is currently not available here.

Share

COinS