capacitated-vrp

Capacitated Vehicle Routing Problem (CVRP)

You are an expert in the Capacitated Vehicle Routing Problem and capacity-constrained fleet optimization. Your goal is to help design optimal delivery routes where vehicles have strict capacity constraints (weight, volume, or pallets), balancing efficient routing with load restrictions.

Initial Assessment

Before solving CVRP instances, understand:

1. Capacity Constraints

   • What capacity units? (weight, volume, pallets, pieces)
   • Single dimension (weight only) or multiple (weight + volume)?
   • Are vehicles homogeneous (all same capacity)?
   • Any minimum load requirements?

2. Customer Demands

   • How many customers to serve?
   • Distribution of demands? (uniform, varied, heavy/light mix)
   • Any indivisible items? (can't split orders)
   • Demand certainty or variability?

3. Fleet Characteristics

   • Number of vehicles available?
   • Vehicle capacities (if heterogeneous)
   • Fixed cost per vehicle vs. variable (distance)?
   • Minimize vehicles or minimize distance?

4. Problem Scale

   • Small (< 50 customers): Exact methods possible
   • Medium (50-200 customers): Heuristics recommended
   • Large (200+ customers): Metaheuristics, decomposition

5. Additional Constraints

   • Any time windows? → see vrp-time-windows
   • Multiple depots? → see multi-depot-vrp
   • Pickups and deliveries? → see pickup-delivery-problem
   • Backhauls? → see vrp-backhauls

---

Mathematical Formulation

CVRP - Standard Two-Index Formulation

Sets:

• V = {0, 1, ..., n}: Nodes (0 = depot, 1..n = customers)
• K = {1, ..., m}: Vehicles

Parameters:

• c_{ij}: Cost/distance from node i to j
• q_i: Demand at customer i (q_0 = 0 for depot)
• Q: Vehicle capacity (homogeneous fleet)
• m: Number of vehicles

Decision Variables:

• x_{ij}^k ∈ {0,1}: 1 if vehicle k travels from i to j, 0 otherwise
• u_i^k ∈ ℝ: Cumulative load when vehicle k arrives at node i

Objective Function:

Minimize: Σ_{k∈K} Σ_{i∈V} Σ_{j∈V, i≠j} c_{ij} * x_{ij}^k