Vehicle Routing Problem (VRP)

The foundational extension of the standard VRP where each vehicle has a finite carrying capacity (weight, volume, or pallet count). The total demand of customers assigned to a single route cannot exceed the vehicle's capacity constraint. This transforms the problem from a pure routing challenge into a simultaneous assignment and routing problem, where the solver must cluster customers into feasible groups before sequencing them. CVRP is the baseline for most real-world logistics, as unlimited capacity is never a practical assumption.

Introduces a hard or soft temporal constraint where each customer must be serviced within a predefined interval. A vehicle arriving early must wait, while late arrivals incur a penalty or are forbidden. This adds a scheduling dimension to the spatial routing problem, requiring solvers to balance route compactness with temporal feasibility. VRPTW is critical for urban distribution, grocery delivery, and any operation governed by strict appointment slots. The tightness of time windows directly impacts fleet utilization.

Models the transportation of goods or passengers between paired origin-destination locations. A single request consists of a pickup node and a corresponding delivery node, linked by a precedence constraint—the pickup must be visited before the delivery. This is the canonical model for ride-hailing services, courier operations, and less-than-truckload (LTL) freight consolidation. The pairing constraint fundamentally changes the solution structure, as vehicles carry inventory that must be unloaded at a specific future stop.

Generalizes the problem to a mixed fleet of vehicles with varying capacities, fixed costs, variable operating costs, and specialized equipment (e.g., refrigeration, lift gates). The solver must simultaneously decide which vehicle type to assign to each route in addition to the routing and sequencing decisions. This reflects the reality of most logistics operators who manage a diverse asset pool. The trade-off between using a small number of large vehicles versus many smaller ones becomes a central optimization variable.

Addresses the reality that input parameters are random variables, not deterministic values. Customer demand, travel times, or even customer presence may be unknown at the time of planning and are modeled with probability distributions. The goal shifts from finding a single optimal route to designing a robust or recourse-based strategy. A common approach is two-stage stochastic programming, where a planned route is executed, and a corrective recourse action (e.g., returning to the depot for restocking) is triggered if a failure occurs. This is essential for modeling operational uncertainty.

A real-time variant where new orders arrive continuously during the execution of the plan, requiring the routes to be updated on the fly. Unlike static VRP, where all information is known a priori, DVRP requires an online algorithm that reacts to streaming events. This is the operational model for modern on-demand delivery platforms and emergency service dispatch. The key performance metric shifts from static optimality to the quality of real-time decision-making under partial information, often evaluated through competitive ratio analysis.

The standard VRP is extended by critical real-world constraints. Capacitated VRP (CVRP) limits the load a vehicle can carry. VRP with Time Windows (VRPTW) requires deliveries within strict time slots. The Pickup and Delivery Problem (PDP) enforces precedence, ensuring a pickup occurs before its corresponding drop-off. These variants form the building blocks of all commercial routing engines.

VRP is NP-hard, making exact solutions infeasible for large fleets. Metaheuristics find near-optimal solutions quickly:

• Genetic Algorithm: Evolves a population of routes using crossover and mutation.
• Simulated Annealing: Escapes local optima by probabilistically accepting worse solutions.
• Adaptive Large Neighborhood Search (ALNS): Iteratively destroys and repairs parts of a solution, learning which heuristics perform best.

For smaller, highly constrained problems, exact methods guarantee optimality. Mixed-Integer Linear Programming (MILP) models the problem with linear equations and integer variables, solved via Branch and Bound. Column Generation tackles large-scale problems by iteratively generating only the most promising route variables, often used as a subroutine in Branch and Price algorithms.

The foundation of any VRP solver is a high-speed shortest path algorithm. Dijkstra's Algorithm finds the shortest path from a single source. A Search* uses a heuristic to guide the search toward the destination. For production road networks, Contraction Hierarchies preprocess the graph to answer queries in microseconds, making it the standard for calculating the distance matrix used in VRP solvers.

Real-world logistics are not static. Time-Dependent VRP models travel times that vary by time of day. Stochastic VRP treats demand or travel time as random variables. Model Predictive Control (MPC) provides a framework for continuous re-optimization: solve a plan over a horizon, execute the first step, observe new data, and re-solve. This handles disruptions like traffic jams or new orders in real-time.

Routing is rarely about a single goal. Multi-Objective Optimization balances conflicting objectives like minimizing cost, maximizing service level, and reducing Carbon Footprint. The result is a Pareto Frontier: a set of non-dominated solutions where improving one objective degrades another. A dispatcher can then choose the optimal trade-off based on the day's business priorities.