Home » Freight Routing and Scheduling

Freight Routing and Scheduling

Dashboard > Freight Forwarder > Surface Transport > Freight Routing and Scheduling IN PROGRESS

LESSON PROGRESS 35% COMPLETE

Most of our daily requirements are made by the service provider coming to our premises. These
services are home delivery of Pizza within 30 minutes, transportation service of office picking all
employees or school children, Milkman delivering milk door-to-door and postal/courier services. In
such services, service delivery and timely service are very important. These issues mainly require
scheduling and routing of service vehicles.

The objective of most routing and scheduling problems is to minimize the total cost of providing the
service. The scheduling of customer service and the routing of service vehicles are at the heart of many
service operations.

Vehicle Routing and Scheduling

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem
seeking to service a number of customers with a fleet of vehicles. Often the context is that of
delivering goods located at a central depot to customers who have placed orders for such goods.
Objective of such problems is to minimize the time and distance traveled. Many methods have been
developed for searching for good solutions to the problem, but for all but the smallest problems,
finding global minimum for the cost function is computationally complex. Hence many good heuristics
have been developed for these types of problems which yield good solutions if not optimal solutions.

Vehicle routing and scheduling problems are relatively complicated as, there are many different types
of problem that can arise, each of which needs to be understood and approached in a different way, ,
there are many detailed aspects that need to be taken into account and there are a number of
different methods or algorithms that can be used to produce solutions.

Problem Types – The different types of problems are

Strategic problems are concerned with the longer-term aspects of vehicle routing and
scheduling, in particular where there is a regular delivery of similar products and quantities to
fixed or regular customers.
Tactical problems are concerned with routes that have to be scheduled on a weekly or a daily
basis.
Interactive basis allows the scheduler to use the computer to derive the most effective routes.
Actual demand data are used rather than historical demand, and these ‘real-time’ data provide
 the basis on which routes are scheduled.

Characteristics of Routing and Scheduling

Routing and scheduling problems are often presented as graphical networks. Circles are called nodes
and represent pickup and/or delivery points. A specific node represents a depot or home node, from
which the vehicle’s trip originates and ends. Connecting these nodes are line segments referred to as
arcs. Arcs describe the time, cost, or distance required to travel from one node to another. Undirected
arcs are represented by simple line segments. Directed arcs are indicated by arrows.

Feasibility – Minimum-cost solution or any other criterion like time or distance traveled is subject to
the tour being feasible. Feasibility implies that

A tour must include all nodes

A node must be visited only once
A tour must begin and end at a depot.

Route: Sequence in which the nodes (or) arcs are to be visited

Schedule: Specifies when each node has to be visited

Routing and Scheduling Problems

Various routing and scheduling problems are

Traveling Salesman problem (TSP) – We begin with a set of nodes, to be visited by a single
vehicle. The nodes may be visited in any order, there are no precedence relationships, the travel
costs between two nodes are the same regardless of the direction traveled, and there are no
delivery-time restrictions. In addition, vehicle capacity is not considered. The output for the
single-vehicle problem is a route or a tour where each node is visited only once and the route
begins and ends at the depot node. The tour is formed with the goal of minimizing the total
tour cost.
Multiple traveling salesman problem (MTSP) – It is an extension of the traveling salesman
problem and occurs when a fleet of vehicles must be routed from a single depot. The goal is to
generate a set of routes, one for each vehicle in the fleet but, a node may be assigned to only
one vehicle with vehicle will have more than one node assigned to it. There are no restrictions
on the size of the load or number of passengers a vehicle may carry. The solution to this
problem will give the order in which each vehicle is to visit its assigned nodes. The objective is
to develop the set of minimum-cost routes, with cost may be monetary amount, distance, or
travel time
Vehicle routing problem (VRP) – If we now restrict the capacity of the multiple vehicles and
couple with it the possibility of having varying demands at each node, the problem is classified
as a VRP.
Chinese postman problem (CRP) – if the demand for the service occurs on the arcs, rather
than at the nodes, or if demand is so high that individual demand nodes become too numerous
to specify, we have a CRP.
 Problem Demand Arcs Depot Vehicle Vehicle
count Count Capacity

Traveling At the nodes Directed or 1 =1 Unlimited

salesman undirected
problem

Multiple At the nodes Directed or 1 >1 Unlimited

traveling undirected
salesman
problem

Vehicle At the nodes Directed or 1 >1 Limited

routing undirected
problem

Chinese On the arcs Directed or 1 ≥1 Limited or

postman undirected unlimited
problem

Solution Approach to Routing and Scheduling Problems

Two commonly used heuristics for the traveling salesman problem are the nearest neighbor procedure
and the Clark and Wright savings heuristic.

Nearest Neighbor Procedure (NNP) builds a tour based on the cost or distance of traveling from the
last-visited node to the closest node in the network. The steps in NNP are:

1) Start with a node at the beginning of the tour (say depot node)

2) Find the node closest to the last node and add to the tour. If the closest node is

already in the tour or already there in the path then select next closest node.

3) Go to step 2 until all nodes have been added

4) Connect the first and the last node to form a complete tour

Clark and Wright Savings Heuristic (C-W) – Clark and Wright (C-W) algorithm was developed by
Enter G Clarke and J. W. Wright. The basis for C-W algorithm is savings concept where these savings
are realized by linking pairs of delivery points served by a single depot in the network. First step in C &
W heuristic is to select a node as depot node and label as node 1.

To understand the savings concept, assume n-1 vehicles are available where n is the number of nodes.
Each vehicle travels from the depot directly to the node and return to the depot. As we can see in the
network below for milk delivery example, one vehicle goes from depot to node 2 and come back and
other vehicle goes from depot to node 3 and comes back to depot (node 1).
Scheduling Service Vehicles
Scheduling problems have delivery-time restrictions with specified starting and ending times for a
service in advance. Subway schedules fall into this category. A service scheduling problem is called
two-sided window if the time limits are specified such as a delivery has to be made between 11 am
and 2 pm. A service scheduling problem is called one-sided window if a service specifies that it should
precede a given time, for example the case of newspaper, delivery should complete before 7 am.

These problems consists of a

set of tasks, each with starting time and ending times

set of directed arcs with starting and ending locations.

The set of vehicles may be housed at one or more depots.

Deadhead Time
Deadhead time is a user-specified period of time such that start time of task j must be longer than the
end time of task i. It is the non-productive time required for the vehicle to travel from one task
location to another or return to the depot empty.

The concurrent Scheduler Approach – This heuristic is used to solve the above type of scheduling
problem. The procedure is as

Order all tasks by starting times

Assign first task to vehicle 1
For the remaining number of tasks, assign the next task to vehicle that has the minimum
deadhead time to that task. Otherwise create a new vehicle and assign the task to it.

Freight Routing and Scheduling

  Previous Topic Back to Lesson Mark Complete 

Course Progress

32% COMPLETE Last activity on June 21, 2024 9:57 am

Course Home

 Expand All

 Course Videos – Freight Forwarder

 12 Topics

 Freight Planning
 9 Topics

 Freight Transportation
 6 Topics

Surface Transport
14 Topics


 Road Freight Transport

 International Road Freight

 Types of Road Freight Transport

 Vehicle Selection and Acquisition

 Freight Costing

Freight Routing and Scheduling

Vehicle Fleets Assessments

Factors Affecting Vehicle Utilization

Motor Vehicles Act 1988

Central Motor Vehicle Rules 1989

Carriers Act 1865

Rail Transport

Railways Act 1989

Intermodal Transport

Containerisation
  11 Topics

Inland Container Depots (ICD) and Container Freight Stations (CFS)

 5 Topics

Sea Transport
 14 Topics

Airline Transport
 11 Topics

International Freight Transport

 8 Topics

Integrated Logistics
 5 Topics

Future Developments
 3 Topics

Return to Freight Forwarder

Copyright © 2024 Vskills