GTC 2020: GPU-Accelerated Tabu Search and Large Neighborhood Search to Solve Vehicle Routing Problem with Time Windows
After clicking “Watch Now” you will be prompted to login or join.
Click “Watch Now” to login or join the NVIDIA Developer Program.
GPU-Accelerated Tabu Search and Large Neighborhood Search to Solve Vehicle Routing Problem with Time Windows
Minhao Liu , WalmartLabs | Deyi Zhang, Walmart Labs
Learn various metaheuristic optimization algorithms to solve large-scale vehicle routing problems with time windows with GPU programming. We'll introduce a Tabu Search algorithm designed to exploit the parallelism in neighborhood search and its OpenACC-based implementation that applies deep-copy and manages complex data types. Then we'll introduce an Adaptive Large Neighborhood Search algorithm in which various combinations of destroy-and-repair heuristics are adaptively applied during the optimization process for the exploration of a substantially wider neighborhood of the solution space. We'll also describe the ALNS implementation using CUDA C and its running test on an NVIDIA DGX Station.