Dial-a-ride problems consist in designing efficient vehicle routes for door-to-door passenger transportation while ensuring time-windows, maximum user ride time limits, and maximum route duration limits. Much progress has been made on algorithms to solve DARP. However, many of these algorithms are computationally complex, and often too slow for real-world scenarios. To address this issue, this paper presents a GPU-accelerated tabu search algorithm (G-TS) for the dial-a-ride problem (DARP), in which three new GPU kernels are introduced: (i) parallel construction heuristic, (ii) parallel neighborhood generation, and (iii) parallel neighborhood evaluation. These kernels are designed carefully to reduce CPU-GPU communication latency while maximizing overall speedup. Numerical experiments have been carried out on various standard DARP instances to investigate the performance and convergence of G-TS on an Nvidia Tesla P100 GPU. It is observed that the proposed G-TS algorithm performs 31 times faster than single-core CPU-based tabu search imnlementation on Iarge-scale DARP instances.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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




    Publication date :

    2018-11-01


    Size :

    572780 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    A Granular Tabu Search algorithm for the Dial-a-Ride Problem

    Kirchler, Dominik | Online Contents | 2013


    A Granular Tabu Search algorithm for the Dial-a-Ride Problem

    Kirchler, Dominik / Wolfler Calvo, Roberto | Elsevier | 2013


    A tabu search heuristic for the static multi-vehicle dial-a-ride problem

    Cordeau, Jean-François / Laporte, Gilbert | Elsevier | 2002