Accelerating the performance of optimization algorithms is crucial for many day-to-day applications. Mobility-on-demand is one such application that is transforming urban mobility by offering reliable and convenient on-demand door-to-door transportation at any time. Dial-a-ride problem (DARP) is an underlying optimization problem in the operational planning of mobility-on-demand systems. The primary objective of DARP is to design routes and schedules to serve passenger transportation requests with high-level user comfort. DARP often arises in dynamic real-world scenarios, where rapid route planning is essential. The traditional CPU-based algorithms are generally too slow to be useful in practice. Since customers expect quick response for their mobility requests, there has been a growing interest in fast solution methods. Therefore, in this paper, we introduce a GPU-based solution methodology for the dial-a-ride problem to produce good solutions in a short time. Specifically, we develop a GPU framework to accelerate time-critical neighborhood exploration of local search operations under the guidance of metaheuristics such as tabu search and variable neighborhood search. Besides, we propose device-oriented optimization strategies to enhance the utilization of a current-generation GPU architecture (Tesla P100). We report speedup achieved by our GPU approach when compared to its classical CPU counterpart, and the effect of each device optimization strategy on computational speedup. Results are based on standard test instances from the literature. Ultimately, the proposed GPU methodology generates better solutions in a short time when compared to the existing sequential approaches.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A Generic GPU-Accelerated Framework for the Dial-A-Ride Problem




    Publication date :

    2021-10-01


    Size :

    3886009 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    GPU-Accelerated Tabu Search Algorithm for Dial-A-Ride Problem

    Pandi, Ramesh Ramasamy / Ho, Song Guang / Nagavarapu, Sarat Chandra et al. | IEEE | 2018


    Dial-a-Ride

    Jørgensen, Rene Munk | BASE | 2003

    Free access

    Dial-a-Ride Services

    Community Transport Association | British Library Conference Proceedings | 1993



    The dial-a-ride problem: models and algorithms

    Cordeau, Jean-François / Laporte, Gilbert | Springer Verlag | 2007