Routing Foundations and Network Models

Introduction

Fleet operations convert transport demand into movement decisions: which vehicle should serve which customer, in what sequence, along which roads, at what time, and under which operating restrictions. Routing is therefore more than finding the geographically shortest path. A professional routing decision must balance distance, travel time, tolls, fuel, vehicle capacity, driver hours, customer time windows, road restrictions, reliability, safety, and service quality.

This chapter develops the mathematical foundations used in fleet routing. It introduces graph theory, shortest-path algorithms, minimum-cost flow, the travelling-salesperson problem (TSP), vehicle-routing models, and transportation models. It also explains how real operational constraints alter apparently optimal routes.

Learning Objectives

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

1. Represent a transport system as a directed or undirected weighted graph.
2. Distinguish shortest-path, minimum-cost-flow, transportation, TSP, and vehicle-routing models.
3. Apply Dijkstra’s algorithm and interpret its assumptions.
4. Formulate routing objectives involving distance, time, tolls, and operating cost.
5. Explain capacity, time-window, service, and regulatory constraints.
6. Evaluate routing solutions critically in a practical fleet context.

1. The Network View of Fleet Operations

A road network is represented by a graph G = (V, A), where V is the set of nodes and A is the set of arcs. Nodes may represent depots, customers, intersections, ports, charging stations, or transfer terminals. An arc represents a feasible movement from one node to another.

In an undirected graph, movement is possible in both directions with the same representation. In a directed graph, arc (i, j) may exist without arc (j, i), or the two directions may have different attributes. One-way streets, turn restrictions, gradients, toll differences, and congestion make directed graphs particularly important in logistics.

Each arc can carry several weights:

A route is a sequence of connected arcs. If route R contains arcs A(R), its total distance is:

Its total travel time, excluding service time, is:

If service at node i takes sᵢ time units, total route duration becomes:

The equations assume additive arc and service measures. They are suitable when congestion, waiting, and interaction effects are either absent or already incorporated into the arc values.

1.1 Cost functions and multi-objective routing

A fleet manager rarely minimises distance alone. A generalized arc cost can be expressed as:

Here wᵢⱼ is generalized cost, dᵢⱼ is distance, tᵢⱼ is time, τᵢⱼ is toll, eᵢⱼ is emissions, and α, β, γ, and δ are conversion weights. The weights must convert all components into a common unit, usually currency or a normalized score. This is a managerial preference model, not a physical law. Results are sensitive to the selected weights.

An alternative is a constrained objective: minimise monetary cost subject to a maximum duration, emissions ceiling, or service-level requirement. This is often more transparent than combining incomparable measures into one score.

2. Graph-Theoretic Foundations

Important graph concepts include:

• Path: a sequence of nodes and arcs with no required repetition.
• Walk: a sequence that may repeat nodes or arcs.
• Cycle: a closed path that begins and ends at the same node.
• Connected graph: every relevant pair of nodes is linked by a path.
• Degree: the number of arcs incident to a node; in directed graphs, in-degree and out-degree are distinguished.
• Adjacent nodes: nodes directly connected by an arc.
• Subgraph: a graph formed from a subset of nodes and arcs.
• Feasible arc: an arc permitted by vehicle, road, regulatory, and operational conditions.

Network representation may use an adjacency matrix or adjacency list. A matrix is convenient for dense networks and direct lookup; an adjacency list is more memory-efficient for sparse road networks. Geographic information systems generally store additional geometry and attributes beyond the mathematical graph.

A critical modelling decision is the time basis of arc weights. A static network uses one value for each arc. A time-dependent network uses tᵢⱼ(h), the travel time on arc (i, j) when departure occurs at time h. Time-dependent models are more realistic under congestion but require more complex algorithms and data.

3. Shortest-Path Models

The shortest-path problem seeks a path from an origin o to a destination d that minimises additive arc weight:

where P is an o–d path and wᵢⱼ is distance, time, cost, or another chosen weight. The model assumes a single origin and destination, additive weights, and known arc values.

3.1 Dijkstra’s algorithm

Dijkstra’s algorithm solves the single-source shortest-path problem when every arc weight is non-negative. It maintains a tentative label L(i), the best currently known cost from the source to node i.

The principal steps are:

1. Set L(o) = 0 and L(i) = ∞ for all other nodes.
2. Select the unvisited node with the smallest tentative label.
3. For each outgoing arc (i, j), test relaxation:

1. Record predecessor information when an improvement occurs.
2. Mark i permanent and repeat until the destination is permanent or all reachable nodes are processed.

The relaxation equation is valid because any route reaching j through i has cost L(i) + wᵢⱼ. With non-negative weights, once the smallest tentative label is selected, no later route through an unprocessed node can improve it.

Worked example. Suppose the following directed arcs have travel times in minutes: A–B = 4, A–C = 2, C–B = 1, B–D = 5, C–D = 8, and B–C = 3. From A to D:

• Initial labels: A = 0, B = 4, C = 2, D = ∞.
• Select C (2): B becomes min(4, 2 + 1) = 3; D becomes 2 + 8 = 10.
• Select B (3): D becomes min(10, 3 + 5) = 8.
• Select D (8): terminate.

The shortest route is A → C → B → D, with travel time 8 minutes. The direct-looking route A → B → D takes 9 minutes.

Dijkstra’s algorithm should not be used directly with negative arc weights. Negative costs are unusual in ordinary road travel but may arise in abstract network models. Bellman–Ford or other suitable methods are then required. Dijkstra also requires care in time-dependent networks; the ordinary static version is not automatically valid when later departure changes arc travel time.

3.2 K-shortest paths and operational robustness

The single shortest path may be unsuitable if it passes through a frequently congested bridge or has no alternative during disruption. K-shortest-path methods generate several low-cost alternatives. A dispatcher can then consider reliability, driver familiarity, hazardous-material restrictions, or incident exposure.

A route with expected travel time 55 minutes and standard deviation 20 minutes may be operationally inferior to one with expected time 60 minutes and standard deviation 5 minutes when a customer requires dependable arrival. Thus, routing should distinguish expected efficiency from schedule reliability.

4. Minimum-Cost Flow Models

Shortest path concerns one movement. Minimum-cost flow models represent multiple units moving through a network with supplies, demands, and arc capacities.

Let xᵢⱼ be the flow on arc (i, j), uᵢⱼ its capacity, and cᵢⱼ its unit cost. Let bᵢ be node supply: positive for supply, negative for demand, and zero for a transshipment node. The minimum-cost-flow model is:

subject to flow balance:

and capacity restrictions:

A balanced network requires ∑ bᵢ = 0. Costs must be measured per unit of flow, such as currency per pallet. The model assumes divisible flow unless integrality constraints are added. In parcel or vehicle applications, indivisibility may make integer or mixed-integer models necessary.

Minimum-cost flow is useful for allocating shipments across depots, transport corridors, cross-docks, and vehicle capacity. It does not, by itself, determine the detailed sequence in which a particular truck visits customers.

5. Transportation Models

The transportation model is a structured special case of minimum-cost flow. It allocates quantities from m origins to n destinations. Let xᵢⱼ be the quantity shipped from origin i to destination j, cᵢⱼ unit transport cost, aᵢ supply, and bⱼ demand.

subject to:

For an exactly balanced problem, supply and demand constraints are equalities and total supply equals total demand. Unbalanced models can be balanced with a dummy origin or destination, provided the associated penalty or zero cost has a clear interpretation.

Transportation models answer “how much should move between each origin and destination?” They do not normally answer “which customer should be visited immediately before which other customer?” That distinction separates transportation planning from routing.

6. The Travelling-Salesperson and Vehicle-Routing Problems

The TSP seeks a minimum-cost tour that visits each customer exactly once and returns to the origin. For nodes V and binary decision variable xᵢⱼ, where xᵢⱼ = 1 if the tour travels directly from i to j:

subject to one departure and one arrival at every node:

These constraints alone may create several disconnected cycles. Subtour-elimination constraints are therefore required. One standard form uses a subset S of customer nodes:

for every nonempty proper subset S. This formulation is exact but potentially large. Practical solvers use branch-and-cut, cutting planes, and specialized heuristics.

The TSP is appropriate for one vehicle, one depot, and a visit to every customer. Fleet operations usually require the capacitated vehicle-routing problem (CVRP), in which several vehicles have capacity Q and customer i has demand qᵢ. A route must satisfy:

for every vehicle route Rₖ.

Common extensions include:

• VRP with time windows (VRPTW): customer i must be served within [aᵢ, bᵢ].
• Open VRP: vehicles need not return to the depot.
• Multi-depot VRP: vehicles originate from several depots.
• Pickup-and-delivery VRP: pickup must precede the corresponding delivery.
• Electric VRP: battery state and charging decisions are included.
• Periodic VRP: customers require service on specified days or frequencies.

A time-window constraint can be represented using service-start time Tᵢ and waiting variable. At minimum:

If arc (i, j) is used, a common sequencing constraint is:

where sᵢ is service time and M is a sufficiently large constant. M must be chosen carefully: an excessively large value weakens computation and can cause numerical difficulties; an insufficient value incorrectly removes feasible solutions.

7. Practical Constraints and Cost Components

A routing model should represent the constraints that materially affect feasibility or cost.

Capacity

Capacity may be measured in weight, volume, pallet positions, compartments, or combinations. A vehicle can be weight-feasible but volume-infeasible. Multi-compartment vehicles also require compatibility constraints for temperature-controlled, hazardous, or segregated products.

Driver hours and breaks

Legal driving limits, maximum duty periods, and mandatory breaks restrict route duration. These are regulatory constraints, not merely cost preferences. A route that appears cheapest may be illegal if it requires excessive duty time.

Time windows and service levels

A customer’s receiving window, appointment, or promised delivery time may dominate distance minimisation. Early arrival may also create waiting cost and dock congestion.

Road and vehicle restrictions

Bridge weight limits, height restrictions, low-emission zones, truck bans, vehicle dimensions, and hazardous-material rules determine whether an arc is feasible. Such restrictions should be encoded by removing the arc or assigning a prohibitive cost—not by relying on driver discretion after optimisation.

Tolls and fixed vehicle costs

Total route cost commonly includes variable and fixed components:

Fₖ is the fixed cost of using vehicle k, v_d is variable distance cost per kilometre, v_t is time cost per hour, and τᵢⱼ is toll. Units must be consistent. If fuel is included in v_d, it should not be added again as a separate duplicate cost.

8. Worked Integrated Example

A depot serves three customers. Vehicle capacity is 10 units. Customer demands are A = 4, B = 3, and C = 2, so all can be served on one route. Arc data are:

Assume symmetric return arcs, variable distance cost of 1.20 currency/km, time cost of 18 currency/h, and fixed vehicle cost of 40 currency. Compare route Depot–A–B–C–Depot with Depot–B–A–C–Depot. The required return-arc values are inferred from symmetry.

For Depot–A–B–C–Depot:

• Distance = 8 + 5 + 3 + 9 = 25 km.
• Travel time = 0.20 + 0.15 + 0.10 + 0.30 = 0.75 h.
• Toll = 0 + 0 + 0 + 0 = 0.
• Cost = 40 + (1.20 × 25) + (18 × 0.75) = 40 + 30 + 13.50 = 83.50.

For Depot–B–A–C–Depot:

• Distance = 6 + 5 + 4 + 9 = 24 km.
• Travel time = 0.25 + 0.15 + 0.20 + 0.30 = 0.90 h.
• Toll = 2 + 0 + 1 + 0 = 3.
• Cost = 40 + (1.20 × 24) + (18 × 0.90) + 3 = 40 + 28.80 + 16.20 + 3 = 88.00.

The first route is cheaper despite being 1 km longer, because it avoids tolls and has lower travel time. This illustrates why distance-only routing can produce inferior fleet decisions.

9. Illustrative Case: Urban Grocery Distribution

Background

A fictional regional grocery distributor operates one depot and 18 refrigerated vehicles. Each vehicle has a 12-pallet capacity. Stores impose delivery windows, and city regulations prohibit heavy vehicles on selected roads during morning periods.

Problem

The existing planning process assigned customers geographically and then allowed dispatchers to adjust sequences manually. On-time delivery was 91%, average vehicle utilisation was 68%, and several routes exceeded driver duty limits during congestion.

Analysis

The firm built a time-dependent directed network. Arc travel times varied by departure period; prohibited arcs were removed for restricted vehicles and time periods. The model included vehicle capacity, pallet compatibility, service times, store windows, break rules, and a cost function containing fixed vehicle cost, distance, paid driver time, and late-delivery penalties.

A two-stage approach was selected. First, a mixed-integer routing model created daily routes. Second, a rolling-horizon dispatcher re-optimised routes when traffic incidents, cancellations, or urgent orders occurred. Candidate routes were checked against a geographic information system and driver operating policies.

Outcome

In the illustrative implementation, the number of vehicles required on a representative day fell from 18 to 16, average utilisation rose to 82%, and on-time delivery increased to 97%. Results should not be interpreted as universal benchmarks: they depend on demand density, data quality, labour rules, and the validity of travel-time estimates.

Learning points

1. Geographic closeness does not guarantee route compatibility.
2. Time windows and service times can be more restrictive than distance.
3. A feasible route must satisfy legal and physical constraints, not only mathematical objectives.
4. Human dispatch expertise remains valuable for exceptions and unrecorded operational knowledge.
5. Performance should be measured using cost, service, utilisation, safety, emissions, and driver impact together.

10. Technology, AI, and Governance

Modern routing platforms combine optimisation solvers, telematics, GPS traces, traffic feeds, digital maps, warehouse systems, and customer-order data. Machine-learning models may forecast travel time, demand, or failed deliveries; optimisation then uses those forecasts to construct routes.

AI does not remove the need for model governance. Managers should validate map attributes, monitor forecast error, document objective weights, test unusual scenarios, and provide override procedures. Automated routes can reproduce data bias—for example, systematically assigning difficult or unsafe stops to particular drivers or depots. Personal data from vehicle tracking must be collected lawfully, secured, retained only as necessary, and used transparently.

A prudent deployment process includes:

• master-data validation;
• feasibility testing against actual vehicle and legal constraints;
• sensitivity analysis for traffic and demand uncertainty;
• human review of high-risk routes;
• audit trails for route changes;
• cybersecurity controls for connected vehicles;
• continuous measurement against pre-agreed KPIs.

Relevant KPIs include cost per stop, cost per kilometre, kilometres per delivery, vehicle utilisation, route completion rate, on-time-in-full delivery, failed-delivery rate, driver overtime, empty kilometres, energy use, and emissions. KPIs must be interpreted together: reducing kilometres while increasing failed deliveries is not a genuine improvement.

11. Limitations and Critical Evaluation

Routing models simplify reality. Travel times are uncertain, demand may change after dispatch, service times are imperfectly observed, and drivers may know constraints absent from databases. A mathematically optimal solution under inaccurate data is operationally poor.

Other limitations include:

• computational difficulty of large integer-routing models;
• unstable recommendations when costs are nearly equal;
• excessive reliance on a single objective;
• weak treatment of disruption and resilience;
• privacy and surveillance concerns;
• model infeasibility caused by overly strict or inconsistent constraints.

Managers should use scenario analysis. For example, compare solutions under normal traffic, severe congestion, vehicle breakdown, demand growth, and road closure. Robust or stochastic optimisation may be justified when uncertainty is substantial, although these methods require probability estimates and can increase computational burden.

Chapter Summary

Fleet routing is founded on graph representation: nodes describe operational locations and arcs describe feasible movements with distance, time, cost, toll, emissions, and risk attributes. Shortest-path models select a route between an origin and destination; Dijkstra’s algorithm is appropriate for non-negative static arc weights. Minimum-cost-flow and transportation models allocate quantities through networks, while TSP and vehicle-routing models determine visit sequences and vehicle tours.

Real fleet decisions require more than distance minimisation. Capacity, time windows, service duration, driver hours, road restrictions, tolls, vehicle compatibility, congestion, reliability, and regulatory requirements must be represented explicitly. Generalised cost functions can combine measures, but constrained formulations often provide clearer managerial control. Modern systems integrate optimisation, GIS, telematics, traffic data, and AI forecasts, subject to governance, privacy, safety, and cybersecurity requirements. The best route is therefore a feasible, lawful, reliable, and economically defensible operating plan—not merely the geometrically shortest path.

Key Terms

Graph: Mathematical structure consisting of nodes and connecting arcs.

Node: Location or state represented in a network.

Arc: Directed connection between two nodes.

Path: Sequence of connected arcs between locations.

Weight: Numerical attribute assigned to an arc or route.

Shortest path: Minimum-weight path between an origin and destination.

Relaxation: Updating a tentative shortest-path label when a cheaper route is found.

Minimum-cost flow: Model that sends flow through a capacitated network at minimum total cost.

Transportation model: Flow model allocating supply from origins to destination demands.

TSP: Tour visiting every required node once and returning to the origin.

VRP: Routing problem involving multiple vehicles and customer visits.

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

Time window: Permitted interval for service at a customer.

Subtour: Disconnected cycle within a proposed TSP solution.

Generalized cost: Weighted combination of measures such as distance, time, tolls, and emissions.

Flow balance: Equality between a node’s inflow, outflow, and net supply or demand.

Feasible route: Route satisfying all operational, physical, and regulatory restrictions.

Time-dependent network: Network whose arc conditions vary with departure time.

Route robustness: Ability of a route to perform acceptably under uncertainty or disruption.

Review Questions

Short Answer Questions

1. What is the difference between a node and an arc in a logistics network?
2. State the main condition under which Dijkstra’s algorithm is valid.
3. Why does a transportation model not normally determine customer visit sequence?
4. What is the purpose of a capacity constraint in the CVRP?
5. Give two examples of regulatory constraints that can make an arc infeasible.

Long Answer Questions

1. Explain how a road network can be represented as a directed weighted graph, including at least four possible arc attributes.
2. Compare shortest-path, minimum-cost-flow, transportation, TSP, and VRP models in terms of decision purpose and application.
3. Derive and explain the logic of the relaxation step in Dijkstra’s algorithm.
4. Discuss the advantages and risks of using a generalized cost function in fleet routing.
5. Explain how data quality, uncertainty, and governance affect the success of AI-enabled routing.

Analytical / Application Questions

1. A fleet manager must choose between a 40 km route taking 0.8 hours with a toll of 10 currency units and a 46 km route taking 0.6 hours with no toll. Distance costs 1 currency/km and driver time costs 20 currency/hour. Which route has the lower variable cost, and what non-cost factors should be reviewed?
2. Design a feasible modelling approach for a depot serving customers with different vehicle capacities, delivery windows, and restricted urban roads. Identify the decision variables, objective, and at least five constraints.
3. A route is mathematically shortest but has highly variable travel time and a high probability of closure. Explain how you would evaluate alternative routes and recommend a decision using reliability and resilience considerations.

Multiple Choice Questions with Answers

Question 1

In a directed logistics graph, what does an arc normally represent?

A. A feasible movement between two nodes

B. A vehicle’s total carrying capacity

C. A customer’s demand forecast

D. A driver’s legal duty period

Correct Answer: A. A feasible movement between two nodes

Question 2

Dijkstra’s algorithm requires which condition on arc weights?

A. All arc weights must be identical

B. All arc weights must be non-negative

C. Every node must have exactly two arcs

D. The network must contain no cycles

Correct Answer: B. All arc weights must be non-negative

Question 3

In the worked shortest-path example, what is the shortest route from A to D?

A. A → B → D, taking 9 minutes

B. A → C → D, taking 10 minutes

C. A → C → B → D, taking 8 minutes

D. A → B → C → D, taking 15 minutes

Correct Answer: C. A → C → B → D, taking 8 minutes

Question 4

What does a minimum-cost-flow model primarily determine?

A. The exact service sequence for one truck

B. The allocation of flow through a capacitated network

C. The legal driving-break schedule for every driver

D. The geometry of a road intersection

Correct Answer: B. The allocation of flow through a capacitated network

Question 5

Which problem requires a tour visiting each required node once and returning to the origin?

A. Transportation problem

B. Shortest-path problem

C. Travelling-salesperson problem

D. Maximum-spanning-tree problem

Correct Answer: C. Travelling-salesperson problem

Question 6

A vehicle has capacity 10 units and serves customers demanding 4, 3, and 2 units. What is the remaining capacity after service?

A. 0 units

B. 1 unit

C. 2 units

D. 3 units

Correct Answer: B. 1 unit

Question 7

In a time-window model, what does aᵢ ≤ Tᵢ ≤ bᵢ express?

A. Vehicle capacity feasibility

B. Permitted service-start time at customer i

C. Maximum toll on arc i

D. Minimum number of vehicles

Correct Answer: B. Permitted service-start time at customer i

Question 8

Using the chapter’s integrated example, what is the cost of Depot–A–B–C–Depot?

A. 73.50 currency units

B. 83.50 currency units

C. 88.00 currency units

D. 93.00 currency units

Correct Answer: B. 83.50 currency units

Question 9

Why can a distance-only route be inferior to a longer route?

A. Distance is never measurable

B. Longer routes always use fewer vehicles

C. Time, tolls, reliability, or constraints may make it more costly or infeasible

D. Shortest-path algorithms ignore all nodes

Correct Answer: C. Time, tolls, reliability, or constraints may make it more costly or infeasible

Question 10

Which is an appropriate governance practice for AI-enabled routing?

A. Allowing the system to change objectives without documentation

B. Ignoring map and vehicle-data quality

C. Maintaining audit trails and testing routes against legal constraints

D. Removing human review from high-risk routes

Correct Answer: C. Maintaining audit trails and testing routes against legal constraints