Foundations of Route Planning and Scheduling

Introduction and context

Route planning and scheduling determine how transportation resources move products, people, or service personnel through a network. Route planning primarily addresses where a vehicle should travel and in what sequence. Scheduling addresses when activities should occur, including departure, arrival, loading, unloading, service, and return times. In practice, the two decisions are interdependent: a route that is geographically attractive may be infeasible because of time windows, driver regulations, congestion, or vehicle capacity.

Within supply chain management, routing and scheduling connect procurement, inventory, warehousing, customer service, sustainability, and financial performance. A distribution centre may have sufficient inventory and warehouse capacity, yet still fail customers if delivery routes are poorly designed. Conversely, minimizing kilometres alone may produce late deliveries, excessive overtime, poor asset utilization, or unacceptable environmental impacts.

The central managerial challenge is therefore not simply to find the shortest route. It is to design a feasible and economically appropriate transportation plan that balances cost, service, risk, resilience, and strategic objectives.

Learning objectives

After studying this chapter, the reader should be able to:

1. Define the principal terminology used in route planning and scheduling.
2. Distinguish strategic, tactical, and operational routing decisions.
3. Explain planning horizons and the relationship between long-term network design and daily dispatching.
4. Interpret transportation economics, including fixed, variable, time-based, and service-related costs.
5. Relate customer service requirements to route and schedule feasibility.
6. Identify major routing problem classes and their managerial implications.
7. Evaluate technology, sustainability, governance, and implementation issues.
8. Apply foundational concepts to a realistic distribution problem.

1. Core terminology

A transportation network consists of nodes and arcs. Nodes may include suppliers, factories, distribution centres, cross-docks, stores, customers, ports, and vehicle depots. Arcs represent roads, rail links, waterways, air corridors, or other connections. A network may be directed, meaning that travel conditions differ by direction, or undirected when movement is assumed to be equivalent in both directions.

A depot is a location from which vehicles depart and to which they may return. A customer stop is a location requiring delivery, pickup, service, or both. A tour is the sequence of stops assigned to one vehicle during a planning period. A route may refer either to that sequence or to the physical path connecting successive stops; analysts should define the term precisely because the two meanings are not identical.

A visit is a vehicle’s service at a customer. Service time is the time spent loading, unloading, installing, collecting, or otherwise serving the customer. Travel time is the time spent moving between locations. Dwell time includes non-moving time at a location and may include waiting, inspection, paperwork, and service.

A time window is an interval during which service must begin or be completed. For a customer with an earliest service time of 09:00 and a latest service time of 11:00, arrival before 09:00 may require waiting, while arrival after 11:00 may violate the requirement. A hard time window prohibits violation; a soft time window permits violation but applies a penalty or reduces service quality.

A vehicle routing problem (VRP) assigns customers to vehicles and determines visit sequences subject to constraints. Important variants include:

• Capacitated VRP (CVRP): vehicles have limited weight, volume, pallet, or unit capacity.
• VRP with time windows (VRPTW): service must respect specified time intervals.
• Pickup-and-delivery problem: goods are collected at one location and delivered to another, often with precedence requirements.
• Multi-depot VRP: vehicles operate from more than one depot.
• Periodic VRP: customers are served according to recurring patterns over several days or weeks.
• Open VRP: vehicles need not return to their starting depot.
• Dynamic VRP: customer requests, travel conditions, or vehicle availability change during execution.

A constraint limits feasible solutions. Common constraints include vehicle capacity, driver working hours, road restrictions, delivery precedence, depot hours, product compatibility, and legal rest requirements. An objective function expresses what the organization seeks to minimize or maximize, such as total cost, distance, emissions, lateness, or a weighted combination.

A feasible solution satisfies all mandatory constraints. An optimal solution is the best feasible solution according to a defined objective and model. Because many routing problems are computationally difficult, organizations often use a high-quality heuristic solution rather than proving mathematical optimality. A service-level agreement (SLA) specifies contractual performance requirements such as delivery windows, response times, proof of delivery, or fill-rate expectations.

2. The planning hierarchy and planning horizons

Routing decisions occur at three connected levels. The boundaries are not absolute, but the distinction is useful for governance and accountability.

Strategic role

Strategic planning asks whether the network is capable of supporting the business model. Decisions include the number and location of depots, the use of dedicated fleets or third-party logistics providers, vehicle technology, mode selection, and the positioning of inventory. Strategic choices shape the geography and cost structure within which all later route plans must operate.

For example, placing a depot closer to customers may reduce delivery distance but increase facility cost. A centralized network may achieve inventory pooling and lower stockholding while increasing final-mile travel. Strategic evaluation therefore requires total landed cost and service analysis, not isolated transport cost comparisons.

Tactical role

Tactical planning converts strategy into repeatable operating patterns. It determines delivery territories, customer frequency, vehicle mix, driver shifts, appointment policies, and the allocation of demand to facilities. Tactical plans often use historical demand, average travel times, seasonal patterns, and expected growth.

A route that is feasible under average demand may fail during peak periods. Tactical planning should therefore examine variability, not just average volume. Scenario analysis may test holiday demand, driver shortages, fuel-price changes, road closures, or the addition of electric vehicles with charging constraints.

Operational role

Operational planning creates and executes routes for a particular day or shift. It incorporates current orders, vehicle availability, driver schedules, traffic, weather, cancellations, and urgent requests. Operational planning is frequently iterative: a route is generated, monitored, and revised as events occur.

The hierarchy is recursive. Operational performance supplies data for tactical redesign; tactical patterns expose strategic weaknesses; and strategic decisions establish the resources available to operations. Poor information sharing between levels creates inconsistent assumptions and unstable plans.

3. Transportation economics

Transportation cost has several components, and their behaviour differs. A basic total-cost representation is:

Here, C_total is total relevant cost for the planning period; C_fixed includes costs that do not change with a particular route, such as vehicle ownership or contracted capacity; C_distance depends on kilometres or miles; C_time depends on driving, waiting, or working hours; C_service includes loading, unloading, tolls, and special handling; C_penalty represents lateness, failed delivery, or contractual penalties; and C_externality represents costs imposed on society or the environment, such as emissions or congestion. The formula is a managerial accounting framework rather than a universal law. Components must be defined consistently and should not be double-counted.

For a simple vehicle trip, distance-related cost may be estimated as:

where d is distance in kilometres and c_d is cost per kilometre. If fuel consumption is explicitly modelled, fuel cost can be estimated as:

where r is fuel consumption in litres per 100 kilometres and p_f is fuel price per litre. This estimate assumes consumption is stable over the trip. In reality, consumption varies with load, speed, terrain, temperature, idling, and driving behaviour.

Time-based labour cost can be represented as:

where h is paid labour hours and w is the fully burdened hourly labour rate. The rate may include wages, benefits, payroll taxes, allowances, and overtime premiums. Treating labour as purely distance-based is often misleading because waiting and service activities consume paid time without increasing kilometres.

A vehicle with 180 km of travel, consumption of 24 L per 100 km, and fuel priced at 1.70 currency units per litre uses:

(180 × 24 / 100) = 43.2 litres.

Thus fuel cost is 43.2 × 1.70 = 73.44 currency units. If the driver works 8 hours at a fully burdened rate of 28 currency units per hour, labour cost is 224 currency units. The combined fuel and labour estimate is 297.44 currency units before tolls, maintenance, depreciation, overhead, and penalties.

Economies and diseconomies

Transportation has economies of scale because fixed vehicle and administrative costs can be spread over more shipments. Consolidation can reduce cost per unit, but it may increase inventory, handling, lead time, and the risk of late delivery. Larger vehicles may reduce cost per case but face access restrictions and lower route flexibility.

There are also economies of density: serving many customers in a compact area reduces average deadheading and improves stop productivity. Conversely, rural or geographically dispersed demand can make a small shipment expensive even when vehicle capacity is available.

A relevant decision is whether to minimize distance, time, number of vehicles, or total cost. These objectives can conflict. A route using fewer vehicles may require overtime. A route minimizing kilometres may create long waiting periods because of time windows. The objective must reflect the organization’s actual economics and service commitments.

4. Service requirements and feasibility

A route is operationally valuable only when it delivers the promised service. Important requirements include delivery date, time window, order completeness, product condition, appointment procedures, proof of delivery, vehicle access, and customer communication.

For a route beginning at time t₀, the arrival time at a stop can be expressed conceptually as:

where t_i is arrival time at stop i, travel_i-1,i is travel time from the previous location, and service_i-1 is time spent at the previous location. If arrival occurs before the opening of a time window, waiting may be required. If the latest allowable time is exceeded, the route is infeasible under a hard-window policy.

Capacity is multidimensional. A vehicle may be limited by mass, cubic volume, pallet positions, compartments, temperature zones, hazardous-material rules, or axle weight. A route that fits by weight may fail by volume, and a route that fits physically may violate product compatibility requirements.

Service requirements should be translated into explicit model parameters. Vague statements such as deliver quickly or provide excellent service are insufficient for planning. Better specifications identify measurable thresholds, such as 98% on-time delivery, a two-hour appointment window, maximum response time of four hours, or no more than one failed delivery attempt.

5. A conceptual model of routing decisions

A useful routing workflow contains six linked stages:

1. Demand definition: validate orders, quantities, locations, priorities, and service requirements.
2. Resource definition: confirm vehicles, drivers, depots, shifts, equipment, and legal restrictions.
3. Feasibility analysis: identify impossible combinations before optimization.
4. Route construction: assign stops and sequence them using an appropriate method.
5. Schedule generation: calculate arrival, service, departure, and return times.
6. Execution and control: dispatch, monitor, communicate, and revise.

This workflow emphasizes that optimization is not the first step. Incorrect addresses, missing service times, or unrealistic travel estimates will produce apparently precise but operationally defective plans.

A route planner should distinguish hard constraints from preferences. For example, vehicle capacity and driver legal limits are normally hard constraints. A preference for balanced route duration may be soft and represented by a penalty. This distinction allows managers to understand which trade-offs are permissible.

6. Worked application: regional grocery distribution

The following is an illustrative case, not a report of an actual company.

Background

FreshRoute Distribution supplies eight supermarkets from one regional depot. Each store requires a morning delivery, and the fleet consists of two refrigerated vehicles. Each vehicle can carry 12 roll-cages. Drivers work a maximum of 9 hours, including loading, driving, service, and return. Stores have different unloading times and time windows.

Problem

Historical routes frequently return late. Dispatchers believe that the main causes are inaccurate service-time assumptions and assigning stores by geography alone. Management wants to improve punctuality without immediately purchasing another vehicle.

Analysis

The planner first validates demand and discovers that one store regularly requires 10 roll-cages but had been represented as 6 in the planning system. The planner also replaces a standard 15-minute service assumption with store-specific values ranging from 20 to 45 minutes. Travel times are adjusted using time-of-day data rather than free-flow distance estimates.

The eight stores are then grouped into two preliminary territories. Capacity is checked using roll-cages, and each vehicle’s route is tested against the morning time windows. One geographically compact grouping is rejected because it requires a long wait between two appointments and causes overtime. A slightly longer route is accepted because it sequences the stores in a way that removes waiting and respects the earliest receiving times.

Approach and solution

The revised planning process uses the following policy:

• demand is frozen at a defined planning cut-off time;
• service times are estimated by store and product type;
• routes are evaluated using total working time, not kilometres alone;
• hard time windows and refrigeration requirements cannot be violated;
• a contingency of 30 minutes is retained for each vehicle;
• dispatchers review exceptions before release to drivers.

The organization also introduces electronic proof of delivery and records actual arrival and service times. These data are used weekly to recalibrate planning parameters.

Outcome

In the first month, the number of late deliveries falls substantially, while distance changes only marginally. The principal improvement comes from better data and sequencing rather than a sophisticated optimization algorithm. The case demonstrates that route quality depends on model validity, service-time measurement, and execution discipline.

Learning points

1. Geographic closeness does not guarantee schedule feasibility.
2. Service time may be as important as travel time.
3. Capacity must be measured using the limiting resource.
4. Data governance is a prerequisite for optimization.
5. A practical contingency can improve reliability even when it slightly increases planned time.

7. Methods and technology

Small operations may use spreadsheets, mapping software, or manual dispatching. Larger operations commonly use transport management systems (TMS), geographic information systems (GIS), fleet telematics, mobile applications, and optimization engines. A TMS may integrate orders, carrier contracts, rates, route plans, dispatch instructions, tracking, invoicing, and performance reporting.

Optimization approaches include exact mathematical programming, constructive heuristics, local search, metaheuristics, and simulation. Exact methods can provide optimality certificates for smaller instances but may become computationally demanding as customers and constraints increase. Heuristics can generate strong solutions quickly and are often more useful for daily operations. Simulation is valuable for testing variability, congestion, breakdowns, and demand scenarios rather than merely producing one nominal route.

Artificial intelligence and machine learning are increasingly used for travel-time prediction, demand forecasting, estimated arrival times, anomaly detection, and dynamic re-routing. They do not eliminate the need for managerial judgment. Models may reproduce historical bias, fail under unusual conditions, or recommend routes that violate unrecorded operational rules. Human review, explainability, monitoring, and override procedures remain important.

Technology should be selected according to decision complexity and data maturity. Automating poor master data can increase the speed of bad decisions. Implementation should therefore address address quality, geocoding, product attributes, vehicle capacities, customer calendars, driver rules, and integration ownership.

8. Sustainability, ethics, and governance

Routing affects fuel consumption, greenhouse-gas emissions, noise, congestion, and local air quality. Distance reduction generally helps, but it is not the only factor: speed, load, idling, vehicle type, road grade, and failed deliveries also matter. A sustainability objective can be incorporated through emissions metrics, alternative-fuel constraints, consolidation policies, or restricted delivery practices.

Environmental decisions should be transparent about system boundaries. For example, an electric vehicle may have zero tailpipe emissions during operation but still involve electricity-generation and battery-manufacturing impacts. Comparisons should specify whether they measure tailpipe, well-to-wheel, or life-cycle emissions.

Ethical issues include driver workload, unsafe schedules, discriminatory service allocation, privacy, and surveillance. Telematics data can improve safety and accuracy but may also be used in ways that create excessive monitoring. Organizations should define legitimate purposes, access controls, retention periods, and employee communication.

Regulatory requirements may include driver hours, rest periods, vehicle weights, hazardous materials, food safety, accessibility, data protection, and local delivery restrictions. Compliance must be encoded where possible, but responsibility cannot be delegated entirely to software. Managers remain accountable for the safety and legality of dispatch decisions.

9. Challenges and limitations

Several limitations recur across industries:

• Demand uncertainty: orders may arrive late, be cancelled, or change quantity.
• Travel-time uncertainty: congestion, weather, incidents, and road works undermine deterministic schedules.
• Inaccurate master data: wrong coordinates or service times invalidate otherwise sophisticated models.
• Objective conflict: cost, punctuality, driver equity, resilience, and emissions may point to different solutions.
• Human acceptance: drivers and customers may reject routes that appear efficient but are impractical.
• Model complexity: adding every operational detail can make models slow, opaque, and difficult to maintain.
• Disruption: breakdowns, labour shortages, cyber incidents, and infrastructure failures require contingency plans.

A robust planning process therefore uses sensitivity analysis and scenario testing. Managers should ask how a plan performs if demand rises, a vehicle is unavailable, travel time increases, or a major customer changes its receiving window. The best nominal plan is not always the best plan under uncertainty.

10. Best-practice principles

Effective route planning and scheduling generally follow these principles:

1. Define service promises before selecting an optimization objective.
2. Separate hard constraints from preferences and penalties.
3. Measure both distance and time, including waiting and service.
4. Maintain accurate, governed master data.
5. Plan at strategic, tactical, and operational levels with clear ownership.
6. Use realistic variability and contingency assumptions.
7. Evaluate total cost rather than fuel or kilometres alone.
8. Include driver, customer, safety, and regulatory perspectives.
9. Monitor execution against plan and learn from deviations.
10. Treat technology as an enabler of sound processes, not a substitute for them.

Chapter Summary

Route planning determines the sequence and physical movement of stops, while scheduling determines when travel and service activities occur. Together they form a core supply chain capability linking network design, fleet resources, customer service, and operational control.

Strategic decisions shape the network and transport model; tactical decisions establish repeatable territories, fleet arrangements, and service patterns; operational decisions construct and adjust daily routes. Transportation economics includes fixed, distance-based, time-based, service, penalty, and external costs. Minimizing kilometres alone can produce poor outcomes when labour, waiting, capacity, time windows, or service penalties dominate.

A feasible route must respect capacity, time, legal, product, and customer constraints. Reliable planning depends on accurate demand, locations, service times, travel estimates, and resource data. TMS platforms, telematics, optimization, simulation, and AI can improve decisions, but technology cannot correct weak data or unclear objectives. Sustainable and ethical practice requires attention to emissions, driver welfare, privacy, safety, and regulatory compliance. The fundamental professional skill is balancing cost, service, resilience, and practicality across interconnected planning horizons.

Key Terms

Arc: A directed or undirected connection between two network nodes.

Capacity constraint: A limit on weight, volume, pallets, compartments, or another vehicle resource.

Depot: A facility from which vehicles operate and may return.

Dynamic VRP: A vehicle routing problem in which information changes during execution.

Feasible solution: A plan satisfying all mandatory constraints.

Hard time window: A time interval that cannot be violated.

Heuristic: A procedure that seeks a good solution efficiently without necessarily proving optimality.

Objective function: A mathematical representation of the criterion to minimize or maximize.

Open VRP: A routing problem in which vehicles do not necessarily return to the starting depot.

Route: A planned sequence or physical path linking transportation stops.

Service time: Time spent performing delivery, pickup, installation, or related customer activity.

Soft time window: A preferred time interval whose violation incurs a penalty or service loss.

Strategic planning: Long-term decisions concerning network structure, facilities, modes, and fleet strategy.

Tactical planning: Medium-term decisions concerning territories, fleet allocation, frequencies, and standard operating patterns.

Time window: An interval during which service must begin or finish.

Tour: The sequence of stops assigned to one vehicle during a planning period.

Transportation network: Nodes and connecting arcs through which goods, people, or services move.

Vehicle Routing Problem: A problem of assigning and sequencing customer visits subject to constraints.

Waiting time: Time incurred when a vehicle or driver cannot proceed or serve immediately.

Review Questions

Short Answer Questions

1. Distinguish route planning from scheduling.
2. What is the difference between a hard and a soft time window?
3. Identify three examples of strategic transportation decisions.
4. Why can minimizing distance fail to minimize total transportation cost?
5. What is meant by a feasible routing solution?

Long Answer Questions

1. Explain the relationship between strategic, tactical, and operational routing decisions, using an example of a retail distribution network.
2. Discuss the main components of transportation cost and explain why labour and waiting time should be modelled explicitly.
3. Describe how customer service requirements influence route feasibility and fleet design.
4. Compare exact optimization, heuristics, simulation, and AI-enabled planning approaches.
5. Evaluate the ethical, environmental, and regulatory responsibilities of a transport planner.

Analytical / Application Questions

1. A vehicle travels 240 km and consumes 22 L per 100 km. Fuel costs 1.80 currency units per litre, and the driver works 7.5 hours at 30 currency units per hour. Calculate fuel cost and labour cost, then explain which relevant costs are excluded from the estimate.
2. Two geographically close customers have non-overlapping receiving windows, while two more distant customers have compatible windows. Explain how a planner should compare these alternatives and identify the data required.
3. Design a planning policy for a grocery distributor facing uncertain demand, driver-hour limits, refrigeration requirements, and a 98% on-time delivery target. Identify hard constraints, soft objectives, data requirements, and monitoring measures.

Multiple Choice Questions with Answers

Question 1

Which decision is primarily strategic?

A. Sequencing today’s customer stops

B. Selecting the location of a regional distribution centre

C. Reassigning a stop after a vehicle breakdown

D. Recording electronic proof of delivery

Correct Answer: B. Selecting the location of a regional distribution centre

Question 2

What is the defining feature of a hard time window?

A. It is used only for premium customers

B. It can be violated without consequence

C. It cannot be violated in a feasible solution

D. It applies only to vehicle departure

Correct Answer: C. It cannot be violated in a feasible solution

Question 3

Which cost commonly depends on paid working hours rather than kilometres?

A. Driver labour cost

B. Road distance cost

C. Vehicle depreciation per kilometre

D. Fuel consumption per kilometre

Correct Answer: A. Driver labour cost

Question 4

A route that satisfies every mandatory constraint is called:

A. Optimal

B. Feasible

C. Dynamic

D. Periodic

Correct Answer: B. Feasible

Question 5

Which problem variant requires service to occur within specified intervals?

A. Open VRP

B. Multi-depot VRP

C. VRP with time windows

D. Uncapacitated assignment problem

Correct Answer: C. VRP with time windows

Question 6

A vehicle travels 180 km and consumes 24 L per 100 km. How much fuel does it use?

A. 24.0 L

B. 43.2 L

C. 75.0 L

D. 432 L

Correct Answer: B. 43.2 L

Question 7

Why can a geographically compact route still be infeasible?

A. Compact routes always require two depots

B. Geography eliminates all capacity constraints

C. Time windows, service times, or capacity may be violated

D. Compact routes cannot use refrigerated vehicles

Correct Answer: C. Time windows, service times, or capacity may be violated

Question 8

Which activity is primarily operational?

A. Choosing the long-term transport mode

B. Determining the number of future depots

C. Constructing and dispatching tomorrow’s routes

D. Designing the corporate service strategy

Correct Answer: C. Constructing and dispatching tomorrow’s routes

Question 9

What is a major risk of applying AI to routing without governance?

A. It guarantees mathematical optimality

B. It may reproduce data bias or fail under unusual conditions

C. It eliminates the need for accurate addresses

D. It prevents all regulatory violations automatically

Correct Answer: B. It may reproduce data bias or fail under unusual conditions

Question 10

Why should service time be included in route planning?

A. It consumes working time and affects arrival feasibility

B. It is always equal to travel time

C. It changes only fuel price

D. It applies only to international transport

Correct Answer: A. It consumes working time and affects arrival feasibility