Classical Routing and Optimization Models

Introduction

Route planning converts physical movement through a supply network into a structured decision problem. A logistics manager may need to determine the least-cost path between a distribution centre and a customer, allocate vehicles to delivery zones, sequence visits to retail outlets, or route flows through a multimodal network while respecting capacity. These decisions are closely related, but they are not interchangeable. The mathematical structure of the decision determines the appropriate optimization model.

This chapter develops five foundational models: shortest path, minimum-cost flow, maximum flow, assignment, and the traveling salesperson problem (TSP). It also introduces vehicle-routing extensions, complexity considerations, solution methods, and practical issues such as uncertainty, time windows, sustainability, and data governance. The models are classical because they provide the conceptual and algorithmic foundations for modern transportation-management systems and advanced optimization software.

Learning Objectives

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

1. Represent a logistics network as a directed or undirected graph.
2. Formulate shortest-path and minimum-cost-flow models mathematically.
3. Distinguish flow, assignment, TSP, and vehicle-routing problems.
4. Apply appropriate algorithms and interpret their computational complexity.
5. Analyze assumptions, limitations, and managerial implications.
6. Evaluate a routing solution under cost, service, capacity, and sustainability criteria.

1. Network Representation and Modeling Logic

A 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 plants, warehouses, cross-docks, customers, ports, or intersections. An arc represents a permitted movement between two nodes. For an undirected road, movement is possible in both directions; for a directed arc, movement is permitted only in the indicated direction.

Each arc may have one or more attributes:

A generalized arc cost can combine these attributes:

Here pᵢⱼ is direct monetary cost, tᵢⱼ is time, eᵢⱼ is emissions, and α and β are managerial conversion weights. The units must be made compatible: for example, α may be currency per hour and β currency per kilogram of CO₂e. This weighted formulation is useful, but it can conceal trade-offs. A solution minimizing generalized cost may be slower or less environmentally desirable than another solution. Multi-objective or constrained formulations are often preferable when priorities are strategic.

A decision variable should represent the operational choice. For routing, a common binary variable is xᵢⱼ = 1 if arc (i, j) is selected and 0 otherwise. For flow, xᵢⱼ may instead be a nonnegative quantity transported on the arc. Correctly distinguishing these interpretations is essential.

2. Shortest-Path Problems

2.1 Concept and formulation

The shortest-path problem identifies a minimum-cost route from an origin node s to a destination node r. Costs may represent distance, time, fuel, tolls, risk, or a weighted combination.

Let xᵢⱼ be a binary variable indicating whether arc (i, j) belongs to the selected path. The basic formulation is:

subject to flow conservation:

The first constraint sends one unit of flow from the origin to the destination. At intermediate nodes, incoming and outgoing selected flow must balance. The model assumes a known network, additive arc costs, and no requirement to visit multiple customers. If costs are nonnegative, the problem has especially efficient solution methods.

2.2 Algorithms and complexity

Dijkstra’s algorithm repeatedly labels the unprocessed node with the smallest tentative distance and relaxes its outgoing arcs. With a binary heap, its common complexity is O((|V| + |A|) log |V|), although implementation details affect the exact bound. It requires nonnegative arc costs.

The Bellman–Ford algorithm can handle negative arc costs and detects negative cycles, but is slower, with complexity O(|V||A|). Negative transportation costs are unusual in ordinary logistics, but the algorithm is important conceptually and in applications involving rebates, credits, or transformed network models.

The Floyd–Warshall algorithm computes shortest paths between all pairs of nodes in O(|V|³) time. It is useful for relatively small, dense networks where many origin–destination queries must be answered.

2.3 Worked example

Suppose a shipment travels from A to D through the following directed arcs:

Candidate routes include A–B–D with cost 4 + 5 = 9, A–C–D with cost 2 + 8 = 10, and A–C–B–D with cost 2 + 1 + 5 = 8. Therefore, the shortest route is A–C–B–D, with total cost 8. The result illustrates why a locally cheapest first arc is not necessarily part of the best complete route.

2.4 Practical limitations

A static shortest-path solution can become infeasible when travel times change, roads are closed, vehicle dimensions are restricted, or delivery appointments impose time windows. A route that is shortest in distance may not be fastest during congestion. Dynamic routing therefore updates arc attributes as information changes, while stochastic routing models represent travel times as random variables rather than fixed values.

3. Minimum-Cost Flow and Maximum Flow

3.1 Minimum-cost flow

Minimum-cost flow generalizes shortest path by allowing multiple units of flow, several origins and destinations, arc capacities, and node supply or demand. Let bᵢ denote the net supply at node i: positive for supply, negative for demand, and zero for a transshipment node. Let xᵢⱼ ≥ 0 be flow on arc (i, j), with capacity uᵢⱼ.

subject to:

Feasibility requires that total supply equals total demand:

The model assumes linear costs and divisible flow. If a truck must be dispatched as an indivisible whole vehicle, a mixed-integer model may be required. Under integral supplies, capacities, and a network incidence matrix, the linear minimum-cost-flow model has integral extreme-point solutions, meaning that an optimal basic solution can be integral without explicitly imposing binary variables.

3.2 Maximum-flow problem

Maximum flow seeks the greatest quantity that can move from source s to sink r, subject to arc capacities. With fᵢⱼ representing flow:

subject to flow conservation at intermediate nodes and 0 ≤ fᵢⱼ ≤ uᵢⱼ. The max-flow/min-cut theorem states that the maximum feasible flow equals the capacity of the minimum s–r cut. In supply chains, this can identify bottleneck corridors, warehouse throughput limits, or port capacity constraints.

3.3 Example: capacity bottleneck

A distribution network has source S, intermediate nodes X and Y, and destination D. Capacities are S–X = 40, S–Y = 30, X–D = 25, and Y–D = 30 units per day. Although 70 units can leave S, only 55 units can reach D because the inbound arcs to D total 25 + 30 = 55. The destination-side cut therefore establishes an upper bound of 55 units. This analysis distinguishes a transportation bottleneck from a demand problem: increasing source supply cannot raise deliveries unless downstream capacity is expanded.

4. Assignment Models

The assignment problem allocates each worker, vehicle, driver, order, or territory to exactly one counterpart, while each counterpart receives exactly one resource. Let xᵢⱼ = 1 if resource i is assigned to task j and 0 otherwise. If cᵢⱼ is the cost of that assignment:

subject to:

The standard model assumes equal numbers of resources and tasks, one-to-one allocation, known costs, and independent assignment effects. The Hungarian algorithm solves the square assignment problem in polynomial time, commonly stated as O(n³). For unequal sets, dummy rows or columns can represent unused capacity, with carefully chosen penalty costs.

Worked example

Three vehicles must be assigned to three delivery zones. The cost matrix is:

The assignment A–Zone 2, B–Zone 3, and C–Zone 1 has total cost 6 + 4 + 3 = 13. Other combinations, such as A–Zone 1, B–Zone 3, C–Zone 2, total 8 + 4 + 8 = 20. The minimum assignment is therefore cost 13, assuming all zones can be served independently and vehicle capacities are adequate.

Assignment is not a substitute for routing. If one vehicle can serve several customers on a tour, assignment alone ignores sequencing and route interactions. Conversely, assignment can be a useful first-stage approximation for large planning problems.

5. The Traveling Salesperson Problem

5.1 Definition and formulation

The TSP seeks a minimum-cost tour that visits each customer exactly once and returns to the starting node. Let V be the set of locations and xᵢⱼ be a binary variable indicating whether the tour travels directly from i to j. The basic degree constraints are:

The objective is:

Degree constraints alone may produce several disconnected cycles. Subtour-elimination constraints are therefore needed. For every proper nonempty subset S of locations:

This prevents a closed subtour containing only nodes in S. In practice, modern mixed-integer solvers often generate such constraints dynamically through branch-and-cut rather than listing all of them in advance.

5.2 Complexity and solution methods

The TSP is NP-hard. No polynomial-time algorithm is known for solving every instance exactly, and the computational burden can grow rapidly as the number of locations increases. Exact approaches include integer programming, branch-and-bound, branch-and-cut, and dynamic programming for small instances. Heuristics such as nearest neighbour, insertion methods, 2-opt, and 3-opt can obtain good solutions quickly. Metaheuristics, including tabu search, simulated annealing, and genetic algorithms, explore broader solution spaces but do not guarantee optimality.

A two-opt move removes two tour arcs and reconnects the two resulting paths in the alternative order. If the resulting tour is shorter, the move is accepted. This simple local-search technique often improves a constructive initial solution substantially.

5.3 Assumptions and limits

The classical symmetric TSP assumes cᵢⱼ = cⱼᵢ. Real roads are often asymmetric because of one-way streets, turn restrictions, grades, congestion, and different travel times by direction. The asymmetric TSP permits cᵢⱼ ≠ cⱼᵢ. The classical TSP also assumes one vehicle, one depot, no capacity limit, no service time, and no time windows. These assumptions rarely hold fully in commercial distribution.

6. From TSP to Vehicle Routing

The vehicle-routing problem (VRP) extends the TSP to multiple vehicles and operational restrictions. Common variants include:

A basic capacitated VRP uses binary arc variables xᵢⱼᵏ for vehicle k and load variables to prevent infeasible tours. A typical capacity requirement is:

where qᵢ is demand at customer i, yᵢᵏ indicates service by vehicle k, and Qₖ is vehicle capacity. This constraint is necessary but not sufficient: route continuity, depot departure and return, customer coverage, and subtour elimination must also be enforced.

Time-window models use arrival-time variables Tᵢ and constraints of the form:

Here sᵢ is service time at i, tᵢⱼ is travel time, and M is a sufficiently large constant. If arc (i, j) is selected, the constraint enforces temporal sequencing; if it is not selected, the large-M term relaxes the constraint. Poorly chosen M values can cause numerical instability, so tighter bounds are preferred.

7. Selecting a Model and Algorithm

Model selection should begin with the operational question rather than the available software.

A useful workflow is: define nodes and arcs; collect costs, times, capacities, and demands; identify constraints; formulate the model; validate the data; solve; test sensitivity; and translate the output into executable routes. The mathematically optimal solution is not automatically operationally valid. Dispatchers should verify road restrictions, loading feasibility, driver regulations, appointment commitments, and exceptional events.

8. Illustrative Case: Regional Grocery Distribution

Background

The following is a fictional illustrative case. A grocery distributor operates one regional depot and serves eight stores. Each store has a daily demand, a delivery time window, and a service duration. The distributor has three identical vehicles, each with capacity 4,000 kg. Fuel, driver time, and emissions are important, but service reliability is a contractual requirement.

Problem

A simple TSP would be inappropriate because there are multiple vehicles, vehicle capacities, service times, and time windows. The relevant model is a capacitated VRP with time windows and a weighted operating objective. The objective might minimize:

where λ converts emissions into the organization’s chosen monetary or policy weight.

Analysis and approach

The planning team first uses a shortest-path engine to calculate travel times between every pair of relevant locations. These times form the arc data for the VRP. Demand is then used in capacity constraints, while store appointments become time-window constraints. A mixed-integer solver is used for a small daily instance. For larger instances, the team constructs an initial feasible solution using a savings heuristic and improves it with local search.

The planner compares three scenarios:

The balanced scenario is selected because it satisfies all appointment commitments while reducing empty travel. The dispatcher retains authority to alter routes when a road closure, refrigeration problem, or urgent order occurs.

Outcome and learning points

The case demonstrates model hierarchy. Shortest paths supply travel-time data; the VRP determines customer sequencing and vehicle assignment; capacity and time-window constraints determine feasibility. It also shows why optimization should be embedded in a control process rather than treated as a one-time answer. The value of a route plan depends on data quality, execution discipline, and the ability to reoptimize when conditions change.

9. Complexity, Uncertainty, and Robustness

Polynomial-time problems such as standard shortest path and assignment are generally more scalable than NP-hard problems such as TSP and VRP. Complexity does not mean that a problem is unusable; it means that exact solution time can become unpredictable as instance size and constraints grow.

Uncertainty enters through travel time, demand, vehicle availability, service duration, and road access. A deterministic model may use expected values, but this can produce fragile schedules. Robust optimization protects against specified deviations, for example by reserving time slack. Stochastic programming represents scenarios and probabilities, while rolling-horizon control repeatedly solves the problem using updated information.

Sensitivity analysis should examine changes in fuel price, demand, travel time, capacity, and penalty costs. If small data changes produce large route changes, management should avoid presenting the solution as precise or permanent. Scenario analysis is especially valuable when the cost differences among alternative routes are small.

10. Technology, Governance, and Ethical Issues

Modern transportation systems combine optimization with geographic information systems, telematics, cloud computing, and machine-learning forecasts. AI can predict travel time, demand, or failed deliveries, but prediction is not optimization: a forecast estimates what may happen, whereas optimization selects an action under constraints. Human oversight remains necessary when data are incomplete or operational rules are not encoded.

Important governance practices include:

• documenting objective functions, penalties, and assumptions;
• validating map, address, capacity, and time-window data;
• monitoring whether algorithms systematically disadvantage particular regions or driver groups;
• protecting customer, driver, and vehicle-location data;
• retaining an override and incident-reporting process;
• auditing model performance against actual service and emissions outcomes.

A route that minimizes cost by imposing unsafe driving schedules is unacceptable. Driver-hours regulations, rest requirements, vehicle weight limits, hazardous-material rules, accessibility obligations, and environmental regulations must be treated as hard constraints where applicable. Ethical route planning therefore includes safety, fairness, privacy, and worker welfare—not only cost efficiency.

11. Best Practices for Professional Application

1. Define the decision and the unit of analysis before selecting an algorithm.
2. Separate fixed costs, variable movement costs, penalties, and service constraints.
3. Use realistic travel-time distributions or time-dependent travel times when congestion matters.
4. Validate feasibility independently of the solver.
5. Prefer constrained multi-objective analysis to arbitrary cost weighting when trade-offs are strategic.
6. Compare optimized routes with a credible operational baseline.
7. Use lower and upper bounds to communicate solution quality for difficult integer problems.
8. Reoptimize selectively rather than changing routes unnecessarily during execution.
9. Record assumptions and version the input data and model.
10. Measure outcomes such as on-time delivery, kilometres, vehicle utilization, emissions, and driver overtime.

Chapter Summary

Classical network models translate supply-chain movement into mathematically defined decisions. Shortest-path models select a least-cost route between two nodes and can be solved efficiently under common conditions. Minimum-cost flow models distribute multiple units through capacitated networks, while maximum-flow models identify throughput limits. Assignment models allocate resources to individual tasks but do not generally determine multi-stop tours. The TSP constructs a single tour visiting every location, whereas the VRP extends routing to multiple vehicles, capacities, time windows, and other operational realities.

Model assumptions determine applicability. Nonnegative arc costs support Dijkstra’s algorithm; negative costs require different methods. Assignment and shortest-path problems are polynomially solvable, while TSP and most VRPs are NP-hard and often require integer programming, heuristics, or hybrid methods. In practice, shortest-path calculations frequently serve as inputs to larger routing models. Effective implementation requires data validation, sensitivity analysis, human oversight, regulatory compliance, and ongoing measurement.

Key Terms

Graph: A mathematical structure consisting of nodes and connecting arcs.

Node: A location or state in a network.

Arc: A directed connection between two nodes.

Shortest path: The least-cost route between an origin and destination.

Flow conservation: The requirement that inflow and outflow satisfy node supply or demand.

Minimum-cost flow: A model that sends required quantities through a network at minimum total cost.

Maximum flow: The greatest feasible quantity that can move from a source to a sink.

Capacity: The maximum permitted flow, load, or activity on an arc or vehicle.

Assignment problem: A one-to-one allocation of resources to tasks.

TSP: A minimum-cost tour visiting each location once and returning to the origin.

Subtour: A disconnected cycle within a proposed TSP solution.

VRP: A routing model involving multiple vehicles and customer-service constraints.

Time window: The permitted interval for serving a customer.

Mixed-integer programming: Optimization containing continuous and discrete decision variables.

NP-hard: A complexity classification indicating that no polynomial-time solution method is known for all instances.

Heuristic: A procedure that seeks good solutions without guaranteeing optimality.

Robust optimization: Optimization designed to remain effective under specified uncertainty.

Generalized cost: A combined measure incorporating monetary and nonmonetary attributes.

Flow bottleneck: A capacity restriction limiting network throughput.

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

Review Questions

5 Short Answer Questions

1. What is the difference between a node and an arc in a logistics network?
2. Why can assignment models not usually replace vehicle-routing models?
3. What condition must total node supplies and demands satisfy in a balanced minimum-cost-flow model?
4. Why are subtour-elimination constraints needed in the TSP?
5. State one reason a shortest-distance route may not be the fastest route.

5 Long Answer Questions

1. Formulate a shortest-path problem and explain the meaning of its flow-conservation constraints.
2. Compare shortest path, minimum-cost flow, assignment, TSP, and VRP in terms of decisions and assumptions.
3. Explain why the TSP is computationally more difficult than the standard assignment problem.
4. Discuss how capacity and time windows change a basic routing problem.
5. Evaluate the advantages and limitations of combining monetary cost, travel time, and emissions in a generalized objective function.

3 Analytical / Application Questions

1. A company must move products from two plants to three warehouses through a network with arc capacities and different costs. Specify the variables, objective, and constraints for a minimum-cost-flow formulation.
2. A delivery route has excellent distance performance but repeatedly violates customer appointments. Diagnose the modeling deficiency and propose two model or data changes.
3. Design a decision process for a distributor that combines shortest-path calculations, a vehicle-routing model, real-time updates, and governance controls. Explain what should remain under human review.

Multiple Choice Questions with Answers

Question 1

Which model is most appropriate for finding the least-cost route between one origin and one destination when intermediate transshipment is allowed?

A. Assignment model

B. Shortest-path model

C. Traveling salesperson problem

D. Maximum-flow model

Correct Answer: B. Shortest-path model

Question 2

In a balanced minimum-cost-flow model, which condition is required?

A. Every arc must have equal cost

B. Every node must have zero demand

C. Total supply must equal total demand

D. All flows must be binary

Correct Answer: C. Total supply must equal total demand

Question 3

A standard assignment model requires which relationship in its square form?

A. Each resource and each task is matched exactly once

B. Each vehicle visits every customer

C. Flow must maximize network throughput

D. Every route must return to a depot

Correct Answer: A. Each resource and each task is matched exactly once

Question 4

Why are subtour-elimination constraints needed in the TSP?

A. To permit multiple visits to each customer

B. To prevent disconnected cycles that do not form one complete tour

C. To convert costs into travel times

D. To enforce vehicle capacity

Correct Answer: B. To prevent disconnected cycles that do not form one complete tour

Question 5

What is the computational classification of the classical TSP?

A. Strongly polynomial for all instances

B. NP-hard

C. Infeasible by definition

D. A continuous optimization problem only

Correct Answer: B. NP-hard

Question 6

A route uses arcs with costs 4, 1, and 5. What is its total additive cost?

A. 9

B. 10

C. 11

D. 20

Correct Answer: B. 10

Question 7

Which algorithm requires nonnegative arc costs in its standard form?

A. Dijkstra’s algorithm

B. Bellman–Ford algorithm

C. Hungarian algorithm

D. Floyd–Warshall algorithm

Correct Answer: A. Dijkstra’s algorithm

Question 8

A vehicle-routing problem with customer appointment intervals requires which additional feature?

A. Substitution of all costs with zero

B. Time-window constraints

C. Removal of vehicle capacities

D. A requirement that every arc be symmetric

Correct Answer: B. Time-window constraints

Question 9

If arcs entering a destination have capacities of 25 and 30 units, what upper bound do those arcs impose on flow into that destination?

A. 5 units

B. 25 units

C. 30 units

D. 55 units

Correct Answer: D. 55 units

Question 10

Which statement best distinguishes prediction from optimization in a modern routing system?

A. Prediction estimates conditions; optimization selects actions under constraints

B. Prediction always guarantees the best route

C. Optimization requires no operational data

D. Prediction and optimization are mathematically identical

Correct Answer: A. Prediction estimates conditions; optimization selects actions under constraints