Routing, Scheduling, Dispatch, and Execution

Introduction

Transport operations convert customer requirements into physical movements of vehicles, people, and freight. The quality of this conversion affects cost, service reliability, asset utilization, emissions, safety, and customer experience. Routing determines where a vehicle should travel; scheduling determines when activities should occur; dispatch assigns resources and releases work; execution manages the movement in real time and responds to deviations.

These activities are interdependent. A mathematically short route may be infeasible because of vehicle capacity, delivery windows, road restrictions, driver hours, or pickup-before-delivery requirements. Conversely, a slightly longer route may be superior if it consolidates shipments, reduces empty running, or improves delivery reliability. Graduate-level transport management therefore requires both optimization and operational judgment.

Learning Objectives

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

1. Distinguish routing, scheduling, dispatch, and execution decisions.
2. Formulate shortest-path, transportation, assignment, vehicle-routing, pickup-and-delivery, and time-window models.
3. Construct feasible trip plans that consider capacity, working time, consolidation, and empty running.
4. Explain dispatch control, proof of delivery, exception management, and performance measurement.
5. Evaluate technology-enabled and dynamic dispatch systems critically.
6. Recommend an integrated operating approach for a practical transport problem.

1. The Decision Architecture of Transport Operations

A transport plan typically contains decisions at three horizons:

Routing selects a sequence of nodes and links. Scheduling assigns times to arrivals, departures, loading, unloading, breaks, and service activities. Dispatch communicates authorized work to a vehicle, driver, or carrier and monitors acceptance. Execution is the controlled realization of the plan, including exception handling.

The objective is rarely simply to minimize distance. A general operational objective can be expressed as:

where D is distance, T is travel and waiting time, V is vehicle or driver cost, E is energy or emissions cost, L is lateness or service-penalty cost, and R is operational risk. The coefficients represent the organization’s monetary or managerial valuation of each element. The expression is useful only when all terms are measured on a compatible basis, usually currency per planning period.

2. Network Representation and Shortest Path

A transport network is represented as a directed or undirected graph G = (N, A). N is the set of nodes, such as depots, customers, terminals, or charging points; A is the set of usable arcs or links. Each arc (i,j) has a cost cᵢⱼ, such as distance, travel time, toll, or generalized cost.

For a path P, its total cost is:

The shortest-path problem seeks the path with minimum C(P) between an origin and destination. Dijkstra’s algorithm is appropriate when all arc costs are nonnegative. Bellman–Ford can accommodate negative arc costs, although negative costs are unusual in physical transport networks. A shortest-path result is valid only for the selected cost definition and network conditions.

A time-dependent network requires cᵢⱼ(t), because travel time may depend on departure time. A route that is shortest at 05:00 may not be shortest at 08:00. Restrictions such as vehicle height, hazardous-material rules, road closures, and low-emission zones must be encoded as feasibility conditions rather than treated as optional preferences.

Worked example: shortest path

Suppose four nodes are connected by these travel times: A–B = 8 minutes, A–C = 5, B–D = 6, C–D = 12, and B–C = 2. The route A–B–D takes 14 minutes; A–C–D takes 17 minutes; and A–C–B–D takes 5 + 2 + 6 = 13 minutes. Therefore, under the stated static travel times, A–C–B–D is shortest. The conclusion changes if the C–B link is one-way in the opposite direction or if congestion makes its effective travel time exceed 3 minutes.

3. Transportation and Assignment Models

The transportation model allocates quantities from origins to destinations. Let xᵢⱼ be the quantity shipped from origin i to destination j, sᵢ be origin supply, dⱼ be destination demand, and cᵢⱼ be unit transport cost.

subject to:

For a balanced model, total supply equals total demand and the inequalities may be replaced by equalities. Costs must use consistent units, such as dollars per pallet, and quantities must use a consistent unit such as pallets or tonnes. This model does not decide the sequence of stops; it allocates flow.

The assignment model is a special case in which each job is assigned to one resource. Let xᵢⱼ = 1 if vehicle i performs job j, and 0 otherwise. If cᵢⱼ is the cost or penalty of the assignment:

with each job assigned once and each vehicle assigned at most its permitted number of jobs. Assignment is useful for allocating drivers to trips, vehicles to routes, or carriers to lanes, but it does not by itself optimize the order of multiple stops.

4. Vehicle-Routing Problems

The vehicle-routing problem (VRP) determines routes for a fleet serving geographically distributed customers. A basic capacitated VRP usually assumes one depot, known customer demand, homogeneous or specified vehicle capacities, and travel costs known in advance. Each customer must be visited once, vehicle capacity cannot be exceeded, and every route starts and ends at the depot unless an open-route design is intended.

A binary variable xᵢⱼᵏ equals 1 when vehicle k travels directly from node i to node j. A service variable yᵢᵏ indicates whether vehicle k serves customer i. A capacity constraint can be written as:

where qᵢ is customer demand and Qᵏ is vehicle capacity. The model also needs flow-conservation constraints, depot departure and return constraints, customer-visit constraints, and subtour-elimination constraints. Subtour elimination prevents a solution containing a disconnected customer cycle that never connects to the depot.

Common VRP variants include:

• Capacitated VRP: vehicle capacity is the primary restriction.
• Distance- or duration-constrained VRP: route length or working time is limited.
• Heterogeneous-fleet VRP: vehicles differ in capacity, cost, equipment, or access.
• Multi-depot VRP: vehicles originate from more than one depot.
• Periodic VRP: customers require service on specified days or frequencies.
• Split-delivery VRP: a customer may be served by multiple vehicles.
• Green VRP: fuel, energy, or emissions are included in the objective.

Exact mixed-integer optimization can produce high-quality solutions but may become computationally difficult as the number of customers and constraints grows. Practical systems commonly use savings methods, insertion heuristics, local search, tabu search, simulated annealing, genetic algorithms, or hybrid matheuristics. A heuristic is not automatically inferior: a slightly higher-cost solution that is generated quickly and remains robust under uncertainty may be operationally preferable.

5. Pickup-and-Delivery and Time Windows

Pickup-and-delivery problems require freight to be collected at one location and delivered to another. The precedence condition requires pickup before its associated delivery. Vehicle capacity must be updated after every stop, not merely checked against total route demand. Compatibility constraints may also apply to temperature, hazardous materials, security, or product segregation.

If pickup p has quantity qₚ and delivery d removes that quantity, route load evolves as:

where Lᵣ is load after stop r. Feasibility requires 0 ≤ Lᵣ ≤ Q at every stop, assuming nonnegative load and capacity Q.

A vehicle-routing problem with time windows (VRPTW) assigns each customer an arrival or service time within an interval [aᵢ, bᵢ]. If tᵢ is service start time and sᵢ is service duration:

Here τᵢⱼ is travel time, M is a sufficiently large constant, and xᵢⱼ indicates whether arc (i,j) is used. The constant must be large enough to deactivate the constraint when the arc is not selected, but excessively large values can weaken optimization performance. Service must satisfy aᵢ ≤ tᵢ ≤ bᵢ. Waiting is allowed only where operationally permitted.

Time windows may be hard or soft. A hard window makes violation infeasible. A soft window permits violation with a penalty, which can be represented by lateness ℓᵢ ≥ max(0, tᵢ − bᵢ) and a penalty term pᵢℓᵢ. Soft windows are useful when customer priority and realistic service trade-offs must be modeled.

6. Trip Planning, Consolidation, and Empty Running

Trip planning begins with clean order data: origin, destination, quantity, dimensions, weight, handling requirements, requested time, service duration, and legal restrictions. The planner then checks compatibility, groups orders, selects equipment, sequences stops, schedules driver breaks, and calculates expected arrival times.

Consolidation combines compatible shipments into one movement. It can lower cost per shipment and reduce emissions, but it may increase handling, dwell time, route complexity, or risk of late delivery. A consolidation decision should therefore compare the incremental cost and service effect, not merely vehicle fill.

Vehicle utilization has several dimensions:

• Weight utilization = loaded weight ÷ legal payload capacity.
• Cube utilization = occupied volume ÷ usable volume.
• Time utilization = productive operating time ÷ available working time.
• Distance utilization = revenue or loaded distance ÷ total distance.

Empty running occurs when a vehicle travels without revenue-generating or planned repositioning freight. The empty-distance ratio can be expressed as:

The ratio is dimensionless and normally reported as a percentage. Reducing empty running may involve backhaul development, freight exchanges, dynamic matching, regional balancing, drop-and-hook operations, or redesigned depot locations. However, a backhaul should not be accepted if it creates excessive waiting, violates driver hours, risks service failure, or requires an uneconomic detour.

7. Dispatch and Execution Control

Dispatch translates a plan into executable work. A dispatch packet commonly includes trip identity, vehicle and driver, sequence of stops, appointment windows, freight details, safety instructions, contact information, required documents, and escalation procedures. Dispatch should confirm vehicle readiness, driver availability, legal compliance, load completion, and customer readiness before release.

A practical execution cycle is:

1. Validate orders and constraints.
2. Build or import a feasible plan.
3. Assign vehicle, driver, and equipment.
4. Confirm loading and documentation.
5. Release the trip through a transport-management or fleet-management system.
6. Monitor milestones: accepted, arrived, loaded, departed, delivered, and closed.
7. Detect exceptions and re-plan where necessary.
8. Capture proof of delivery and financial data.
9. Review performance and update master data.

Dispatch rules may be simple, such as earliest due date, nearest feasible vehicle, or highest customer priority. More advanced systems use rolling-horizon optimization: at each decision point, known information is re-optimized while protecting committed stops. Excessive re-optimization can create instability, confuse drivers, and undermine customer promises. Operational systems therefore need “plan freeze” rules specifying which decisions may no longer be changed.

8. Exceptions and Resilience

Exceptions include vehicle breakdowns, driver absence, traffic disruption, failed delivery, incorrect address, damaged freight, temperature excursion, missing documentation, customer closure, and capacity shortfall. Exception management should classify events by severity, probability, response time, and authority required.

A useful control logic is:

• Detect: receive telematics, driver, customer, or system signal.
• Diagnose: determine cause, impact, and affected orders.
• Decide: compare recovery options such as reassignment, resequencing, cross-docking, subcontracting, or customer notification.
• Communicate: inform affected stakeholders and record commitments.
• Recover: execute the approved alternative.
• Learn: analyze root cause and update standards.

Key performance indicators should distinguish plan quality from execution quality. Examples include on-time-in-full delivery, schedule adherence, tender acceptance, route completion, cost per shipment, cost per kilometre, vehicle utilization, empty-distance ratio, dwell time, failed-delivery rate, claims rate, and proof-of-delivery cycle time. A high on-time rate achieved through excessive overtime or unsafe driving is not a successful system.

9. Proof of Delivery and Data Governance

Proof of delivery (POD) establishes that a delivery occurred under defined conditions. It may include recipient identity, timestamp, location, quantity received, signature, photograph, barcode scan, electronic seal, and damage notation. A robust POD process distinguishes “delivered” from “delivered in full and undamaged.” Exceptions must be recorded at the point of handover because retrospective reconstruction is less reliable.

Data governance is central to routing quality. Incorrect geocodes, outdated service times, inaccurate vehicle capacities, and missing access restrictions generate systematically infeasible plans. Master-data ownership should be assigned, changes should be auditable, and sensitive driver or customer information should be protected. Electronic monitoring must comply with applicable privacy, labor, transport, and data-retention requirements.

10. Technology, AI, and Human Judgment

Modern transport-management systems integrate order management, route optimization, telematics, warehouse events, maps, carrier portals, and customer notifications. GPS data supports estimated arrival times, geofencing, and milestone detection. Digital documents reduce administrative delay, while mobile applications enable electronic POD and exception reporting.

AI and machine learning can improve travel-time prediction, demand forecasting, anomaly detection, ETA estimation, and dynamic matching. Their value depends on data quality, explainability, monitoring, and human override. A model trained on normal conditions may perform poorly during extreme weather, labor disruption, or unusual road closures. Optimization algorithms should therefore expose assumptions and infeasibility causes rather than presenting a single answer as unquestionable.

Automation also creates governance risks: biased carrier scoring, opaque allocation decisions, excessive worker surveillance, cybersecurity exposure, and unsafe pressure to meet algorithmic schedules. Human dispatchers remain essential for judgment under ambiguity, relationship management, and ethical escalation.

Applied Case: NorthRiver Foods (Illustrative)

Background

NorthRiver Foods operates one regional depot and serves 18 retailers with refrigerated vehicles. Orders arrive throughout the day, and deliveries have two-hour appointment windows. The fleet includes six vehicles with different capacities. The company has experienced 14% empty-distance, late deliveries during afternoon congestion, and frequent manual changes by dispatchers.

Problem

The existing process grouped orders by geographic intuition, then assigned the nearest available vehicle. It ignored product compatibility, unloading duration, and the effect of traffic on time windows. Drivers also returned to the depot after morning deliveries even when compatible backhaul orders were available.

Analysis

The operations team first corrected customer coordinates, measured realistic service times, and classified products by temperature and handling compatibility. It then created a heterogeneous-fleet VRPTW model with vehicle capacity, driver-hours, pickup-before-delivery, and refrigeration constraints. Hard windows were retained for two major retailers; smaller customers received soft windows with explicit lateness penalties. A rolling dispatch procedure was added for disruptions after route release.

Approach and solution

The planning process was changed to:

1. Freeze the next two hours of committed stops.
2. Optimize uncommitted orders every 30 minutes.
3. Protect driver breaks and legal limits.
4. Offer compatible backhaul loads before authorizing depot return.
5. Notify customers when predicted lateness exceeded 20 minutes.
6. Require electronic POD with quantity and damage confirmation.

Dispatchers reviewed algorithmic suggestions and could override them with a recorded reason. The system ranked solutions using transport cost, lateness penalties, refrigeration risk, and empty distance rather than distance alone.

Outcome

In this illustrative case, the redesigned process reduced empty-distance to 9%, improved on-time-in-full performance, and reduced manual route changes. The improvement did not result solely from optimization software. It depended on accurate master data, realistic service times, disciplined freeze rules, driver involvement, and customer communication.

Learning points

First, routing quality is constrained by data quality. Second, a feasible and stable plan is more valuable than a theoretical minimum-distance plan. Third, dynamic dispatch should re-optimize selectively, not continuously. Finally, performance measures must balance cost, service, utilization, safety, and sustainability.

Challenges and Limitations

Routing models simplify reality. Travel times are uncertain, customer behavior is variable, and service times may be correlated with congestion or delivery difficulty. A solution that is optimal under average conditions may be fragile under disruption. Robust and stochastic approaches can represent uncertainty, but they require probability estimates and may increase computational burden.

Other limitations include computational complexity, inaccurate demand forecasts, poor adoption by drivers, incompatible information systems, and incentive conflicts between shippers, carriers, and customers. A low-cost route for a shipper may transfer waiting or handling costs to a carrier. Governance should therefore define service standards, data responsibilities, escalation rights, and allocation of gains and losses.

Best-Practice Framework

A mature operation should:

• maintain accurate geospatial, vehicle, driver, and service-time data;
• model legal, safety, environmental, and customer constraints explicitly;
• separate strategic, planning, and execution decisions;
• use consolidation when compatibility and service economics support it;
• measure empty running and productive utilization together;
• establish plan-freeze and re-planning rules;
• give drivers clear, safe, and change-controlled instructions;
• capture reliable electronic POD and exception codes;
• audit optimization assumptions and algorithmic outcomes;
• review root causes rather than treating every exception as an isolated event.

Chapter Summary

Routing selects movement sequences, scheduling assigns times, dispatch releases work, and execution controls the movement in real conditions. Shortest-path, transportation, assignment, VRP, pickup-and-delivery, and time-window models address different decision structures and should not be substituted for one another. Practical planning must incorporate capacity, precedence, compatibility, driver limits, service windows, consolidation, and empty running.

Effective execution depends on disciplined dispatch, milestone visibility, exception recovery, proof of delivery, and accurate data governance. Optimization and AI can improve decisions, but their output must be evaluated for feasibility, robustness, transparency, safety, privacy, and operational acceptance. The central managerial task is to integrate mathematical planning with human judgment and resilient execution.

Key Terms

Routing: Selecting the sequence and links used to move between locations.

Scheduling: Assigning times to travel, service, loading, unloading, and breaks.

Dispatch: Releasing assigned work and instructions to a vehicle, driver, or carrier.

Execution: Physical and administrative realization of a transport plan.

Shortest path: Minimum-cost path between two network nodes.

Transportation model: Flow-allocation model assigning quantities from origins to destinations.

Assignment model: Model matching jobs or resources under assignment constraints.

Vehicle-routing problem: Optimization of routes for vehicles serving multiple locations.

Time window: Permitted interval for service at a customer or facility.

Pickup-and-delivery problem: Routing problem requiring collection and subsequent delivery of associated freight.

Precedence: Requirement that one activity occur before another.

Consolidation: Combining compatible shipments into a shared movement.

Empty running: Vehicle travel without revenue-generating or planned freight movement.

Rolling-horizon optimization: Repeated re-planning as new information becomes available.

Exception management: Detection, recovery, communication, and learning from operational deviations.

Proof of delivery: Evidence that freight was delivered under specified conditions.

Plan freeze: Rule preventing changes to selected committed decisions.

Electronic geofence: Virtual boundary used to detect location-based events.

Master data: Persistent operational information such as locations, capacities, and service times.

Robustness: Ability of a plan to perform acceptably under uncertainty and disruption.

Review Questions

Short Answer Questions

1. Distinguish routing, scheduling, dispatch, and execution.
2. When is Dijkstra’s algorithm appropriate for shortest-path analysis?
3. Why must vehicle load be checked after every pickup and delivery stop?
4. Define empty-distance ratio and explain its managerial value.
5. What information should normally be captured in electronic proof of delivery?

Long Answer Questions

1. Explain how a capacitated VRP differs from a transportation model and an assignment model.
2. Discuss the advantages and risks of hard versus soft customer time windows.
3. Describe an integrated dispatch and exception-management process.
4. Evaluate the role of consolidation and backhaul planning in reducing transport cost and emissions.
5. Explain why data governance is essential to successful route optimization.

Analytical / Application Questions

1. A route has customer demands of 4, 6, and 5 tonnes and a vehicle capacity of 12 tonnes. Explain why a route serving all three customers may be infeasible, and propose two planning alternatives.
2. A dispatcher can accept a backhaul that reduces empty distance but causes a 35-minute delay to a high-priority delivery. Identify the relevant objective trade-offs and recommend the information required before deciding.
3. Design a rolling-horizon dispatch policy for a depot facing uncertain traffic, driver-hour constraints, and two-hour delivery windows. Specify freeze rules, re-planning frequency, exception triggers, and performance measures.

Multiple Choice Questions with Answers

Question 1

Which decision is primarily addressed by a shortest-path model?

A. Selecting the least-cost sequence between an origin and destination

B. Assigning every customer to a different vehicle

C. Determining the quantity shipped from each supplier

D. Recording proof of delivery

Correct Answer: A. Selecting the least-cost sequence between an origin and destination

Question 2

In a capacitated vehicle-routing problem, which condition must hold throughout a route?

A. Every customer must have the same demand

B. Vehicle load must not exceed vehicle capacity

C. Every route must use the shortest possible arc

D. All customers must be served at the same time

Correct Answer: B. Vehicle load must not exceed vehicle capacity

Question 3

What does a transportation model primarily allocate?

A. Driver breaks to shifts

B. Vehicles to stop sequences

C. Shipment quantities from origins to destinations

D. Arrival times within customer windows

Correct Answer: C. Shipment quantities from origins to destinations

Question 4

A pickup-and-delivery route must normally satisfy which precedence condition?

A. Delivery occurs before pickup

B. Pickup and delivery occur simultaneously

C. Pickup occurs before its associated delivery

D. The vehicle must return to the depot between pickup and delivery

Correct Answer: C. Pickup occurs before its associated delivery

Question 5

If loaded distance is 700 km and total distance is 1,000 km, what is the empty-distance ratio when empty distance is 300 km?

A. 3%

B. 30%

C. 43%

D. 70%

Correct Answer: B. 30%

Question 6

What is the main purpose of a plan-freeze rule in dynamic dispatch?

A. To prevent all future optimization

B. To stabilize committed work and avoid disruptive changes

C. To guarantee that traffic conditions remain constant

D. To eliminate the need for driver communication

Correct Answer: B. To stabilize committed work and avoid disruptive changes

Question 7

Which item is most directly associated with proof of delivery?

A. Vehicle purchase price

B. Supplier production forecast

C. Recipient confirmation and delivery timestamp

D. Annual depot rent

Correct Answer: C. Recipient confirmation and delivery timestamp

Question 8

Why can a slightly longer route be operationally better than the shortest route?

A. It may improve consolidation, feasibility, or service reliability

B. Longer routes always consume less fuel

C. Shortest-path algorithms cannot use travel time

D. Longer routes eliminate all delivery windows

Correct Answer: A. It may improve consolidation, feasibility, or service reliability

Question 9

Which algorithm is appropriate for a network with nonnegative arc costs?

A. Dijkstra’s algorithm

B. A proof-of-delivery protocol

C. A warehouse slotting rule

D. A depreciation schedule

Correct Answer: A. Dijkstra’s algorithm

Question 10

Which practice best supports responsible use of AI in dispatch?

A. Hiding model assumptions from dispatchers

B. Allowing automatic changes without safety constraints

C. Monitoring performance, explaining assumptions, and retaining human override

D. Optimizing only distance regardless of service or legal limits

Correct Answer: C. Monitoring performance, explaining assumptions, and retaining human override