6. Routing, Scheduling and Fleet Management

Introduction and Context

Transportation performance is determined not only by the availability of vehicles but also by the quality of decisions concerning where vehicles should travel, in what sequence, at what time, with which loads, and under whose control. Routing, scheduling and fleet management therefore form an integrated decision system within logistics. A route that is geographically short may be operationally poor if it encounters congestion, violates a delivery time window, creates driver overtime, or leaves the vehicle returning empty. Similarly, a large fleet does not necessarily provide better service; excess capacity can produce low utilisation and high ownership cost.

Routing determines the paths and sequence of visits. Scheduling assigns activities to specific times, vehicles and drivers. Fleet management governs the acquisition, deployment, maintenance, replacement and utilisation of vehicles and related resources. These decisions operate at different planning levels. Strategic decisions include fleet size, vehicle types, depot locations and outsourcing policy. Tactical decisions include driver rosters, maintenance plans, service territories and carrier allocation. Operational decisions include daily route construction, dispatching, rescheduling and exception management.

The central managerial challenge is to balance cost, service, risk and sustainability. This chapter develops the principal quantitative models used for that purpose, including shortest-path, transportation, assignment and vehicle-routing models, and then connects them with time windows, backhauls, fleet sizing, driver scheduling, maintenance and empty-mile reduction.

Learning Objectives

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

1. Distinguish routing, scheduling and fleet-management decisions at strategic, tactical and operational levels.

2. Apply shortest-path, transportation, assignment and vehicle-routing logic to logistics problems.

3. Explain the effects of time windows, service times, backhauls and driver regulations on route feasibility.

4. Estimate fleet requirements and evaluate utilisation, productivity and empty mileage.

5. Design practical approaches to driver scheduling, maintenance and dispatch control.

6. Evaluate the managerial, technological, ethical and environmental implications of fleet decisions.

The Decision Architecture of Transport Operations

A useful starting point is to separate the physical network from the operating plan. The network contains depots, customers, cross-docks, suppliers, roads and possible transfer points. The operating plan specifies vehicle movements, shipment quantities, delivery times, drivers and resources. A feasible plan must satisfy demand, vehicle capacity, route continuity, driver availability, legal restrictions and customer commitments.

Routing is primarily a spatial decision. It answers the question: which links and stops should be included in a trip? Scheduling is both temporal and organisational: when will each activity occur, and which vehicle or driver will perform it? Fleet management concerns the resource base that makes the plan possible. The three areas are interdependent. A route plan requiring 25 vehicle-hours cannot be implemented with a fleet capable of only 20 available vehicle-hours. Conversely, adding vehicles may solve a capacity shortage but increase fixed cost and reduce average utilisation.

The principal objective functions include minimising distance, travel time, fuel, labour, tolls, emissions, late deliveries, fleet size or total cost. In practice, logistics companies normally use a weighted or constrained objective. For example, a carrier may minimise cost subject to a 98 per cent on-time delivery target, rather than minimise distance without regard to service.

Important terminology includes an origin, destination, depot, node, arc, stop, leg, tour, route, trip, load, shipment, backhaul, deadhead or empty mile, dwell time and service time. A route is the sequence of links followed by a vehicle; a tour generally denotes a complete movement beginning and ending at a depot. Vehicle capacity may be expressed by weight, volume, pallet positions, compartments or a combination of these. A route is feasible only when all relevant capacity dimensions are respected.

From Network Paths to Vehicle Routes

Shortest-path models

The shortest-path problem identifies the least-cost path between an origin and destination in a network. Each arc has a cost, such as distance, travel time, toll or generalised cost. If the network is represented by nodes and directed arcs, the objective is to minimise the sum of arc costs while maintaining connectivity between the origin and destination.

Dijkstra’s algorithm is suitable when arc costs are non-negative. It progressively labels nodes according to their least known cost from the origin and permanently selects the unvisited node with the smallest label. When negative arc costs or more complex conditions exist, other algorithms may be required. In logistics applications, the shortest path is useful for navigation, line-haul planning and estimating travel time between customers. It is not, by itself, a solution to a multi-customer delivery problem because it does not decide the order in which customers are visited.

Travel time should not be treated as a fixed property of distance. Time-dependent routing uses different arc costs for different periods, reflecting congestion, restrictions and operating conditions. A route selected at 06:00 may be inferior at 08:00. Robust planning may therefore minimise expected travel time or include a buffer for variability.

Transportation models

The transportation model determines how quantities should be shipped from multiple origins to multiple destinations at minimum cost. Let xij be the quantity shipped from origin i to destination j, cij the unit cost, ai the supply at origin i and bj the demand at destination j. A basic formulation is:

Minimise Z = Σi Σj cijxij

subject to Σj xij ≤ ai for every origin, Σi xij = bj for every destination, and xij ≥ 0.

The model is valuable for allocating product from plants, warehouses or suppliers to markets. It differs from routing because it concerns quantities between origin-destination pairs rather than the sequence of stops made by a particular vehicle. Nevertheless, transportation-model results can provide the shipment flows that later become inputs to vehicle-routing and dispatch decisions.

The basic model may be extended with vehicle capacities, fixed dispatch costs, multiple products, transshipment, service constraints and carbon costs. If supply and demand are unequal, a dummy origin or destination can balance the formulation, but the resulting flows must be interpreted carefully rather than accepted automatically as an operational plan.

Assignment models

An assignment model allocates one resource to one task, normally with each resource and task used once. Examples include assigning drivers to routes, vehicles to tours, technicians to maintenance jobs or carriers to lanes. If cij is the cost of assigning resource i to task j, the objective is to minimise Σi Σj cijxij, with each row and column summing to one and xij binary.

The Hungarian method efficiently solves the classical assignment problem. Real operations often require extensions: a driver may be unavailable, a vehicle may lack refrigeration, or a route may require a specific licence. Such restrictions are represented by prohibited assignments or very high penalty costs. Assignment results must also be checked against working-time, safety and collective-agreement requirements.

Vehicle-routing models

The vehicle-routing problem (VRP) determines routes for a fleet serving a set of customers. The classical capacitated VRP assumes a depot, known customer demands, homogeneous vehicle capacity and a requirement that each customer be visited once. Each route starts and ends at the depot, and the total demand on a route cannot exceed vehicle capacity.

Important variants include the vehicle-routing problem with time windows (VRPTW), heterogeneous-fleet VRP, multi-depot VRP, pickup-and-delivery VRP, periodic VRP and open VRP. In a pickup-and-delivery problem, precedence constraints may require a pickup before its associated delivery. In a multi-depot problem, customers and vehicles may be linked to different depots. These variants are generally computationally difficult as the number of customers increases; exact optimisation may be suitable for small instances, while heuristics and metaheuristics are common for operational-scale problems.

A practical route-construction process may first generate an initial feasible plan, then improve it by exchanges. In a savings heuristic, the planner begins with separate depot-to-customer routes and evaluates the saving from combining two routes. Local-search methods use moves such as relocating a customer, swapping two customers or reversing a segment. More advanced methods include tabu search, simulated annealing, genetic algorithms and adaptive large-neighbourhood search. The value of any algorithm depends on data quality and operational feasibility, not merely on its mathematical sophistication.

Time Windows, Service Conditions and Backhauls

A time window specifies when a customer may be served. Hard windows make service outside the interval infeasible; soft windows permit violation at a penalty. A route must account for travel time, waiting, unloading, documentation, security checks and loading or unloading equipment. Ignoring service time is a common source of unrealistic schedules.

Time-window planning involves a trade-off between route compactness and customer convenience. A geographically efficient sequence may arrive too early at one customer and too late at another. Waiting can be acceptable when early arrival is permitted, but it consumes driver and vehicle time. Time windows also create shadow costs: a narrow window may require an additional vehicle even when total daily demand would otherwise fit within the existing fleet.

Backhauling means using the return journey to carry a load, often from a customer or supplier near the delivery territory back toward a depot or another destination. It reduces empty mileage and improves asset productivity. A backhaul must be evaluated for compatibility of products, equipment, loading sequence, delivery deadlines, contamination risk and contractual responsibility. A low-priced backhaul that causes a late primary delivery or excessive detour is not necessarily economical.

Consolidation and dynamic routing can improve vehicle fill, but consolidation may delay urgent shipments. The appropriate decision depends on the value of service, inventory consequences, vehicle cost and the reliability of demand information.

Fleet Sizing, Utilisation and Driver Scheduling

Fleet sizing begins with workload rather than with historical vehicle numbers. A simplified requirement can be estimated as:

Required vehicles = peak workload in vehicle-hours ÷ productive available hours per vehicle.

The result must be adjusted for vehicle capacity, legal driving limits, loading and unloading, maintenance, breaks, reserve requirements and demand variability. Peak-day demand is important because a fleet sized only for average demand may fail during predictable surges. However, sizing entirely for the absolute maximum may create excessive idle capacity. Options such as subcontracting, leasing, temporary vehicles and flexible shifts can provide peak capacity.

Fleet utilisation has several meanings. Time utilisation is productive operating hours divided by available vehicle hours. Capacity utilisation is loaded weight, volume or pallet positions divided by available capacity. Distance utilisation is loaded kilometres divided by total kilometres. These measures should be reported separately because a vehicle can be highly utilised in time but poorly utilised by weight, or carry a full load on only one direction of a trip.

Driver scheduling must account for legal driving and rest rules, shift length, breaks, qualifications, route duration, depot start times and fairness. A roster that minimises cost but systematically produces fatigue is operationally and ethically unacceptable. Driver schedules can be formulated as set-partitioning or mixed-integer models, but practical systems often combine optimisation with negotiated rules and manual review.

Fleet composition is another strategic decision. Smaller vehicles may access urban streets and provide frequency, while larger vehicles offer lower unit cost on dense corridors. Electric vehicles may have lower operating emissions and maintenance needs but require charging time, battery capacity and suitable range. Refrigerated, hazardous-material and multi-compartment fleets impose additional constraints.

Maintenance and Vehicle Replacement

Maintenance affects both cost and service reliability. Corrective maintenance repairs a vehicle after failure; preventive maintenance is performed according to time, mileage or usage; predictive maintenance uses condition information to anticipate failure. A sound programme combines statutory inspections, manufacturer guidance, operating data and risk assessment.

Vehicle availability can be represented as the proportion of time a vehicle is serviceable and ready for work. A fleet plan should include maintenance capacity, spare vehicles, parts availability and workshop scheduling. Preventive maintenance may temporarily reduce available capacity but can lower breakdown risk and disruption. Replacement decisions should consider total cost of ownership, including acquisition, finance, fuel or energy, tyres, maintenance, residual value, downtime and environmental compliance.

Dispatch Control and Digital Decision Support

Modern transport management systems integrate orders, vehicle locations, driver availability, maps, traffic data, proof of delivery, maintenance records and billing. Route-optimisation engines can generate plans, while telematics provide actual position, speed, idling, harsh braking and fuel or energy data. Geofencing can identify arrival and departure, and electronic proof of delivery supports customer visibility and dispute resolution.

Analytics should distinguish planned from actual performance. Useful measures include on-time-in-full delivery, cost per stop, cost per kilometre, stops per route-hour, vehicle fill, empty-mile percentage, utilisation, fuel or energy per tonne-kilometre, breakdown frequency and maintenance compliance. Exception dashboards are more valuable than large volumes of unprioritised data. A planner should know which late deliveries require intervention and which deviations are harmless.

Artificial intelligence and machine learning can improve demand forecasting, arrival-time prediction, dynamic re-routing, anomaly detection and maintenance prediction. Their outputs remain dependent on reliable data and appropriate human oversight. A model trained on historical routes may reproduce inefficient practices or disadvantage particular drivers. Automated recommendations should therefore be explainable, auditable and subject to operational review.

Illustrative Case: Northstar Regional Distribution

Background

Northstar is a fictional distributor of packaged food operating from one regional depot. It serves 42 retail outlets with a mixed fleet of rigid trucks and smaller urban vehicles. Deliveries are scheduled in the morning, and several suppliers offer collection opportunities on return journeys.

Situation and problem

The company historically assigned customers to vehicles by territory. This produced familiar routes but resulted in 19 per cent empty kilometres, frequent overtime on Tuesdays and underused capacity on Fridays. Some stores required delivery between 08:00 and 10:00, while others accepted deliveries throughout the day. The fleet consisted of more vehicles than the average daily workload required, but peak demand and vehicle breakdowns still caused service failures.

Analysis

The logistics team first cleaned customer-location, demand, service-time and time-window data. A transportation analysis reviewed which supplier-to-depot flows could be consolidated. A VRPTW model was then used to generate candidate routes, with vehicle capacity and driver-hour limits included. Routes were assigned to vehicles through an assignment model that considered body type, refrigeration and availability. The team separately identified compatible backhauls and excluded loads that could contaminate food products or compromise delivery sequence.

The analysis showed that territory-based routing was not the least-cost structure. Two neighbouring territories could be combined in the afternoon, while certain early-window stores required a dedicated route. A small reserve vehicle was more economical than maintaining the former excess fleet because it covered breakdowns and predictable peaks. Preventive maintenance was shifted to low-demand afternoons.

Approach and solution

Northstar introduced rolling weekly planning with daily dynamic adjustments. Early-window customers were protected as hard constraints; flexible customers were used to absorb changes. Drivers received route plans with estimated service times and were consulted before implementation. Supplier collections were added only when they caused no violation of delivery commitments. The company also adopted measures for loaded distance, route-hour utilisation and backhaul success rather than relying only on total kilometres.

Outcome

In this illustrative case, the redesigned system reduced empty travel, improved the balance between Tuesday and Friday workloads, and made the fleet requirement more stable. The most important improvement did not come from a single algorithm. It resulted from combining accurate master data, route optimisation, fleet assignment, driver participation, maintenance planning and exception management.

Learning points

The case demonstrates that routing should not be isolated from scheduling and fleet policy. A mathematically shorter route may be inferior if it ignores time windows or labour constraints. Backhauls create value only when operationally compatible. Finally, utilisation indicators must be interpreted together: reducing empty kilometres is useful, but not if it increases lateness, unsafe driving or product damage.

Risks, Limitations and Professional Governance

Routing models can fail because of inaccurate addresses, outdated travel times, incorrect customer demand, missing service times or unrecorded restrictions. Optimisation can also produce fragile plans with no allowance for congestion, loading delays or failed deliveries. Planners should test scenarios, include buffers and maintain contingency routes.

Common mistakes include optimising distance while ignoring time, measuring fleet utilisation only by kilometres, assigning drivers without considering fatigue, treating historical territories as permanent, and accepting software output without field validation. Another error is to pursue maximum vehicle fill when partial loads are necessary to meet service commitments.

Fleet decisions have ethical and regulatory dimensions. Compliance may cover driving hours, rest periods, vehicle safety, weight limits, hazardous materials, emissions zones, data protection and employment rights. Telematics data should be collected for legitimate purposes, protected from unauthorised access and used transparently. Performance systems should not encourage speeding, skipped breaks or unsafe manoeuvres. Procurement and subcontracting decisions should include safety standards, insurance, driver welfare and audit rights rather than focusing solely on price.

Emerging Directions and Best Practices

Current developments include electric and alternative-fuel fleets, urban consolidation, autonomous assistance, connected vehicles, digital freight matching and carbon-aware routing. Electric fleet planning requires simultaneous decisions about routes, charging locations, battery state, payload and grid capacity. Carbon-aware routing may choose a slightly longer route if it reduces congestion, idling or energy use, but environmental objectives should be measured rather than assumed.

Effective practice generally involves the following principles:

• build accurate customer, vehicle, driver and travel-time data;
• define service constraints before selecting an objective function;
• integrate routing with fleet assignment, maintenance and labour planning;
• use robust buffers and explicit contingency procedures;
• measure cost, service, safety, utilisation and environmental performance together;
• involve drivers and dispatchers in design and review;
• validate algorithmic plans against operational reality;
• review actual-versus-planned results and continuously improve the data and model.

Chapter Summary

Routing selects the sequence and paths of vehicle movements, scheduling places those movements in time, and fleet management provides and controls the required resources. Shortest-path models address movement between two points; transportation models allocate quantities between origins and destinations; assignment models match resources with tasks; and vehicle-routing models construct multi-customer tours subject to capacity and service restrictions. Time windows, service times, backhauls and driver rules determine practical feasibility. Fleet sizing must reflect peak workload, capacity, availability and uncertainty, while utilisation should be measured through time, capacity and loaded-distance indicators. Maintenance, technology, analytics and human judgement jointly support reliable operations. The most effective transport decisions balance cost with service, safety, resilience, legal compliance and environmental responsibility.

Key Terms

Shortest path: The least-cost or least-time path between two nodes in a network.

Arc: A directed connection between two nodes with an associated cost or travel time.

Transportation model: A linear optimisation model allocating quantities from origins to destinations.

Assignment model: A model matching resources to tasks, usually on a one-to-one basis.

Vehicle-routing problem: A model for designing vehicle tours that serve multiple customers.

Time window: The permitted interval for serving a customer or performing an activity.

Service time: The time spent loading, unloading, checking documents or otherwise serving a stop.

Backhaul: A return movement carrying freight instead of travelling empty.

Deadhead: Vehicle movement without revenue-generating or planned freight.

Fleet utilisation: The extent to which vehicle time, distance or capacity is productively used.

Vehicle availability: The proportion of fleet time during which a vehicle is serviceable and ready.

Preventive maintenance: Planned maintenance performed before failure occurs.

Predictive maintenance: Maintenance scheduled using condition or failure-prediction information.

Capacity constraint: A restriction imposed by vehicle weight, volume, pallets or other limits.

Hard constraint: A condition that cannot be violated in a feasible solution.

Soft constraint: A condition that may be violated at a specified penalty.

Telematics: Connected technology capturing vehicle location, behaviour and operating data.

Empty-mile percentage: Empty kilometres expressed as a proportion of total kilometres.

Robust planning: Planning that incorporates uncertainty, buffers and contingency capability.

Total cost of ownership: The complete acquisition, operating, maintenance, downtime and disposal cost of an asset.

Review Questions

Short Answer Questions

1. How does a shortest-path model differ from a vehicle-routing model?

2. What is the purpose of a transportation model in distribution planning?

3. Define a hard time window and a soft time window.

4. Why should fleet utilisation be measured through more than one indicator?

5. Distinguish preventive maintenance from predictive maintenance.

Long Answer Questions

1. Explain how routing, scheduling and fleet management interact across strategic, tactical and operational decisions.

2. Discuss the assumptions, uses and limitations of transportation, assignment and vehicle-routing models.

3. Explain the major factors that should be considered when sizing a delivery fleet.

4. Analyse how driver regulations, service times and customer time windows affect route feasibility.

5. Discuss how technology and analytics can improve dispatching while creating governance and ethical risks.

Analytical / Application Questions

1. A depot has 18 customer orders, two vehicle sizes and four customers with narrow morning windows. Design a modelling approach, identify the relevant constraints and explain how you would validate the resulting routes.

2. A carrier reports high vehicle-kilometre utilisation but low profit and frequent overtime. Diagnose at least four possible causes using the performance concepts in this chapter and recommend corrective actions.

3. A distributor is considering a backhaul programme from retail customers to a supplier. Develop a decision framework covering compatibility, route feasibility, cost, service, safety and environmental effects.

22. Multiple Choice Questions with Answers

Question 1

Which model is most directly concerned with finding the least-cost path between one origin and one destination?

A. Assignment model

B. Shortest-path model

C. Transportation model

D. Vehicle-routing model

Correct Answer: B. Shortest-path model

Question 2

A route visits every customer once, starts and ends at a depot, and must not exceed vehicle capacity. Which problem best represents it?

A. Capacitated vehicle-routing problem

B. Basic assignment problem

C. Shortest-path problem

D. Unbalanced transportation problem

Correct Answer: A. Capacitated vehicle-routing problem

Question 3

Why can a geographically shortest route be operationally infeasible?

A. Distance is never relevant to transport cost

B. It may violate time windows or driver-hour constraints

C. Shortest routes always require more vehicles

D. It cannot include a depot

Correct Answer: B. It may violate time windows or driver-hour constraints

Question 4

Which activity most directly reduces empty mileage?

A. Increasing waiting time at the depot

B. Adding compatible freight to a return journey

C. Restricting all vehicles to one-way trips

D. Reducing preventive maintenance

Correct Answer: B. Adding compatible freight to a return journey

Question 5

A driver is assigned to a refrigerated route but is unavailable that day. Which modelling approach is most directly relevant to replacing the driver or resource?

A. Assignment model

B. Shortest-path model

C. Transportation model

D. Inventory model

Correct Answer: A. Assignment model

Question 6

Which measure is calculated as loaded kilometres divided by total kilometres?

A. Time utilisation

B. Capacity utilisation

C. Distance utilisation

D. Vehicle availability

Correct Answer: C. Distance utilisation

Question 7

What is the principal planning danger of sizing a fleet only for average daily demand?

A. It necessarily increases empty mileage

B. It may fail during predictable peak periods

C. It eliminates the need for subcontractors

D. It always creates excessive idle capacity

Correct Answer: B. It may fail during predictable peak periods

Question 8

Which statement best describes a soft time window?

A. Service outside the window is impossible under all circumstances

B. The window applies only to vehicle maintenance

C. Violation is permitted but incurs a penalty or service cost

D. The window is ignored during route optimisation

Correct Answer: C. Violation is permitted but incurs a penalty or service cost

Question 9

Why should telematics-based driver performance systems be governed carefully?

A. They cannot record vehicle location

B. They may encourage unsafe behaviour or misuse personal data

C. They eliminate all maintenance requirements

D. They make time windows unnecessary

Correct Answer: B. They may encourage unsafe behaviour or misuse personal data

Question 10

A company wants to reduce breakdown-related service failures without eliminating all reserve vehicles. Which combination is most appropriate?

A. Corrective maintenance only and no contingency capacity

B. Preventive or predictive maintenance plus a planned reserve

C. Maximum vehicle loading and reduced inspections

D. Longer routes and fewer workshop resources

Correct Answer: B. Preventive or predictive maintenance plus a planned reserve