Fact-checked by Grok 2 weeks ago

Vehicle routing problem

The vehicle routing problem (VRP) is a combinatorial optimization problem seeking to find the optimal set of routes for a fleet of identical vehicles stationed at a central depot to serve a given set of geographically scattered customers, each demanding a specified quantity of goods, while minimizing the total travel distance or cost and respecting constraints such as limited vehicle capacity and maximum route length. Each customer must be visited exactly once by exactly one vehicle, with all vehicles starting and ending their routes at the depot. The VRP was first formally introduced in 1959 by George B. Dantzig and John H. Ramser in their seminal paper "The Truck Dispatching Problem," which addressed the routing of gasoline delivery trucks from a bulk terminal to service stations using a heuristic approach based on linear programming relaxations.^[1] Since then, the problem has evolved significantly, with early contributions like the Clarke-Wright savings algorithm in 1964 providing foundational heuristics for practical implementation.^[2] As an NP-hard problem, the VRP is computationally challenging, with exact algorithms such as branch-and-cut-and-price capable of solving instances up to around 100-135 customers, while heuristic and metaheuristic methods like tabu search and genetic algorithms are employed for larger-scale real-world applications. It plays a central role in logistics and supply chain management, underpinning efficient operations in sectors including e-commerce delivery, municipal waste collection, and emergency response services, where optimized routing can reduce fuel consumption, operational costs, and environmental impact by up to 20-30% in typical scenarios. To accommodate diverse practical needs, numerous variants of the VRP have been studied, including the capacitated VRP (CVRP) which enforces vehicle load limits, the VRP with time windows (VRPTW) that restricts delivery times, and the pickup and delivery problem (PDP) involving both collection and distribution tasks.^[2] These extensions reflect the problem's adaptability to heterogeneous fleets, dynamic environments, and stochastic demands, fostering ongoing research in areas like machine learning integration for route prediction.

Problem Description

Basic Setup

The vehicle routing problem (VRP) is a combinatorial optimization problem that seeks to determine optimal routes for a fleet of vehicles to serve a set of customers, starting and ending at a central depot, while minimizing the total cost, typically measured as travel distance or time.^[1] This problem arises in distribution and logistics contexts, where efficient route planning reduces operational expenses and improves resource utilization.^[2] The core components of the VRP include a single depot serving as the origin and destination for all vehicles, a set of customer locations each with a specific demand to be satisfied, a fleet of homogeneous or heterogeneous vehicles each subject to capacity limits, and a road network modeled as a complete graph with nodes representing locations and edges weighted by travel distances or times.^[2] The decision variables in the VRP consist of the assignment of routes to individual vehicles and the sequence in which customers are visited along each route, ensuring that all demands are met without violating vehicle constraints.^[1] The primary objective of the VRP is to minimize the total travel distance or cost across all routes, with secondary goals often including the minimization of the number of vehicles used to promote fleet efficiency.^[2] The VRP generalizes the traveling salesman problem (TSP), which represents the special case of a single vehicle serving all customers.^[2] To illustrate, consider a basic VRP instance with one depot (node 0), five customers (nodes 1 through 5) located at distinct points on a plane, and two vehicles each with a capacity of 100 units. Customer demands are, for example, 20, 30, 25, 40, and 35 units respectively, and distances between nodes form a metric graph. An optimal solution might assign one vehicle to visit customers 1, 2, and 3 (total demand 75) in the sequence 0-1-2-3-0, and the other to 4 and 5 (total 75) as 0-4-5-0, minimizing the combined route length while respecting capacities.^[1]

Mathematical Formulation

The basic mathematical formulation of the vehicle routing problem (VRP), often referred to as the capacitated VRP (CVRP) and extendable to heterogeneous fleets, is an integer linear programming model that minimizes the total routing cost while respecting capacity limits and ensuring each customer is served exactly once by one vehicle route starting and ending at the depot. This formulation uses three-index decision variables to distinguish routes by vehicle and incorporates the Miller-Tucker-Zemlin (MTZ) constraints to eliminate subtours. The model assumes a complete directed graph with non-negative costs satisfying the triangle inequality, homogeneous or heterogeneous vehicle capacities, and non-negative customer demands.^[3]

Notation

Let V = \{0, 1, \dots, n\} denote the vertex set, where vertex 0 is the depot and vertices $1, \dots, n are customers; let K = \{1, \dots, m\} be the set of available vehicles. The parameters are c_{ij} \geq 0 (travel cost from i to j in V \times V), q_i \geq 0 (demand at vertex i, with q_0 = 0), and Q_k > 0 (capacity of vehicle k \in K).^[3]

Decision Variables

x_{ijk} \in \{0,1\} \ \forall i,j \in V, \, i \neq j, \, k \in K: equals 1 if vehicle k travels directly from i to j, and 0 otherwise.
u_{ik} \geq 0 \ \forall i \in V, \, k \in K: auxiliary variable representing the cumulative demand served by vehicle k upon leaving vertex i (with u_{0k} = 0 \ \forall k \in K).

Objective Function

The objective is to minimize the total travel cost:

\min \sum_{k \in K} \sum_{i \in V} \sum_{\substack{j \in V \\ j \neq i}} c_{ij} x_{ijk}

Constraints

Each vehicle must depart from and return to the depot exactly once:

\sum_{\substack{j \in V \\ j \neq 0}} x_{0jk} = 1 \quad \forall k \in K

\sum_{\substack{i \in V \\ i \neq 0}} x_{i0k} = 1 \quad \forall k \in K

Each customer must be visited exactly once across all vehicles:

\sum_{k \in K} \sum_{\substack{j \in V \\ j \neq i}} x_{ijk} = 1 \quad \forall i \in \{1, \dots, n\}

Flow conservation holds at each customer for each vehicle:

\sum_{\substack{j \in V \\ j \neq i}} x_{jik} - \sum_{\substack{j \in V \\ j \neq i}} x_{ijk} = 0 \quad \forall i \in \{1, \dots, n\}, \, k \in K

Capacity constraints ensure the total demand assigned to each vehicle does not exceed its capacity:

\sum_{i \in \{1, \dots, n\}} q_i \sum_{\substack{j \in V \\ j \neq i}} x_{ijk} \leq Q_k \quad \forall k \in K

Subtour elimination constraints, adapted from the MTZ formulation originally developed for the TSP, prevent disconnected cycles for each vehicle by enforcing that the cumulative load increases appropriately along the route:

u_{ik} - u_{jk} + Q_k x_{ijk} \leq Q_k - q_j \quad \forall i,j \in \{1, \dots, n\}, \, i \neq j, \, k \in K

Bounds on the auxiliary variables ensure feasibility with demands and capacities:

q_i \leq u_{ik} \leq Q_k \quad \forall i \in \{1, \dots, n\}, \, k \in K

These constraints collectively ensure valid routes. The degree and flow conservation constraints guarantee that the solution forms paths starting and ending at the depot, with each customer included exactly once. However, without subtour elimination, feasible solutions to these alone may include disconnected cycles (subtours) among customers that exclude the depot, violating the route structure. The MTZ constraints address this by assigning monotonically increasing values to u_{ik} along each vehicle's path—specifically, if vehicle k travels from i to j, then u_{jk} \geq u_{ik} + q_j, which propagates cumulatively from the depot and precludes cycles since loads cannot decrease or loop without exceeding capacity bounds. This mechanism, originally developed for the traveling salesman problem by Miller, Tucker, and Zemlin (1960), is adapted here to ensure connectivity to the depot for each vehicle's support graph.^[4]

Historical Development

Origins and Early Formulations

The vehicle routing problem (VRP) emerged in the field of operations research during the mid-20th century, fueled by the post-World War II economic expansion that dramatically increased commercial distribution and logistics demands across growing economies.^[5] This period saw a surge in the need for efficient fleet management to handle rising volumes of goods, particularly in sectors like fuel and consumer deliveries, as supply chains transitioned from wartime logistics to peacetime commerce.^[6] Concurrently, the advent of early digital computers in the late 1950s enabled the application of mathematical optimization techniques to these practical challenges, marking a pivotal shift toward computational solutions in operations research.^[6] A key precursor to the VRP was the traveling salesman problem (TSP), which gained prominence in operations research during the early 1950s through efforts to solve practical instances using methods like cutting planes, as demonstrated in landmark work solving a 42-city problem. The VRP extends the TSP by incorporating multiple vehicles, capacity limits, and a central depot, addressing more realistic distribution scenarios.^[5] The VRP was formally introduced in 1959 by George B. Dantzig and John H. Ramser in their paper "The Truck Dispatching Problem," which focused on optimizing routes for a fleet of gasoline delivery trucks serving service stations from a bulk terminal, thereby establishing the core concept of vehicle routing.^[1] Their work presented an initial heuristic algorithm based on linear programming relaxations, vertex matching to respect vehicle capacities, and manual adjustments to resolve fractional solutions, applied to a small instance with one depot and seven customers.^[1] Early formulations, including this one, emphasized static and deterministic settings typical of distribution networks, where vehicles depart from and return to a single depot while minimizing total travel distance under capacity constraints.^[5] Building on this foundation, the early 1960s saw the development of practical heuristics, most notably the savings algorithm by G. Clarke and J. W. Wright in 1964. This method starts with individual routes to each customer and iteratively merges pairs to maximize "savings" in total distance—calculated as the reduction from serving them separately versus jointly—while adhering to capacity limits, providing an efficient way to construct near-optimal routes for larger fleets. The algorithm's simplicity and effectiveness made it a cornerstone for subsequent heuristic approaches in VRP solving.^[5]

Key Milestones and Evolution

The vehicle routing problem (VRP) evolved significantly from the 1970s onward, building on its foundational formulation in 1959 by Dantzig and Ramser for truck dispatching.^[7] In the 1970s, research on the CVRP advanced with heuristics such as Yellow (1970)'s computational modification to the savings algorithm, incorporating a route shape parameter to balance direct and indirect paths in route construction.^[8] Concurrently, exact methods emerged through branch-and-bound algorithms, notably Christofides, Mingozzi, and Toth (1979), who developed a framework using minimum spanning trees and shortest path relaxations to solve small to medium CVRP instances optimally. These contributions shifted focus from basic routing to capacity-aware optimization, laying groundwork for practical applications in distribution.^[7] The 1980s saw the formalization of the VRP with time windows (VRPTW), addressing scheduling constraints in real-time operations; Solomon (1987) introduced benchmark instances that remain standard for evaluating algorithms today due to their realistic clustered and random customer distributions. By the 1990s, metaheuristics gained prominence for tackling NP-hard variants, with tabu search—originally proposed by Glover (1986)—adapted for VRP through neighborhood exploration and memory mechanisms to avoid local optima, as in Taillard (1993) and Gendreau et al. (1994).^[9] Genetic algorithms also emerged, evolving populations of route solutions via crossover and mutation to approximate optimal fleet assignments, exemplified by early applications like Potvin and Bengio (1996). This decade marked a key organizational milestone, as ORSA/TIMS (now INFORMS) fostered VRP study groups in the early 1990s, leading to dedicated annual workshops that promoted collaboration and benchmark standardization.^[7] Entering the 2000s, exact methods refined through column generation and set partitioning formulations improved solvability for larger instances; for example, branch-and-price frameworks were further developed, culminating in the robust branch-and-cut-and-price algorithm by Fukasawa et al. (2006), which solved CVRP instances up to 100 customers exactly by stabilizing column generation with aggregation strategies. In the 2010s and 2020s, the rise of dynamic VRP variants—driven by e-commerce expansion, including Amazon's post-2015 optimizations for last-mile delivery amid surging online orders—prompted integration of machine learning, particularly reinforcement learning, to handle stochastic demands and real-time rerouting; Nazari et al. (2018) demonstrated attention-based neural policies outperforming traditional heuristics on dynamic benchmarks by learning adaptive policies from simulations.^[10] In the early 2020s, further ML advancements include adversarial generative flow networks for end-to-end VRP solving, as demonstrated in recent works (as of 2025).^[11] These developments reflect VRP's adaptation to urban logistics challenges, with ML enabling scalable solutions for fluctuating environments.^[12]

Variants

Capacitated and Basic Variants

The capacitated vehicle routing problem (CVRP) extends the basic vehicle routing problem by incorporating vehicle capacity constraints, where each vehicle has a maximum load capacity Q, and the total demand served on any route must not exceed this limit, with split deliveries to customers disallowed.^[1] This formulation was first introduced by Dantzig and Ramser in their 1959 study on the truck dispatching problem, modeling a fleet of identical vehicles servicing gasoline delivery to service stations while respecting load limits.^[1] Unlike the unconstrained basic VRP, which resembles a collection of traveling salesman problems without load considerations, the CVRP introduces a bin-packing-like subproblem for assigning customers to vehicles to balance loads efficiently before routing.^[13] The CVRP is strongly NP-hard, as established by reductions from known NP-complete problems like the partition problem, making exact solutions computationally intensive for large instances.^[14] Benchmark instances for evaluating CVRP algorithms, such as those developed by Christofides et al. in 1979, typically feature 50 to 200 customers with varying depot locations and demand distributions, serving as standard tests for scalability and solution quality.^[15] The distance-constrained vehicle routing problem (DVRP) further modifies the basic VRP by imposing a maximum total route length L per vehicle to avoid excessively long tours, often aiming to minimize either the total distance traveled or the number of vehicles used.^[16] This variant, analyzed in depth by Li, Simchi-Levi, and Desrochers in 1992, addresses practical limitations like driver fatigue or regulatory restrictions on travel duration.^[16] Mixed variants combining capacity and distance constraints, such as the distance-constrained CVRP, integrate both load and tour length limits to model real-world operations more accurately, where shorter routes can significantly reduce fuel consumption—for instance, in urban freight distribution, total fuel use is proportional to distance traveled at rates like 9.5 liters per 100 km.^[17] These combined constraints highlight trade-offs in load balancing and route efficiency, promoting sustainable logistics by minimizing environmental impacts alongside costs.^[18]

Time and Service Constraint Variants

The Vehicle Routing Problem with Time Windows (VRPTW) extends the basic vehicle routing problem by imposing time constraints on customer service, where each customer i specifies a time interval [a_i, b_i] during which service must begin. If a vehicle arrives before a_i, it must wait until the window opens; arrival after b_i renders the route infeasible under hard time window constraints. This variant is particularly relevant for just-in-time delivery systems, where temporal synchronization is essential to minimize delays and holding costs.^[19] In the VRPTW, service times s_i are incorporated at each customer location to account for unloading, loading, or handling activities, which add to the cumulative route duration after arrival and waiting. The total time for a route includes travel times, service times, and any waiting periods, ensuring that the sequence of visits respects all time windows while adhering to vehicle capacity limits from capacitated variants. This integration of service times transforms the problem into a scheduling-rerouting hybrid, as the order of visits directly impacts feasibility due to temporal dependencies.^[20] Extensions to the VRPTW include soft time windows, which permit early or late arrivals with associated penalties rather than strict infeasibility, allowing for more flexible solutions in practice. Penalty functions typically charge costs proportional to the deviation from the window, such as linear or quadratic terms for earliness and tardiness, enabling trade-offs between time violations and total routing expenses. Seminal work on soft time windows, such as tabu search heuristics, demonstrated improved solution quality on benchmark instances by balancing these penalties with distance and capacity objectives. Solomon's benchmarks from 1987, consisting of 56 instances with 100 customers (and smaller 25- and 50-customer variants), along with later extensions like Gehring-Homberger instances up to 1000 customers, remain the standard for evaluating VRPTW algorithms.^[20] These datasets incorporate clustered, random, and mixed customer distributions with varying time window tightness, facilitating comparisons of solution quality and computational performance.^[20] The primary challenges in time and service constraint variants stem from the need to integrate scheduling feasibility checks, which exponentially increase complexity compared to the Capacitated VRP (CVRP) due to the additional temporal dimensions and sequencing constraints.^[19] Ensuring all routes satisfy time windows often requires dynamic programming or branch-and-price techniques, as simple distance-based heuristics fail to capture waiting and service interactions. This heightened NP-hardness limits exact solutions to instances with fewer than 100 customers in most cases, driving reliance on advanced heuristics for larger problems.

Pickup, Delivery, and Multi-Depot Variants

The Vehicle Routing Problem with Pickup and Delivery (VRPPD) extends the classical VRP by incorporating bidirectional transportation requests, where vehicles must collect goods from pickup locations and deliver them to corresponding delivery sites, often under paired constraints. In this variant, each request consists of a specific pickup and delivery pair, with the pickup operation required to precede the delivery on the same vehicle to ensure compatibility and prevent cross-hauling, where incompatible loads mix on a single route.^[21] Precedence constraints enforce that no delivery occurs before its associated pickup, while capacity limits restrict the total load at any point in the route, accounting for both incoming pickups and outgoing deliveries.^[22] This formulation arises in reverse logistics scenarios, such as waste collection or product returns, where vehicles handle both supply and recovery flows without intermediate transshipment.^[21] The VRPPD is NP-hard, as it generalizes the capacitated VRP by setting all pickup or delivery demands to zero, reducing to the known NP-hard CVRP; alternatively, reductions from the Hamiltonian path problem demonstrate its computational intractability for even small instances. Seminal work by Savelsbergh and Sol formalized the general pickup and delivery problem, emphasizing set-partitioning models to handle precedence and pairing without load mixing.^[22] Benchmarks for evaluating VRPPD algorithms, such as those introduced by Li and Lim, include instances with up to 1,000 paired requests, often incorporating time windows as an add-on constraint to simulate real-time scheduling pressures.^[23] The Multi-Depot VRP (MDVRP) further generalizes the VRPPD by allowing multiple depots as origins and endpoints for vehicle routes, enabling assignment of customers or request pairs to the nearest or most efficient depot to balance workload and reduce empty travel.^[21] In this setup, vehicles depart from and return to their assigned depots, with the objective of minimizing total routing costs while respecting capacity and precedence rules for pickups and deliveries. This variant is particularly relevant in distributed logistics networks, such as regional warehouses serving urban areas, where depot selection optimizes resource allocation across sites. The Dial-a-Ride Problem (DARP) represents a passenger-oriented adaptation of the VRPPD, focusing on on-demand transportation services where vehicles pick up users at origins and deliver them to destinations, incorporating ride-sharing and comfort constraints beyond mere capacity.^[21] Key features include maximum ride-time limits to minimize user inconvenience, alongside time windows for pickups and compatibility rules ensuring paired transport on the same vehicle without excessive detours.^[24] Originating in urban paratransit systems, DARP enforces no cross-hauling by design, as each user's pickup-delivery pair must be handled integrally, often with multi-dimensional capacities for seating or accessibility needs.^[21] Psaraftis introduced dynamic programming approaches for small-scale DARP instances with up to nine requests, highlighting the added complexity from stochastic user arrivals in real operations.^[24] Benchmarks like those from Cordeau extend to 32 requests, testing scalability under comfort metrics such as total user wait time.^[21]

Applications

Logistics and Supply Chain

The vehicle routing problem (VRP) plays a central role in last-mile delivery operations, where goods are transported from distribution centers to end customers, optimizing routes to minimize travel distance and time while serving geographically dispersed locations. A prominent example is the United Parcel Service (UPS) ORION system, which was rolled out in 2012 and integrates VRP principles to dynamically optimize routes for over 55,000 drivers, achieving savings of approximately 100 million miles driven annually by 2018. As of 2025, ORION continues to yield ~100 million miles in annual savings despite workforce adjustments including ~48,000 job cuts.^[25]^[26] This implementation has reduced fuel consumption and operational costs, demonstrating VRP's impact on efficiency in parcel delivery networks. In supply chain integration, VRP facilitates coordination between inventory management and distribution, ensuring timely replenishment from warehouses to retail outlets or customers by solving routing decisions that account for stock levels and demand forecasts. For instance, integrated models combine VRP with inventory allocation to distribute limited goods across a fleet, maximizing profit while balancing holding costs and delivery schedules in warehouse-to-store networks. Such approaches address the interplay between upstream inventory decisions and downstream routing, enhancing overall supply chain responsiveness.^[27]^[28] Fleet management increasingly incorporates the electric vehicle routing problem (EVRP), a VRP variant that plans routes for battery-electric fleets while incorporating charging station visits to manage limited range and recharge times. In logistics, EVRP applications optimize urban distribution by minimizing energy use and downtime, supporting transitions to sustainable fleets in sectors like e-commerce and retail. Systematic reviews highlight EVRP's role in transport logistics, where it reduces emissions compared to traditional diesel routing without compromising service levels.^[29] VRP solutions in logistics typically yield cost reductions of 10-30% through improved fuel efficiency and route consolidation, with broader adoption driven by regulatory pushes for sustainability. The European Union's Green Deal, launched in 2019, emphasizes sustainable transport optimization, including green VRP variants that prioritize low-emission routing to meet climate neutrality goals by 2050.^[30]^[31] A notable case study involves grocery delivery during the COVID-19 pandemic from 2020 to 2022, when online orders surged by up to fivefold, requiring VRP adaptations—such as capacitated VRP (CVRP) and VRP with time windows (VRPTW)—to handle demand spikes, dynamic customer locations, and capacity constraints in perishable goods distribution. E-grocery networks leveraged VRP models to enhance resilience, integrating real-time data for route adjustments amid disrupted supply chains and increased delivery volumes.^[32]^[33]

Emerging and Specialized Uses

In recent years, the vehicle routing problem (VRP) has been adapted for healthcare applications, particularly in ambulance routing and medical supply delivery. Ambulance routing often employs the multi-depot VRP (MDVRP) variant to coordinate fleets from multiple hospital bases, optimizing response times while accounting for dynamic patient priorities and traffic conditions.^[34] For medical supply delivery, such as blood transports, the VRP with pickup and delivery (VRPPD) addresses time-sensitive constraints to maintain product viability, ensuring efficient collection from donors and distribution to hospitals.^[35] E-commerce and ride-sharing platforms have leveraged dynamic VRP formulations to handle real-time dispatching. In systems like Uber and Lyft, dynamic VRP integrates on-demand requests with vehicle assignment, minimizing wait times through optimized pickup and drop-off locations that incorporate walking distances for passengers.^[36] Post-2015 FAA regulations enabling commercial drone operations have spurred drone-assisted VRP variants, where unmanned aerial vehicles collaborate with ground fleets for last-mile delivery, reducing overall travel time in urban settings.^[37] Environmental concerns have driven the green VRP, which minimizes emissions by incorporating fuel consumption models and alternative vehicle types into routing decisions. Integrated with geographic information systems (GIS), green VRP evaluates terrain impacts on CO2 output, supporting urban planning for sustainable logistics networks.^[38] Post-2020 advancements in AI, such as InstaDeep's Jumanji suite, have enhanced VRP solvers using reinforcement learning for robotics applications, enabling scalable solutions to complex routing in dynamic environments.^[39] In disaster response, VRP models have been proposed for optimizing relief goods distribution and road recovery planning, drawing on the 2011 Japan tsunami to prioritize vehicle routes amid debris and infrastructure damage.^[40] Specialized uses include waste collection, modeled as the periodic VRP to schedule visits over multiple days while respecting bin capacities and collection frequencies. This variant optimizes fleet utilization in municipal systems, often incorporating intermediate facilities for unloading to extend route efficiency.^[41]

Solution Methods

Exact Methods

Exact methods for the vehicle routing problem (VRP) aim to find provably optimal solutions by formulating the problem as an integer linear program (ILP) and employing optimization techniques that explore the solution space exhaustively. These approaches are particularly effective for small- to medium-sized instances, where the computational cost remains manageable, but they face exponential growth in complexity for larger problems due to the NP-hard nature of the VRP. The primary ILP formulations fall into two categories: vehicle flow models, which use arc-based variables to track vehicle traversals and commodity movements, and set partitioning models, which select predefined routes to cover all customers exactly once.^[42] Vehicle flow formulations model the VRP using variables that represent the number of vehicles traversing each arc, combined with flow conservation constraints to ensure feasible routes. In commodity flow variants, additional variables track the flow of demand (commodities) along paths from the depot to customers, enforcing capacity limits through aggregate flow balances; a two-commodity network flow extension strengthens these by separately modeling vehicle and load flows, improving the linear programming (LP) relaxation bounds. To prevent disconnected subtours, generalized subtour elimination constraints are incorporated, which generalize the Miller-Tucker-Zemlin formulation by imposing cumulative flow or visit order restrictions across subsets of customers, ensuring all routes connect back to the depot without isolated cycles. These formulations are compact, with a polynomial number of variables and constraints, making them suitable for direct solving with general-purpose ILP solvers like CPLEX or Gurobi.^[43]^[43]^[44] Branch-and-bound and branch-and-cut algorithms solve these ILP formulations by relaxing the integer constraints to obtain LP bounds and systematically branching on fractional variables to prune suboptimal subtrees. In branch-and-cut variants, violated inequalities are dynamically added as cutting planes to tighten the LP relaxation; for capacity constraints in vehicle flow models, rounded capacity inequalities are particularly effective, requiring that subsets of customers exceeding a fractional vehicle capacity be served by at least the ceiling of that fraction, which cuts off infeasible fractional solutions while preserving integrality. These methods excel in handling the combinatorial explosion through strong bounds and reduced branching, as demonstrated in robust implementations that integrate cutting planes with primal heuristics for faster convergence.^[45] Set partitioning formulations, in contrast, use column generation to manage the exponential number of possible routes efficiently. The master problem is a restricted set partitioning ILP that selects a subset of routes to cover customers without overlap, solved via LP relaxation; new columns (routes) are generated by solving a subproblem formulated as the elementary shortest path problem with resource constraints (ESPPRC), which finds the lowest-reduced-cost path from depot to depot visiting an elementary set of customers while respecting capacity and other resources, using dynamic programming with labeling techniques to avoid cycles. Branching occurs on arc or customer variables in a branch-and-price framework to reach integer optimality. Compared to vehicle flow models, set partitioning provides superior LP bounds for better pruning but demands sophisticated column management, leading to slower initial solves though often tighter overall optimality proofs.^[42] The VRPSolver by Fukasawa et al. (2006) combines branch-and-cut-and-price elements, achieving optimal solutions for all standard benchmark instances with up to 100 customers and larger ones up to 135 vertices. Recent implementations, such as updates to VRPSolver and other branch-and-cut-and-price solvers like RouteOpt, have extended these capabilities to instances with up to 670 customers as of 2023.^[45]^[46]

Heuristic and Metaheuristic Methods

Heuristic and metaheuristic methods provide practical approximation algorithms for solving large-scale instances of the vehicle routing problem (VRP), prioritizing computational efficiency and good solution quality over exact optimality guarantees. These approaches are essential for real-world applications where problem sizes render exact methods infeasible, often delivering solutions within a few percent of the optimum in reasonable time.^[47]^[48] Classical heuristics focus on constructing initial feasible routes efficiently. The Clarke-Wright savings algorithm, introduced in 1964, starts with individual routes from depot to each customer and iteratively merges them based on a "savings" metric—the reduction in total distance achieved by combining two routes. This parallel version of the algorithm builds routes by prioritizing the highest savings while respecting capacity constraints, providing a quick initial solution for the capacitated VRP.^[47] Similarly, the sweep algorithm by Gillett and Miller (1974) polarizes customers around the depot in angular coordinates and "sweeps" a radial line clockwise to sequentially assign customers to vehicles, forming clusters before optimizing intra-route sequences; it excels in geographic clustering for medium- to large-scale problems.^[48] These construction heuristics serve as starting points for further refinement. Local search methods improve initial solutions by exploring neighborhoods through small perturbations. Common intra-route moves include the 2-opt operator, which reverses a segment of a route to eliminate crossings and reduce distance, originally adapted from the traveling salesman problem. Inter-route moves such as relocate (shifting a customer to another route) and exchange (swapping customers between routes) address load balancing and feasibility. These are often enhanced with metaheuristic acceptance criteria, like simulated annealing, which probabilistically accepts worse solutions early to escape local optima, gradually cooling to favor improvements; this combination yields robust enhancements for VRP variants. Metaheuristics extend local search with higher-level strategies to navigate the search space more globally. Tabu search, applied to the VRP with time windows (VRPTW) by Taillard in 1997, maintains a short-term memory (tabu list) of recent moves to forbid repetitive actions, preventing cycling while allowing aspiration criteria for promising tabu moves; it efficiently handles time constraints in parallel implementations.^[49] Genetic algorithms, as in Prins's 2004 approach, evolve populations of route encodings using crossover operators like ordered crossover to preserve route contiguity, combined with mutation and local search for hybrid evolution; these operators ensure feasible offspring for capacitated VRPs. Ant colony optimization, adapted from Dorigo's work in the 1990s, simulates pheromone trails on a graph where artificial ants construct routes probabilistically based on accumulated "pheromones" from good solutions, with evaporation to diversify; it has been tailored for dynamic VRP updates. Hybrid metaheuristics represent state-of-the-art for benchmark instances. The adaptive large neighborhood search (ALNS) by Ropke and Pisinger (2006) iteratively destroys and repairs partial solutions using diverse destroy (e.g., random or worst removal) and repair (e.g., regret insertion) operators, with adaptive weights updating based on operator performance; it excels in VRPTW and pickup-delivery variants by balancing exploration and exploitation.^[50] Metaheuristics generally achieve optimality gaps of 1-5% on standard benchmarks compared to exact methods for small instances, with hybrids like ALNS often closing to under 1% on larger sets. Evaluation of these methods emphasizes trade-offs between solution quality and computation time. Classical heuristics construct solutions in linear time relative to customer count, ideal for real-time planning, but may yield 5-10% gaps without refinement. Metaheuristics, requiring more iterations, scale to hundreds of customers in minutes on modern hardware, offering 1-5% gaps suitable for logistics optimization where exact solutions via branch-and-cut exceed hours even for modest sizes.

Challenges and Future Directions

Computational Complexity

The vehicle routing problem (VRP) is NP-hard, as demonstrated by a straightforward reduction from the traveling salesman problem (TSP), which is itself NP-hard; specifically, setting the number of vehicles to one and capacities to infinity transforms the VRP into the TSP. The capacitated VRP (CVRP) is also NP-hard, established through reductions combining the bin packing problem (for capacity allocation) and the Hamiltonian cycle problem (for routing feasibility). Variants of the VRP exhibit even stronger hardness. The VRP with time windows (VRPTW) is strongly NP-hard, meaning the problem remains NP-hard even when numerical inputs are polynomially bounded; this follows from a reduction showing that determining the feasibility of a solution with a fixed number of vehicles is NP-complete. Similarly, the VRP with pickup and delivery (VRPPD) is NP-hard, with proofs via reductions from the TSP in cases where pickup or delivery demands dominate, or more complex reductions such as from 3-SAT for precedence-constrained variants. In terms of approximability, the metric CVRP admits constant-factor approximation algorithms but is APX-hard, implying no polynomial-time approximation scheme (PTAS) exists unless P=NP; this hardness arises from reductions incorporating the metric TSP (for which the Christofides algorithm yields a 1.5-approximation) alongside bin packing elements that prevent direct extension of TSP bounds to the VRP. No constant-factor approximation is possible for certain non-metric or generalized VRP formulations unless P=NP, highlighting the inherent intractability.^[51] Exact solutions to VRP instances typically require exponential time and are feasible only for small scales, with state-of-the-art branch-and-cut-and-price methods solving up to 50-100 nodes within reasonable computational limits before optimality gaps become prohibitive. From a parameterized complexity perspective, the VRP is fixed-parameter tractable when parameterized by the treewidth of the underlying graph, allowing efficient algorithms for graphs with bounded treewidth via dynamic programming over tree decompositions.^[52] These theoretical results underscore the necessity of heuristic and metaheuristic approaches for practical VRP instances of realistic size, as exact methods scale poorly beyond small networks.

Recent Advances and Open Problems

Recent advances in the vehicle routing problem (VRP) have increasingly incorporated machine learning techniques to enhance route prediction and optimization, building on early reinforcement learning models like the attention-based approach introduced by Nazari et al. in 2018. Extensions through 2024 and 2025 have integrated deep neural networks and hybrid ML-metaheuristic frameworks, enabling more adaptive solutions for large-scale instances by learning from historical routing data and predicting optimal sequences. For instance, a 2025 review highlights how these ML-driven methods, such as graph neural networks combined with reinforcement learning, improve generalization across VRP variants by reducing reliance on instance-specific tuning.^[53]^[12] Quantum computing pilots have emerged as a promising frontier for tackling VRP's combinatorial complexity, with D-Wave's quantum annealing systems applied to real-world routing scenarios since 2023. These approaches encode VRP formulations as quadratic unconstrained binary optimization problems, leveraging quantum hardware to explore solution spaces more efficiently than classical methods for medium-sized instances. A 2024 study demonstrated D-Wave's hybrid solver achieving feasible routes for package delivery problems with up to 30 nodes, showing competitive performance with traditional solvers.^[54]^[55] In dynamic and stochastic VRP, real-time rerouting has advanced through integrations with traffic data sources, particularly post-2022 developments using APIs like Google Maps for adaptive planning. These systems incorporate live congestion and delay predictions to adjust routes on-the-fly, minimizing disruptions in urban logistics. A 2024 framework combining Google Maps API data with mathematical modeling reduced total travel times by up to 15% in simulated dynamic environments compared to static benchmarks.^[56] Sustainability-focused variants have evolved to address emissions and energy constraints, extending foundational electric VRP models like Schneider et al.'s 2014 work on time-windowed routing with recharging. Recent multi-objective formulations from 2020 onward incorporate battery degradation and carbon footprint minimization, optimizing for both cost and environmental impact in electric vehicle fleets. A 2024 multi-objective model for capacitated electric VRP balanced routing efficiency with emissions reductions through Pareto-optimal solutions.^[57] Despite these progresses, open problems persist in scaling exact methods to instances with over 1,000 customers, where branch-and-cut algorithms remain computationally prohibitive due to exponential growth in solution spaces. Current exact solvers handle up to a few hundred nodes reliably, but extensions to thousand-scale problems require novel decomposition techniques or hybrid quantum-classical integrations to maintain optimality guarantees. Uncertainty modeling in stochastic VRP also poses significant challenges, particularly in capturing demand variability and correlated disruptions like weather or supply fluctuations. While scenario-based approaches approximate stochastic elements, they struggle with high-dimensional uncertainty propagation, leading to suboptimal robustness in real-world deployments. Enhanced probabilistic modeling, potentially via ML surrogates, is needed to better quantify and mitigate these risks without excessive computational overhead.^[58] Benchmarks from 2025 indicate that ML-hybrid methods outperform classical metaheuristics by approximately 10% in solution quality on dynamic VRP instances, underscoring their potential for practical adoption while highlighting the need for standardized testing suites to compare emerging techniques.^[59]

References

[1]
The Truck Dispatching Problem | Management Science - PubsOnLine
The paper is concerned with the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations ...
[2]
The vehicle routing problem: An overview of exact and approximate ...
In this paper, some of the main known results relative to the Vehicle Routing Problem are surveyed. The paper is organized as follows: (1) definition; ...
[3]
Formulations and Valid Inequalities for the Heterogeneous Vehicle ...
Jul 14, 2005 · We develop six different formulations: the first four based on Miller-Tucker-Zemlin constraints and the last two based on flows.
[4]
Using the Miller-Tucker-Zemlin constraints to formulate a minimal ...
These formulations are based on the well known Miller-Tucker-Zemlin [1] subtour elimination constraints.
[5]
Fifty Years of Vehicle Routing | Transportation Science - PubsOnLine
Oct 21, 2009 · View PDF · View PDF. Tools. Add to favorites · Download Citations · Track ... Fifty Years of Vehicle Routing. Gilbert Laporte. Gilbert Laporte.
[6]
The History and Future of Operations - Harvard Business Review
Jun 30, 2015 · And from the days of the first commercial IBM mainframes in the late 1950s, computers have driven increasing efficiency in manufacturing and ...
[7]
Fifty Years of Vehicle Routing - PubsOnLine
Laporte: Fifty Years of Vehicle Routing. Transportation Science 43(4), pp. 408–416, © 2009 INFORMS. 409 to highly sophisticated mathematical programming.
[8]
A Robust Approach to the Capacitated Vehicle Routing Problem ...
Apr 24, 2020 · Yellow (1970) introduced the parameter λ (called the route shape parameter), which controls the relative importance of the direct arc between ...
[9]
Tabu Search heuristics for the Vehicle Routing Problem with Time ...
This paper surveys the research on the Tabu Search heuristics for the Vehicle Routing Problem with Time Windows (VRPTW).
[10]
2021 Amazon Last Mile Routing Research Challenge: Data Set
Sep 14, 2022 · In this article, we describe the data set released for the research challenge, which includes route-, stop-, and package-level features for ...<|separator|>
[11]
(PDF) Integrating Machine Learning Into Vehicle Routing Problem
Aug 6, 2025 · Machine learning (ML)-based methods have been applied to a variety of combinatorial optimization problems, specifically VRPs.
[12]
[PDF] arXiv:2307.12136v2 [cs.LG] 11 Jun 2024
Jun 11, 2024 · The two sub-problems of 3L-CVRP, vehicle routing and bin-packing, have already been studied independently in the reinforcement learning ...
[13]
[PDF] Complexity of vehicle routing and scheduling problems
The complexity of a class of vehicle routing and scheduling problems is investigated and known NP-hardness results are reviewed and compiled to compile the ...Missing: hard | Show results with:hard
[14]
Christofides et al. 1979 - CMT - VRP-REP: the vehicle routing ...
The Christofides et al. 1979 - CMT dataset is a public, VRP-REP compliant dataset with 14 instances for the Capacitated Vehicle Routing Problem.
[15]
On the Distance Constrained Vehicle Routing Problem - PubsOnLine
Two objective functions are considered: minimize the total distance traveled by vehicles and minimize the number of vehicles used.Missing: definition | Show results with:definition
[16]
[PDF] Distance-Constrained Capacitated Vehicle Routing Problem for The ...
The product of the total distance covered, an average fuel consumption of 9.5 litres per 100km and average cost of fuel per litre at N142,. N163 and N213 ...
[17]
Distance-constrained capacitated vehicle routing problems with ...
The vehicle routing problem (VRP) is commonly defined as the problem of determining optimal delivery or collection routes from several depots to a set of ...
[18]
Vehicle Routing Problem with Time Windows - SpringerLink
In this chapter we discuss the Vehicle Routing Problem with Time Windows in terms of its mathematical modeling, its structure and decomposition alternatives.
[19]
Solomon benchmark - SINTEF
Apr 18, 2008 · Here you find pointers to instance definitions and best known solutions for the 25 and 50 customer instances of Solomon's VRPTW benchmark problems from 1987.
[20]
[PDF] A survey on pickup and delivery models Part II: Transportation ...
Aug 30, 2006 · This part covers all those problem types where goods are transported between pickup and delivery locations, referred to as Vehicle Routing ...
[21]
The General Pickup and Delivery Problem | Transportation Science
In pickup and delivery problems vehicles have to transport loads from origins to destinations without transshipment at intermediate locations.
[22]
A metaheuristic for the pickup and delivery problem with time windows
In this paper, we propose a metaheuristic to solve the pickup and delivery problem with time windows. Our approach is a tabu-embedded simulated annealing ...
[23]
The pickup and delivery problem with time windows - ScienceDirect
The vehicle routing problem (vrp) involves the design of a set of minimum cost routes for a fleet of vehicles which services exactly once a set of customers ...
[24]
A Dynamic Programming Solution to the Single Vehicle Many-to ...
An investigation of the single-vehicle, many-to-many, immediate-request dial-a-ride problem is developed in two parts (I and II).
[25]
How UPS' ORION Algorithm Transformed Its Route Optimization -
Jul 26, 2025 · UPS' ORION algorithm cut 100 million miles from delivery routes each year, saving $300–$400 million and reducing emissions by 100,000 metric ...Missing: vehicle | Show results with:vehicle
[26]
An Integrated Inventory Allocation and Vehicle Routing Problem
We address the problem of distributing a limited amount of inventory among customers using a fleet of vehicles so as to maximize profit.
[27]
On the integrated production, inventory, and distribution routing ...
The integrated Production, Inventory, and Distribution Routing Problem (PIDRP) is concerned with coordinating production, inventory, and delivery operations to ...
[28]
Electric vehicle routing problem: A systematic review and a
This study reviews the development of electric vehicle routing problem (EVRP) in transport logistics.
[29]
Vehicle Routing Problem: Meaning and Solutions (In-depth Guide)
Aug 25, 2025 · The Vehicle Routing Problem (VRP) is a combinatorial optimization challenge that determines the most efficient routes for a fleet of vehicles to ...Types of Vehicle Routing... · Why Do I Need to Solve... · VRP Solution Methods
[30]
(PDF) An Algorithm for Transport Optimization as the Effect of the ...
Aug 7, 2025 · In implementing the European Green Deal to align with the Paris Agreement, the EU has raised its climate ambition and in 2022 is negotiating ...
[31]
Online grocery delivery: Sustainable practice, or congestion ...
During the COVID-19 pandemic we witnessed an unprecedented growth in the use of online grocery services. As of July of 2019, only 20% of customers in the US had ...
[32]
Enhancing E-Grocery-Delivery-Network Resilience with ... - MDPI
Sep 25, 2023 · This paper examines the challenges associated with the efficient planning and operation of an E-grocery delivery system using Autonomous Delivery Robots (ADR)
[33]
A Comprehensive Survey on the Ambulance Routing and Location ...
Jan 10, 2020 · This paper surveys ambulance routing (ARP) and location (ALP) problems, which are modifications of vehicle routing (VRP) and maximum covering ( ...Missing: MDVRP | Show results with:MDVRP
[34]
[PDF] VEHICLE ROUTING FOR BLOOD PRODUCT DELIVERY - thaijo.org
Abstract. This study examines a real life case from a third-party logistics service provider using vehicles to substitute for hospital ambulances.
[35]
On-demand high-capacity ride-sharing via dynamic trip-vehicle ...
Jan 3, 2017 · ... Uber, Lyft, and Via. These systems are able to provide users with a reliable mode of transportation that is catered to the individual and ...
[36]
The flying sidekick traveling salesman problem - ScienceDirect.com
This paper provides two mathematical programming models aimed at optimal routing and scheduling of unmanned aircraft, and delivery trucks, in this new paradigm ...
[37]
A GIS based 3D-Routing-Model to estimate and reduce CO2 ...
The objective of this work was to develop a GIS-based 3D-Routing-Model to illustrate the effects of road inclination on fuel consumption and CO2-Emissions, as ...
[38]
[PDF] Modeling Disaster Response Operations including Road Network ...
In the aftermath of the Great East Japan Earthquake and Tsunami, more than 85 percent of damages on the priority expressway have been recovered after 24 hours ( ...
[39]
The periodic vehicle routing problem with intermediate facilities
For instance, in waste collection problems, each customer has to be typically served with a given periodicity, say once a week, and the working days include all ...
[40]
[PDF] A generalized formulation for vehicle routing problems - arXiv
Sep 16, 2017 · Different types of formulations are proposed in the literature to model vehicle routing problems. Currently, the most used ones can be ...
[41]
An Exact Algorithm for the Capacitated Vehicle Routing Problem ...
In this paper, we describe a new integer programming formulation for the CVRP based on a two-commodity network flow approach.
[42]
Generalized Subtour Elimination Constraints and Connectivity ... - jstor
This paper examines some properties of generalized subtour elimination ... solution of some V.R.P.s-e.g. the capacitated vehicle routeing problem (C.V.R.P.).
[43]
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle ...
Oct 12, 2005 · The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean ...
[44]
Scheduling of Vehicles from a Central Depot to a Number of ...
This paper, after considering certain theoretical aspects of the problem, develops an iterative procedure that enables the rapid selection of an optimum or ...
[45]
A Heuristic Algorithm for the Vehicle-Dispatch Problem - PubsOnLine
This paper introduces and illustrates an efficient algorithm, called the sweep algorithm, for solving medium- as well as large-scale vehicle-dispatch problems.
[46]
A simple and effective evolutionary algorithm for the vehicle routing ...
This paper proposes a GA without trip delimiters, hybridized with a local search procedure. At any time, a chromosome can be converted into an optimal VRP ...
[47]
Order-first split-second methods for vehicle routing problems: A review
Two good examples are the sweep algorithm, commonly attributed to Gillett and Miller (1974), and the Fisher and Jaikumar (1981), where clusters are obtained ...Missing: original | Show results with:original
[48]
Approximation algorithms for some vehicle routing problems
There is an easy reduction proving the NP-hardness of this problem between kPP and MAX WEIGHTED ATMOST PP that consist to complete the graph G instance of kPP ...
[49]
[2509.10361] Parameterized Complexity of Vehicle Routing - arXiv
Sep 12, 2025 · We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and W[\cdot]-hardness for various parameterizations, ...
[50]
[2507.00218] Learning for routing: A guided review of recent ... - arXiv
Jun 30, 2025 · This paper reviews the current progress in applying machine learning (ML) tools to solve NP-hard combinatorial optimization problems, with a focus on routing ...Missing: 2020-2025 | Show results with:2020-2025
[51]
Solving a real-world package delivery routing problem using ...
Oct 21, 2024 · Research focused on the conjunction between quantum computing and routing problems has been very prolific in recent years.
[52]
https://arxiv.org/abs/2509.10361
[53]
Integration of Google Maps API with mathematical modeling for ...
We introduce a novel solution that integrates real-time traffic data into daily vehicle route planning. Specifically, our method incorporates Google Maps API.Missing: rerouting | Show results with:rerouting
[54]
A Sustainable Multi-Objective Model for Capacitated-Electric ... - MDPI
The present study aims to develop a multi-objective mathematical programming model for the Capacitated Electric Vehicle Routing Problem (CEVRP), considering all ...
[55]
A scalable learning approach for the capacitated vehicle routing ...
We propose a heuristic for solving large capacitated vehicle routing problem (CVRP) that carefully integrates a machine learning heuristic with Integer Linear ...Missing: uncertainty | Show results with:uncertainty
[56]
Review of Stochastic Dynamic Vehicle Routing in the Evolving ...
This paper aims to analyse the key concepts, challenges, and recent advancements and opportunities in the evolving urban logistics landscape.
[57]
Deep reinforcement learning for dynamic vehicle routing with ...
In this work, we propose a deep reinforcement learning framework to learn adaptive routing policies for dynamic capacitated vehicle routing problem environments ...