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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2015-02-11


    Size :

    21 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English






    Dial-a-Ride Services

    Community Transport Association | British Library Conference Proceedings | 1993


    Some approaches on checkpoint dial-a-ride problems

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


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

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