Incorporating travel time means and standard deviations into transportation network design problem: a hybrid method based on column generation and Lagrangian relaxation

ABSTRACT

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.

KEYWORDS:

• Network design problem
• travel time variability
• mean-standard deviation objective
• column generation
• Lagrangian relaxation

Acknowledgments

This research is supported by the National Natural Science Foundation of China (No. 52172318 and 52131203). Additionally, we are also thankful to anonymous referees for their constructive feedbacks in leading to the current form of this article.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [52131203]; National Natural Science Foundation of China [52172318].