Vehicle Routing Problem (VRP) - Handbook

Type: IP (Integer Programming)

This handbook explains the Vehicle Routing sample problem in the LP Black Box platform.

The Vehicle Routing Problem (VRP) determines optimal routes for a fleet of vehicles.

---

The Problem

Scenario

A delivery company has 1 vehicle with capacity 50, and must deliver to 4 customers.

Customer	Demand	Distance from Depot
Customer A	15	10 km
Customer B	20	15 km
Customer C	10	8 km
Customer D	25	20 km

Vehicle Capacity: 50 units
Max Distance: 100 km

Your Goal

Maximize total deliveries (or minimize distance) while respecting vehicle capacity and max distance.

The Variables

Variable	Type	Meaning
deliver_A	Integer ≥ 0	Units delivered to Customer A
deliver_B	Integer ≥ 0	Units delivered to Customer B
deliver_C	Integer ≥ 0	Units delivered to Customer C
deliver_D	Integer ≥ 0	Units delivered to Customer D
route_A	Binary	Visit Customer A? (0 or 1)
route_B	Binary	Visit Customer B?
route_C	Binary	Visit Customer C?
route_D	Binary	Visit Customer D?

The Constraints

1. Vehicle Capacity: Total deliveries cannot exceed 50

   • deliver_A + deliver_B + deliver_C + deliver_D ≤ 50

2. Distance Limit: Total route distance ≤ 100 km

   • 10×route_A + 15×route_B + 8×route_C + 20×route_D ≤ 100

3. Delivery Requirement: Can only deliver if visiting (linking constraint)

   • deliver_A ≤ 50 × route_A
   • deliver_B ≤ 50 × route_B
   • deliver_C ≤ 50 × route_C
   • deliver_D ≤ 50 × route_D

4. Minimum Deliveries: Must deliver to at least 3 customers

   • route_A + route_B + route_C + route_D ≥ 3

5. Non-negativity: deliver_X ≥ 0

The Objective

Maximize total demand served:

• 15×deliver_A + 20×deliver_B + 10×deliver_C + 25×deliver_D

Or Minimize distance:

• 10×route_A + 15×route_B + 8×route_C + 20×route_D

---

How to Use

Step 1: Load the Sample

Select Vehicle Routing from the dropdown.

Step 2: Solve

The solver determines which customers to serve and how much to deliver to each.

Step 3: Interpret Results

• Binary variables = 1 means "visit this customer"
• Integer variables show delivery quantities

---

Try It Yourself

• Add a second vehicle
• Change vehicle capacity to 30
• Add constraint requiring Customer A must be served
• Switch to minimize distance objective

---

VRP Variants

Variant	Description
CVRP	Capacitated VRP (vehicle capacity limits)
VRPTW	VRP with Time Windows
VRP with Pickup	Delivery + Pickup
Multi-depot VRP	Multiple warehouses

---

Real-World Applications

• Delivery Logistics: UPS, FedEx route planning
• School Bus Routing: Optimal bus routes
• Street Sweeping: Efficient cleaning routes
• Mail Delivery: Postal route optimization
• Field Service: Technician dispatch

---

This demonstrates how Integer Programming solves routing and delivery optimization.