查看文章

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 …