Vehicle Routing Problem Models and Variants

Introduction

Vehicle routing is the structured design of vehicle movements from one or more origins to a set of customers or facilities. It determines which locations each vehicle visits, in what sequence, and sometimes on which day and at what time. In practice, routing decisions affect transportation cost, fleet utilization, customer service, emissions, driver workload, and compliance with operating restrictions.

The classical Vehicle Routing Problem (VRP) is deceptively simple: serve every customer once, begin and end at a depot, respect vehicle capacity, and minimize cost. Real distribution systems rarely satisfy all of these assumptions. Fleets may contain different vehicle types; customers may require pickups as well as deliveries; a customer’s demand may be divided among vehicles; vehicles may start at different depots; and service may be restricted to specified days or time windows. The value of VRP modeling therefore lies not in one universal model, but in selecting a formulation whose assumptions represent the operating system sufficiently well.

This chapter develops major VRP variants and explains how they are related. It emphasizes model structure, assumptions, managerial interpretation, and implementation choices. The notation is based on mixed-integer programming, although the same concepts support constraint programming, metaheuristics, simulation, and commercial optimization software.

Learning objectives

By the end of this chapter, you should be able to:

1. Formulate the capacitated vehicle routing problem and explain its principal constraints.
2. Distinguish multi-depot, heterogeneous-fleet, pickup-and-delivery, split-delivery, periodic, open, and time-window variants.
3. Select an appropriate VRP variant for a realistic distribution setting.
4. Interpret objective functions, feasibility conditions, and trade-offs in routing models.
5. Evaluate data, technology, governance, and implementation issues in practical routing projects.

1. A common modeling language

Let customers be represented by nodes in a directed network. A depot is usually node 0, and customer nodes belong to set N. Let K denote the set of available vehicles. For an arc from node i to node j, let cᵢⱼ be travel cost, tᵢⱼ travel time, and dᵢ customer demand. A binary decision variable xᵢⱼᵏ equals 1 if vehicle k travels directly from i to j and 0 otherwise. A visit variable yᵢᵏ equals 1 when vehicle k serves customer i. Vehicle capacity is Qᵏ.

The variable xᵢⱼᵏ is a routing variable; it does not by itself prove that a customer is served. Service constraints are therefore required. A route is a sequence of arcs, such as 0 → 4 → 2 → 7 → 0. The route’s travel cost is the sum of the costs of its arcs:

The summation is taken over all relevant arcs and the selected vehicle. If cost is measured in currency per kilometre, cᵢⱼ must be multiplied by distance in kilometres, or it may already include distance-based cost. Fixed vehicle-use costs, driver costs, tolls, emissions charges, and overtime may be added separately.

A standard weighted objective is:

where fₖ is the fixed cost of using vehicle k, zₖ is a binary vehicle-use variable, and P represents penalty terms. Penalties should be used cautiously: an excessively large penalty can create numerical instability, whereas a small penalty may allow unacceptable service violations.

The principal assumptions of a basic VRP are often the following:

• every customer is known before planning;
• each customer is served once;
• demand is deterministic;
• vehicles have fixed capacities;
• travel costs are known and usually symmetric or directed in a known way;
• routes begin and end at a depot;
• vehicles are available for the planning horizon; and
• service does not depend on complex appointment constraints.

These assumptions are modeling choices, not laws of distribution. A robust model makes them explicit.

2. The Capacitated Vehicle Routing Problem

The Capacitated Vehicle Routing Problem (CVRP) is the foundational model. One depot supplies customers with known nonnegative demand. Each customer is visited exactly once, each route starts and finishes at the depot, and the total demand assigned to a vehicle cannot exceed its capacity.

A simplified formulation uses xᵢⱼᵏ and yᵢᵏ. Customer coverage is imposed by:

Each vehicle must have consistent flow into and out of a customer:

The sums include appropriate nodes and exclude self-loops. Capacity is represented by:

Depot departure and return constraints link vehicle use to route formation. For example, if zₖ indicates use of vehicle k:

Flow conservation alone can permit disconnected subtours, such as a cycle among customers that never connects to the depot. Subtour-elimination constraints are therefore essential. One classical family uses ordering variables uᵢ for customers:

for distinct customers i and j, with bounds such as 1 ≤ uᵢ ≤ |N|. This Miller–Tucker–Zemlin-style constraint prevents a customer-only cycle under the stated bounds. Alternative formulations include cut-set constraints, single-commodity flow, and multi-commodity flow. Stronger formulations generally produce better optimization performance but may require more variables or constraints.

Worked example: capacity feasibility

Suppose four customers have demands of 3, 5, 4, and 6 pallets. Two identical vehicles each have capacity 10 pallets. A route serving customers with demands 3 and 6 carries 9 pallets and is feasible. A route serving customers with demands 5, 4, and 3 carries 12 pallets and is infeasible. A feasible assignment is therefore, for example, {6, 3} and {5, 4}, with loads 9 and 9 pallets. This simple calculation illustrates that a geographically attractive route may still be impossible because of capacity.

The CVRP is computationally difficult: it is NP-hard, meaning that no polynomial-time exact algorithm is known for the general case. Exact mixed-integer optimization is useful for small and medium instances or for producing benchmark solutions. Large operational instances commonly require savings heuristics, local search, tabu search, simulated annealing, genetic algorithms, adaptive large-neighborhood search, or hybrid methods.

3. Multi-depot VRP

In a Multi-Depot VRP (MDVRP), vehicles may originate from several depots. Each customer must be assigned to a depot and a vehicle, subject to depot inventories, fleet availability, and route constraints. The model is appropriate for regional distribution networks, cross-dock systems, and firms operating multiple branches.

Let D be the set of depots and K_d the vehicles associated with depot d. A vehicle route must leave and return to its assigned depot. The assignment constraint can be expressed as:

Depot-specific capacity or fleet limits may be written as:

When vehicles are allowed to end at a depot different from their origin, the problem becomes a more general multi-depot or end-depot routing problem. That flexibility can reduce distance but may create vehicle-repositioning, labor, and asset-control costs. Depot assignment should not be determined only by geographic proximity; inventory availability, loading time, congestion, and service territory rules may dominate.

4. Heterogeneous-fleet VRP

A Heterogeneous-Fleet VRP (HFVRP) contains vehicles with different capacities, fixed costs, variable costs, speeds, access restrictions, or emissions characteristics. A small van may enter urban streets but carry little freight; a large truck may be cheaper per pallet but unable to access a customer.

Vehicle type affects both cost and feasibility. If vehicle k has capacity Qᵏ, the capacity constraint remains:

A vehicle-type availability constraint can be written as:

where K_g is the set of vehicles of type g and m_g is the number available. A route may also be prohibited for a vehicle because of road restrictions, refrigeration requirements, hazardous-material rules, or loading compatibility. Such restrictions should be represented as explicit feasibility constraints rather than hidden in cost estimates.

Fleet choice creates an important trade-off. A large vehicle can consolidate demand and reduce the number of routes, but its fixed cost, access limitations, and empty running may be higher. A fleet model should therefore consider total cost, not capacity utilization alone. Environmental objectives may include fuel consumption or emissions by vehicle and arc. If eᵢⱼᵏ denotes emissions, a carbon-aware objective may add λ∑ₖ∑ᵢ∑ⱼ eᵢⱼᵏxᵢⱼᵏ, where λ is the monetary value assigned to an emissions unit. The value of λ is a policy choice and should be disclosed.

5. Pickup-and-delivery routing

Pickup-and-Delivery VRP (PDVRP) models shipments that have an origin and a destination. Examples include courier collections, reverse logistics, reusable packaging, repair returns, and passenger transportation. A pickup-and-delivery request r has pickup node p(r), delivery node q(r), and quantity wᵣ.

The defining precedence condition is that pickup must occur before delivery. If Aᵣ and Bᵣ represent service positions, then:

The exact expression depends on the position variables used. In a vehicle-load formulation, load evolves along a route. If Lᵢᵏ is the load after visiting i, pickup quantities increase load and delivery quantities decrease it. A generic balance is:

where M is a sufficiently large valid constant. Loads must satisfy 0 ≤ Lᵢᵏ ≤ Qᵏ. In many pickup-and-delivery systems, pairing constraints also require the pickup and corresponding delivery to be served by the same vehicle.

The distinction between delivery-only capacity and pickup-and-delivery capacity is important. A vehicle may begin with outbound goods, collect returns, and approach capacity even when its remaining deliveries are small. Incorrectly modeling only delivery demand can produce operationally impossible routes.

6. Split-delivery VRP

In a Split-Delivery VRP (SDVRP), a customer’s demand may be served by multiple vehicles. This is useful when customer demand exceeds vehicle capacity, when deliveries are divisible, or when avoiding an extra long route has high value.

Let qᵢᵏ be the quantity delivered to customer i by vehicle k. Demand satisfaction becomes:

Vehicle capacity becomes:

A binary variable may indicate whether vehicle k visits i, with linking constraints such as qᵢᵏ ≤ dᵢyᵢᵏ. If a model permits splitting without controlling the number of visits, it may generate many small deliveries that are mathematically efficient but operationally undesirable. Stop costs, minimum drop quantities, or a limit on the number of visits can address this issue.

Split delivery can lower travel cost and improve capacity utilization, but it may increase receiving labor, congestion, paperwork, and customer dissatisfaction. It is especially appropriate for bulk commodities and less appropriate where a customer expects one sealed shipment.

7. Periodic and multi-period VRP

A Periodic VRP (PVRP) plans service over several days rather than one day. Customers may require particular visit frequencies, such as three visits per week, and may have allowable visit-day combinations. The model must jointly decide service days and routes.

Let T be the set of planning periods and yᵢₜ indicate whether customer i is served in period t. If customer i requires rᵢ visits, then:

If a customer can be served only on allowable days Aᵢ, then yᵢₜ = 0 for t not in Aᵢ. Daily routing variables then connect selected customers to vehicles in each period. Inventory and service-level requirements may also link periods. For a replenishment setting, the planner may permit a delivery schedule only if inventory remains between lower and upper bounds.

Periodic routing creates a strategic trade-off between route efficiency and customer convenience. A schedule that is cheapest on each individual day may be inferior over the week if it creates uneven workloads, excessive driver overtime, or poor coordination with warehouse operations.

8. Open vehicle routing

In the Open VRP, a vehicle need not return to its original depot. Routes may start at a depot and finish at the last customer, a different facility, or another operational endpoint. This is relevant to one-way delivery operations, contractor fleets, and routes where drivers finish at home or a regional terminal.

Open routing can reduce deadhead distance, but the apparent saving may be transferred to another activity: vehicle recovery, driver transportation, repositioning, or next-day availability. Therefore, the objective should include end-of-route costs and the next planning period’s starting location where relevant. An open route is not automatically cheaper once asset and labor consequences are included.

9. Vehicle Routing Problem with Time Windows

In the VRP with Time Windows (VRPTW), customer i must be served within [aᵢ, bᵢ]. Let sᵢ be service start time and τᵢ service duration. If vehicle k travels from i to j, then:

The time-window restriction is:

Here tᵢⱼ and τᵢ are measured in consistent time units, such as minutes, and M must be large enough to deactivate the precedence constraint when xᵢⱼᵏ = 0 but not unnecessarily large. Waiting is allowed when a vehicle arrives before aᵢ, unless the operating policy forbids it. If service must finish by bᵢ, the interpretation and constraint must be adjusted accordingly.

Time windows may be hard or soft. A hard window makes violation infeasible. A soft window allows violation with a penalty, such as:

where early_i and late_i measure deviations and αᵢ, βᵢ are penalty rates. Soft windows are useful when customers have differentiated service agreements, but the penalty must reflect contractual and reputational consequences.

Time windows can make a route infeasible even when distance and capacity are adequate. Service time, loading delays, traffic uncertainty, driver breaks, and depot queues must be included in realistic schedules. Deterministic travel times may be inappropriate in congested networks; robust or stochastic methods can add buffers or optimize expected and risk-adjusted performance.

10. Combining variants

Real systems commonly require a combination of variants. For example, a regional food distributor may operate a multi-depot, heterogeneous-fleet, pickup-and-delivery VRPTW with periodic service. Combining features increases realism but also increases data requirements, computational complexity, and model risk.

A useful modeling sequence is:

1. Define the service promise and planning horizon.
2. Identify physical flows: deliveries, pickups, returns, and transfers.
3. Identify resources: depots, vehicle types, drivers, and loading equipment.
4. Specify hard constraints and negotiable preferences.
5. Build a simple validated model.
6. Add variants one at a time and test their operational effect.
7. Compare optimized routes with dispatcher knowledge and field feasibility.

Over-modeling can be as harmful as under-modeling. A sophisticated model using unreliable travel times or inaccurate service durations may produce less useful routes than a simpler model with credible data.

11. Illustrative case: NorthRiver Medical Supply

This is a fictional illustrative case.

Background

NorthRiver Medical Supply distributes medicines and clinical consumables from two depots to 38 hospitals. The fleet includes refrigerated vans and larger temperature-controlled trucks. Hospitals have receiving windows, emergency orders occur during the day, and reusable containers are collected on return journeys.

Problem

The existing planning process assigns customers to depots manually and sequences stops by geographic proximity. It frequently creates late arrivals at large hospitals, underuses the larger trucks, and fails to reserve sufficient capacity for container returns. One hospital requires three deliveries per week, while several rural hospitals accept deliveries only in morning windows.

Analysis

The correct model is not a basic CVRP. It requires:

• multiple depots and depot-specific vehicle availability;
• heterogeneous refrigerated vehicles;
• pickup-and-delivery flows for reusable containers;
• time windows and service times;
• periodic service requirements; and
• possibly soft penalties for noncritical lateness.

Emergency orders should be handled through a re-optimization policy rather than simply inserted without checking capacity and time feasibility. Travel-time estimates should use historical time-of-day data, and a practical buffer should be tested through simulation.

Approach and solution

NorthRiver first created a baseline multi-depot VRPTW using confirmed customer windows and measured service times. It then added vehicle types and container pickups. Periodic service patterns were generated for the weekly horizon, with constraints preventing a hospital from receiving multiple visits too close together. Routes were optimized overnight, and dispatchers retained authority to approve emergency changes.

The organization used a lexicographic policy: first minimize hard violations, then minimize weighted transport cost and overtime, and finally reduce emissions. This hierarchy prevented a small cost saving from overriding a medical delivery requirement. Candidate plans were tested against historical travel-time scenarios before deployment.

Outcome

In the pilot region, the model reduced total route kilometres and improved on-time performance, but it also revealed that some apparently efficient routes created excessive loading peaks at one depot. The final implementation therefore included depot appointment limits and a small fleet reserve. The outcome demonstrates that routing optimization must be coordinated with warehouse capacity, inventory readiness, driver schedules, and exception management.

Learning points

The case illustrates four principles. First, variant selection should follow the physical system. Second, reverse flows must be modeled explicitly. Third, service reliability may be more important than distance minimization. Fourth, optimization output requires operational validation and human governance.

12. Solution methods and technology

Exact mixed-integer programming can provide optimality proofs for smaller cases and lower bounds for larger cases. Heuristics are often faster and more adaptable. Construction heuristics create an initial solution, while improvement methods modify route segments through moves such as relocate, swap, 2-opt, and cross-exchange. Large-neighborhood search repeatedly destroys and repairs parts of a solution, making it effective for complex constraints.

A practical architecture commonly contains: a master-data layer, a travel-time and geospatial layer, an optimization engine, a dispatcher interface, a mobile execution system, and a monitoring layer. Artificial intelligence can support demand forecasting, travel-time prediction, anomaly detection, and adaptive search. It should not be treated as a substitute for explicit constraints. A machine-learning model may predict travel time well but still produce an infeasible route unless capacity, precedence, time windows, and legal restrictions are enforced.

Important performance measures include total cost, kilometres, vehicle utilization, route duration, on-time percentage, overtime, number of stops, emissions, failed deliveries, and solution computation time. A single objective can conceal poor performance in another dimension. Managers should examine a Pareto frontier or scenario comparison when cost, service, and sustainability objectives conflict.

13. Governance, ethics, and limitations

Routing systems influence workloads, customer access, and environmental exposure. Ethical implementation requires attention to driver break rules, safe operating hours, equitable workload allocation, and nondiscrimination among service territories. A model should never reward unsafe speeding or systematically assign difficult routes to particular workers without review.

Data governance is equally important. Customer locations, delivery records, driver identifiers, and GPS traces may be personal or commercially sensitive. Access controls, retention policies, audit logs, and transparent use purposes are necessary. Optimization results should be explainable enough for dispatchers and affected employees to challenge obvious errors.

Models also have limitations. Demand and travel times are uncertain; costs may be estimated poorly; disruptions can invalidate a plan; and local operational knowledge may not be encoded. Scenario analysis, rolling-horizon replanning, robust optimization, and simulation help manage uncertainty. Nevertheless, no model eliminates managerial judgment. The objective is disciplined decision support, not blind automation.

Best-practice checklist

• Define every hard constraint and every penalty explicitly.
• Validate coordinates, demands, service times, vehicle capacities, and working hours.
• Use consistent units for distance, time, quantity, cost, and emissions.
• Prevent subtours and verify route connectivity.
• Test capacity, precedence, time windows, and depot balance independently.
• Compare model output with experienced dispatchers.
• Stress-test routes under traffic, demand, and vehicle-availability scenarios.
• Monitor actual versus planned arrival times and service durations.
• Preserve a feasible fallback plan for system outages or emergencies.
• Review worker safety, privacy, and fairness implications.

Chapter Summary

The Vehicle Routing Problem is a family of models for assigning and sequencing vehicle movements under operational constraints. The CVRP introduces customer coverage, vehicle capacity, depot return, flow conservation, and subtour elimination. The multi-depot variant assigns customers and vehicles across several origins. Heterogeneous-fleet models account for differing capacities, costs, and access rules. Pickup-and-delivery models enforce paired service and pickup-before-delivery precedence. Split-delivery models allow demand to be divided among vehicles. Periodic models coordinate service over multiple days, open models permit routes not to return to the starting depot, and time-window models impose service-start restrictions.

These variants can be combined, but added realism increases computational and data demands. Effective practice begins with a clear representation of physical flows and service commitments, uses validated data and suitable solution methods, and evaluates cost alongside service, safety, sustainability, and organizational feasibility. Optimization technology, including AI, is valuable when governed by explicit constraints, transparent objectives, and human operational review.

Key Terms

Vehicle Routing Problem: A family of models for designing vehicle routes to serve geographically distributed locations.

CVRP: Vehicle routing problem with customer demands and vehicle-capacity constraints.

MDVRP: Vehicle routing problem involving multiple depots.

HFVRP: Vehicle routing problem with vehicles having different characteristics.

Pickup-and-delivery: Routing in which goods are collected at specified origins and delivered to paired destinations.

Split delivery: Service in which one customer’s demand may be divided among several vehicles.

Periodic VRP: Routing over multiple periods with prescribed visit frequencies or day combinations.

Open VRP: Routing in which vehicles need not return to their starting depot.

VRPTW: Vehicle routing problem with customer service time windows.

Subtour: A disconnected cycle that does not connect to the depot route.

Flow conservation: The requirement that route flow entering and leaving a served node be balanced.

Capacity constraint: A restriction limiting the quantity carried by a vehicle.

Time window: The allowable interval for beginning or completing customer service.

Service time: Time required to load, unload, inspect, or otherwise serve a location.

Precedence constraint: A rule requiring one activity to occur before another.

Heterogeneous fleet: A fleet containing vehicle types with different capacities or costs.

Soft constraint: A preferred condition that may be violated at a specified penalty.

Rolling-horizon planning: Repeatedly updating a plan as new information becomes available.

Subtour elimination: Constraints or methods preventing disconnected customer cycles.

Robust routing: Routing designed to remain feasible or effective under uncertainty.

Review Questions

Short Answer Questions

1. What distinguishes the CVRP from the basic traveling salesperson problem?
2. Why are subtour-elimination constraints needed in a vehicle-routing formulation?
3. What operational condition is represented by pickup-before-delivery precedence?
4. State one advantage and one disadvantage of split deliveries.
5. What is the difference between a hard and a soft time window?

Long Answer Questions

1. Explain the principal decision variables and constraints in a capacitated vehicle-routing model.
2. Compare multi-depot and heterogeneous-fleet routing, including the managerial implications of each.
3. Discuss how periodic routing changes the planning problem compared with single-day routing.
4. Explain why route distance alone is an inadequate objective for medical or time-sensitive distribution.
5. Evaluate the role of exact optimization, heuristics, simulation, and AI in practical routing systems.

Analytical / Application Questions

1. A distributor has two depots, three vehicle types, customer pickup returns, and morning receiving windows. Identify the VRP variants required and justify each one.
2. A route is feasible by total demand but repeatedly arrives late. Diagnose at least four modeling or data issues that could explain the failure and propose corrective actions.
3. Design a performance scorecard for comparing two routing plans when cost, on-time service, emissions, driver overtime, and computational time all matter.

Multiple Choice Questions with Answers

Question 1

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

A. ∑ₖ yᵢᵏ = 1 for every customer i

B. ∑ᵢ dᵢyᵢᵏ ≤ Qᵏ for every vehicle k

C. sⱼ ≥ sᵢ + τᵢ + tᵢⱼ

D. ∑ₖ zₖ ≤ 1

Correct Answer: A. ∑ₖ yᵢᵏ = 1 for every customer i

Question 2

What is the primary purpose of subtour-elimination constraints?

A. To increase vehicle capacity

B. To prevent disconnected customer-only cycles

C. To assign customers to multiple depots

D. To calculate emissions

Correct Answer: B. To prevent disconnected customer-only cycles

Question 3

Which feature defines a pickup-and-delivery VRP?

A. Every route must use an identical vehicle

B. Customers may be served only once per month

C. Paired pickup and delivery activities must obey precedence

D. Vehicles must always return to the same depot

Correct Answer: C. Paired pickup and delivery activities must obey precedence

Question 4

A customer demands 12 pallets and a vehicle has capacity 10 pallets. Which variant can permit service by that vehicle together with another vehicle?

A. Open VRP only

B. Split-delivery VRP

C. Periodic VRP only

D. Traveling salesperson problem

Correct Answer: B. Split-delivery VRP

Question 5

In a heterogeneous-fleet VRP, what may differ among vehicles?

A. Only customer names

B. Only route sequence

C. Capacity, cost, speed, or access eligibility

D. The definition of a depot

Correct Answer: C. Capacity, cost, speed, or access eligibility

Question 6

If a customer must be served between 09:00 and 11:00, this requirement is a:

A. Capacity limit

B. Time window

C. Subtour cut

D. Fleet-type constraint

Correct Answer: B. Time window

Question 7

What is a defining feature of an open VRP?

A. Vehicles may not visit customers

B. Vehicles need not return to their starting depot

C. All demands must be split

D. All customers must have identical time windows

Correct Answer: B. Vehicles need not return to their starting depot

Question 8

For a periodic VRP, what does ∑ₜ yᵢₜ = rᵢ represent?

A. Vehicle capacity

B. Required number of visits to customer i

C. Total travel time

D. Number of depots

Correct Answer: B. Required number of visits to customer i

Question 9

Why should pickup quantities be included in a pickup-and-delivery vehicle-load calculation?

A. Pickups can increase the vehicle’s onboard load after collection

B. Pickups always reduce travel time

C. Pickups eliminate time windows

D. Pickups make all vehicles identical

Correct Answer: A. Pickups can increase the vehicle’s onboard load after collection

Question 10

Which statement best describes a soft time window?

A. The window is ignored completely

B. Violation is allowed but incurs a specified penalty

C. The customer is removed from the model

D. The vehicle capacity is increased

Correct Answer: B. Violation is allowed but incurs a specified penalty