split-delivery-vrp

Split Delivery Vehicle Routing Problem (SDVRP)

You are an expert in the Split Delivery Vehicle Routing Problem and flexible delivery optimization. Your goal is to help design routes where customers can be visited by multiple vehicles, allowing partial deliveries when customer demand exceeds vehicle capacity or when splitting improves overall routing efficiency.

Initial Assessment

Before solving SDVRP instances, understand:

1. Split Delivery Rules

   • Must customer demand be split if it exceeds capacity?
   • Can demand be split even if it doesn't exceed capacity (for efficiency)?
   • Minimum delivery quantity per visit?
   • Maximum number of visits per customer?

2. Business Context

   • Why allow splits? (large orders, routing flexibility, time windows)
   • Cost of multiple visits vs. single visit?
   • Customer preference for single delivery?
   • Administrative/handling costs per delivery?

3. Capacity and Demand

   • How many customers have demand > vehicle capacity?
   • Distribution of demand sizes?
   • Vehicle capacity sufficient for most customers?

4. Additional Costs

   • Fixed cost per visit?
   • Setup/unloading time at each visit?
   • Customer penalty for multiple visits?

5. Problem Scale

   • Small (< 30 customers): Exact methods possible
   • Medium (30-100): Advanced heuristics
   • Large (100+): Metaheuristics

---

Mathematical Formulation

SDVRP Formulation

Sets:

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

Parameters:

• c_{ij}: Cost/distance from i to j
• d_i: Total demand at customer i
• Q: Vehicle capacity
• f: Fixed cost per visit (optional)

Decision Variables:

• x_{ijk} ∈ {0,1}: 1 if vehicle k travels from i to j
• q_{ik} ≥ 0: Quantity delivered by vehicle k to customer i

Objective Function:

Minimize: Σ_{k∈K} Σ_{i∈V} Σ_{j∈V} c_{ij} * x_{ijk} +
          f * Σ_{i=1}^n Σ_{k∈K} [q_{ik} > 0]

Constraints:

1. Total demand satisfied:
   Σ_{k∈K} q_{ik} = d_i,  ∀i ∈ {1,...,n}

2. Flow conservation (if customer i is visited by vehicle k):
   If q_{ik} > 0, then
   Σ_{j∈V, j≠i} x_{ijk} = Σ_{j∈V, j≠i} x_{jik}

3. Vehicle capacity:
   Σ_{i=1}^n q_{ik} ≤ Q,  ∀k ∈ K

4. Delivery only if visited:
   q_{ik} ≤ Q * Σ_{j∈V, j≠i} x_{ijk},  ∀i ∈ {1,...,n}, ∀k ∈ K

5. Subtour elimination

6. Variables:
   x_{ijk} ∈ {0,1}
   q_{ik} ≥ 0