Study guide
15.2 Distribution Strategies, Cross-Docking, and Vehicle Routing
FE Industrial and Systems Study Guide Exam
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: Exam Overview, CBT Strategy & Handbook Navigation
1.1 FE Industrial Exam Structure, CBT Logistics, and Pacing 1.2 Using the NCEES FE Reference Handbook and Approved Calculators
2 Chapter 2: Mathematics for Industrial Engineers
2.1 Analytic Geometry, Coordinate Systems, and Trigonometry 2.2 Calculus: Differential, Integral, and Series Approximations 2.3 Linear Algebra: Matrix Operations, Systems of Equations, and Vectors
3 Chapter 3: Engineering Sciences Core
3.1 Thermodynamics Fundamentals and Fluid Flow Principles 3.2 Statics, Dynamics, and Mechanics of Materials Core 3.3 Electrical Circuits, DC/AC Analysis, and Power in Industrial Systems
4 Chapter 4: Ethics and Professional Practice
4.1 NCEES Model Rules of Professional Conduct and Technical Society Ethics 4.2 Engineering Licensure, Public Welfare, and Professional Liability 4.3 Engineering Contracts, Intellectual Property, and Conflicts of Interest
5 Chapter 5: Engineering Economics
5.1 Time Value of Money, Discount Factors, and Equivalence 5.2 Evaluating Alternatives: Present Worth, Equivalent Annual Cost, and IRR 5.3 Incremental Rate of Return, Replacement Analysis, and Break-Even 5.4 Depreciation Methods, MACRS, Income Taxes, and Inflation
6 Chapter 6: Probability Foundations & Distributions
6.1 Basic Probability Concepts, Conditional Probability, and Bayes' Theorem 6.2 Discrete Probability Distributions 6.3 Continuous Probability Distributions
7 Chapter 7: Statistical Inference, Regression & Design of Experiments
7.1 Sampling Distributions, Central Limit Theorem, and Confidence Intervals 7.2 Hypothesis Testing: Means, Proportions, and Variances 7.3 Linear Regression, Correlation Analysis, and Design of Experiments (ANOVA)
8 Chapter 8: Data, Logic, Modeling & Linear Programming
8.1 Optimization Modeling: Decision Variables, Objectives, and Constraints 8.2 Linear Programming: Graphical Solutions and Simplex Fundamentals 8.3 Duality, Sensitivity Analysis, and Integer Linear Programming 8.4 Data, Logic Development, and Analytics
9 Chapter 9: Stochastic Models & Simulation
9.1 Queuing Theory: Little's Law, M/M/1, and Multi-Server Systems 9.2 Discrete-Time Markov Chains: Transition Matrices and Steady-State Probabilities 9.3 Discrete-Event Simulation Principles and Monte Carlo Modeling
10 Chapter 10: Engineering Management, Project Planning & Performance Measurement
10.1 Organizational Structure, Leadership, and Worker Motivation Theories 10.2 Project Management: WBS, Critical Path Method (CPM), PERT, and Crashing 10.3 Earned Value Management (EVM), Decision Trees, and Risk Preference 10.4 Performance Measurement: Productivity, KPIs, Wage Systems, and the Balanced Scorecard
11 Chapter 11: Manufacturing & Production Systems
11.1 Manufacturing Processes, Material Processing, and Tolerancing 11.2 Assembly Line Balancing, Takt Time, Cycle Time, and Throughput 11.3 Sustainable Manufacturing, Waste Minimization, and Life-Cycle Assessment
12 Chapter 12: Production Planning, Inventory Control & Sequencing
12.1 Demand Forecasting Methods and Forecast Error Tracking 12.2 Aggregate Planning, Master Production Scheduling (MPS), and MRP 12.3 Deterministic Inventory Models: EOQ, EPQ, and Safety Stock 12.4 Job Sequencing, Dispatching Rules, and Flow Shop Scheduling
13 Chapter 13: Lean Systems & Theory of Constraints
13.1 Lean Foundations: Value Stream Mapping, Seven Wastes, and 5S 13.2 Pull Systems, Kanban, Just-In-Time (JIT), and SMED Setup Reduction 13.3 Theory of Constraints: Bottleneck Identification and Drum-Buffer-Rope
14 Chapter 14: Facilities Planning & Material Handling
14.1 Facility Location Analysis: Qualitative Factor Rating and Centroid Method 14.2 Facility Layout Design and Flow Analysis 14.3 Material Handling Equipment, Warehousing, and AS/RS
15 Chapter 15: Supply Chain Design & Logistics
15.1 Supply Chain Network Architecture and Transportation Modes 15.2 Distribution Strategies, Cross-Docking, and Vehicle Routing 15.3 The Bullwhip Effect, Risk Pooling, and Supply Chain Coordination
16 Chapter 16: Human Factors & Cognitive Ergonomics
16.1 Cognitive Engineering, Human-Machine Interface, Displays, and Controls 16.2 Anthropometric Principles, Percentile Design, and Biomechanical Posture 16.3 Environmental Ergonomics: Industrial Noise, Lighting, and Heat Stress
17 Chapter 17: Physical Ergonomics & Workplace Safety
17.1 Physical Ergonomics: The NIOSH Manual Lifting Equation 17.2 Cumulative Trauma Disorders and Postural Assessment 17.3 Workplace Safety: OSHA Standards, Hazard Analysis, and Control Hierarchy
18 Chapter 18: Work Design & Measurement
18.1 Methods Engineering, Process Charting, and Principles of Motion Economy 18.2 Direct Stopwatch Time Study: Observed Time, Performance Rating, and Allowances 18.3 Predetermined Time Systems, Work Sampling, and Learning Curves
19 Chapter 19: Quality Management, Six Sigma & Analytical Tools
19.1 Quality Philosophies, Total Quality Management, and Cost of Quality 19.2 Six Sigma DMAIC Methodology and Quality Function Deployment 19.3 The Seven Basic Quality Tools, Root Cause Analysis, and Taguchi Loss Function
20 Chapter 20: Statistical Process Control
20.1 Statistical Process Control Principles, Variation, and Run Rules 20.2 Variable Control Charts: X-bar & R, X-bar & S, and Individual-Moving Range 20.3 Attribute Control Charts: Defectives (p, np) and Defects (c, u)
21 Chapter 21: Process Capability & Acceptance Sampling
21.1 Process Capability Indices and Defect Levels 21.2 Acceptance Sampling Concepts and Operating Characteristic Curves 21.3 Sampling Risks, AQL, LTPD, and Standard Sampling Plans
22 Chapter 22: Systems Engineering & Life-Cycle Management
22.1 The Systems Engineering V-Model, Stakeholder Requirements, and Functional Architecture 22.2 Configuration Management, Interface Control, and Verification & Validation 22.3 Life-Cycle Costing, Maintainability, and System Availability
23 Chapter 23: Reliability Engineering & Risk Analysis
23.1 Reliability Mathematics, Hazard Rates, and the Bathtub Curve 23.2 System Reliability Configurations: Series, Parallel, and k-out-of-n Systems 23.3 Failure Modes and Effects Analysis and Fault Tree Analysis
15.2 Distribution Strategies, Cross-Docking, and Vehicle Routing
Key Takeaways Explain This Topic AI
Direct shipping bypasses intermediate distribution facilities to minimize handling touches and warehousing capital, whereas milk runs combine multiple pickups or drop-offs onto a consolidated linehaul.
Cross-docking transfers inbound freight directly to outbound trailers in under 24 hours, eliminating put-away storage, rack infrastructure, and order-picking labor.
Successful cross-docking operations depend strictly on electronic data interchange (EDI 856 Advanced Shipping Notices), standardized barcoding/RFID, and time-slotted dock door appointments.
The Traveling Salesperson Problem (TSP) models single-vehicle closed-loop routing, solved heuristically by the greedy Nearest Neighbor method, which selects the closest unvisited node at each step.
The Clarke-Wright savings method solves multi-vehicle routing problems (VRP) by iteratively merging dedicated out-and-back radial trips based on maximum distance savings: s ( i , j ) = c ( 0 , i ) + c ( 0 , j ) − c ( i , j ) s(i, j) = c(0, i) + c(0, j) - c(i, j) s ( i , j ) = c ( 0 , i ) + c ( 0 , j ) − c ( i , j ) subject to vehicle capacity constraints.
Last updated: September 2026
Distribution management focuses on the tactical and operational execution of moving finished goods from manufacturing plants and distribution hubs to retail shelves or customer doorsteps. Industrial engineers select distribution strategies to minimize handling touches, maximize freight fill rates, and establish optimal vehicle delivery routes. Advanced techniques such as cross-docking and mathematical vehicle routing algorithms directly determine the velocity, cost, and reliability of the logistics network.
1. Distribution Network Strategies and Topologies
The configuration of physical distribution channels dictates how inventory is positioned and how transport is scheduled. Core Distribution Network Topologies
- (a) Direct Shipping (b) Direct Shipping with Milk Runs
- [Plant] [Plant]
- ┌──┴──┐ ┌──┴────────────────┐
- ▼ ▼ ▼ ▼
- [R1] [R2] [Stop 1] ──> [Stop 2] ──> [Stop 3]
- (c) Intermediate DC with Storage (d) Cross-Docking Facility
- [Plants A, B, C] [Suppliers A, B, C]
- │ │ (Inbound Staging)
- ▼ ▼
- [Storage DC] [Cross-Dock Hub] (Dwell < 24 hrs, No Storage)
- (Pallet Racks, Picking) │ (Sortation & Direct Transfer)
- │ ▼
- ▼ [Outbound Retail Trailers]
- [Retail Stores] [Stores 1, 2, 3]
- Comparison of Distribution Strategies
Network Design Structural Characteristics Major Cost Advantages Primary Operational Limitations
Direct Shipping Shipments move directly from plant to retail customer without entering any intermediate warehouse. Eliminates intermediate warehouse leasing, zero handling touches, reduces pipeline transit time. Requires large order quantities (Full Truckloads); small orders incur prohibitive LTL freight costs; high destination inventory.
Direct Shipping with Milk Runs A dedicated vehicle visits multiple suppliers to consolidate parts for one plant, or delivers from one plant to multiple retailers along a single circuit. Consolidates small LTL orders into a single full truckload; eliminates intermediate DC handling; predictable delivery schedules. High routing complexity; delays at one stop ripple throughout subsequent deliveries; requires geographically clustered nodes.
Intermediate DC with Storage Suppliers ship bulk full truckloads to a central warehouse; inventory is slotted into racks; orders are picked, packed, and shipped. High safety stock buffer against demand spikes; supplier lead times are decoupled from customer order lead times; break-bulk efficiency. High capital investment in storage racking and automated picking systems; high inventory carrying costs; double material handling.
Cross-Docking Inbound shipments are unloaded, sorted by outbound store destination, and loaded directly into outbound trailers with zero long-term storage. Eliminates put-away, storage, and picking labor (~60% of warehouse operational cost); drastically accelerates inventory turnover. Demands rigorous EDI synchronization, strict carrier dock appointment compliance, automated sortation systems, and zero-defect packaging.
2. Cross-Docking Operations and Architectural Requirements
Cross-docking is a logistics technique where freight is transferred directly from inbound receiving trailers to outbound delivery trailers with minimal or zero intermediate storage dwell time (typically under 24 hours , and virtually never exceeding 48 hours). Cross-Dock Facility Material Flow (I-Shape Terminal Layout)
- Inbound Dock Doors (Receiving Side)
- ▼ ▼ ▼ ▼ ▼
- ┌───────────────────────────────────────────────────┐
- │ [ Inbound Staging & Deconsolidation ] │
- │ │ │
- │ ▼ │
- │ [ Automated Barcode / RFID Sortation Conveyor ] │
- │ │ │
- │ ▼ │
- │ [ Outbound Staging & Direct Trailer Loading ] │
- └───────────────────────────────────────────────────┘
- ▲ ▲ ▲ ▲ ▲
- Outbound Dock Doors (Shipping Side)
- Operational Configurations: Pre-Distribution vs. Post-Distribution
Pre-Distribution Cross-Docking : The supplier pre-sorts, packs, and labels individual cartons or pallets with the ultimate retail store destination before the shipment leaves the factory. The cross-dock personnel or sortation conveyors simply read the destination barcode and route the container directly to the corresponding outbound trailer.
Post-Distribution Cross-Docking : The supplier ships bulk pallets of single SKUs to the cross-dock. Upon arrival, the facility's Warehouse Management System (WMS) dynamically allocates the palletized goods to open store orders, cross-dock operators break down pallets, and cartons are sorted and labeled for outbound delivery trailers.
Critical Technical Requirements for Cross-Docking
Electronic Data Interchange (EDI 856 / ASN) : Inbound trailers must transmit an Advanced Shipping Notice (ASN) prior to arrival, itemizing pallet and carton contents down to the serial shipping container code (SSCC).
Automated Identification : Every container must carry a standardized machine-readable identifier (GS1-128 barcode or EPC RFID tag) to enable high-speed overhead scanning on sortation conveyors.
Synchronized Carrier Dock Scheduling : Inbound delivery windows and outbound linehaul departures must be tightly synchronized. If an inbound trailer is 2 hours late, downstream outbound trucks face departure delays or move partially empty.
Facility Architectural Layout : Modern cross-dock terminals utilize an elongated I-shape rectangular footprint . Mathematically, an I-shape minimizes the average travel distance between inbound dock doors on one side and outbound dock doors on the opposing side. For massive terminals with more than 150–200 dock doors, T-shaped or X-shaped footprints are deployed to prevent forklift congestion.
Economic Advantages
Traditional warehousing allocates 55% to 65% of its operating budget to put-away, storage replenishment, and manual order picking . Cross-docking bypasses all three functions, driving warehouse handling costs down to basic unloading, sorting, and direct loading.
3. Network Routing: The Traveling Salesperson Problem (TSP)
When a single vehicle must visit a set of geographically dispersed customer locations and return to its home depot, the routing optimization is modeled as a Traveling Salesperson Problem (TSP) .
Mathematical Formulation
Given a set of nodes V = { 0 , 1 , 2 , … , n } V = \{0, 1, 2, \dots, n\} V = { 0 , 1 , 2 , … , n } , where Node 0 is the central depot and nodes { 1 , … , n } \{1, \dots, n\} { 1 , … , n } represent customer stops, with travel cost/distance c i j c_{ij} c ij between nodes i i i and j j j : min ∑ i = 0 n ∑ j = 0 n c i j x i j \min \sum_{i=0}^n \sum_{j=0}^n c_{ij} x_{ij} min i = 0 ∑ n j = 0 ∑ n c ij x ij Subject to: ∑ j = 0 , j ≠ i n x i j = 1 ∀ i ∈ V (Leave each node exactly once) \text{Subject to: } \sum_{j=0, j \ne i}^n x_{ij} = 1 \quad \forall i \in V \quad \text{(Leave each node exactly once)} Subject to: j = 0 , j = i ∑ n x ij = 1 ∀ i ∈ V (Leave each node exactly once) ∑ i = 0 , i ≠ j n x i j = 1 ∀ j ∈ V (Enter each node exactly once) \sum_{i=0, i \ne j}^n x_{ij} = 1 \quad \forall j \in V \quad \text{(Enter each node exactly once)} i = 0 , i = j ∑ n x ij = 1 ∀ j ∈ V (Enter each node exactly once) ν i − u j + n x i j ≤ n − 1 ∀ 1 ≤ i ≠ j ≤ n (Subtour Elimination Constraints) \nu_i - u_j + n x_{ij} \le n - 1 \quad \forall 1 \le i \ne j \le n \quad \text{(Subtour Elimination Constraints)} ν i − u j + n x ij ≤ n − 1 ∀1 ≤ i = j ≤ n (Subtour Elimination Constraints) x i j ∈ { 0 , 1 } , u i ≥ 0 x_{ij} \in \{0, 1\}, \quad u_i \ge 0 x ij ∈ { 0 , 1 } , u i ≥ 0
The Miller-Tucker-Zemlin (MTZ) subtour elimination constraints prevent the formation of isolated cycles that do not pass through the central depot.
Complexity : The TSP is NP-hard. An exact exhaustive search requires evaluating ( n − 1 ) ! 2 \frac{(n-1)!}{2} 2 ( n − 1 )! possible tours for a symmetric network, making heuristic approaches mandatory for practical engineering.
The Nearest Neighbor (NN) Heuristic
The Nearest Neighbor method is a greedy construction heuristic:
Start at the central depot (Node 0).
Identify the unvisited customer node closest to the current location.
Travel to that node, add it to the tour, and flag it as visited.
Repeat Steps 2 and 3 until all n n n customer nodes have been visited.
Travel from the final customer node directly back to the central depot.
Limitation : Because NN makes locally greedy choices early in the tour, it frequently leaves isolated, distant nodes for the final steps, forcing a catastrophic and expensive final return leg.
4. The Capacitated Vehicle Routing Problem (CVRP) and Clarke-Wright Savings Method
When a fleet of vehicles with finite payload capacities ( Q Q Q ) must serve customer demands ( d i d_i d i ) from a central depot, the problem expands into the Capacitated Vehicle Routing Problem (CVRP) .
Clarke-Wright Savings Algorithm Derivation
Developed by Geoff Clarke and John Wright, this heuristic constructs multi-stop vehicle routes by iteratively merging radial round-trips based on distance savings. Clarke-Wright Savings Concept
Baseline: Separate Radial Routes (Total = 2*c(0,i) + 2*c(0,j)) Merged Route: Single Tour (Total = c(0,i) + c(i,j) + c(j,0))
- [Depot 0] [Depot 0]
- ╱ ▲ ╲ ▲ ╱ ▲
- ╱ ╱ ╲ ╲ ╱ ╲
- ▼ ╱ ▼ ╲ ▼ ╲
- [Cust i] [Cust j] [Cust i] ──────> [Cust j]
Baseline Inefficient Solution : Each customer i i i is served by an independent out-and-back radial round trip from the depot (Node 0): Distance for Customer i = c ( 0 , i ) + c ( i , 0 ) = 2 c ( 0 , i ) \text{Distance for Customer } i = c(0, i) + c(i, 0) = 2 c(0, i) Distance for Customer i = c ( 0 , i ) + c ( i , 0 ) = 2 c ( 0 , i ) Total Baseline Distance = ∑ i = 1 n 2 c ( 0 , i ) \text{Total Baseline Distance} = \sum_{i=1}^n 2 c(0, i) Total Baseline Distance = i = 1 ∑ n 2 c ( 0 , i )
Merged Route : If customer i i i and customer j j j are combined onto a single vehicle route ( 0 → i → j → 0 0 \to i \to j \to 0 0 → i → j → 0 ): Merged Distance = c ( 0 , i ) + c ( i , j ) + c ( j , 0 ) \text{Merged Distance} = c(0, i) + c(i, j) + c(j, 0) Merged Distance = c ( 0 , i ) + c ( i , j ) + c ( j , 0 )
Savings Formulation : The distance saved ( s ( i , j ) s(i, j) s ( i , j ) ) by linking customer i i i and customer j j j directly rather than returning to the depot between stops is: s ( i , j ) = [ 2 c ( 0 , i ) + 2 c ( 0 , j ) ] − [ c ( 0 , i ) + c ( i , j ) + c ( j , 0 ) ] s(i, j) = [2 c(0, i) + 2 c(0, j)] - [c(0, i) + c(i, j) + c(j, 0)] s ( i , j ) = [ 2 c ( 0 , i ) + 2 c ( 0 , j )] − [ c ( 0 , i ) + c ( i , j ) + c ( j , 0 )] s ( i , j ) = c ( 0 , i ) + c ( 0 , j ) − c ( i , j ) s(i, j) = c(0, i) + c(0, j) - c(i, j) s ( i , j ) = c ( 0 , i ) + c ( 0 , j ) − c ( i , j )
Algorithmic Execution Steps
Calculate the savings s ( i , j ) = c ( 0 , i ) + c ( 0 , j ) − c ( i , j ) s(i, j) = c(0, i) + c(0, j) - c(i, j) s ( i , j ) = c ( 0 , i ) + c ( 0 , j ) − c ( i , j ) for all distinct pairs of customers i i i and j j j ( i ≠ j i \ne j i = j ).
Rank all candidate pairs ( i , j ) (i, j) ( i , j ) in strictly descending order of savings.
Starting from the top of the savings list, merge customer i i i and customer j j j onto a common route provided:
Both i i i and j j j are currently adjacent to the depot (neither node is already interior to an established multi-stop route).
Customers i i i and j j j do not already belong to the same route (prevents forming closed loops that bypass the depot).
The sum of customer demands on the proposed merged route does not exceed vehicle capacity Q Q Q : ∑ k ∈ Route d k ≤ Q \sum_{k \in \text{Route}} d_k \le Q k ∈ Route ∑ d k ≤ Q
Repeat Step 3 until the savings list is exhausted or no further feasible capacity merges exist.
5. Freight Consolidation Economics
Freight consolidation combines multiple small consignments destined for a common geographic zone into a single high-volume linehaul transport.
Break-Bulk Terminal Mechanics
Inbound Gathering : Local pickup trucks gather small LTL shipments from multiple regional manufacturing plants and bring them to an origination break-bulk terminal.
Consolidation : Shipments sharing a distant regional destination are loaded into a single 53-ft trailer to achieve a high weight/cube utilization (approaching 45 , 000 lbs 45,000\text{ lbs} 45 , 000 lbs ).
Linehaul : The trailer executes a long-distance linehaul under full truckload economics.
Break-Bulk Sort & Delivery : At the destination break-bulk hub, the trailer is unloaded, and freight is distributed among local delivery trucks for final delivery.
Freight Tariff Structures and the Weight-Bumping Rule
Motor freight carriers publish sliding-scale tariff rates per hundredweight ( / c w t /cwt / c wt ). As shipment weight crosses defined weight brackets, the rate per hundredweight decreases: Standard LTL Weight Brackets: L5C (< 500 lbs) --> M5C (500-999 lbs) --> M1M (1,000-1,999 lbs)
--> M2M (2,000-4,999 lbs) --> M5M (5,000-9,999 lbs) --> TL (Truckload)
The Bumping / Phantom Weight Rule : Carriers permit shippers to "bump" a shipment's billed weight to the minimum weight of the next higher bracket if doing so produces a lower total freight charge: Billed Charge = min ( W actual × R current , W bracket, min × R higher ) \text{Billed Charge} = \min\left(W_{\text{actual}} \times R_{\text{current}}, \; W_{\text{bracket, min}} \times R_{\text{higher}}\right) Billed Charge = min ( W actual × R current , W bracket, min × R higher )
- 6. Step-by-Step Worked Engineering Calculations
- Worked Example 15.2.1: Nearest Neighbor Heuristic for TSP
Problem : A distributor must route a delivery van from its central depot (Node 0) to four customer retail locations (Nodes 1, 2, 3, and 4) and return to the depot. The symmetric travel distance matrix (in miles) is provided below.
- Nodes 0 (Depot) 1 2 3 4
- 0 — 12 25 18 30
- 1 12 — 15 22 28
- 2 25 15 — 10 14
- 3 18 22 10 — 16
- 4 30 28 14 16 —
Construct the complete delivery tour using the greedy Nearest Neighbor heuristic starting at Depot 0.
Compute the total traveled mileage of the Nearest Neighbor tour.
Compare this result with an alternative sequence 0 → 3 → 2 → 4 → 1 → 0 0 \to 3 \to 2 \to 4 \to 1 \to 0 0 → 3 → 2 → 4 → 1 → 0 to assess optimality.
Solution :
Step 1: Execute Nearest Neighbor Step-by-Step
Start at Node 0 :
Distances to unvisited nodes: c ( 0 , 1 ) = 12 c(0, 1) = 12 c ( 0 , 1 ) = 12 , c ( 0 , 2 ) = 25 c(0, 2) = 25 c ( 0 , 2 ) = 25 , c ( 0 , 3 ) = 18 c(0, 3) = 18 c ( 0 , 3 ) = 18 , c ( 0 , 4 ) = 30 c(0, 4) = 30 c ( 0 , 4 ) = 30 .
Minimum distance is c ( 0 , 1 ) = 12 c(0, 1) = 12 c ( 0 , 1 ) = 12 . Move to Node 1 .
Visited : { 0 , 1 } \{0, 1\} { 0 , 1 } . Current path: 0 → 1 0 \to 1 0 → 1 .
From Node 1 :
Distances to unvisited nodes: c ( 1 , 2 ) = 15 c(1, 2) = 15 c ( 1 , 2 ) = 15 , c ( 1 , 3 ) = 22 c(1, 3) = 22 c ( 1 , 3 ) = 22 , c ( 1 , 4 ) = 28 c(1, 4) = 28 c ( 1 , 4 ) = 28 .
Minimum distance is c ( 1 , 2 ) = 15 c(1, 2) = 15 c ( 1 , 2 ) = 15 . Move to Node 2 .
Visited : { 0 , 1 , 2 } \{0, 1, 2\} { 0 , 1 , 2 } . Current path: 0 → 1 → 2 0 \to 1 \to 2 0 → 1 → 2 .
From Node 2 :
Distances to unvisited nodes: c ( 2 , 3 ) = 10 c(2, 3) = 10 c ( 2 , 3 ) = 10 , c ( 2 , 4 ) = 14 c(2, 4) = 14 c ( 2 , 4 ) = 14 .
Minimum distance is c ( 2 , 3 ) = 10 c(2, 3) = 10 c ( 2 , 3 ) = 10 . Move to Node 3 .
Visited : { 0 , 1 , 2 , 3 } \{0, 1, 2, 3\} { 0 , 1 , 2 , 3 } . Current path: 0 → 1 → 2 → 3 0 \to 1 \to 2 \to 3 0 → 1 → 2 → 3 .
From Node 3 :
Only unvisited node remaining is Node 4. c ( 3 , 4 ) = 16 c(3, 4) = 16 c ( 3 , 4 ) = 16 . Move to Node 4 .
Visited : { 0 , 1 , 2 , 3 , 4 } \{0, 1, 2, 3, 4\} { 0 , 1 , 2 , 3 , 4 } . Current path: 0 → 1 → 2 → 3 → 4 0 \to 1 \to 2 \to 3 \to 4 0 → 1 → 2 → 3 → 4 .
Return to Depot :
Travel from Node 4 back to Node 0. c ( 4 , 0 ) = 30 c(4, 0) = 30 c ( 4 , 0 ) = 30 .
Final Nearest Neighbor Tour : 0 → 1 → 2 → 3 → 4 → 0 0 \to 1 \to 2 \to 3 \to 4 \to 0 0 → 1 → 2 → 3 → 4 → 0 .
Step 2: Calculate Total Mileage Total Distance = c ( 0 , 1 ) + c ( 1 , 2 ) + c ( 2 , 3 ) + c ( 3 , 4 ) + c ( 4 , 0 ) \text{Total Distance} = c(0, 1) + c(1, 2) + c(2, 3) + c(3, 4) + c(4, 0) Total Distance = c ( 0 , 1 ) + c ( 1 , 2 ) + c ( 2 , 3 ) + c ( 3 , 4 ) + c ( 4 , 0 ) Total Distance = 12 + 15 + 10 + 16 + 30 = 83 miles \text{Total Distance} = 12 + 15 + 10 + 16 + 30 = 83\text{ miles} Total Distance = 12 + 15 + 10 + 16 + 30 = 83 miles
Step 3: Evaluate Alternative Tour ( 0 → 3 → 2 → 4 → 1 → 0 0 \to 3 \to 2 \to 4 \to 1 \to 0 0 → 3 → 2 → 4 → 1 → 0 ) Alternative Distance = c ( 0 , 3 ) + c ( 3 , 2 ) + c ( 2 , 4 ) + c ( 4 , 1 ) + c ( 1 , 0 ) \text{Alternative Distance} = c(0, 3) + c(3, 2) + c(2, 4) + c(4, 1) + c(1, 0) Alternative Distance = c ( 0 , 3 ) + c ( 3 , 2 ) + c ( 2 , 4 ) + c ( 4 , 1 ) + c ( 1 , 0 ) Alternative Distance = 18 + 10 + 14 + 28 + 12 = 82 miles \text{Alternative Distance} = 18 + 10 + 14 + 28 + 12 = 82\text{ miles} Alternative Distance = 18 + 10 + 14 + 28 + 12 = 82 miles
Engineering Takeaway : The alternative tour ( 82 miles 82\text{ miles} 82 miles ) is shorter than the Nearest Neighbor tour ( 83 miles 83\text{ miles} 83 miles ). This demonstrates that the greedy Nearest Neighbor heuristic is not guaranteed to find the global optimum because it was forced to make an expensive 30-mile final return leg ( 4 → 0 4 \to 0 4 → 0 ).
Worked Example 15.2.2: Clarke-Wright Savings Method for CVRP
Problem : A regional parts depot (Node 0) operates delivery trucks with a payload capacity of Q = 1 , 000 lbs Q = 1,000\text{ lbs} Q = 1 , 000 lbs . Three commercial repair shops must be serviced:
- Customer 1: Demand d 1 = 400 lbs d_1 = 400\text{ lbs} d 1 = 400 lbs
- Customer 2: Demand d 2 = 500 lbs d_2 = 500\text{ lbs} d 2 = 500 lbs
- Customer 3: Demand d 3 = 350 lbs d_3 = 350\text{ lbs} d 3 = 350 lbs
The travel distances (in miles) from the depot and between customers are:
Depot distances: c ( 0 , 1 ) = 20 c(0, 1) = 20 c ( 0 , 1 ) = 20 , c ( 0 , 2 ) = 30 c(0, 2) = 30 c ( 0 , 2 ) = 30 , c ( 0 , 3 ) = 25 c(0, 3) = 25 c ( 0 , 3 ) = 25
Inter-customer distances: c ( 1 , 2 ) = 22 c(1, 2) = 22 c ( 1 , 2 ) = 22 , c ( 1 , 3 ) = 28 c(1, 3) = 28 c ( 1 , 3 ) = 28 , c ( 2 , 3 ) = 32 c(2, 3) = 32 c ( 2 , 3 ) = 32
Calculate the baseline total mileage if every customer is served by an independent out-and-back radial trip.
Compute the Clarke-Wright savings value s ( i , j ) s(i, j) s ( i , j ) for all pairs.
Determine the final vehicle routes and verify capacity feasibility.
Compute the final total system mileage and net miles saved.
Solution :
Step 1: Baseline Radial Solution Baseline Distance = 2 c ( 0 , 1 ) + 2 c ( 0 , 2 ) + 2 c ( 0 , 3 ) = 2 ( 20 ) + 2 ( 30 ) + 2 ( 25 ) = 40 + 60 + 50 = 150 miles \text{Baseline Distance} = 2 c(0, 1) + 2 c(0, 2) + 2 c(0, 3) = 2(20) + 2(30) + 2(25) = 40 + 60 + 50 = 150\text{ miles} Baseline Distance = 2 c ( 0 , 1 ) + 2 c ( 0 , 2 ) + 2 c ( 0 , 3 ) = 2 ( 20 ) + 2 ( 30 ) + 2 ( 25 ) = 40 + 60 + 50 = 150 miles
Step 2: Compute Pairwise Savings Using s ( i , j ) = c ( 0 , i ) + c ( 0 , j ) − c ( i , j ) s(i, j) = c(0, i) + c(0, j) - c(i, j) s ( i , j ) = c ( 0 , i ) + c ( 0 , j ) − c ( i , j )
Pair (1, 2): s ( 1 , 2 ) = c ( 0 , 1 ) + c ( 0 , 2 ) − c ( 1 , 2 ) = 20 + 30 − 22 = 28 miles s(1, 2) = c(0, 1) + c(0, 2) - c(1, 2) = 20 + 30 - 22 = 28\text{ miles} s ( 1 , 2 ) = c ( 0 , 1 ) + c ( 0 , 2 ) − c ( 1 , 2 ) = 20 + 30 − 22 = 28 miles
Pair (2, 3): s ( 2 , 3 ) = c ( 0 , 2 ) + c ( 0 , 3 ) − c ( 2 , 3 ) = 30 + 25 − 32 = 23 miles s(2, 3) = c(0, 2) + c(0, 3) - c(2, 3) = 30 + 25 - 32 = 23\text{ miles} s ( 2 , 3 ) = c ( 0 , 2 ) + c ( 0 , 3 ) − c ( 2 , 3 ) = 30 + 25 − 32 = 23 miles
Pair (1, 3): s ( 1 , 3 ) = c ( 0 , 1 ) + c ( 0 , 3 ) − c ( 1 , 3 ) = 20 + 25 − 28 = 17 miles s(1, 3) = c(0, 1) + c(0, 3) - c(1, 3) = 20 + 25 - 28 = 17\text{ miles} s ( 1 , 3 ) = c ( 0 , 1 ) + c ( 0 , 3 ) − c ( 1 , 3 ) = 20 + 25 − 28 = 17 miles
Ranked Savings Table :
- Pair (1, 2): s ( 1 , 2 ) = 28 miles s(1, 2) = 28\text{ miles} s ( 1 , 2 ) = 28 miles
- Pair (2, 3): s ( 2 , 3 ) = 23 miles s(2, 3) = 23\text{ miles} s ( 2 , 3 ) = 23 miles
- Pair (1, 3): s ( 1 , 3 ) = 17 miles s(1, 3) = 17\text{ miles} s ( 1 , 3 ) = 17 miles
- Step 3: Route Merging with Capacity Verification
Evaluate Rank 1 (Pair 1, 2) :
Combined demand: d 1 + d 2 = 400 + 500 = 900 lbs d_1 + d_2 = 400 + 500 = 900\text{ lbs} d 1 + d 2 = 400 + 500 = 900 lbs .
Capacity check: 900 lbs ≤ Q = 1 , 000 lbs 900\text{ lbs} \le Q = 1,000\text{ lbs} 900 lbs ≤ Q = 1 , 000 lbs . Feasible!
Form Route 1: 0 → 1 → 2 → 0 0 \to 1 \to 2 \to 0 0 → 1 → 2 → 0 (or 0 → 2 → 1 → 0 0 \to 2 \to 1 \to 0 0 → 2 → 1 → 0 ). Nodes 1 and 2 are now linked.
Evaluate Rank 2 (Pair 2, 3) :
Node 2 is already linked to Node 1. Merging Node 3 with Node 2 creates a multi-stop route 0 → 1 → 2 → 3 → 0 0 \to 1 \to 2 \to 3 \to 0 0 → 1 → 2 → 3 → 0 .
Combined demand: d 1 + d 2 + d 3 = 400 + 500 + 350 = 1 , 250 lbs d_1 + d_2 + d_3 = 400 + 500 + 350 = 1,250\text{ lbs} d 1 + d 2 + d 3 = 400 + 500 + 350 = 1 , 250 lbs .
Capacity check: 1 , 250 lbs > Q = 1 , 000 lbs 1,250\text{ lbs} > Q = 1,000\text{ lbs} 1 , 250 lbs > Q = 1 , 000 lbs . Infeasible! Vehicle capacity violated; reject this merge.
Evaluate Rank 3 (Pair 1, 3) :
Merging Node 3 with Node 1 also requires serving all three customers on one vehicle ( 1 , 250 lbs > 1 , 000 lbs 1,250\text{ lbs} > 1,000\text{ lbs} 1 , 250 lbs > 1 , 000 lbs ). Infeasible! Reject.
Node 3 must remain on its own dedicated radial route: 0 → 3 → 0 0 \to 3 \to 0 0 → 3 → 0 .
Step 4: Final Routing Solution and Net Mileage
Route 1 : 0 → 1 → 2 → 0 0 \to 1 \to 2 \to 0 0 → 1 → 2 → 0 Distance 1 = c ( 0 , 1 ) + c ( 1 , 2 ) + c ( 2 , 0 ) = 20 + 22 + 30 = 72 miles \text{Distance}_1 = c(0, 1) + c(1, 2) + c(2, 0) = 20 + 22 + 30 = 72\text{ miles} Distance 1 = c ( 0 , 1 ) + c ( 1 , 2 ) + c ( 2 , 0 ) = 20 + 22 + 30 = 72 miles Payload 1 = 400 + 500 = 900 lbs ( 90 % capacity utilization ) \text{Payload}_1 = 400 + 500 = 900\text{ lbs} \quad (90\%\text{ capacity utilization}) Payload 1 = 400 + 500 = 900 lbs ( 90% capacity utilization )
Route 2 : 0 → 3 → 0 0 \to 3 \to 0 0 → 3 → 0 Distance 2 = 2 c ( 0 , 3 ) = 2 × 25 = 50 miles \text{Distance}_2 = 2 c(0, 3) = 2 \times 25 = 50\text{ miles} Distance 2 = 2 c ( 0 , 3 ) = 2 × 25 = 50 miles Payload 2 = 350 lbs \text{Payload}_2 = 350\text{ lbs} Payload 2 = 350 lbs
Total System Mileage : Total Miles = 72 + 50 = 122 miles \text{Total Miles} = 72 + 50 = 122\text{ miles} Total Miles = 72 + 50 = 122 miles
Net Savings : Savings = Baseline − Total = 150 − 122 = 28 miles \text{Savings} = \text{Baseline} - \text{Total} = 150 - 122 = 28\text{ miles} Savings = Baseline − Total = 150 − 122 = 28 miles (Note: Net savings exactly matches s ( 1 , 2 ) = 28 miles s(1, 2) = 28\text{ miles} s ( 1 , 2 ) = 28 miles ).
7. NCEES Reference Handbook Tips & Realistic Exam Traps
The Clarke-Wright Savings Formula Trap : The formula is s ( i , j ) = c ( 0 , i ) + c ( 0 , j ) − c ( i , j ) s(i, j) = c(0, i) + c(0, j) - c(i, j) s ( i , j ) = c ( 0 , i ) + c ( 0 , j ) − c ( i , j ) . A common exam blunder is adding the inter-customer distance ( c ( 0 , i ) + c ( 0 , j ) + c ( i , j ) c(0, i) + c(0, j) + c(i, j) c ( 0 , i ) + c ( 0 , j ) + c ( i , j ) ) or forgetting that the savings represents what is eliminated when returning to the depot is bypassed.
Capacity Constraint Violations : In any CVRP problem, always verify cumulative demand before executing a merge. FE questions frequently present a customer pair with the highest mathematical savings that exceeds the truck payload limit. If capacity is exceeded, the merge is invalid and must be skipped.
Subtour Traps in Heuristic Merges : In Clarke-Wright, you can only link customer i i i and customer j j j if both nodes are currently directly connected to the depot. If customer i i i is already an interior stop on an existing route (e.g., 0 → k → i → m → 0 0 \to k \to i \to m \to 0 0 → k → i → m → 0 ), customer i i i cannot be linked to customer j j j without disconnecting an existing customer.
Cross-Docking Dwell Time Definition : On the exam, if a question describes a distribution center where inventory is stored in multi-level pallet racks for several weeks before being picked to fulfill retail orders, that facility is a traditional warehouse , NOT a cross-dock. Cross-docking involves minimal dwell (< 24 hours) and zero rack storage.