Glossary · approach
Capacitated Vehicle Routing
Designing minimum-cost vehicle routes that start and end at a single depot, visit each customer exactly once, with total demand per route not exceeding vehicle capacity.
Capacitated Vehicle Routing ProblemCVRPTruck Dispatching Problem
The Capacitated Vehicle Routing Problem (CVRP) is the problem of designing the minimum-cost set of vehicle routes that (a) start and end at a single depot, (b) visit each customer exactly once, and (c) keep the total demand on each route at or below the vehicle's capacity. It has no time windows — that extension is VRPTW. The cost is usually total distance, total time, or a combination of fuel and driver wage. CVRP is NP-hard and is the canonical ancestor of the entire VRP family, opened by Dantzig and Ramser (1959) as 'The Truck Dispatching Problem'. The standard reference book is Toth and Vigo (2014). Practical solution methods range from the classical Clarke-Wright savings heuristic (1964) — still benchmark-quality on moderate instances — through 2-opt and Or-opt improvement, modern branch-and-cut-and-price exact algorithms (Fukasawa et al. 2006), and Adaptive Large Neighborhood Search (ALNS) metaheuristics.
Örnek
A regional distributor delivers daily from one depot to 80 customers, each with a known kg demand; vehicles carry 2 tonnes; the question is how many vehicles dispatch, which customers on each, and in what order to minimise total kilometres.