Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching

TLDR

Vehicle routing research has largely focused on static problems, yet recent technological advances enable real‑time decision making using up‑to‑date routing data. The study aims to solve a dynamic courier dispatch problem in which customer requests with soft time windows are assigned in real time to a fleet of moving vehicles. To tackle this, the authors adapt a tabu search heuristic originally designed for static routing and parallelize it to boost computational speed. Experiments with varying request arrival rates show the parallel tabu search performs competitively against other heuristic methods.

Abstract

An abundant literature about vehicle routing and scheduling problems is available in the scientific community. However, a large fraction of this work deals with static problems where all data are known before the routes are constructed. Recent technological advances now create environments where decisions are taken quickly, using new or updated information about the current routing situation. This paper describes such a dynamic problem, motivated from courier service applications, where customer requests with soft time windows must be dispatched in real time to a fleet of vehicles in movement. A tabu search heuristic, initially designed for the static version of the problem, has been adapted to the dynamic case and implemented on a parallel platform to increase the computational effort. Numerical results are reported using different request arrival rates, and comparisons are established with other heuristic methods.