Highlights A new distributed VNS is proposed for solving large scale DARPs. The proposal partitionates the requests into several sets to optimize the solution in parallel. The algorithm is tested on demanding scenarios in the city of San Francisco. The results have been compared against other distributed and sequential algorithms. According to the statistical tests, the proposal has obtained the best results.

    Abstract These days, transportation and logistic problems in large cities are demanding smarter transportation services that provide flexibility and adaptability. A possible solution to this arising problem is to compute the best routes for each new scenario. In this problem, known in the literature as the dial-a-ride problem, a number of passengers are transported between pickup and delivery locations trying to minimize the routing costs while respecting a set of prespecified constraints. This problem has been solved in the literature with several approaches from small to medium sized problems. However, few efforts have dealt with large scale problems very common in massive scenarios (big cities or highly-populated regions). In this study, a new distributed algorithm based on the partition of the requests space and the combination of the routes is presented and tested on a set of 24 different scenarios of a large-scale problem (up to 16,000 requests or 32,000 locations) in the city of San Francisco. The results show that, not only the distributed algorithm is able to solve large problem instances that the corresponding sequential algorithm is unable to solve in a reasonable time, but also to have an average improvement of 9% in the smaller problems. The results have been validated by means of statistical procedures proving that the distributed algorithm can be an effective way to solve high dimensional dial-a-ride problems.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A distributed VNS algorithm for optimizing dial-a-ride problems in large-scale scenarios


    Beteiligte:


    Erscheinungsdatum :

    2015-02-11


    Format / Umfang :

    21 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Solving large-scale dial-a-ride vehicle routing and scheduling problems

    Jaw, Jang-Jei | DSpace@MIT | 1984

    Freier Zugriff

    Some approaches on checkpoint dial-a-ride problems

    Pratelli, A. / Wessex Institute of Technology | British Library Conference Proceedings | 2002


    Dial-a-Ride Services

    Community Transport Association | British Library Conference Proceedings | 1993


    Proactive shuttle dispatching in large-scale dynamic dial-a-ride systems

    Tafreshian, Amirmahdi / Abdolmaleki, Mojtaba / Masoud, Neda et al. | Elsevier | 2021