Vehicle Routing and Optimization

Introduction

Vehicle routing is the systematic design of journeys for a fleet that serves geographically dispersed customers. A routing decision determines which vehicle serves each customer, the sequence of visits, departure and arrival times, and sometimes the quantities collected or delivered. In logistics, routing is inseparable from fleet size, vehicle capacity, driver availability, service commitments, fuel consumption, road restrictions, and uncertainty in demand and travel time.

The classical Vehicle Routing Problem (VRP) is deceptively simple to state: determine a set of least-cost routes beginning and ending at a depot so that every customer is served subject to operational constraints. Its practical variants are computationally difficult because routing combines assignment, sequencing, scheduling, and resource-allocation decisions. The VRP is NP-hard; consequently, exact optimization is usually practical only for relatively small or structured instances, while large operational problems require heuristics, metaheuristics, decomposition, or hybrid approaches.

This chapter develops mathematical formulations and solution methods for capacitated, time-window, pickup-and-delivery, split-delivery, multi-depot, heterogeneous-fleet, dynamic, and stochastic routing problems. The emphasis is not only on obtaining a mathematically attractive route, but also on producing a feasible, explainable, robust, and implementable operating plan.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Formulate major vehicle-routing variants using decision variables, objective functions, and constraints.
2. Distinguish feasibility, optimality, robustness, and service quality in routing decisions.
3. Select appropriate exact, heuristic, metaheuristic, and rolling-horizon methods.
4. Evaluate routes using cost, utilization, distance, emissions, lateness, and operational-risk measures.
5. Design routing processes for dynamic and stochastic environments.
6. Interpret managerial, technological, ethical, and governance implications of routing optimization.

1. Routing as a Network Optimization Problem

A road network may be represented by a directed or undirected graph. Let customers and depots be nodes, and let arcs represent feasible movements between nodes. For a complete customer graph, let:

• N be the set of nodes, including depot(s);
• V be the set of vehicles;
• c_ij be the cost of travelling from node i to node j;
• t_ij be travel time on arc (i,j);
• q_i be customer demand;
• Q_k be the capacity of vehicle k.

Costs may include distance, fuel, tolls, driver wages, vehicle depreciation, emissions penalties, and the monetary consequences of lateness. A route is a sequence of nodes satisfying all applicable restrictions. A routing plan is a collection of routes assigned to vehicles.

The basic operational distinction is between hard constraints and soft constraints. A hard constraint cannot be violated, such as a legal vehicle capacity limit. A soft constraint may be violated at a specified penalty, such as a preferred delivery window. In professional applications, soft constraints are often essential because forcing every business requirement to be hard can make the model infeasible.

Core routing terminology

2. The Classical Capacitated VRP

In the Capacitated Vehicle Routing Problem (CVRP), one depot supplies customers with known, non-negative demands. Each vehicle has capacity Q, every customer is served once, and each route starts and ends at the depot.

A binary variable x_ijk equals 1 if vehicle k travels directly from node i to node j, and 0 otherwise. Let y_ik equal 1 if vehicle k serves customer i. A standard objective is to minimize total travel cost:

The objective assumes that costs are additive across arcs and that the cost of a movement does not depend on route history. If fuel consumption depends strongly on load, congestion, or road gradient, this assumption must be modified.

Each customer must be served exactly once:

Flow conservation ensures that a vehicle entering a customer also leaves it:

Vehicle capacity is enforced by:

Here, node 0 denotes the depot. The capacity equation is valid when demand is delivered from the depot and vehicle load is not replenished during the route.

A major modelling issue is elimination of subtours. Degree and flow constraints alone can produce a cycle among customers that is disconnected from the depot. One family of subtour-elimination constraints uses load variables u_i:

For an arc from customer i to customer j, these constraints impose a consistent accumulation of delivered demand. They are commonly associated with Miller–Tucker–Zemlin-style formulations. Alternative formulations include cut-set constraints, single-commodity flow, and set-partitioning models. Stronger formulations generally produce better lower bounds but may require more variables or separation procedures.

Feasibility checks

Before optimization, basic feasibility should be tested. Necessary conditions include:

This condition is necessary but not sufficient. A plan may still be infeasible because of route-duration limits, customer compatibility, restricted access, or time windows. If all customers must be served and the total demand exceeds available capacity, the model must either add vehicles, allow split deliveries, permit outsourcing, or introduce unmet-demand penalties.

Worked example: a small CVRP

An illustrative depot serves four customers with demands 2, 3, 4, and 1 units. Two identical vehicles each have capacity 6 units. The total demand is 10 units, while total fleet capacity is 12 units, so aggregate capacity is sufficient. However, no vehicle can serve customers with demands 3 and 4 together because their combined demand is 7. A feasible partition is:

• Vehicle 1: customers with demands 4 and 2, total load 6;
• Vehicle 2: customers with demands 3 and 1, total load 4.

The example demonstrates that aggregate capacity is only a preliminary test. Feasibility depends on the partition of customers among routes and, in a time-dependent problem, on the temporal ordering of visits.

3. Time-Window Routing

The Vehicle Routing Problem with Time Windows (VRPTW) adds a service interval for each customer. Customer i may be served only within [a_i,b_i]], where a_i is the earliest service time and b_i is the latest. Let s_i be service duration and T_i be the start of service.

For an arc (i,j) selected in a route, temporal feasibility requires:

where M is a sufficiently large constant. The service-time bounds are:

The units of T_i, s_i, and t_ij must be identical, such as minutes from the beginning of the planning day. M must be large enough to deactivate the sequencing constraint when the arc is not selected, but excessively large values can weaken the linear programming relaxation and cause numerical instability.

Waiting is permitted when a vehicle reaches a customer before a_i. If early arrival is not allowed operationally, the model must distinguish arrival time from service-start time. A route may therefore include travel, waiting, service, and return-to-depot time. A maximum route duration constraint can be written as:

where H_k is the permitted duration for vehicle k.

Time-window models involve a trade-off between distance and schedule flexibility. A geographically short route may be infeasible because its customers have incompatible windows, while a longer route may be feasible because it visits customers in a more suitable temporal order. Practical objectives often combine travel cost and lateness penalties:

where L_i and E_i represent lateness and earliness deviations, and α and β are penalty weights. For hard windows, these deviation variables are not permitted to be positive.

4. Pickup-and-Delivery Problems

In a Pickup-and-Delivery Problem (PDP), a request has both an origin and a destination. Examples include parcel collection, reverse logistics, passenger transport, reusable packaging, and spare-parts returns. A request r has pickup node p_r, delivery node d_r, and quantity w_r.

The principal precedence condition is:

In a route sequence, the pickup must occur before its corresponding delivery. If vehicle capacity is Q, load evolution must satisfy:

This expression is written for successive route positions h and h+1. It assumes quantities are measured in a common capacity unit and that pickups increase load while deliveries reduce it. In a mixed pickup-and-delivery operation, a vehicle may have unused capacity initially, collect goods, deliver some goods, and then collect additional goods.

PDPs are substantially more difficult than ordinary deliveries because route feasibility depends on sequence as well as customer assignment. Pairing and precedence constraints can also interact with time windows, vehicle compatibility, and maximum ride-time or transit-time requirements.

5. Split Deliveries and Related Variants

In a standard CVRP, each customer is served once. In a Split Delivery VRP (SDVRP), a customer may be served by multiple vehicles or on multiple visits. Let z_ik denote the quantity delivered to customer i by vehicle k. Demand satisfaction becomes:

and vehicle capacity becomes:

The variable z_ik is continuous when goods are divisible; it must be integer when items are indivisible. Split delivery can reduce total distance and improve fleet utilization, especially when a few customers have demand close to vehicle capacity. It also increases handling, scheduling complexity, customer inconvenience, and the risk of multiple delivery appointments.

Other important variants include:

• Open VRP: vehicles need not return to the starting depot.
• Periodic VRP: customers are served on selected days over a planning horizon.
• Inventory-routing problem: routing and customer inventory decisions are integrated.
• Green VRP: fuel, emissions, alternative fuels, or energy consumption are explicitly modelled.
• Location-routing problem: depot or facility locations and routes are optimized jointly.

6. Multi-Depot and Heterogeneous-Fleet Routing

In a Multi-Depot VRP (MDVRP), vehicles start from one of several depots. Each customer must be assigned to a depot and a vehicle, subject to depot capacity, fleet availability, and route restrictions. Let z_id equal 1 if customer i is assigned to depot d. Then:

A customer may be assigned based on proximity, vehicle availability, service region, or total network cost. Simple nearest-depot allocation is not generally optimal because it ignores route interactions and depot congestion.

A heterogeneous fleet contains vehicles differing in capacity, cost, dimensions, equipment, or energy source. Let Q_k be vehicle-specific capacity and c_ijk vehicle-specific travel cost. The capacity restriction becomes:

Vehicle-specific constraints may include refrigerated capability, hazardous-material authorization, tail-lift availability, height restrictions, and driver qualification. A vehicle with greater capacity may have higher fixed and variable cost, so the largest vehicle is not automatically the best choice.

A realistic objective often includes fixed vehicle activation cost:

where u_k is 1 if vehicle k is used and F_k is its fixed operating cost. This formulation captures the trade-off between using more vehicles with shorter routes and fewer vehicles with longer routes.

7. Exact Optimization Methods

Exact methods seek a provably optimal solution or a mathematically certified optimality gap. The principal approaches are:

Mixed-integer linear programming

MILP represents routing choices with binary variables and continuous scheduling or load variables. Modern solvers use branch-and-bound, cutting planes, presolve, heuristics, and parallel processing. MILP is valuable for small and medium instances, strategic planning, benchmarking heuristics, and situations requiring explainable constraints.

Set-partitioning and column generation

A route-based formulation treats each feasible route as a column. Let R be the set of feasible routes and a_ir equal 1 if route r serves customer i. If c_r is route cost and y_r indicates route selection:

subject to:

The challenge is that R may be enormous. Column generation begins with a restricted set of routes and generates promising routes by solving a pricing problem. In VRP applications, the pricing problem is often a resource-constrained shortest-path problem. Branch-and-price adds branching to obtain integrality; branch-and-cut adds valid inequalities and separation procedures.

Exact methods are not synonymous with practical superiority. An exact solver may spend substantial computational effort proving that a solution is optimal when an operationally indistinguishable solution is already available. The value of an optimality certificate depends on the decision context.

8. Heuristics and Metaheuristics

Heuristics construct good solutions rapidly without guaranteeing optimality. Common constructive methods include:

• Savings heuristic: initially creates one route per customer and merges routes when the saving is attractive.
• Sweep method: sorts customers by polar angle around a depot and groups them into capacity-feasible routes.
• Insertion heuristics: insert an unassigned customer where the incremental cost or time penalty is smallest.
• Cluster-first, route-second: groups customers, then sequences each cluster.

For two routes containing depot–i–depot and depot–j–depot, the classical distance saving from merging them is:

This expression assumes symmetric or appropriately directed travel costs and does not, by itself, guarantee capacity or time-window feasibility.

Metaheuristics explore broader solution spaces. Important families include:

• Local search: repeatedly applies improving moves such as relocate, swap, and 2-opt.
• Tabu search: temporarily forbids recently used moves to escape local optima.
• Simulated annealing: occasionally accepts worsening moves, with acceptance probability declining as a control parameter cools.
• Genetic algorithms: evolve populations of encoded routing solutions through selection, crossover, and mutation.
• Ant colony optimization: reinforces promising arcs using artificial pheromone trails.
• Large neighbourhood search (LNS): destroys part of a solution and reconstructs it, often with an exact or sophisticated repair operator.
• Adaptive LNS: changes destroy and repair operators according to their historical performance.

A solution method should specify its representation, feasibility mechanism, neighborhood operators, termination condition, random-seed policy, and evaluation criteria. Reporting only the best run is weak practice; repeated runs and dispersion measures are needed for stochastic algorithms.

9. Dynamic and Stochastic Routing

A static routing model assumes that all relevant information is known before dispatch. In reality, new orders arrive, traffic changes, customers become unavailable, and actual service times differ from estimates. A dynamic VRP updates routes as information arrives. A stochastic VRP explicitly models uncertain quantities such as demand, travel time, cancellations, or service duration.

A practical dynamic architecture is:

1. Generate an initial plan using currently known information.
2. Execute the first part of the plan.
3. Receive new orders and observations.
4. Freeze decisions that can no longer be changed.
5. Re-optimize the unfrozen remainder.
6. Communicate route changes and monitor service performance.

This is a rolling-horizon or model-predictive-control approach. Re-optimization should include a stability penalty so that unnecessary route changes are discouraged:

where γ represents the operational cost or managerial importance of changing previously communicated plans.

Stochastic methods include scenario-based stochastic programming, chance constraints, robust optimization, and simulation-based optimization. A chance constraint may require a service condition to hold with probability at least 1−ε:

Here, ε is the tolerated probability of violation. Such a condition is meaningful only when the probability model is credible and sufficiently calibrated. Robust optimization instead protects against a specified uncertainty set, often producing safer but more conservative routes.

A useful operational distinction is between risk-neutral and risk-averse objectives. Risk-neutral optimization minimizes expected cost, whereas risk-averse optimization may penalize variance, high-percentile duration, or service failure. The appropriate choice depends on customer commitments, emergency consequences, and the cost of unused capacity or protective slack.

10. Worked Application: Regional Distributor

The following is an illustrative case. A regional distributor serves supermarkets from one depot. It operates six vehicles, including three 8-pallet vehicles and three 12-pallet vehicles. Orders arrive by 18:00 for next-day service. Supermarkets have delivery windows, some roads prohibit large vehicles, and returned packaging must be collected.

Problem

The existing manual plan uses one route per sales territory. It frequently produces low vehicle utilization, late deliveries in the urban area, and unnecessary returns to the depot. The manager wants to reduce cost without weakening delivery reliability.

Analysis

The operation is a heterogeneous-fleet pickup-and-delivery VRPTW. Delivery quantities consume capacity; returned packaging collected during the route increases vehicle load. The model must include:

• customer service windows and service durations;
• vehicle-specific capacity and road eligibility;
• pickup-before-depot-return logic for returned packaging;
• maximum driver duty and route duration;
• fixed activation costs;
• a penalty for late service and route changes;
• a practical reserve for uncertain travel time.

The planning team first validates data. Geocoded addresses are checked, travel times are estimated by time of day, service durations are derived from historical observations, and missing return quantities are assigned probability distributions rather than silently set to zero.

Approach

A two-stage process is used. First, a MILP assigns difficult customers and determines a high-quality skeleton for the routes. Second, adaptive large neighbourhood search sequences visits and repairs time-window and load violations. During execution, a rolling-horizon optimizer replans only the unserved portion of routes every 30 minutes or when a major event occurs.

The evaluation function combines operating cost, lateness, infeasible-solution penalties, and route instability. Large vehicles are prohibited from restricted roads, and a reserve capacity of 10% is maintained for uncertain returns. The reserve is not treated as a universal law; it is a managerial policy calibrated using historical failure rates.

Outcome

In the pilot, the algorithm reduces empty return travel and increases average pallet utilization while maintaining the required delivery-service level. The most important improvement is not the shortest route in isolation, but coordinated assignment of vehicle type, delivery time, return collection, and urban access restrictions. Dispatchers retain authority to override a route when local knowledge identifies a road closure or customer-specific issue.

Learning points

1. Correct classification of the routing variant is essential.
2. Data quality can dominate algorithm choice.
3. A route must remain feasible after pickups, not merely after deliveries.
4. A technically optimal plan may be unacceptable if it changes too frequently.
5. Human override should be governed, recorded, and reviewed rather than treated as algorithmic failure.

11. Evaluation, Governance, and Implementation

Routing solutions should be evaluated on more than total distance. Useful performance indicators include:

Carbon calculations must identify the boundary and emission factor. A simplified fuel-based estimate is:

Fuel may be measured in litres and the emission factor in kilograms of CO₂e per litre, producing kilograms of CO₂e. Electric fleets require an appropriate energy boundary, such as electricity drawn from the grid, and should account for charging availability and battery constraints.

Implementation requires an integrated data and control architecture: order management, telematics, map services, traffic data, warehouse readiness, driver communication, and proof-of-delivery systems. APIs and event streams can support dynamic updates, but automated re-routing should not create unsafe or unlawful instructions.

AI can assist with demand forecasting, travel-time prediction, service-time estimation, address correction, and route construction. However, predictive accuracy does not guarantee operational fairness or feasibility. Models should be monitored for data drift, systematically poor performance in particular regions, and inappropriate recommendations. Human accountability remains necessary for safety, labor compliance, customer commitments, and exceptional events.

Routing also raises governance concerns. Driver data may reveal working patterns and personal information. Optimization that systematically assigns the most difficult routes to a particular group may create inequitable workloads. Compliance requirements may include maximum driving hours, rest periods, hazardous-material rules, vehicle weight limits, accessibility obligations, and local delivery restrictions. These requirements should be encoded as constraints or approval rules, not left to informal memory.

12. Challenges and Limitations

First, model realism creates computational complexity. Adding time windows, multiple depots, vehicle types, pickups, uncertainty, and energy constraints can cause solution times to grow rapidly. Second, data uncertainty limits the value of precision: a mathematically exact solution based on poor travel-time estimates is not operationally exact. Third, cost objectives can conflict with service, driver welfare, emissions, and customer relationships.

Fourth, route plans are vulnerable to endogenous effects. If every carrier follows a historically estimated travel time, congestion patterns may change. Fifth, frequent re-optimization can create instability, confuse drivers, and undermine customer trust. Sixth, a solver may exploit an unintended modelling loophole—for example, by using unrealistic waiting, omitting loading time, or treating a restricted road as available. Model validation must therefore include scenario testing, route replay, and field review.

Best practice is to begin with a validated feasible baseline, add complexity incrementally, compare methods on common benchmark instances, measure actual operational outcomes, and maintain an audit trail of data, parameters, overrides, and route changes.

Chapter Summary

Vehicle routing is a family of network optimization problems involving assignment, sequencing, scheduling, and resource constraints. The CVRP assigns each customer to one capacity-feasible depot route; VRPTW adds service intervals; pickup-and-delivery models impose pairing and precedence; split-delivery models allow demand to be divided; multi-depot and heterogeneous-fleet models represent distributed resources and vehicle-specific capabilities. Dynamic and stochastic models address new information and uncertainty through rolling horizons, scenarios, chance constraints, or robust protection.

MILP, branch-and-cut, branch-and-price, and column generation can provide exact solutions or optimality bounds. Constructive heuristics, local search, tabu search, simulated annealing, genetic algorithms, and adaptive large neighbourhood search are important for large practical instances. Method selection should consider scale, time available, data quality, explainability, and the cost of infeasibility.

Professional routing requires more than minimizing distance. Service reliability, driver safety, emissions, route stability, legal compliance, human oversight, and data governance must be incorporated into design and evaluation. The best implementation is a controlled decision system that combines optimization, accurate data, operational knowledge, and continuous performance monitoring.

Key Terms

Vehicle Routing Problem: Optimization problem for designing routes that serve a set of nodes with a fleet of vehicles.

Capacitated VRP: Routing problem in which vehicle load cannot exceed capacity.

Time window: Earliest and latest permitted time for service.

Pickup-and-Delivery Problem: Routing problem with paired origin and destination requests.

Split Delivery VRP: Problem allowing one customer’s demand to be served by multiple visits or vehicles.

Multi-Depot VRP: Routing problem involving two or more origin depots.

Heterogeneous fleet: Fleet containing vehicles with different capacities, costs, or capabilities.

Subtour: Disconnected cycle that fails to connect to the depot route.

Feasible solution: Solution satisfying all hard constraints.

MILP: Mixed-integer linear programming model containing continuous and discrete decisions.

Column generation: Method that generates promising route variables instead of listing all routes initially.

Branch-and-price: Combination of branch-and-bound and column generation.

Heuristic: Problem-solving method designed to find good solutions without an optimality guarantee.

Metaheuristic: General search framework that guides exploration of complex solution spaces.

Rolling horizon: Repeatedly updating a plan as time advances and information changes.

Chance constraint: Constraint required to hold with a specified probability.

Robust optimization: Optimization designed to remain feasible across a defined uncertainty set.

Route stability: Degree to which planned routes remain unchanged after replanning.

Optimality gap: Difference between an incumbent solution and a certified bound on the optimum.

Service-level constraint: Requirement governing delivery reliability or customer performance.

Review Questions

Short Answer Questions

1. What distinguishes a hard constraint from a soft constraint in vehicle routing?
2. Why are subtour-elimination constraints required in a CVRP formulation?
3. State the precedence requirement in a pickup-and-delivery problem.
4. What is the principal operational advantage of allowing split deliveries?
5. Define rolling-horizon routing.

Long Answer Questions

1. Formulate the main assignment, capacity, flow, and timing components of a VRPTW.
2. Compare MILP, column generation, and metaheuristic approaches for large routing problems.
3. Explain how heterogeneous-fleet constraints affect vehicle assignment and route cost.
4. Discuss the advantages and limitations of robust optimization and chance constraints.
5. Explain why data quality and governance are as important as algorithm selection in routing implementation.

Analytical / Application Questions

1. A distributor has customers whose total demand is below total fleet capacity, but several time windows overlap narrowly. Develop a procedure for testing whether the instance is feasible before running a full optimization model.
2. Design an objective function for a dynamic delivery operation that balances travel cost, lateness, emissions, and route instability. Explain how the weights should be calibrated.
3. A route collects returns after making deliveries. Identify the load, precedence, vehicle-compatibility, and uncertainty constraints that should be added to a basic CVRP model.

Multiple Choice Questions with Answers

Question 1

Which constraint ensures that every customer is served exactly once in a standard CVRP?

A. ∑ vehicle capacities must equal zero

B. ∑ vehicle assignment variables for each customer equals 1

C. Every vehicle must visit every customer

D. Every route must contain the same number of customers

Correct Answer: B. ∑ vehicle assignment variables for each customer equals 1

Question 2

In a pickup-and-delivery problem, which relationship is mandatory?

A. Delivery must occur before pickup

B. Pickup and delivery must use different fleets

C. Pickup must occur before its corresponding delivery

D. Pickup quantity must always equal vehicle capacity

Correct Answer: C. Pickup must occur before its corresponding delivery

Question 3

What is the main purpose of subtour-elimination constraints?

A. To increase customer demand

B. To prevent disconnected customer cycles

C. To force all vehicles to be used

D. To remove vehicle-capacity limits

Correct Answer: B. To prevent disconnected customer cycles

Question 4

A vehicle has capacity 10 units and is assigned demands of 4, 3, and 2 units. What is its unused capacity?

A. 1 unit

B. 2 units

C. 3 units

D. 9 units

Correct Answer: A. 1 unit

Question 5

Which feature distinguishes a split-delivery VRP from a standard CVRP?

A. Vehicles cannot return to the depot

B. Customers may be served by more than one vehicle or visit

C. All vehicles must have different capacities

D. Travel times are always stochastic

Correct Answer: B. Customers may be served by more than one vehicle or visit

Question 6

In a time-window model, what does T_i usually represent?

A. Vehicle capacity at node i

B. Cost of vehicle i

C. Start of service at customer i

D. Number of vehicles at depot i

Correct Answer: C. Start of service at customer i

Question 7

Which method generates promising route variables instead of explicitly listing every possible route initially?

A. Column generation

B. Nearest-neighbour sorting only

C. Simple capacity checking

D. Inventory counting

Correct Answer: A. Column generation

Question 8

What is a principal characteristic of a heterogeneous fleet?

A. All vehicles have identical capacities and costs

B. Vehicles differ in capacities, costs, or capabilities

C. Vehicles cannot serve customers

D. Vehicles must operate from different countries

Correct Answer: B. Vehicles differ in capacities, costs, or capabilities

Question 9

What is the purpose of a route-stability penalty in dynamic routing?

A. To encourage unnecessary route changes

B. To discourage excessive changes to communicated plans

C. To eliminate all travel costs

D. To make every route identical

Correct Answer: B. To discourage excessive changes to communicated plans

Question 10

A chance constraint written as P(route duration ≤ H) ≥ 1−ε requires what?

A. The route always has zero duration

B. The route duration exceeds H with probability ε or less

C. The vehicle capacity equals H

D. The route must use exactly ε vehicles

Correct Answer: B. The route duration exceeds H with probability ε or less