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.
GPU-Accelerated Tabu Search Algorithm for Dial-A-Ride Problem
2018-11-01
572780 byte
Conference paper
Electronic Resource
English
A Granular Tabu Search algorithm for the Dial-a-Ride Problem
Online Contents | 2013
|A Granular Tabu Search algorithm for the Dial-a-Ride Problem
Elsevier | 2013
|A tabu search heuristic for the static multi-vehicle dial-a-ride problem
Elsevier | 2002
|A tabu search heuristic for the static multi-vehicle dial-a-ride problem
Online Contents | 2003
|Combining multicriteria analysis and tabu search for dial-a-ride problems
Online Contents | 2013
|