Search

Travel times in real-world transportation networks are affected by many disruptions. When we conduct the network design optimization, the traffic condition and its resulting travel time variability should be taken into account. However, most of the previous network design optimizations adopted the lengths or expected travel times of links. Based on travel time means and standard deviations, we develop an arc-based model that is a nonlinear and concave integer program. By the Dantzig-Wolfe reformulation, we transform it into an equivalent column-based model that is an integer linear program with a large number of variables. Based on the column-based model, we develop a hybrid method based on column generation and Lagrangian relaxation. The restricted master problem can be settled by the linear programming solvers. The pricing subproblems incorporate independent reliable shortest path problems and a knapsack problem. In numerical experiments, the proposed method can generate feasible solutions with good integrality gaps. [ABSTRACT FROM AUTHOR]

We study the capacitated arc routing problem in the state-space-time network. A multi-commodity network flow model is formulated in the state-space-time network. Two Lagrangian relaxation-based decomposition methods are developed to tackle this problem. By dualizing the coupling constraints to the objective function, the Lagrangian relaxed problem (LR) can be decomposed into several routing subproblems in the state-space-time network. Then we extend quadratic penalty terms to the LR and obtain an augmented Lagrangian relaxed problem (ALR). By applying the alternating direction method of multipliers and linearization techniques, we decompose the ALR into a sequence of routing subproblems. We solve these subproblems of LR and ALR by a time-dependent dynamic programming algorithm. Feasible solutions are produced according to the result of the LR or ALR. The Lagrangian multipliers are updated by the subgradient optimization method. We implement the proposed methods in three networks, showing that the ALR-based method has better performance. [ABSTRACT FROM AUTHOR]

This paper concentrates on the mean-standard deviation shortest path problem, which is an important extension of traditional shortest path problem. Due to the standard deviation term, the general formulation of this problem is nonlinear and concave. We transform this formulation into a mixed-integer conic quadratic program and develop a generalized Benders decomposition approach. The Benders master problem is a continuous conic quadratic program about travel time mean and standard deviation. The subproblem is a least expected travel time path problem with the variance limit. At each iteration, the subproblem generates a generalized Benders optimality cut for the relaxed Benders master problem. The relaxed Benders master problem provides an ascending lower bound and the subproblem produces a feasible solution to update the upper bound. In the numerical experiments, all instances in four transportation networks are solved optimally. This paper provides a novel solving scheme for the mean-standard deviation shortest path problem. [ABSTRACT FROM AUTHOR]