FREIGHT

MANAGEMENT
Dr. LE THI DIEM CHAU
Dr. TRAN QUYNH LE
Assoc.Prof. Do Ngoc Hien
Dr. Nguyen Duc Duy
Dr. Tran Quoc Cong
Industrial Systems Engineering Department
Mechanical Engineering Faculty
Ho Chi Minh City University of Technology – VNU
Chapter 4
 Frieght Logistics,
distribution and transport
(Concepts_P2)
 Location in
networks

Collaboration in Transportation
freight and service
distribution networks

Green freight Routing

distribution problems

Integrated
routing problems
Location in networks

1 • Hub location problems

2 • p-Hub median problems

3 • Capacitated hub location problems

4 • Other types of hub location problems

5 • Congestion in hub location problems

6 • Facility location problems

7 • Uncertainty in location problems

Facility location problems

 Involves only a subset of the decisions of the hub location problem,

namely assignment and location.

 The flow decisions are often not explicitly stated but are a consequence
of the assignment decisions
 Facility location problems

a) A sample instance of the facility b) A typical solution to a facility

location problem location problem
 Facility location problems

c) A typical hub-and-spoke network

b) A facility location problem configuration
 Uncapacitated - no limitation on the
- Allow each customer to be facility location amount of supply
assigned to and receive direct problem
shipments from multiple
facilities
Multiple- Variants of the Capacitated
assignment
facility location
facility location facility location
problem problem
problems

- a limited amount of
Single- commodity to all the
assignment customers
- Each customer can only be
assigned to a single facility
Uncapacitated facility location problem
 Notation:
Uncapacitated facility location problem
 Objective function:
Uncapacitated facility location problem
 Subject to:
Capacitated facility location problem

 Two types of capacity restrictions:

- the amount of demand that can be shipped from each facility in the
multiple-assignment case

- the number of customers assigned to each facility assuming single-

assignment.
Capacitated facility location problem: Case 1

Subject to:
Capacitated facility location problem: Case 1
Subject to:
Capacitated facility location problem: Case 1
Subject to:

Or

namely the total capacity available across the potential facilities must be
sufficiently large so as to be able to meet the total demand
Capacitated facility location problem: Case 2

Subject to:
Capacitated facility location problem: Case 2
Subject to:

Or
Routing problems/Short-haul transportation

1 • Routing in freight distribution

2 • Travelling salesman problem

3 • Vehicle routing problem

 1. Routing in freight distribution
❖ Freight distribution can be done in one of the two following ways:

Full truckload (FTL) Less-than full truckload (LTL)

 The amount of freight requested  The quantity of goods required by customers is
from the origin by a customer is smaller
enough to fill the capacity of the  Consolidation of orders into as few vehicles as
vehicle possible
 Referred to as a direct shipment  Each vehicle will have to follow a route in
or direct distribution which multiple stops will be performed
 Total amount of goods carried on a vehicle will
be limited by the capacity of the vehicle
1. Routing in freight distribution
Network topology

Timescales for planning and implementation

Customers

Time

Vehicles

Objectives
 Nodes: origins Network topology
and destinations
D
M
A G

Q
E
C

F
Arcs (directed)
Sea or
K
edges (undirected)

Depot I

O J

B
 Timescales for planning and
Customers
implementation

• Short time span: day: daily, • Be located on the nodes

weekly, or every day of a given • Request a collection (pick up)
week or delivery of a particular good
• The demand: deterministic &
stochastic
• Often restricted to be visited by
a single vehicle…
 Time Vehicles Objectives

• Travel time • Type of vehicle • Minimise the total

• Time windows • Vehicle capacity travel time
• Service time • Fleet size • Minimise the number
• An unlimited number of vehicles
of vehicles • Minimise a cost
function
• Minimise any penalty
• Maximise a profit
function
• Minimise any risks
or hazards
Travelling salesman problem
(TSP)
Travelling salesman problem (TSP)

 Determining a minimum-cost route that starts from a depot ➔ visits each

customer exactly ➔ returns to the depot
 Cost between a pair of nodes is often defined to be equal to the distance
between the nodes ➔ a minimum-length route
 Constraint: each customerneeds to be visited exactly once
 No further restrictions such as capacities, or time windows
 Be a special VRP with a single vehicle
Travelling salesman problem (TSP)
Asymmetric travelling salesman Symmetric travelling salesman
problem (ATSP) problem (STSP)
 Khoảng cách (hoặc chi phí) giữa hai địa  Khoảng cách (hoặc chi phí) giữa hai
điểm có thể không đối xứng ➔ Ma trận địa điểm bất kỳ là đối xứng ➔ Ma
khoảng cách là ma trận không đối xứng trận khoảng cách là ma trận đối xứng
Asymmetric travelling salesman problem (ATSP)
Asymmetric travelling salesman problem (ATSP)
Example
Distance data (in miles) for the parcel delivery example

Southampton (0), Romsey (1), Winchester (2), Salisbury (3), Lyndhurst (4)
and Micheldever (5)
Asymmetric travelling salesman problem (ATSP)
Asymmetric travelling salesman problem (ATSP)
 Summary
The asymmetric travelling salesman problem (ATSP)
• xij = 1 if arc (i, j ) is part of the solution, 0 otherwise.
 Summary
The asymmetric travelling salesman problem (ATSP)
• Con (7.1) = degree constraints = single arc enters each vertex j.
• Con (7.2) = degree constraints = single arc exits each vertex j.
• Con (7.3) = xij is in a set X that is a single directed tour or circuit.
Con (7.4) = connectivity constraints = a circuit has at least one arc coming out
from each proper and nonempty subset s of vertices in V’
• Con (7.5) = subcircuit elimination constraints
= prevent the subcircuits with less than |s| vertices
• Con (7.4) and (7.5) contain large number of constraints
→ Redundant for |s| = 1 by Con(7.2).
Symmetric travelling salesman problem
(STSP)
• xij = 1 if edge (i,j) is part of the solution, 0 otherwise. (i<j)
Symmetric travelling salesman problem
(STSP)
• Con (7.6) = degree constraints
→ Exactly two edges must be incident to every vertex j.
• Con (7.7) = connectivity constraints
→ For every vertex subset s, there exist at least two edges with one
endpoint in S⊂ V’ and the other endpoint in V’\S
• Con (7.7) are redundant if |s| = 1 because of Con (7.6).
• Con (7.7) can be replaced with sub cycle elimination constraints.
Vehicle Routing Problems (VRP)
Vehicle Routing
Problem (VRP)

Different variants of the VRP

(adapted from Weise et al., 2010).
Vehicle Routing Problem (VRP)
• VRP: Vehicle routing problem.
• Periodic VRP (PVRP): The Periodic Vehicle
Routing Problem (PRVP) asks to determine
visit schedules and routes to minimize the
total transportation costs for a planning
horizon of multiple periods.
• MDVRP -Multi Depot Vehicle Routing
Problem: The multi-depot vehicle routing
problem (MDVRP) arises as a generalization
of the vehicle routing problem (VRP), where
vehicles depart from and return to one of
multiple depot locations.
Vehicle Routing Problem (VRP)

Comparison between VRP versus MDVRP

Vehicle Routing Problem (VRP)
• CVRP-The capacitated VRP: a VRP solution
needs to consider the load capacity as a
constraint.
• DVRP: VRP with distance or time constraints.
• DCVRP: Distance-constrained capacitated vehicle
routing problems.
Vehicle Routing Problem (VRP)
• VRP with time windows (VRPTW): can be defined
as choosing routes for limited number of vehicles to
serve a group of customers in the time windows.
 Vehicle Routing Problem (VRP)
• The VRP with heterogeneous fleet of vehicles:
Heterogeneous fleet vehicle routing problem is a
kind of VRP that vehicles have different capacity
and costs.
Vehicle Routing Problem (VRP)
• Vehicle Routing Problems with Backhauls (VRPB):
where customers can return some commodities are very
common. Therefore all deliveries for each route must be
completed before any pickups are made. Then, it also
becomes necessary to take into account that the goods
which customers return to the deliverer must fit into the
vehicle.
 Vehicle Routing Problem (VRP)
• VRPSPD-Pickup and deliveries and periodic VRP:
both pickup and delivery tasks simultaneously occur at
various customer locations.
• VRPPD-Pickup and deliveries and periodic VRP: is a
generalized version of the VRP that not only includes
deliveries but also enables pickup of products from the
customers.
Vehicle Routing Problem (VRP)

Dynamic VRP (DVRP): The Dynamic Vehicle Routing Problem

(DVRP) is one of the important variants of VRP. Its aim consists in
designing the optimal set of routes for a fleet of vehicles in order to
serve a given set of customers while new customer orders arrive
during the performance of the planned earlier work day.
Vehicle Routing Problem (VRP)

The traditional Vehicle Routing Problem (VRP) Dynamic Vehicle Routing Problem (DVRP)
 VRP
Objectives in routing problems - Related to Flows/Tours
Cost (C) Transfers (Tr)
Total costs; Refueling cost; Fuel cost; # inter-modal transfers; # intra-modal transfers
Purchasing cost; Routing cost; Environment (Env)
Negative impact on economy C02/CO/greenhouse gas emissions
Distance (D) Energy/fuel consumption
Total distance; Average distance Environmental risk Health risk (HeRi)
Time (T) Population (group) exposure
Total time Accident rate
Earnings (E) Risk exposure
Profit Safety distance
Balance (B) Traffic volume
Longest distance; Distance difference; Makespan Load Transportation risk Total/min. individual perceived risk
difference; # customers visited; Utility level difference; Military risk (MiRi)
Lowest dissimilarity Average dissimilarity Detection probability
Reliability (Rel) Jamming probability Threat exposure
Time; budget; Route
Sequence preference (S)
Realization of urgent queries Station conditional
dependence
Vehicle Routing Problem (VRP)
Objectives in routing problems - Related to Nodes/Arcs/Edges
Time windows (TW) Respecting due dates
#/degree of violations Customer costs (CC)
Total/max. waiting time Inventory cost
Time deviations Sum of service and inventory cost
Coverage (Cov) Utility (U)
totallavg./max. distance between unvisited Individual disutility
nodes and tour Customer utility
(un)covered demand Populations' disutility
frequency/ratel# backorder(s)
Comfort (Com)
Extra time compared to direct routing
Time to destination (TD)
Customer movement time Max. speed
Vehicle Routing Problem (VRP)

Objectives in routing problems - Related to Related to Resources

Related to Resources Facilities (F) commodities

Facility cost Human resources (HR)
Transportation means (TM) regionalization workforce
# refuelings * deployment efficiency
# vehicles # drivers *
Vehicle waiting time Driver wages *
Capacity utilization Goods (G) Consistency in driver assignment
Merchandise deterioration Consistency in truck arrival *
expected utility level of relief Driver utility *
Vehicle Routing Problem (VRP)-Taxonomy
1. Type of study
1.1. Theory
1.2. Applied methods
1.2.1. Exact methods
1.2.2. Classical Heuristics
1.2.3. Metaheuristics
1.2.4. Simulation
1.2.5. Real-time solution methods
1.3. Implementation documented
1.4. Survey, review or meta-research
Vehicle Routing Problem (VRP)-Taxonomy
2. Scenario Characteristics 2.5.4. Unknown
2.1. Number of stops on route 2.6. Time window structure
2.1.1. Known (deterministic) 2.6.1. Soft time windows
2.1.2. Partially known, partially probabilistic 2.6.2. Strict time windows
2.2. Load splitting constraint 2.6.3. Mix of both
2.2.1. Splitting allowed 2.7. Time horizon
2.2.2. Splitting not allowed 2.7.1. Single period
2.3. Customer service demand quantity 2.7.2. Multi-period
2.3.1. Deterministic 2.8. Backhauls
2.3.2. Stochastic 2.8.1. Nodes request simultaneous pickups and
2.3.3. Unknown deliveries
2.4. Request times of new customers 2.8.2. Nodes request either linehaul or backhaul
2.4.1. Deterministic service, but not both
2.4.2. Stochastic 2.9. Node/Arc covering constraints
2.4.3. Unknown 2.9.1. Precedence and coupling constraints
2.5. Onsite service/waiting times 2.9.2. Subset covering constraints
2.5.1. Deterministic 2.9.3. Recourse allowed
2.5.2. Dependent
2.5.3. Stochastic
Vehicle Routing Problem (VRP)-Taxonomy
3. Problem Physical Characteristics 3.6.1. Single vehicle
3.1. Transportation network design 3.6.2. Limited number of vehicles
3.1.1. Directed network 3.6.3. Unlimited number of vehicles
3.1.2. Undirected network 3.7. Capacity consideration
3.2. Location of addresses (customers) 3.7.1. Capacitated vehicles
3.2.1. Customer on nodes 3.7.2. Uncapacitated vehicles
3.2.2. Arc routing instances 3.8. Vehicle homogeneity (Capacity)
3.3. Number of points of origin 3.8.1. Similar vehicles
3.3.1. Single origin 3.8.2. Load-specific vehicles
3.3.2. Multiple origin 3.8.3. Heterogeneous vehicles
3.4. Number of points of loading/unloading 3.8.4. Customer-specific vehicles
facilities (depot) 3.9. Travel time
3.4.1. Single depot 3.9.1. Deterministic
3.4.2. Multiple depots 3.9.2. Function dependent (a function of current
3.5. Time window type time)
3.5.1. Restriction on customers 3.9.3. Stochastic
3.5.2. Restriction on depot/hubs 3.9.4. Unknown
3.5.3. Restriction on drivers/vehicle
3.6. Number of vehicles
Vehicle Routing Problem (VRP)-Taxonomy
4. Information Characteristics 4.3.2. Global
4.1. Evolution of information 4.4. Processing of information
4.1.1. Static 4.4.1. Centralized
4.1.2. Partially dynamic 4.4.2. Decentralized
4.2. Quality of information 5. Data Characteristics
4.2.1. Known (Deterministic) 5.1. Data used
4.2.2. Stochastic 5.1.1. Real-world data
4.2.3. Forecast 5.1.2. Synthetic data
4.2.4. Unknown (Real-time) 5.1.3. Both real and synthetic data
4.3. Availability of information 5.2. No data used
4.3.1. Local
 SOLUTION
METHODS

META-
EXACT HEURISTICS
HEURISTICS

Integer &
Dynamic Constructive Ilterative Two-phase Adaptative Evolutionary Search Machine
Tree search Linear
programming methods methods methods methods methods methods learning
programming

Branch and Column Clarke and Adaptive Neighborhood Reimforcement

(bound, price, Gauss-Seidel Local search Ant colony
generation Wright guidance search learning
or cut)

Scalarization Cluster Bee Simulated

Backtracking Dijkstra Sweep method GRASP
method insertion evolutionary annealing
search

Path based Nearest Sampling Cluster first Fix and Genetic

neighbour average Tabu search
approach route second optimize algorithm
insertion approximation

Lexicographic Quantile-based Real time Metetic

Scatter search
and goal scenario traceability algorithm
programming analysis data routing
optimization model
Particle swarm
Iterative optimization
improvement

Chemical
reaction
Gutiérrez-Sánchez, A., & Rocha-Medina, L. B. (2022). VRP variants applicable to collecting donations optimization
and similar problems: A taxonomic review. Computers & Industrial Engineering, 164, 107887.
Basic VRP model
Indices and notations:
i: Depot node index i
j: Delivery node index j
n: Number of nodes.
C = {1, 2, …, n} : set of nodes
Di: demand of nodes i
Cap: Capacity of a vehicle.
M: Number of vehicles are available.
c: Using unit cost per vehicle
dij: distance from node i to node j.
Basic VRP model

Decision variables:
 Xij: Xij= 1 if vehicle transports from i to j; 0; otherwise.
 Ui: Load on vehicle after visiting each node.
Basic VRP model

Objective:
The objective is to minimize transportation and used truck costs.

i=n j =n j =n

 
i =1 j = 2( i  j )
d ij  X ij +  c  X 1 j
j =2
Basic VRP model

Subject to:
i=n


i =1(i  j)
X ij = 1 j  C , j  1

j =n

 X ij = 1 i  C , i  1
j =1( i  j )

Equation 2 and Equation 3 mean each node is linked with two other nodes.
Basic VRP model

Subject to:

j =n j =n

X 1j =  X j1  M i, j  C , i & j  1, i  j
j =2 j =2

Equation 4 all route of AGVs begins and finishes at node 1st and the total of used AGVs must
be less than the number of available AGVs.
Basic VRP model

Subject to:

U j  U i − Di + Cap  (1 − X ij ) j  C , j  1

Equation 5: vehicle load; it guarantees that the remaining load on vehicle after visiting a node
is equal to load on vehicle pervious deducts demand.
Basic VRP model

Subject to:

U j  Cap j  C

Equation 6: Vehicle capacity needs to be satisfied.

Basic VRP model

Subject to:

j =n

U
j =2
j  Dj j  C , j  1

Equation 7 guarantees that the vehicle load enough to satisfy the demand.
Basic VRP model

Subject to:

Xij: binary, Ui ≥ 0

Decision variables Ui are positive and the decision variables Xij to be binary is presented in
Equation 8.
 Capacitated vehicle
routing

Vehicle routing with Distance-constrained

time window vehicle routing
Basic VRP

VRP with stochastic

travel time
Uncertainty in VRP
Chance-constrained
model
Dynamic VRP