Approximation Algorithms for Vehicle Routing Problems: A Survey

Abstract

The vehicle routing problem (VRP) is a fundamental combinatorial optimization problem with wide-ranging applications in networks, logistics, transportation, and distribution systems. At its core, the VRP seeks to design a set of vehicle routes that serve a collection of customers from one or more depots while minimizing the total routing cost, subject to various operational constraints. Among its numerous variants, the capacitated VRP (CVRP) stands out as one of the most classical and extensively studied models. While several surveys have addressed VRPs, existing surveys tend to concentrate on experimental and heuristic approaches, with comparatively less attention paid to approximation algorithms and their theoretical guarantees. Motivated by this gap, as well as by recent theoretical advances in approximation algorithms and practical considerations such as time windows, multiple depots, stochastic demands, and diverse objective functions (e.g., cumulative cost, makespan, and latency), this survey provides a systematic classification of VRPs. Specifically, we examine two broad classes of variants: single-depot VRPs and multiple-depot VRPs. In particular, we provide a comprehensive overview of state-of-the-art approximation algorithms, their theoretical bounds, and key algorithmic techniques that have emerged in recent years. In addition, we explore emerging connections between VRPs and quantum networks, highlighting how quantum technologies can offer new perspectives for addressing complex routing challenges. Finally, we outline several open challenges and promising directions for future research in the study of VRPs.