Vehicle Routing Problem (VRP)

The foundational extension of the classic VRP where each vehicle has a maximum load capacity that cannot be exceeded. The total demand of all customers on a route must be less than or equal to the vehicle's capacity.

• Constraint: Vehicle capacity is the binding limitation.
• Objective: Minimize total distance while respecting weight/volume limits.
• Real-world example: A beverage distributor with trucks that can hold 400 cases. The algorithm must cluster stops so no truck is overloaded.
• Complexity driver: The problem becomes a simultaneous clustering and routing challenge, often solved with savings algorithms or set partitioning.

Introduces hard or soft temporal constraints where each customer must be serviced within a specific time interval. Arriving early requires waiting; arriving late incurs a penalty or is infeasible.

• Hard time windows: Late arrival is not permitted.
• Soft time windows: Late arrival is allowed but penalized in the objective function.
• Real-world example: Grocery delivery where customers select a 2-hour delivery slot. The algorithm must sequence stops to honor all commitments.
• Solution approach: Often tackled with Large Neighborhood Search (LNS) or column generation due to the tight scheduling constraints.

Goods must be transported between paired pickup and delivery locations, with the pickup necessarily preceding the delivery on the same vehicle's route. This enforces precedence constraints.

• Pairing constraint: A single vehicle must handle both the pickup and the corresponding delivery.
• Precedence constraint: The pickup must occur before the delivery in the route sequence.
• Real-world example: A ride-hailing service matching drivers to passengers, or a courier moving a package from a warehouse to a residential address.
• Related variant: The Dial-a-Ride Problem (DARP) applies this to passenger transport with user-specific time windows and ride-time limits.

The fleet is not uniform. Vehicles have different capacities, fixed costs, variable costs per kilometer, and operational characteristics (e.g., refrigeration, lift gates). The optimization must simultaneously assign the right vehicle type to the right set of stops.

• Fixed cost: A one-time cost for deploying a vehicle, regardless of distance.
• Variable cost: A cost per unit of distance traveled, which differs by vehicle type.
• Real-world example: A logistics provider with a mixed fleet of cargo bikes, sprinter vans, and box trucks. The algorithm decides which vehicle type serves which urban delivery zone.
• Objective trade-off: Minimizing total cost requires balancing the higher fixed cost of large vehicles against the higher per-stop efficiency they provide.

Unlike static variants where all orders are known in advance, new orders arrive continuously while vehicles are already en route. The algorithm must re-optimize the plan in real-time without disrupting committed deliveries.

• Re-optimization trigger: New order arrival, vehicle delay, or traffic incident.
• Commitment strategy: Some orders are locked and cannot be reassigned; others are flexible.
• Real-world example: A food delivery platform receiving orders throughout the evening. The dispatcher must insert new orders into existing driver routes without violating promised delivery times.
• Enabling technology: Requires a streaming data architecture and fast heuristics that can re-solve the problem in seconds.

Real-world routing is never about a single metric. This formulation simultaneously optimizes conflicting objectives—typically cost, service level, and sustainability—producing a set of trade-off solutions known as the Pareto frontier.

• Common objectives: Minimize total distance, minimize number of vehicles, maximize on-time delivery percentage, minimize CO2 emissions.
• Pareto frontier: A set of non-dominated solutions where improving one objective necessarily degrades another. No single solution is universally best.
• Real-world example: A retailer balancing the cost of same-day delivery against the carbon footprint of deploying additional vehicles. The decision-maker selects a point on the Pareto frontier based on strategic priorities.
• Solution approach: Often uses evolutionary algorithms like NSGA-II that can maintain a diverse population of non-dominated solutions.