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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:
    Song, Maocan (author) / Cheng, Lin (author)

    Published in:

    Transportation Letters ; 15 , 8 ; 823-833


    Publication date :

    2023-09-14


    Size :

    11 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    Unknown