Networks, Transportation, and Logistics | Malone Math

The Central Idea

A transportation or logistics system can often be represented as a network:

\[ \boxed{ \text{nodes} +\text{links} +\text{flows} +\text{capacities} +\text{costs} +\text{decisions} \longrightarrow \text{system performance} }. \]

Nodes may represent cities, warehouses, intersections, ports, customers, or transfer points. Links may represent roads, rail lines, shipping lanes, pipelines, air routes, or information channels.

Graphs as Network Models

A graph is commonly written

\[ \boxed{G=(V,E)}, \]

where $V$ is the set of vertices or nodes and $E$ is the set of edges or links.

The graph captures connectivity before any flow or optimization is added.

Directed and Undirected Networks

In an undirected network, an edge can be traversed in either direction. In a directed network, each arc has a specified direction.

One-way roads, shipping lanes, process flows, and supply-chain movements are often modeled with directed arcs.

Weighted Networks

Edges may carry weights representing distance, travel time, monetary cost, risk, fuel consumption, reliability, or another performance quantity.

If $c_{ij}$ is the cost of moving from node $i$ to node $j$, then the cost of a path is often modeled as

\[ \boxed{ C(P)=\sum_{(i,j)\in P}c_{ij} }. \]

Paths and Routes

A path is a sequence of connected nodes or edges. A route is a path selected for movement through the network.

A logistics model may optimize a single path, a set of paths, or a sequence of stops depending on the decision problem.

Shortest-Path Problems

The shortest-path problem seeks a path from origin $s$ to destination $t$ minimizing total weight:

\[ \boxed{ \min_{P:s\rightarrow t} \sum_{(i,j)\in P}c_{ij} }. \]

The word shortest can refer to distance, time, cost, risk, or any other additive edge weight.

Dynamic Programming View of Shortest Paths

If $d(j)$ is the best known cost to reach node $j$, then a shortest-path recursion has the form

\[ \boxed{ d(j)=\min_i\left[d(i)+c_{ij}\right] }. \]

This principle underlies several shortest-path algorithms.

Minimum Spanning Trees

A minimum spanning tree connects all nodes in an undirected connected network while minimizing total selected edge weight and avoiding cycles.

Such models can support design of low-cost utility, communication, or distribution backbones when every node must be connected.

Network Flow

Let $x_{ij}$ denote flow along arc $(i,j)$. At an intermediate node $i$, conservation often requires

\[ \boxed{ \sum_j x_{ji} = \sum_j x_{ij} }. \]

Flow entering a transshipment node equals flow leaving it unless the node produces, consumes, stores, or loses material.

Source and Sink Nodes

A source supplies flow, while a sink receives it. In a single-source, single-sink flow problem,

\[ \boxed{ \text{flow out of source} = \text{flow into sink} }. \]

This equality follows from conservation across the network.

Capacity Constraints

A link may carry at most a specified capacity $u_{ij}$:

\[ \boxed{ 0\le x_{ij}\le u_{ij} }. \]

Capacity may represent roadway throughput, rail slots, pipeline volume, warehouse processing, aircraft seats, or communication bandwidth.

Maximum-Flow Problems

A maximum-flow model seeks the largest feasible amount that can move from a source to a sink while satisfying link capacities and flow conservation.

The objective is

\[ \boxed{ \max F } \]

subject to the network constraints.

Cuts and Bottlenecks

A cut separates the source from the sink. The capacity of a cut is the total capacity of arcs crossing from the source side to the sink side.

Bottlenecks can often be identified by low-capacity cuts, which limit total network throughput.

Minimum-Cost Flow

If moving one unit along arc $(i,j)$ costs $c_{ij}$, a minimum-cost flow model minimizes

\[ \boxed{ \sum_{(i,j)\in E}c_{ij}x_{ij} } \]

subject to conservation, supply-demand balances, and capacity constraints.

Transportation Problems

Suppose supply location $i$ can ship quantity $s_i$, destination $j$ requires demand $d_j$, and shipping one unit costs $c_{ij}$. The transportation model chooses shipment quantities $x_{ij}$.

A standard objective is

\[ \boxed{ \min \sum_i\sum_j c_{ij}x_{ij} }. \]

Supply Constraints

Each origin cannot ship more than its available supply:

\[ \boxed{ \sum_jx_{ij}\le s_i }. \]

Demand Constraints

Each destination must receive its required quantity:

\[ \boxed{ \sum_i x_{ij}=d_j }. \]

Inequality forms may be used when unmet demand or overdelivery is allowed and penalized.

Transshipment Models

Real logistics networks often include intermediate transfer nodes such as ports, hubs, cross-docks, rail yards, and distribution centers.

Transshipment models extend the transportation problem by allowing material to pass through intermediate nodes before reaching its destination.

Vehicle Routing

Vehicle-routing problems choose routes for a fleet serving multiple customers. They combine path selection with constraints such as

vehicle capacity;
customer demand;
time windows;
driver hours;
depot assignment;
route duration;
pickup and delivery precedence.

The Traveling Salesperson Problem

The traveling salesperson problem seeks a minimum-cost tour that visits each required node once and returns to the origin.

If binary variable $x_{ij}$ indicates whether arc $(i,j)$ is used, a simplified objective is

\[ \boxed{ \min \sum_i\sum_j c_{ij}x_{ij} }. \]

Additional constraints are needed to ensure a single complete tour.

Subtour Elimination

Merely requiring one arrival and one departure at each node can create several disconnected cycles.

Traveling-salesperson formulations therefore require subtour-elimination constraints or equivalent logic to force one connected route.

Vehicle Capacity

If vehicle $k$ has capacity $Q_k$, total assigned demand must satisfy

\[ \boxed{ \sum_i q_i y_{ik}\le Q_k }. \]

Here $q_i$ is demand at customer $i$, and $y_{ik}$ indicates whether customer $i$ is served by vehicle $k$.

Time Windows

A customer may require service between times $a_i$ and $b_i$:

\[ \boxed{ a_i\le t_i\le b_i }. \]

Time-window routing connects spatial routing with scheduling.

Facility Location

Facility-location models decide where warehouses, hubs, plants, depots, stations, or service centers should be placed.

They balance fixed facility costs against transport, service, capacity, and coverage costs.

Binary Facility Decisions

Let

\[ y_j= \begin{cases} 1,&\text{if facility }j\text{ is opened},\\ 0,&\text{otherwise}. \end{cases} \]

Fixed opening cost $f_j$ contributes

\[ \boxed{ \sum_j f_jy_j } \]

to the objective.

Assignment to Facilities

If customer $i$ is assigned to facility $j$, binary variable $x_{ij}$ may be used. Assignment must be linked to facility opening:

\[ \boxed{ x_{ij}\le y_j }. \]

Customers cannot be assigned to a facility that is not open.

Coverage Models

Emergency services, retail sites, charging stations, and public facilities may be evaluated by whether demand points lie within a required distance or travel time.

Coverage models seek facility locations that maximize covered demand or ensure a minimum service standard.

Hub-and-Spoke Networks

A hub-and-spoke system consolidates flows through selected hub nodes. Airlines, parcel networks, and freight systems often use this structure.

Consolidation can create economies of scale but may increase detours, vulnerability, and transfer delays.

Multimodal Transportation

A shipment may travel by truck, rail, ship, air, pipeline, or several modes in sequence.

A multimodal model can assign different costs, speeds, capacities, emissions, and transfer penalties to each mode and interchange point.

Travel Time

On a link of length $L$ traveled at speed $v$,

\[ \boxed{ t=\frac{L}{v} }. \]

In congested systems, speed may itself depend on traffic flow.

Congestion

Travel time often increases nonlinearly as flow approaches road or facility capacity.

A stylized volume-delay relationship is

\[ \boxed{ t(x) = t_0 \left[ 1+\alpha \left(\frac{x}{C}\right)^\beta \right] }. \]

Here $t_0$ is free-flow travel time and $C$ is a capacity scale.

User Equilibrium

In a stylized traffic-assignment model, travelers select routes until no user can reduce individual travel cost by unilaterally switching routes.

This can differ from the routing pattern that minimizes total system travel time.

System Optimum

A system-optimal traffic model minimizes total network travel cost:

\[ \boxed{ \min \sum_a x_a t_a(x_a) }. \]

Individual route choice and system-wide optimization therefore need not produce the same allocation.

Congestion Externalities

When one additional traveler enters a congested link, that traveler may increase travel time for many others.

This difference between private and system cost is an example of an externality.

Traffic Flow

In macroscopic traffic models, flow $q$, density $k$, and mean speed $v$ are related by

\[ \boxed{ q=kv }. \]

The relationship between speed and density then determines a fundamental diagram for traffic.

Capacity and Critical Density

Traffic flow does not increase indefinitely with density. Beyond a critical density, reduced speed can cause throughput to decline.

This nonlinear relationship is central to traffic congestion and roadway capacity modeling.

Dynamic Traffic Models

Time-dependent traffic models track how flow and density evolve across a road network.

Conservation for density $\rho(x,t)$ may be written

\[ \boxed{ \frac{\partial\rho}{\partial t} + \frac{\partial q}{\partial x} =0 }. \]

A relationship $q=q(\rho)$ closes the model.

Queues in Transportation Systems

Vehicles, freight, aircraft, containers, and passengers can accumulate when arrival rates temporarily exceed service capacity.

Queueing models are therefore natural at toll plazas, terminals, ports, security checkpoints, warehouses, and intersections.

Little's Law in Logistics

Under steady conditions,

\[ \boxed{ L=\lambda W }. \]

Average work-in-process equals throughput times average cycle time.

This relationship connects inventory, process flow, and delay.

Warehousing

Warehouse models may represent receiving, put-away, storage, picking, packing, staging, and shipping as linked processes.

Capacity limits and queueing can occur at each stage.

Cross-Docking

Cross-docking reduces storage by transferring inbound goods directly toward outbound shipments.

Models must coordinate arrival times, dock capacity, sorting, consolidation, and outbound schedules.

Inventory and Transportation Tradeoffs

Faster or more frequent shipments can reduce inventory but increase transport cost.

Larger consolidated shipments can lower transportation cost per unit but increase average inventory and delay.

Logistics optimization must therefore consider the system rather than one cost category in isolation.

Safety Stock Across Networks

Inventory buffers are affected by demand variability, lead-time variability, service targets, and the number and placement of stocking locations.

Consolidating inventory can reduce aggregate safety stock under some demand structures, but may increase transport distance or response time.

Supply Networks

A supply network can include suppliers, plants, warehouses, distribution centers, retailers, and customers connected by material and information flows.

Decisions at one layer can create effects throughout the network.

Lead Times

Total lead time can be decomposed into stages:

\[ \boxed{ L_{\text{total}} = L_{\text{processing}} +L_{\text{waiting}} +L_{\text{transport}} +L_{\text{handling}} }. \]

Reducing only one component may have little effect if another stage dominates.

The Bullwhip Effect

Small changes in downstream demand can create larger fluctuations in upstream orders when forecasting, batching, long lead times, local optimization, or shortage responses amplify variability.

The bullwhip effect is a network feedback phenomenon rather than merely a transportation issue.

Reliability

Logistics performance depends not only on average cost and speed but also on reliability.

A route with slightly higher average travel time may be preferable if its variability and disruption risk are substantially lower.

Network Resilience

Resilience concerns how well a network maintains or restores function after disruption.

Models may test failures of links, facilities, suppliers, ports, bridges, or transportation modes.

Redundancy

Redundant routes and facilities can increase resilience but also increase cost.

The design problem is therefore not simply to maximize redundancy, but to balance resilience with efficiency.

Network Centrality

Centrality measures can identify structurally important nodes or links.

A highly central node may be operationally valuable but may also represent a concentration of failure risk.

Shortest Path Is Not Always Best

The geometrically shortest route may have higher tolls, more congestion, lower reliability, hazardous restrictions, or insufficient capacity.

Multi-criteria routing may therefore use a generalized cost such as

\[ \boxed{ c = w_1(\text{time}) +w_2(\text{money}) +w_3(\text{risk}) +w_4(\text{emissions}) }. \]

Multiobjective Logistics

Real logistics decisions may simultaneously consider

cost;
delivery time;
service reliability;
inventory;
emissions;
risk;
resilience.

Different weightings generate different preferred solutions.

Carbon and Energy Models

Transportation emissions can be modeled using activity and emission factors:

\[ \boxed{ E = \sum_m A_m e_m }. \]

Here $A_m$ is transport activity for mode $m$, and $e_m$ is emissions per unit activity.

Vehicle Energy Use

Energy consumption can depend on vehicle mass, speed, grade, acceleration, aerodynamic drag, rolling resistance, payload, and stop frequency.

Route optimization can therefore include physical vehicle models rather than assuming cost depends only on distance.

Fleet Assignment

A fleet may contain vehicles with different capacities, costs, ranges, fuels, charging requirements, or service capabilities.

Assignment models match vehicle types to routes while respecting operational constraints.

Electric-Vehicle Routing

Electric-vehicle models may include battery state of charge $B_t$:

\[ \boxed{ B_{t+1} =B_t-E_t+C_t }. \]

Here $E_t$ is energy consumed and $C_t$ energy added by charging.

Charging location, charger power, queueing, and route timing can all become part of the optimization.

Air Transportation Networks

Airline models may include aircraft assignment, crew scheduling, gate capacity, passenger connections, maintenance, and network recovery after delay.

Hub structure creates both connection efficiency and vulnerability to delay propagation.

Maritime and Port Networks

Maritime logistics involves sailing schedules, berth capacity, container handling, port queues, transshipment, draft restrictions, and inland connections.

A bottleneck at one port can propagate across a much larger supply network.

Rail Networks

Rail systems require routing together with track capacity, meeting and passing, terminal operations, locomotive assignment, and timetable coordination.

Shared infrastructure makes scheduling constraints especially important.

Pipelines and Continuous Flow

Pipeline networks move liquids or gases continuously rather than as discrete vehicles.

Models may combine network conservation with pressure, friction, pump, and compressor relationships.

Stochastic Demand

Customer orders, travel demand, and shipment volumes are often uncertain.

A stochastic logistics model treats some demand quantities as random variables rather than fixed numbers.

Two-Stage Decisions

Some decisions must be made before uncertainty is observed. Later actions can adapt.

A two-stage stochastic model separates

\[ \boxed{ \text{first-stage decisions} \rightarrow \text{uncertainty realized} \rightarrow \text{recourse decisions} }. \]

Robust Optimization

Robust optimization seeks decisions that remain feasible or effective across a specified uncertainty set.

It can be useful when probabilities are poorly known but credible ranges for demand, travel time, or capacity are available.

Discrete-Event Simulation

Logistics systems often evolve through discrete events such as arrivals, departures, loading, unloading, service completion, failures, and repairs.

Discrete-event simulation can represent complex timing and queue interactions that are difficult to capture analytically.

Simulation versus Optimization

Simulation asks,

\[ \boxed{\text{What happens under this policy?}} \]

Optimization asks,

\[ \boxed{\text{Which feasible policy is best under the objective?}} \]

Large logistics studies often combine the two.

Data Sources

Network models may use data from

GPS and telematics;
shipment records;
warehouse management systems;
traffic sensors;
ticketing systems;
port and terminal records;
customer orders;
roadway and infrastructure databases.

Travel-Time Estimation

Travel times may be estimated statistically from observations. If observed time on arc $a$ is $T_a$, a model may estimate

\[ \boxed{ E[T_a\mid x] =f(x;\theta) } \]

using predictors such as time of day, weather, congestion, incidents, or vehicle class.

Calibration

Calibration adjusts parameters so a network model reproduces selected observed behavior, such as traffic counts, shipment volumes, travel times, queue lengths, or facility throughput.

Good calibration does not guarantee good performance under new conditions.

Validation

Validation asks whether the network model is adequate for its intended use.

A routing model may reproduce average trip length yet fail to predict congestion. A warehouse model may reproduce throughput while understating peak queues. A supply network model may match normal operations yet fail under disruption.

Sensitivity Analysis

Sensitivity analysis can examine how outputs respond to changes in

demand;
capacity;
travel time;
fuel cost;
facility cost;
service-time variability;
lead time;
disruption probability.

Uncertainty Analysis

Important uncertainties include demand variation, travel-time variability, equipment failure, weather, labor availability, border delays, port congestion, supplier reliability, and infrastructure outages.

Decision-grade logistics models should report ranges, probabilities, scenarios, or stress results rather than only a nominal optimum.

Example: Shortest Route

Suppose route $A\rightarrow B\rightarrow D$ has costs

\[ 4+7=11, \]

while route $A\rightarrow C\rightarrow D$ has costs

\[ 6+3=9. \]

The lower-cost route is

\[ \boxed{A\rightarrow C\rightarrow D} \]

with total cost $9$.

Example: Capacity Bottleneck

Suppose a route has three sequential links with capacities

\[ 120,\qquad80,\qquad150 \]

units per hour. Since all flow must pass through every link, route capacity is

\[ \boxed{80\text{ units/hour}}. \]

The $80$-unit link is the bottleneck.

Example: Transportation Cost

Suppose $100$ units are shipped from one origin to a destination at $\$4$ per unit and $60$ units to another at $\$7$ per unit. Total transportation cost is

\[ C=(100)(4)+(60)(7) \] \[ =400+420 \] \[ \boxed{C=\$820}. \]

Example: Little's Law

A distribution process completes $50$ orders per hour, and an order spends an average of $0.40$ hour in the system. Then

\[ L=\lambda W =(50)(0.40) \] \[ \boxed{L=20\text{ orders}}. \]

Example: Basic Vehicle Capacity

A truck has capacity $Q=10{,}000$ kg. Three customers require

\[ 2500,\qquad3200,\qquad2900 \]

kg. Total demand is

\[ 2500+3200+2900=8600\text{ kg}. \]

Therefore, the route is feasible with respect to payload capacity because

\[ \boxed{8600\le10{,}000}. \]

Verification

Verification asks whether the network equations and algorithms have been implemented correctly.

Useful checks include

flow conservation at every node;
capacity compliance;
route connectivity;
unit consistency;
comparison with known small-network solutions;
independent cost recalculation;
simulation convergence and event logic checks.

Common Error: Optimizing Distance Alone

Distance may be only one component of logistics cost. Time, tolls, fuel, service reliability, risk, driver hours, and capacity can materially change the preferred route.

Common Error: Ignoring Flow Conservation

A network solution that sends more flow out of an intermediate node than enters it creates material from nowhere unless the node is explicitly modeled as a source.

Node balance is a fundamental verification check.

Common Error: Ignoring Capacity

A shortest or cheapest route may be infeasible if road, terminal, vehicle, warehouse, or handling capacity is insufficient.

Common Error: Treating Average Travel Time as Deterministic

Average travel time does not capture variability, delay tails, or missed connection risk.

Reliability may matter more than average time for high-service operations.

Common Error: Maximizing Utilization Everywhere

Running every resource near full utilization can create severe congestion and make the system fragile to variability.

Strategic buffer capacity can improve throughput and resilience.

Common Error: Optimizing One Stage in Isolation

Lower transport cost can increase inventory. Higher consolidation can increase delay. Fewer warehouses can reduce fixed cost but increase delivery distance.

Logistics decisions should be evaluated at the system level.

Common Error: Ignoring Disruption

A nominally efficient network may depend on one supplier, bridge, hub, or port. Such concentration may create unacceptable failure risk.

Resilience should be modeled explicitly when continuity matters.

A Reliable Modeling Procedure

Define the transportation or logistics decision.
Identify nodes, links, facilities, vehicles, commodities, and demand points.
Assign costs, capacities, travel times, and service constraints.
Write flow-conservation and supply-demand relationships.
Choose routing, flow, facility-location, scheduling, queueing, or simulation structure.
Add uncertainty in demand, travel time, capacity, or disruption when material.
Verify route connectivity, conservation, capacities, and units.
Calibrate travel-time or service parameters using observed data where needed.
Validate against independent network behavior and peak conditions.
Perform sensitivity, scenario, stress, and resilience analysis before committing resources.

Practice 1: Path Cost

A route contains four links with costs

\[ 3,\qquad5,\qquad2,\qquad6. \]

Find the total route cost.

Practice 2: Bottleneck Capacity

A three-link route has capacities

\[ 100,\qquad70,\qquad90 \]

units per hour. Find the maximum flow the route can carry if every shipment must traverse all three links.

Practice 3: Flow Conservation

A transshipment node receives $40$ units from one incoming arc and $25$ from another. If no material is stored or consumed at the node, how much total flow must leave?

Practice 4: Transportation Cost

A company ships $80$ units on a route costing $\$5$ per unit and $120$ units on a route costing $\$3$ per unit. Find total transportation cost.

Practice 5: Vehicle Capacity

A vehicle can carry $6000$ kg. Customer demands are $1500$, $2200$, and $1800$ kg. Determine whether one trip can serve all three customers by payload capacity alone.

Practice 6: Little's Law

A terminal processes $24$ trucks per hour, and each truck spends an average of $0.5$ hour in the terminal. Find the average number of trucks in the system.

Practice 7: Travel Time

A vehicle travels $180$ km at an average speed of $60$ km/h. Find travel time.

Practice 8: Generalized Cost

A route has travel time $2$ hours and monetary cost $\$30$. If a generalized cost model is

\[ c=20(\text{hours})+\text{dollar cost}, \]

find the generalized cost.

Practice 9: Electric-Vehicle Energy Balance

A vehicle begins with $70$ kWh, uses $22$ kWh on the first leg, charges $15$ kWh, then uses $18$ kWh. Find the ending battery energy.

Practice 10: Choose the Better Model

A company selects its distribution network by minimizing average transportation cost, but one port handles most inbound volume and is subject to frequent disruption. Explain why the nominal cost model is incomplete and identify the additional modeling dimension that should be included.

Practice Answers

Practice 1

\[ C=3+5+2+6 \] \[ \boxed{C=16}. \]

Practice 2

The smallest sequential-link capacity is

\[ \boxed{70\text{ units/hour}}. \]

Practice 3

\[ 40+25=65. \]

Therefore,

\[ \boxed{65\text{ units}} \]

must leave the node.

Practice 4

\[ C=(80)(5)+(120)(3) \] \[ =400+360 \] \[ \boxed{C=\$760}. \]

Practice 5

\[ 1500+2200+1800 =5500\text{ kg}. \]

Since

\[ 5500\le6000, \]

the route is feasible by payload capacity:

\[ \boxed{\text{yes}}. \]

Practice 6

\[ L=\lambda W =(24)(0.5) \] \[ \boxed{L=12\text{ trucks}}. \]

Practice 7

\[ t=\frac{180}{60} \] \[ \boxed{t=3\text{ hours}}. \]

Practice 8

\[ c=20(2)+30 \] \[ \boxed{c=70}. \]

Practice 9

\[ B_{\text{end}} =70-22+15-18 \] \[ \boxed{B_{\text{end}}=45\text{ kWh}}. \]

Practice 10

The model considers normal transportation cost but ignores concentration of disruption risk. It should include network resilience, alternative ports or routes, failure scenarios, recovery time, and the cost of service interruption. A slightly more expensive nominal network may provide substantially better continuity under disruption.

What to Remember

graphs represent transportation and logistics systems through nodes and links;
weights can represent distance, time, cost, risk, or other performance measures;
flow conservation and capacity constraints are foundational network relationships;
shortest-path, maximum-flow, minimum-cost-flow, and transportation models answer different questions;
vehicle routing combines path selection with capacity, timing, and sequencing constraints;
facility-location models balance fixed infrastructure cost against transport and service performance;
congestion makes travel time and delay nonlinear near capacity;
logistics decisions couple transportation, inventory, warehousing, and service levels;
resilience requires modeling disruption, redundancy, and network concentration;
verification, validation, sensitivity, uncertainty, and scenario analysis are required before network models support consequential decisions.

Where We Go Next

Network and logistics models show how connected infrastructure, movement, capacity, and uncertainty interact across space and time. Many of the same modeling tools are needed for environmental systems in which air, water, energy, materials, and geophysical processes move through large spatial networks and fields.

The next lesson, Climate, Environment, and Geoscience, develops models of reservoirs, flows, transport, energy balance, environmental change, spatial fields, uncertainty, and large-scale Earth systems.