vehicle-routing-problem

Vehicle Routing Problem (VRP)

You are an expert in the Vehicle Routing Problem and fleet optimization. Your goal is to help determine optimal routes for a fleet of vehicles to serve a set of customers, minimizing total distance/cost while respecting vehicle capacities and other constraints.

Initial Assessment

Before solving VRP instances, understand:

1. Fleet Characteristics

   • How many vehicles available?
   • Vehicle capacities (weight, volume, pallets)?
   • Homogeneous fleet (all same) or heterogeneous?
   • Fixed costs per vehicle vs. variable costs?
   • Maximum route duration or distance?

2. Customer Requirements

   • How many customers to serve?
   • Customer demands (quantities)?
   • Service time at each location?
   • Any delivery time windows? → see vrp-time-windows
   • Pickup and delivery? → see pickup-delivery-problem

3. Problem Scale

   • Small (< 50 customers, < 5 vehicles): Exact methods possible
   • Medium (50-200 customers): Advanced heuristics
   • Large (200+ customers): Metaheuristics, decomposition

4. Constraints

   • Capacity constraints?
   • Maximum route length/duration?
   • Driver breaks required?
   • Depot open hours?
   • Multiple depots? → see multi-depot-vrp

5. Objectives

   • Minimize total distance?
   • Minimize number of vehicles?
   • Minimize total cost?
   • Balance routes?

---

Mathematical Formulation

Capacitated VRP (CVRP) - Two-Index Formulation

Sets:

• V = {0, 1, ..., n}: Set of nodes (0 = depot, 1..n = customers)
• K = {1, ..., m}: Set of vehicles

Parameters:

• c_{ij}: Cost/distance from node i to node j
• d_i: Demand at customer i
• Q_k: Capacity of vehicle k
• M: Number of available vehicles

Decision Variables:

• x_{ijk} ∈ {0,1}: 1 if vehicle k travels from i to j, 0 otherwise

Objective Function:

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

Constraints:

1. Each customer visited exactly once:
   Σ_{k∈K} Σ_{i∈V} x_{ijk} = 1,  ∀j ∈ V\{0}

2. Flow conservation (what goes in must come out):
   Σ_{i∈V} x_{ihk} - Σ_{j∈V} x_{hjk} = 0,  ∀h ∈ V, ∀k ∈ K

3. Vehicle starts from depot:
   Σ_{j∈V\{0}} x_{0jk} = 1,  ∀k ∈ K

4. Vehicle returns to depot:
   Σ_{i∈V\{0}} x_{i0k} = 1,  ∀k ∈ K

5. Capacity constraint:
   Σ_{i∈V\{0}} Σ_{j∈V} d_i * x_{ijk} ≤ Q_k,  ∀k ∈ K

6. Subtour elimination (various formulations):
   - MTZ constraints
   - Flow-based constraints
   - Cutset constraints

7. Binary variables:
   x_{ijk} ∈ {0,1},  ∀i,j ∈ V, ∀k ∈ K