This paper aims at solving the stochastic shortest path problem in vehicle routing, the objective of which is to determine an optimal path that maximizes the probability of arriving at the destination before a given deadline. To solve this problem, we propose a data-driven approach, which directly explores the big data generated in traffic. Specifically, we first reformulate the original shortest path problem as a cardinality minimization problem directly based on samples of travel time on each road link, which can be obtained from the GPS trajectory of vehicles. Then, we apply an $\ell_{1}$- norm minimization technique and its variants to solve the cardinality problem. Finally, we transform this problem into a mixed-integer linear programming problem, which can be solved using standard solvers. The proposed approach has three advantages over traditional methods. First, it can handle various or even unknown travel time probability distributions, while traditional stochastic routing methods can only work on specified probability distributions. Second, it does not rely on the assumption that travel time on different road segments is independent of each other, which is usually the case in traditional stochastic routing methods. Third, unlike other existing methods which require that deadlines must be larger than certain values, the proposed approach supports more flexible deadlines. We further analyze the influence of important parameters to the performances, i.e., accuracy and time complexity. Finally, we implement the proposed approach and evaluate its performance based on a real road network of Munich city. With real traffic data, the results show that it outperforms traditional methods.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Finding the Shortest Path in Stochastic Vehicle Routing: A Cardinality Minimization Approach


    Beteiligte:
    Cao, Zhiguang (Autor:in) / Guo, Hongliang (Autor:in) / Zhang, Jie (Autor:in) / Niyato, Dusit (Autor:in) / Fastenrath, Ulrich (Autor:in)


    Erscheinungsdatum :

    01.06.2016


    Format / Umfang :

    2260957 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Optimal Stochastic Package Delivery Planning with Deadline: A Cardinality Minimization in Routing

    Sawadsitang, Suttinee / Jiang, Siwei / Niyato, Dusit et al. | IEEE | 2017


    Method for calculating shortest vehicle finding path in parking lot

    WANG JIAN / CHANG WENFEI | Europäisches Patentamt | 2015

    Freier Zugriff

    Quantum computing to solve scenario-based stochastic time-dependent shortest path routing

    Dixit, Vinayak V. / Niu, Chence / Rey, David et al. | Taylor & Francis Verlag | 2024

    Freier Zugriff