Vehicle Routing Problem (VRP)

The most fundamental extension where each vehicle has a maximum load capacity (e.g., weight, volume). The primary constraint is that the total demand of customers on a single route cannot exceed the vehicle's capacity.

• Key Challenge: Efficiently packing customer orders into vehicle routes.
• Example: A delivery van with a 1,000 kg limit servicing 50 retail stores.

Each customer must be serviced within a specified time interval [e_i, l_i]. A vehicle arriving early incurs waiting time; arriving late is infeasible.

• Hard vs. Soft Windows: Hard windows cannot be violated; soft windows incur a penalty cost for early/late service.
• Objective: Often minimizes a combination of total distance and waiting time.
• Application: Parcel delivery, technician dispatch, and meal delivery services.

Vehicles must transport goods from pickup locations to corresponding delivery locations. This introduces precedence constraints (pickup before delivery) and pairing constraints (same vehicle must handle both).

• Dial-a-Ride Problem (DARP): A VRPPD variant for transporting people, with added constraints for passenger ride time and vehicle occupancy.
• Use Case: Courier services, shared mobility, and reverse logistics for returns.

The fleet comprises vehicles with different attributes: capacities, fixed costs, and variable operating costs per distance. The solver must decide which vehicle type to assign to each route.

• Strategic Decision: Balancing higher-capacity, expensive trucks against smaller, cheaper vans.
• Related to Pillar: Directly underpins Heterogeneous Fleet Orchestration for mixed fleets of manual and autonomous vehicles.

Customer requests, travel times, or vehicle availability are not fully known in advance but are revealed in real-time during the execution of the routes. Requires online algorithms and real-time replanning.

• Contrast with Static VRP: Static VRP assumes all information is known before optimization begins.
• Enabling Technology: Often solved using Model Predictive Control (MPC) or Reinforcement Learning (RL) frameworks.

Vehicles are located at multiple depots (starting points) and must return to their origin depot or any depot. Adds the strategic decision of assigning customers to depots.

• Complexity: Combines location-allocation with routing decisions.
• Example: A national retailer routing delivery trucks from its regional distribution centers.

This is the most prominent application, where VRP algorithms determine the most efficient routes for delivery vans and couriers to fulfill online orders. Key considerations include:

• Dynamic routing to accommodate real-time order additions and cancellations.
• Time window constraints for customer delivery preferences.
• Capacity constraints for vehicle load limits.
• Driver shift regulations to comply with labor laws. Companies like Amazon, UPS, and FedEx use advanced VRP solvers to manage millions of daily deliveries, often integrating real-time traffic data to minimize fuel consumption and improve estimated time of arrival (ETA) accuracy.

VRP optimizes schedules for technicians performing installations, repairs, and maintenance at customer sites (e.g., for telecom, utilities, or HVAC companies). The problem extends beyond simple routing to include:

• Skill matching: Assigning the right technician with the required expertise and tools to each job.
• Time-bound service level agreements (SLAs).
• Parts inventory on service vehicles, requiring multi-stop replenishment planning.
• Uncertain job durations, making the problem inherently stochastic. Efficient routing here maximizes the number of jobs completed per day and improves first-time fix rates.

Cities use VRP to optimize routes for garbage trucks, street sweepers, and snow plows. This application is characterized by:

• Arc routing problems, where service is performed along streets (edges) rather than at discrete points (nodes).
• Frequency constraints (e.g., weekly residential pickup, daily commercial pickup).
• Vehicle compatibility (e.g., different trucks for recycling, compost, and landfill waste).
• Depot location planning for transfer stations. Optimized routes reduce fuel costs, fleet wear-and-tear, and traffic congestion in residential areas.

This involves designing efficient bus routes and schedules to pick up and drop off passengers at designated stops. It is a complex VRP variant with unique constraints:

• Pickup and Delivery Problem (PDP): Students must be picked up at homes and delivered to schools.
• Maximum ride time constraints to limit how long any passenger is on the bus.
• Vehicle (bus) capacity constraints.
• Mixed loads of students from different schools on the same bus (in some systems). The primary objectives are minimizing fleet size, total travel time, and ensuring equitable service.

At a regional or national scale, VRP optimizes the movement of goods from distribution centers to retail stores or from suppliers to manufacturing plants. This often involves:

• Multi-depot VRP: Vehicles can start and end routes at different warehouses.
• Heterogeneous fleet VRP: Using a mix of truck sizes (e.g., 18-wheelers, box trucks).
• Backhauling: Incorporating the collection of returns or raw materials on return trips to avoid empty miles.
• Cross-docking integration, where goods are immediately transferred from inbound to outbound vehicles without long-term storage.

Services like Uber Pool and Lyft Line solve a dynamic, real-time VRP known as the Dial-a-Ride Problem (DARP). Key algorithmic challenges include:

• Online optimization: Requests arrive continuously and must be inserted into existing routes within seconds.
• Shared rides: Multiple passengers with different origins and destinations can share a vehicle.
• User-specified time windows for pickup and drop-off.
• Dynamic re-routing in response to traffic congestion. The objective is to maximize fleet utilization and ride-sharing efficiency while minimizing passenger detour time.

The Traveling Salesman Problem (TSP) is the fundamental combinatorial optimization problem upon which the VRP is built. It asks: given a list of cities and the distances between each pair, what is the shortest possible route that visits each city exactly once and returns to the origin city? The VRP extends the TSP by introducing multiple vehicles (salesmen) and additional constraints like capacity and time windows.

• Key Difference: TSP finds one optimal tour; VRP finds multiple optimal tours for a fleet.
• Complexity: Both are NP-hard, meaning optimal solutions become computationally intractable as the number of nodes (cities/customers) grows.
• Foundation: Most VRP solution methods use efficient TSP solvers as subroutines for constructing individual vehicle routes.

Mixed-Integer Programming (MIP) is the primary exact mathematical optimization technique used to formulate and solve VRP variants. A MIP model for the VRP uses:

• Binary Decision Variables (e.g., x_{ijk} = 1 if vehicle k travels from customer i to j).
• Continuous Variables (e.g., time of arrival at a customer).
• Linear Constraints to enforce vehicle capacity, flow conservation, and time windows.
• A Linear Objective Function to minimize total distance or cost.

Solvers like Gurobi, CPLEX, and SCIP use algorithms like Branch and Bound and Branch and Cut to find provably optimal solutions for small to medium-sized VRPs. For large-scale problems, MIP is often used to provide strong lower bounds to evaluate heuristic solutions.

Metaheuristics are high-level, general-purpose algorithmic frameworks designed to find high-quality feasible solutions for NP-hard problems like the VRP when exact methods are too slow. They trade guaranteed optimality for practical computational time.

Common metaheuristics for VRP include:

• Genetic Algorithms (GA): Evolve a population of routes using selection, crossover, and mutation.
• Simulated Annealing: Iteratively perturbs a solution, occasionally accepting worse moves to escape local optima.
• Tabu Search: Uses memory structures to avoid revisiting recent solutions.
• Ant Colony Optimization: Inspired by ant foraging, uses pheromone trails to reinforce good path segments.

These are often hybridized with local search procedures (e.g., 2-opt, relocate, exchange operators) to intensively improve individual vehicle routes.

Constraint Programming (CP) is a declarative programming paradigm highly effective for solving highly combinatorial VRPs, especially those with complex side constraints. Instead of an algebraic model, CP states the problem as:

• A set of Variables (e.g., vehicle assigned to each customer, visit time).
• A set of Constraints (e.g., alldifferent(customers), cumulative(resource_usage) for capacity, time window bounds).

Key Strengths for VRP:

• Propagation: CP solvers use constraint-specific inference algorithms to drastically reduce the search space before exploring it.
• Flexibility: Easily accommodates complex, non-linear, or logical constraints (e.g., "if vehicle type A is used, then it cannot service customer Z").
• Hybrid Use: Often combined with MIP in CP-MIP solvers to leverage the strengths of both paradigms.

Model Predictive Control (MPC), or Receding Horizon Control, is a dynamic optimization framework essential for dynamic VRPs where new customer requests arrive in real-time. MPC does not solve the entire future problem at once. Instead, at each decision epoch:

1. It solves a static VRP for all known and predicted requests over a short planning horizon.
2. It executes only the immediate decisions (e.g., next moves for the next 5 minutes).
3. It then re-solves the updated problem at the next epoch, incorporating new information.

This approach provides a principled way to handle uncertainty and dynamism, balancing immediate execution with future foresight. It is the algorithmic core of real-time dispatch engines for ride-sharing, food delivery, and dynamic courier services.

These are the two most fundamental and widely studied extensions of the basic VRP, forming the core of practical logistics models.

• Capacitated VRP (CVRP): The classic VRP where each vehicle has a maximum weight or volume capacity. The sum of demands for customers on a single route cannot exceed the vehicle's capacity. This is the simplest non-trivial VRP variant.

• VRP with Time Windows (VRPTW): Adds hard or soft time window constraints to customer visits. A hard time window [e_i, l_i] means service must begin within that interval. A soft time window allows early/late service but incurs a penalty. This models delivery appointments and business hours, adding a significant temporal scheduling layer to the spatial routing problem.

Most real-world VRPs are combinations, such as the Capacitated VRP with Time Windows (CVRPTW).