?
Click “Watch Now” to login or join the NVIDIA Developer Program.

WATCH NOW

GPU-Accelerated Tabu Search and Large Neighborhood Search to Solve Vehicle Routing Problem with Time Windows

Minhao Liu , WalmartLabs | Deyi Zhang, Walmart Labs

GTC 2020

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.