Vehicle Routing, Dispatching and Scheduling

Introduction and Context

Vehicle routing, dispatching and scheduling convert customer requirements into executable movement plans. In logistics systems, the decision is not simply which vehicle should visit which customer. Managers must determine the sequence of visits, vehicle assignment, departure times, loading feasibility, driver and regulatory constraints, service priorities, and responses to uncertainty. These decisions directly affect transport cost, delivery reliability, fleet utilization, emissions, customer satisfaction and working capital.

The travelling-salesperson problem (TSP) provides the basic routing structure: one vehicle must visit each customer exactly once and return to its origin while minimizing total travel cost. The vehicle-routing problem (VRP) extends this structure to several vehicles and operational restrictions. Important variants include the capacitated VRP, VRP with time windows, multi-depot VRP, pickup-and-delivery VRP, heterogeneous-fleet VRP and dynamic VRP.

Routing is generally computationally difficult. The TSP is NP-hard, and many practical VRP variants are even more complex. Consequently, effective professional practice combines mathematical programming, constructive heuristics, local search, metaheuristics, simulation and real-time decision support rather than relying on one universal method.

Learning Objectives

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

1. Explain the structure and assumptions of TSP, VRP and major VRP variants.
2. Formulate routing, capacity, time-window and precedence constraints mathematically.
3. Distinguish exact methods, heuristics and metaheuristics and select among them.
4. Construct and evaluate dispatching and scheduling plans using operational KPIs.
5. Analyze the effects of multiple depots, heterogeneous fleets, pickups and deliveries, and dynamic demand.
6. Evaluate technology, governance, sustainability and implementation issues in routing systems.

1. From Routing to Dispatching and Scheduling

Three related decisions should be separated conceptually.

• Routing determines the geographical sequence of stops and the arcs travelled.
• Vehicle assignment determines which vehicle serves each route.
• Scheduling determines departure, arrival, service and return times.
• Dispatching releases and revises operational instructions, often with incomplete or changing information.

A route may be represented as a sequence such as depot → customer 4 → customer 2 → customer 7 → depot. A schedule adds times to this sequence. A dispatch plan adds decisions about when the route is released, which driver receives it, and how exceptions are handled.

A useful objective is a weighted total cost:

Here, D is distance, T is operating time, V is the number of vehicles used, L is lateness or service-level violation, E is emissions, and P represents penalties such as overtime or infeasibility. The coefficients c_d, c_t, c_v, c_l, c_e and c_p convert each measure into a common monetary or utility scale. The formulation is applicable when management is willing to express competing objectives through weights. If service levels are non-negotiable, lateness should instead be constrained rather than merely penalized.

A common distance calculation for locations with coordinates is the Euclidean metric:

The units of d_ij are the same as the coordinate units. This approximation is suitable for a planar representation, but urban routing normally requires a road-network travel-time matrix, because roads, one-way streets, bridges and congestion make geographical distance an imperfect proxy for travel time.

2. The TSP Foundation

Let N = {0,1,…,n} be a set of nodes, where node 0 is the depot and the other nodes are customers. Let c_ij be the cost of travelling from node i to node j, and let x_ij equal 1 if that arc is selected and 0 otherwise.

The basic directed TSP can be written as:

subject to:

The first constraint gives every node exactly one outgoing arc; the second gives every node exactly one incoming arc. These constraints alone may produce several disconnected cycles. Subtour-elimination constraints are therefore required. For every proper nonempty subset S of customers, one form is:

This prevents a closed tour entirely within S. In practice, adding every such constraint initially is inefficient; branch-and-cut algorithms add violated subtour constraints during optimization.

The TSP is a useful benchmark and a component of larger routing models, but it assumes one vehicle, a single route, known travel costs and usually one visit per customer. Real operations require additional constraints.

3. Core VRP Formulations

3.1 Capacitated Vehicle-Routing Problem

In the capacitated VRP (CVRP), a fleet of vehicles starts and ends at a depot, each customer is visited once, and vehicle capacity cannot be exceeded. Let K be the vehicle set, q_i customer i demand, and Q_k capacity of vehicle k. A route-level capacity condition is:

where R_k is the customer set assigned to vehicle k. This equation is necessary but does not itself determine the route sequence.

A compact arc formulation uses x_ijk = 1 when vehicle k travels directly from i to j. Flow conservation requires that a vehicle entering a customer also leaves it. Each customer must be served once:

For each vehicle, capacity can be enforced with load variables or cumulative-flow constraints. If y_ik is the load carried after visiting customer i, a typical propagation constraint is:

The large constant Q_k deactivates the relationship when arc i→j is not used. Bounds such as q_i ≤ y_ik ≤ Q_k are also required where applicable. Poorly chosen large constants can weaken optimization and create numerical difficulties; modern formulations often use tighter bounds or specialized valid inequalities.

3.2 Vehicle Routing with Time Windows

Each customer i has an allowable service interval [a_i,b_i]. Let s_i be service duration and t_ij travel time. If B_i is service start time, then:

For a selected arc i→j, temporal consistency requires:

where M is a sufficiently large time constant. Units must be consistent: if B_i is measured in minutes, then s_i, t_ij and M must also be in minutes. Waiting is permitted when a vehicle arrives before a_j; service starts at the later of arrival and the opening time. If waiting is prohibited, an additional restriction is needed.

Time windows can be hard, meaning violation is infeasible, or soft, meaning violation incurs a penalty. Soft windows are useful for emergency services or commercial operations where late delivery is undesirable but occasionally permitted. A lateness variable l_i ≥ 0 can be introduced, with a penalty c_l l_i in the objective.

3.3 Multiple Depots

In a multi-depot VRP, customers may be served from several origins. Decisions include depot assignment and route sequence. A route may be restricted to start and finish at the same depot, or cross-depot operations may be permitted. The model must specify:

• depot capacities and vehicle availability;
• vehicle-to-depot compatibility;
• customer eligibility or service territories;
• whether vehicles must return to their initial depot;
• balancing requirements among depots.

Ignoring depot assignment can produce a geographically short but operationally impossible plan, such as assigning a vehicle to a depot where it is not physically available.

3.4 Pickup-and-Delivery Problems

Pickup-and-delivery routing includes paired pickup and delivery locations. For request r, let p_r be the pickup node and d_r the delivery node. Precedence requires pickup before delivery:

The vehicle must also carry the relevant goods between the two locations. In a pickup-and-delivery problem with vehicle capacities, load changes along the route and must remain within bounds:

where L_ell is the vehicle load after position ell. For returns, backhauls and mixed pickup-delivery operations, the sign and sequence of load changes must be modelled explicitly. A route that is geographically feasible may still be infeasible because delivery goods were loaded after a pickup or because capacity was exceeded between stops.

3.5 Heterogeneous Fleets

Vehicles may differ in capacity, fixed cost, operating cost, refrigeration, access restrictions, fuel type and driver qualifications. Let Q_k be capacity and f_k fixed deployment cost for vehicle k. The objective may include:

where z_k equals 1 when vehicle k is used. Fleet selection should not be based only on capacity. A larger vehicle may reduce route count but incur higher fixed cost, restricted access or higher emissions. Compatibility constraints are essential for hazardous materials, temperature-controlled freight and special handling.

3.6 Dynamic and Stochastic Demand

In a static VRP, all relevant information is available before route construction. In a dynamic VRP, requests, travel times, cancellations and vehicle states are revealed over time. The decision process must balance immediate response against future flexibility. A route that is best at 08:00 may be poor at 10:00 after an urgent request arrives.

Dynamic systems commonly use a rolling horizon:

1. collect current requests and vehicle positions;
2. freeze decisions that cannot realistically be changed;
3. optimize the remaining portion of the plan;
4. dispatch instructions;
5. update the model when new information arrives.

Forecasting can estimate future demand, but forecasts should not be treated as certainty. Robust or stochastic optimization can protect against uncertainty by adding scenario costs, service-risk constraints or conservative capacity buffers.

4. Scheduling and Dispatching Logic

Routing and scheduling should be integrated. A route with low distance may require excessive waiting, overtime or missed appointments. Important scheduling rules include:

• Earliest feasible service: visit the next customer at the earliest time allowed by travel and the time window.
• Latest-start planning: schedule backward from a required delivery deadline to identify the latest feasible departure.
• Slack management: reserve time for congestion, loading delays and service variability.
• Dispatch freezing: prevent constant changes to routes already communicated to drivers.
• Priority classes: protect urgent, medically important or high-penalty requests.

For customer i, arrival time is:

and service begins at:

provided B_i ≤ b_i for a hard time window. If the vehicle arrives early, B_i − A_i is waiting time. Route duration is the return time minus departure time, including service and waiting.

Dispatching also has a human and organizational dimension. Drivers need unambiguous instructions, safe loading information, customer contact protocols and escalation rules. An optimization engine that produces theoretically efficient but operationally confusing instructions may reduce rather than improve performance.

5. Solution Methods

5.1 Exact Optimization

Mixed-integer linear programming, branch-and-bound, branch-and-cut and column generation can prove optimality or provide a bound on the best possible solution. Exact methods are attractive when the instance is small, the decision is high value, or auditability is important.

Their limitations are computational growth, sensitivity to formulation quality and difficulty handling rapidly changing data. A solver may produce an optimal answer for an obsolete travel-time matrix. Practical stopping criteria therefore include time limits, optimality gaps and operational deadlines.

The optimality gap can be expressed, for a minimization problem, approximately as:

where UB is the best feasible solution found and LB is a valid lower bound. The formula assumes UB ≠ 0 and that the bound is expressed for the same objective. A small gap indicates a strong computational certificate, but not necessarily a solution that is preferable under unmodelled operational considerations.

5.2 Constructive Heuristics

Heuristics generate good feasible solutions quickly without guaranteeing optimality. Examples include:

• nearest neighbour;
• cheapest insertion;
• savings methods;
• sweep algorithms based on customer angles;
• regret insertion, which prioritizes customers whose delayed insertion would be costly.

The Clarke–Wright savings idea compares separate depot routes with a combined route. For customers i and j, savings are:

A high positive saving suggests that linking i and j may reduce cost. The method must still check capacity, time windows, route orientation and customer compatibility. Savings are not a guarantee of feasibility or optimality.

5.3 Local Search

Local search begins with a feasible solution and explores neighboring solutions. Common moves are:

• 2-opt: remove two arcs and reconnect the route in a different order;
• relocate: move one customer to another position or route;
• swap: exchange two customers;
• **2-opt

over routes:** exchange route segments;

• cross-exchange: exchange multiple segments between routes.

A move is accepted if it improves the objective, subject to feasibility. Efficient implementations use delta evaluation: instead of recalculating the entire route, they calculate only the cost and constraint changes caused by the move.

5.4 Metaheuristics

Metaheuristics guide broader exploration and reduce the risk of becoming trapped in a local optimum.

• Simulated annealing sometimes accepts worsening moves, with decreasing probability, to escape local minima.
• Tabu search records recently used moves or attributes and temporarily prohibits them, while allowing aspiration if a move produces an exceptional solution.
• Genetic algorithms evolve encoded route populations through selection, crossover and mutation. Specialized route representations are needed to avoid duplicate or missing customers.
• Ant colony optimization uses artificial pheromone trails and heuristic visibility to construct routes.
• Adaptive large-neighbourhood search (ALNS) repeatedly destroys part of a solution and repairs it using competing operators. Operator weights are adapted according to historical performance.

Metaheuristics require calibration, stopping rules and validation. A lower objective in a simulation may result from overfitting parameters to one historical day. Multiple random seeds and out-of-sample testing are therefore important.

5.5 Matheuristics and Hybrid Systems

Matheuristics combine mathematical programming with heuristic search. For example, a heuristic may select customer clusters, followed by an exact solver that optimizes sequencing within each cluster. Alternatively, a large-neighbourhood search may use a mixed-integer solver to repair a difficult segment. These approaches often provide a practical compromise between solution quality, explainability and runtime.

6. Worked Example: A Small Capacitated Route

Consider one depot 0 and four customers. Distances are symmetric and measured in kilometres. Demands are 2, 3, 2 and 3 units, and vehicle capacity is 6 units. Suppose two routes are proposed:

• Route A: 0–1–2–0, with distance 8 + 5 + 7 = 20 km and load 2 + 3 = 5 units.
• Route B: 0–3–4–0, with distance 6 + 4 + 9 = 19 km and load 2 + 3 = 5 units.

Total distance is:

Both routes satisfy capacity because 5 ≤ 6. Total delivered demand is 10 units, while total vehicle capacity used is 12 units, giving a simple capacity utilization measure of:

This calculation measures aggregate payload utilization, not the proportion of distance travelled while loaded. If customers 2 and 3 were exchanged, route loads would become 4 and 6 units, which remains feasible, but distance and time would need to be recalculated. Thus, a capacity-feasible reassignment is not automatically cost-improving.

7. Applied Case: Urban Service Distributor

Background

The following is an illustrative case. A regional food-service distributor operates two depots and a heterogeneous fleet of refrigerated vans and larger trucks. It serves restaurants with morning delivery windows. Orders are received by 18:00 for next-day delivery, but urgent orders and cancellations occur during the morning.

Problem

The company used driver experience and geographical zones to construct routes manually. The resulting problems were overtime, inconsistent arrival times, underutilized small vehicles and occasional capacity violations when returnable packaging was collected. The company also needed to prevent refrigerated products from remaining outside controlled temperature conditions for too long.

Analysis

The planning team built a road-network matrix using historical travel times by time of day. Each customer was assigned demand, service duration, time window, refrigeration requirement and pickup quantity. Vehicles were described by capacity, fixed cost, refrigeration capability, depot and driver availability. The model included:

• depot assignment;
• heterogeneous capacity;
• delivery and packaging pickup quantities;
• hard morning windows for priority restaurants;
• soft windows for ordinary customers;
• driver shift limits;
• maximum route duration;
• a penalty for vehicle use and late service.

A static mixed-integer model was too slow for complete daily reoptimization. The company therefore used a hybrid process: an overnight ALNS generated a strong plan, and a rolling-horizon repair model handled urgent orders. Routes already being driven were frozen except for safety-critical changes.

Approach and Solution

The destroy phase removed geographically related customers, high-penalty customers or randomly selected customers. The repair phase inserted them into feasible positions while evaluating additional distance, time-window risk, refrigeration exposure and vehicle capacity. An exact subproblem optimized the assignment of the most constrained customers.

Dispatchers reviewed exceptions rather than editing every route. The system displayed the reason for a recommended change, such as “vehicle capacity violation avoided” or “priority delivery protected.” Drivers received routes through a mobile application, but the application required confirmation of loading and delivery events.

Outcome

In a controlled four-week pilot, the company compared the system with its historical method using matched demand days. The evaluation focused on cost per delivery, on-time percentage, overtime hours, vehicle utilization and rejected or manually altered recommendations. The pilot showed that route quality improved only when data on service duration, loading completion and vehicle availability were maintained accurately. The main managerial lesson was that optimization was a socio-technical intervention, not merely a software purchase.

Learning Points

1. A realistic model can be more valuable than a mathematically elegant but incomplete model.
2. Hard and soft service constraints should reflect actual commercial priorities.
3. Real-time replanning must protect driver trust and route stability.
4. KPI comparisons require a controlled baseline and consistent definitions.
5. Data governance is a prerequisite for reliable optimization.

8. Performance Measurement and Managerial Interpretation

A routing plan should be evaluated using a balanced set of measures:

Cost minimization alone may encourage excessive workload, fragile schedules or poor service. A route with the lowest planned distance may have no buffer and fail under normal congestion. Managers should examine distributions, not only averages: the 95th percentile of lateness or route duration may reveal operational risk.

9. Technology, AI and Data Governance

Modern routing platforms use geographic information systems, telematics, mobile applications, cloud solvers, demand forecasts and machine-learning models. AI can estimate travel time, service duration, cancellation probability and likely demand. Optimization then uses these estimates as inputs.

Prediction and optimization should not be conflated. A highly accurate travel-time prediction does not determine the best route, and an excellent optimization model cannot compensate for systematically biased predictions. Models should be monitored for drift by season, geography, customer segment and vehicle type.

Governance requirements include:

• traceability of data and model versions;
• human override and escalation procedures;
• cybersecurity for vehicle and customer information;
• access controls for driver and location data;
• testing for discriminatory workload allocation;
• retention and privacy policies;
• audit logs for automated decisions.

A dispatch algorithm should not assign unsafe schedules merely because a service-level penalty is high. Safety rules, legal driving limits and hazardous-material regulations must be hard constraints or mandatory supervisory checks.

10. Challenges, Limitations and Best Practices

Data and model limitations

Travel times vary, service durations are often poorly recorded, addresses may be inaccurate, and demand forecasts may be biased. A model can be exactly solved and still produce poor decisions if inputs are wrong. Data-quality controls should therefore include address validation, duplicate detection, unit checks, historical outlier review and confirmation of vehicle availability.

Computational limitations

Large instances may not be solved to proven optimality in operational time. The organization should specify acceptable runtime, solution gap, stability and minimum service quality before deployment. A fast feasible plan is often preferable to an optimal plan delivered after the dispatch window.

Human limitations

Drivers possess local knowledge about access restrictions, loading areas and customer preferences. Their knowledge should be captured and used to improve the model, not dismissed as resistance. However, informal workarounds should be reviewed for safety and consistency rather than automatically encoded.

Recommended practice

1. Define service and safety policies before selecting an algorithm.
2. Start with a validated baseline and a limited pilot.
3. Use road-network travel times and realistic service durations.
4. Separate hard constraints from economically penalized preferences.
5. Test unusual but feasible instances, not only average days.
6. Compare multiple algorithms and random seeds where applicable.
7. Measure planned versus actual outcomes.
8. Establish route-freezing and human-override rules.
9. Recalibrate forecasts and optimization parameters regularly.
10. Communicate why routes change and how performance is evaluated.

Chapter Summary

Vehicle routing extends the TSP from one tour to a family of constrained logistical planning problems. The CVRP adds vehicle capacity; time-window models add service timing; multi-depot models add origin assignment; pickup-and-delivery models add precedence and load evolution; heterogeneous-fleet models add vehicle-specific capabilities and costs; and dynamic models add decisions under changing information. Routing, assignment, scheduling and dispatching are related but distinct decisions.

Exact optimization provides strong guarantees for suitable instances, while heuristics and metaheuristics provide speed and scalability. Hybrid methods often offer the most practical balance. A high-quality plan must be feasible, cost-effective, robust, safe, explainable and acceptable to the people who execute it. Technology and AI improve forecasting, travel-time estimation and real-time adaptation, but they require data governance, monitoring and human oversight. The ultimate measure of routing excellence is not mathematical elegance alone, but reliable operational performance under real conditions.

Key Terms

TSP: Travelling-salesperson problem in which one tour visits each required node once.

VRP: Vehicle-routing problem involving multiple vehicles and operational constraints.

CVRP: Vehicle-routing problem with vehicle-capacity restrictions.

Time window: Allowed interval for beginning service at a customer.

Hard constraint: Requirement that cannot be violated in a feasible solution.

Soft constraint: Preference whose violation is permitted with a penalty.

Subtour: Disconnected cycle that fails to include the required depot-connected tour.

Multi-depot VRP: Routing problem with two or more possible depots.

Pickup-and-delivery problem: Routing problem involving paired collection and delivery locations.

Precedence constraint: Requirement that one activity occur before another.

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

Dynamic VRP: Routing problem in which information becomes available or changes during operations.

Rolling horizon: Repeated planning process that optimizes a moving future time window.

Heuristic: Practical method that seeks good solutions without guaranteeing optimality.

Metaheuristic: General search strategy designed to explore a broad solution space.

Local search: Improvement procedure based on neighboring solutions.

ALNS: Adaptive large-neighbourhood search using destroy and repair operators.

Optimality gap: Difference between a best feasible solution and a valid bound on the optimum.

Dispatching: Releasing and revising operational instructions for execution.

Route stability: Degree to which communicated routes remain unchanged.

Review Questions

5 Short Answer Questions

1. What is the principal difference between the TSP and the CVRP?
2. Why are subtour-elimination constraints needed in a TSP formulation?
3. Distinguish a hard time window from a soft time window.
4. What does a rolling-horizon dispatch system do?
5. Name two neighborhood moves used in local search for routing.

5 Long Answer Questions

1. Formulate and explain the major constraints in a capacitated vehicle-routing problem with time windows.
2. Compare exact optimization, constructive heuristics and metaheuristics in terms of solution quality, runtime and managerial use.
3. Explain how pickup-and-delivery requirements change both route feasibility and vehicle-load calculations.
4. Discuss the managerial trade-offs involved in operating a heterogeneous fleet.
5. Evaluate the role of data governance and human oversight in AI-enabled dispatching.

3 Analytical / Application Questions

1. A distributor has three vehicles of capacity 8, 10 and 15 units and customers with demands 4, 5, 6, 7 and 8 units. Develop two alternative feasible route assignments and explain which additional data are needed to compare them economically.
2. A route meets all customer time windows under average travel times but fails frequently during evening congestion. Diagnose the modelling weakness and recommend a robust or dynamic planning response.
3. Design an evaluation plan for comparing a manual dispatch process with an ALNS-based system. Specify the baseline, KPIs, experimental period, controls and risks to validity.

Multiple Choice Questions with Answers

Question 1

Which constraint prevents a TSP solution from containing disconnected customer-only cycles?

A. Vehicle-capacity constraint

B. Subtour-elimination constraint

C. Depot-capacity constraint

D. Service-duration constraint

Correct Answer: B. Subtour-elimination constraint

Question 2

A vehicle has capacity 12 units and serves demands of 4, 3 and 5 units. What is its payload utilization on that route?

A. 33.3%

B. 41.7%

C. 75.0%

D. 100.0%

Correct Answer: D. 100.0%

Question 3

In a time-window model, what does B_i represent?

A. Vehicle capacity at customer i

B. Service start time at customer i

C. Distance from the depot to customer i

D. Fixed cost of vehicle i

Correct Answer: B. Service start time at customer i

Question 4

Which method repeatedly removes part of a routing solution and then reconstructs it?

A. Nearest neighbour

B. 2-opt only

C. Adaptive large-neighbourhood search

D. Basic flow conservation

Correct Answer: C. Adaptive large-neighbourhood search

Question 5

For a minimization problem, which pair is used to calculate an approximate optimality gap?

A. Demand and capacity

B. Upper bound and lower bound

C. Arrival time and service time

D. Distance and vehicle speed

Correct Answer: B. Upper bound and lower bound

Question 6

In a pickup-and-delivery problem, what relationship normally must hold?

A. Delivery must occur before pickup

B. Pickup and delivery must use different vehicles

C. Pickup must precede its corresponding delivery

D. Every pickup must return to the depot immediately

Correct Answer: C. Pickup must precede its corresponding delivery

Question 7

What is a defining feature of a heterogeneous fleet?

A. All vehicles have identical capacities

B. Vehicles differ in capabilities or operating costs

C. Vehicles may not return to a depot

D. Demand is unknown at all times

Correct Answer: B. Vehicles differ in capabilities or operating costs

Question 8

Why is road-network travel time generally preferable to Euclidean distance for urban routing?

A. It always eliminates congestion

B. It accounts more realistically for roads and travel restrictions

C. It guarantees an optimal route

D. It removes the need for time windows

Correct Answer: B. It accounts more realistically for roads and travel restrictions

Question 9

What is the main purpose of route freezing in dynamic dispatching?

A. To prohibit all future optimization

B. To prevent communicated routes from changing unnecessarily

C. To ensure every vehicle is fully loaded

D. To replace driver communication

Correct Answer: B. To prevent communicated routes from changing unnecessarily

Question 10

Which statement best describes a soft constraint?

A. It must never be violated

B. It is ignored by the model

C. Its violation is allowed but incurs a penalty

D. It applies only to empty vehicles

Correct Answer: C. Its violation is allowed but incurs a penalty