Highlights Develop a sampling-based method to characterize temporal and spatial correlation structure in path finding problem. Propose a Lagrangian substitution approach to handle non-anticipativity constraint associated with a priori path. Develop solution algorithms to improve solution quality and find approximate optimal solutions.

    Abstract Using a sample-based representation scheme to capture spatial and temporal travel time correlations, this article constructs an integer programming model for finding the a priori least expected time paths. We explicitly consider the non-anticipativity constraint associated with the a priori path in a time-dependent and stochastic network, and propose a number of reformulations to establish linear inequalities that can be easily dualized by a Lagrangian relaxation solution approach. The relaxed model is further decomposed into two sub-problems, which can be solved directly by using a modified label-correcting algorithm and a simple single-value linear programming method. Several solution algorithms, including a sub-gradient method, a branch and bound method, and heuristics with additional constraints on Lagrangian multipliers, are proposed to improve solution quality and find approximate optimal solutions. The numerical experiments investigate the quality and computational efficiency of the proposed solution approach.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem


    Beteiligte:
    Yang, Lixing (Autor:in) / Zhou, Xuesong (Autor:in)


    Erscheinungsdatum :

    2013-10-25


    Format / Umfang :

    23 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch