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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:
    Song, Maocan (Autor:in) / Cheng, Lin (Autor:in)

    Erschienen in:

    Transportation Letters ; 15 , 8 ; 823-833


    Erscheinungsdatum :

    2023-09-14


    Format / Umfang :

    11 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Unbekannt