vRP

The Vehicle Routing Problem (VRP) is a fundamental optimization problem in operations research that seeks the most efficient set of routes for a fleet of vehicles to service a group of customers from a common depot. Each customer has a demand; each vehicle has a capacity; the goal is to minimize total travel distance or cost while fulfilling all demands and adhering to constraints.

The classic capacitated VRP (CVRP) assumes identical vehicles with limited capacity. The VRP with time windows (VRPTW) adds constraints on service times at customers. Other variants include VRPPD, where pickups and deliveries must be matched, the Open VRP where routes do not necessarily return to the depot, multi-depot VRP, and VRP with profits. Distance metrics and objective functions may vary across formulations.

VRP is NP-hard even in its simplest form, so exact solutions are generally feasible only for small instances. In practice, researchers employ exact methods such as integer linear programming formulations with branch-and-cut, as well as specialized solvers. For larger or more complex instances, heuristic and metaheuristic approaches are common, including Clarke–Wrey savings, sweep algorithms, tabu search, genetic algorithms, simulated annealing, ant colony optimization, and various hybrid methods.

The VRP has broad applications in logistics, distribution, and transportation planning, including delivery services, e-commerce fulfillment, waste collection, school bus routing, and ride-sharing. It also informs emerging areas such as drone delivery and last-mile optimization. The problem features standard benchmark instances, such as Solomon’s time-window datasets for VRPTW and numerous CVRP datasets, which guide the development and assessment of solution methods.