A generalized Benders decomposition approach for the mean-standard deviation shortest path problem

ABSTRACT

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.

KEYWORDS:

• Reliable shortest path problem
• Mean-standard deviation objective
• generalized Benders decomposition
• Lagrangian relaxation

Acknowledgments

This research is supported by the National Natural Science Foundation of China (No. 52172318 and No. 52131203). We acknowledge Khani and Boyles (2015) for providing the transportation networks with travel time means and standard deviations. 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 [52172318]; National Natural Science Foundation of China [52131203].