Highlights A bicriterion shortest path problem considers a general nonlinear cost. Applications are identified in which solving such a problem plays an important role. The problem is linearized to a series of constrained shortest path problems. A specialized algorithm is developed to solve these subproblems. Solutions are characterized under special conditions.

    Abstract A bicriterion shortest path problem with a general nonadditive cost seeks to optimize a combination of two path costs, one of which is evaluated by a nonlinear function. This paper first identifies a number of emerging transportation applications for which such a shortest path problem might be considered a core subproblem. We propose to first approximate the general nonlinear cost function with a piecewise linear counterpart, and then solve each linear subproblem sequentially. A specialized algorithm is developed to solve the subproblems, which makes use of the efficient path set (or the convex hull) to update upper and lower bounds of the original problem. Conditions under which the solution to a subproblem must belong to the efficient path set are specified. Accordingly, we show that the optimal path must be efficient if the nonlinear cost function is concave. If the optimal path to a subproblem is not efficient, partial path enumeration, implemented using a simple K-shortest path ranking procedure, is conducted to close the gap. The proposed algorithm includes strategies aiming to expedite path enumeration by using upper bounds derived from the efficient path set. Numerical experiments are conducted to demonstrate correctness and effectiveness of the proposed algorithm.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Bicriterion shortest path problem with a general nonadditive cost


    Beteiligte:
    Chen, Peng (Autor:in) / Nie, Yu (Marco) (Autor:in)


    Erscheinungsdatum :

    2013-01-01


    Format / Umfang :

    17 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    The Traffic Equilibrium Problem with Nonadditive Path Costs

    Gabriel, S. A. / Bernstein, D. | British Library Online Contents | 1997


    The Traffic Equilibrium Problem with Nonadditive Path Costs

    Gabriel, Steven A. | Online Contents | 1997


    A microeconomic interpretation for the system optimal traffic assignment problem with nonadditive path cost

    de Grange, Louis / Muñoz, Juan Carlos / Troncoso, Rodrigo | Taylor & Francis Verlag | 2014


    Approach for Bicriterion Dynamic User Equilibrium Problem

    Lu, Chung-Cheng | Online Contents | 2009