Vehicle Routing Problem (VRP) is a combinatorial optimization problem concerning the assignment of a fleet of vehicles to deliver goods from a central depot to multiple geographically distributed customers, each with specified demand requirements. The problem determines optimal route sequences and vehicle assignments to minimize total transportation cost while respecting vehicle capacity constraints and the constraint that each customer is visited exactly once. VRP is a fundamental class in network optimization, generalizing the Traveling Salesman Problem and requiring consideration of multiple vehicles, capacity limitations, and routing feasibility. Table of Contents: - Problem definition: multi-vehicle distribution from central depot to customers with demand qj - Key decision elements: vehicle-to-route assignment and customer sequence within each route - Constraints: vehicle capacity Q, single visit requirement per customer, return-to-depot requirement - Problem variants: capacity-constrained vs uncapacitated, single vs multiple vehicles, time windows - Relationship to Traveling Salesman Problem: TSP emerges as special case when single vehicle and total demand ≤ Q - Network formulation: complete directed graph with depot (source and sink nodes) and customer nodes - Decision variables: binary assignment variables Xij indicating arc usage in the solution - Objective function: minimization of cost sum (Cij × Xij) across all arcs in selected routes - Flow conservation: ensuring each customer has exactly one incoming and one outgoing arc - Practical manifestation: delivery operations, pickup services, courier routing, distribution networks - Theoretical significance: NP-hard problem requiring heuristic solution methods - Solution approaches: enumeration, branch-and-bound, heuristic algorithms
Vehicle Routing Problem (VRP) is a combinatorial optimization problem concerning the assignment of a fleet of vehicles to deliver goods from a central depot to multiple geographically distributed cus…