Vehicle Routing Problem (VRP)

The foundational variant where each vehicle has a maximum carrying capacity (weight, volume, or pallets). The objective is to service all customers while ensuring the total demand on any single route does not exceed the vehicle's limit.

• Constraint: Sum of customer demands on a route ≤ vehicle capacity.
• Real-world example: A beverage distributor with trucks holding 400 crates each, servicing 50 retail locations.
• Solver approach: Typically tackled with branch-and-cut algorithms or column generation for exact solutions on moderate instances.

Introduces a hard or soft time interval during which each customer must be serviced. Vehicles arriving early must wait; late arrivals incur penalties or are forbidden.

• Hard time windows: Delivery strictly within [e_i, l_i].
• Soft time windows: Late delivery allowed but penalized in the objective function.
• Real-world example: Grocery distribution to supermarkets with strict 5 AM–7 AM receiving slots to avoid daytime congestion.
• Impact: Transforms the problem from purely spatial to spatio-temporal, significantly increasing complexity. Often solved with metaheuristics like Adaptive Large Neighborhood Search (ALNS).

Generalizes the problem where goods must be transported from a pickup location to a delivery location, not just from a central depot. A critical pairing constraint links the pickup and delivery nodes.

• Precedence constraint: Pickup must occur before delivery on the same vehicle.
• Real-world example: A ride-hailing service (Uber/Lyft) matching drivers to riders, or a courier service moving parcels between businesses.
• Dial-a-Ride Problem (DARP): A specialized VRPPD with added user inconvenience constraints like maximum ride time and waiting time.

Moves beyond a uniform fleet to model a mixed set of vehicles with different capacities, fixed costs, and variable operating costs per kilometer. The solver must simultaneously select the optimal fleet composition and routing.

• Decision variables: Vehicle type assignment in addition to routing and sequencing.
• Real-world example: A logistics provider with a mix of small vans (1.5t), medium trucks (7.5t), and large articulated lorries (24t) must decide which vehicle type serves which cluster of customers.
• Cost structure: Balances the lower per-unit cost of large vehicles against their higher fixed deployment cost and restricted access to urban areas.

Injects uncertainty into one or more problem parameters, which are modeled as random variables with known probability distributions. The goal is to find a robust or expectation-minimizing solution.

• Stochastic demands: Customer demand is unknown until the vehicle arrives.
• Stochastic travel times: Traffic and service times are probabilistic.
• Stochastic customers: The presence of a customer requiring service is a random event.
• Solution paradigm: Often solved via a priori optimization (build a planned route, execute with recourse actions like returning to the depot if capacity is exceeded) or Markov Decision Processes for dynamic re-optimization.

Relaxes the requirement for vehicles to return to the depot after completing deliveries. Routes terminate at the final customer, making it a Hamiltonian path problem rather than a cycle.

• Use case: A third-party logistics (3PL) provider that does not own the vehicles; drivers finish their route and go home, or a newspaper delivery route that ends after the last drop.
• Real-world example: A contracted courier delivering packages from a central sortation center using personal vehicles, ending the route at their residence.
• Computational note: While seemingly simpler, OVRP is still NP-hard and requires adapted heuristics that do not penalize the open return leg.

The canonical precursor to the VRP, the TSP seeks the single shortest possible route that visits each node exactly once and returns to the origin. While VRP generalizes this to multiple vehicles with capacity constraints, TSP remains the fundamental building block for intra-route optimization.

• Computational Complexity: NP-hard, meaning no known polynomial-time solution exists for all instances.
• Real-World Analogy: A single technician visiting multiple job sites in a day.
• Key Distinction: TSP has one vehicle with no capacity limit; VRP has a fleet with finite capacity.

A mathematical optimization framework that formulates the VRP as a set of linear equations where some decision variables—like whether a vehicle travels between two nodes—are restricted to integers (often binary 0 or 1). MILP solvers guarantee globally optimal solutions.

• Decision Variables: Binary variables x_ij indicate if a vehicle traverses arc (i,j).
• Constraints: Vehicle capacity, time windows, and flow conservation are expressed as linear inequalities.
• Solver Examples: Gurobi, CPLEX, and OR-Tools use branch-and-cut algorithms to solve MILP formulations.

A declarative paradigm that excels at VRP variants with complex logical constraints, such as precedence relationships or driver shift rules. Instead of minimizing a mathematical function, CP prunes the search space by propagating constraints to eliminate infeasible assignments.

• Strength: Handles non-linear, disjunctive constraints that are difficult to express in MILP.
• Global Constraints: Specialized predicates like circuit() enforce a valid Hamiltonian cycle for each vehicle.
• Use Case: Highly constrained problems like school bus routing with mixed passenger types.

A recursive decomposition method that solves VRP subproblems by breaking them into overlapping stages and storing optimal solutions to avoid redundant computation. It forms the theoretical basis for exact algorithms on small to medium instances.

• State Definition: A state typically includes the set of unvisited customers and the current vehicle location.
• Bellman Equation: The optimal cost-to-go from a state is the minimum immediate cost plus the optimal future cost.
• Curse of Dimensionality: The state space grows exponentially with the number of customers, limiting exact DP to instances with fewer than ~25 stops.

A population-based metaheuristic that evolves a set of candidate VRP solutions over generations using operators inspired by natural selection. It is particularly effective for large-scale, real-world instances where exact methods are computationally intractable.

• Chromosome Encoding: A route is often represented as a giant tour (permutation of all customers) that is split into feasible vehicle routes.
• Crossover Operators: Edge Recombination Crossover (ERX) preserves parent route adjacencies to produce high-quality offspring.
• Mutation: Random swaps or inversions within a route maintain population diversity and prevent premature convergence.

A stochastic local search technique that escapes local optima by probabilistically accepting worse solutions during the search. The probability of accepting an inferior move decreases over time according to a cooling schedule, mimicking the physical annealing of metals.

• Neighborhood Operators: Common moves include relocating a customer between routes (relocate), swapping two customers (exchange), or reversing a segment (2-opt).
• Cooling Schedule: A geometric decay T = α * T with α ∈ [0.85, 0.99] balances exploration and exploitation.
• Advantage: Simple to implement and often finds near-optimal solutions for large VRP instances with minimal parameter tuning.