Vehicle Routing in Transportation Networks

ENGG1400
David Rey
Research Center for Integrated Transport Innovation (rCITI)
School of Civil and Environmental Engineering
UNSW Australia

The Vehicle Routing Problem

Mathematical Formulation

Outline

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Outline

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

History

The Vehicle Routing Problem was first introduced by Dantzig

and Ramser in 1959 as a combinatorial optimization problem.

Generally the context of VRP is that of delivering goods
located in a central depot to a list of customers which have
placed orders for these goods.

This problem can be encountered in the fields of

Transportation, Distribution and Logistics. This problem is

generally hard to solve for a large number of customers.

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Introduction of Vehicle Routing in Networks

Finding the shortest tour to visit all nodes in a network

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Introduction of Vehicle Routing in Networks

Finding the shortest tour to visit all nodes in a network

The tour starts and ends at the depot

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Introduction of Vehicle Routing in Networks

Finding the shortest tour to visit all nodes in a network

The tour starts and ends at the depot

In its most simple version (one vehicle, no capacity), the VRP

is equivalent to the Travelling Salesman Problem (TSP)

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Introduction of Vehicle Routing in Networks

Finding the shortest tour to visit all nodes in a network

The tour starts and ends at the depot

In its most simple version (one vehicle, no capacity), the VRP

is equivalent to the Travelling Salesman Problem (TSP)

TSP is a NP-hard optimization problem, hence VRP is also

NP-hard

A NP-hard problem is a problem for which there is no known polynomial algorithm

The Vehicle Routing Problem

Mathematical Formulation

Vehicle Routing is a Hard Problem

Why is it hard?

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Vehicle Routing is a Hard Problem

Why is it hard?

3 nodes VRP:
Depot (0)

c 12

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Vehicle Routing is a Hard Problem

Why is it hard?

3 nodes VRP:

Paths

Depot (0)

0-123-0
0-132-0
0-213-0

0-231-0
3

c 12

0-312-0
0-321-0

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Vehicle Routing is a Hard Problem

Why is it hard?

3 nodes VRP:

Paths

Depot (0)

0-123-0
0-132-0
0-213-0

0-231-0
3

c 12

0-312-0
0-321-0

For N nodes there are N!

combinations
N
3
4
5
10
100

N! = 1 2 . . . N
6
24
120
3628800
9.332622 10157

The Vehicle Routing Problem

Mathematical Formulation

Outline

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Mathematical Formulation of a basic VRP

Sets and Parameters
G = (N, A) complete network, i.e. every pair of nodes is
linked by two arcs (1 to 2 and 2 to 1)
[tij ] is the cost matrix where i, j N and (i, j) A
K is the set of available vehicles

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Mathematical Formulation of a basic VRP

Sets and Parameters
G = (N, A) complete network, i.e. every pair of nodes is
linked by two arcs (1 to 2 and 2 to 1)
[tij ] is the cost matrix where i, j N and (i, j) A
K is the set of available vehicles

Decision Variables
xijk

1
0

if (i, j) A belongs to the tour of vehicle k K

otherwise

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Objective
The most common objective is to minimize the total transportation
cost (travel time or other) defined by the cost matrix [tij ].

Objective function
z = min

X X

tij xijk

(i,j)A kK

z is equal to the sum of the transportation cost of every tour.

Notation:

(i,j)A

sum over all arcs in the network

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Vehicle Routing Constraints (1)

Flow Conservation Constraints
The nb. of vehicles entering and the nb. of vehicles exiting each
node must the same (similar to Kirchhoffs circuit laws in
electricity).
X
X
xjik = 0
i N, k K
xijk
(i,j)A

(j,i)A

WRONG!!

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Vehicle Routing Constraints (2)

Depot Constraints
Let 0 represent the depot node, each vehicle must leave and come
back to the depot.
X
X
k
k
x0j
= 1 and
xi0
= 1 k K
(0,j)A

(i,0)A

Depot (0)

Depot (0)

vehicle 1 tour
vehicle 2 tour

?
1

?
?

?
?

WRONG!!
2

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Vehicle Routing Constraints (3)

Node Degree Constraints
Let Nc = N \ {0} be the set of customer nodes. Each node must
be visited exactly once and by one vehicle only.
X X
X X
xjik = 1
i Nc
xijk = 1 and
(j,i)A kK

(i,j)A kK

vehicle 1 tour

Depot (0)

Depot (0)

vehicle 2 tour

WRONG!!
2

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Model for the basic VRP?

z = min

X X

tij xijk

(i,j)A kK

subject to

X X

xijk =1

i Nc

xjik =1

i Nc

k
xi0
=1

k K

xjik =0

i N, k K

xijk {0, 1}

(i, j) A, k K

(i,j)A kK

X X

(j,i)A kK

k
x0j
=

(0,j)A

(i,j)A

(i,0)A

xijk

(j,i)A

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Model for the basic VRP?

z = min

X X

tij xijk

(i,j)A kK

subject to

X X

xijk =1

i Nc

xjik =1

i Nc

k
xi0
=1

k K

xjik =0

i N, k K

xijk {0, 1}

(i, j) A, k K

(i,j)A kK

X X

(j,i)A kK

k
x0j
=

(0,j)A

(i,j)A

(i,0)A

xijk

(j,i)A

The solutions of this program can contain subtours

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Example
Assume that there is a single vehicle to route:
Depot (0)

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Example
The previous model for the VRP may produce to subtours
Depot (0)
vehicle 1 tour

subtour

Observe that all constraints are satisfied: Flow conservation

constraints, depot constraints, node degree constraints.

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Subtour Elimination
S={1,2,3}:
It is necessary to eliminate
subtours among customers
nodes

Let S Nc , S has to be
traversed by less than |S| 1 arcs
2

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Subtour Elimination
S={1,2,3}:
It is necessary to eliminate
subtours among customers
nodes

x 12 =1

Let S Nc , S has to be
traversed by less than |S| 1 arcs

x 23 =1

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Subtour Elimination
S={1,2,3}:
It is necessary to eliminate
subtours among customers
nodes

x 12 =1

Let S Nc , S has to be
traversed by less than |S| 1 arcs

x 23 =1

Subtour Constraints
X

(i,j)A:i,jS

xijk |S| 1

S Nc , k K

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Model for the basic VRP

z = min

X X

tij xijk

(i,j)A kK

subject to

X X

xijk =1

i Nc

xjik =1

i Nc

k
xi0
=1

k K

xjik =0

i N, k K

xijk |S| 1

S Nc , k K

xijk {0, 1}

(i, j) A, k K

(i,j)A kK

X X

(j,i)A kK

k
x0j
=

(0,j)A

(i,j)A

(i,0)A

xijk

(j,i)A

(i,j)A:i,jS

Applications

The Vehicle Routing Problem

Mathematical Formulation

Example
Network and costs:
Depot (0)

2
2

6
1

6
1

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Example
1 vehicle:
x
0
1
2
3
4

Depot (0)
vehicle 1 tour

2
2

6
1

1
1
0
0
0

2
0
1
0
0

3
0
0
1
0

4
0
0
0
1
-

Optimal tour: z = 12,

0
0
0
0
1

Path 0-1234-0

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Example
2 vehicles:
Depot (0)
vehicle 1 tour

Optimal tours: z = 5 + 5 = 10

vehicle 2 tour

k = 0 0-12-0,
k = 1 0-43-0,

6
1

6
1

The Vehicle Routing Problem

Mathematical Formulation

Outline

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Capacitated VRP (CVRP)

Assume every node is a customer and every visit corresponds to a
product delivery.

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Capacitated VRP (CVRP)

Assume every node is a customer and every visit corresponds to a
product delivery.

If every costumer has a specific demand, qi 0, then vehicles

have a limited capacity, ck 0, and the total demand for every
tour is bounded by this capacity.

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Capacitated VRP (CVRP)

Assume every node is a customer and every visit corresponds to a
product delivery.

If every costumer has a specific demand, qi 0, then vehicles

have a limited capacity, ck 0, and the total demand for every
tour is bounded by this capacity.
Capacity constraints
X

(i,j)A

xijk qi ck

k K

The Vehicle Routing Problem

Mathematical Formulation

Example: CVRP
With capacity and demand:
Depot (0)

2
2

1
(80)

6
6
1

4
(50)

6
1

2
(100)

3
(30)
vehicle capacity = 130
customer demand = (i)

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Example: CVRP
Previous solution:
Depot (0)
vehicle 1 tour

Previous cost: z = 5 + 5 = 10

vehicle 2 tour

1
(80)

k = 0 0-12-0,
k = 1 0-43-0,

6
6
1

4
(50)

6
1

2
(100)

3
(30)
vehicle capacity = 130
customer demand = (i)

...but infeasible (capacity

violation)!

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Example: CVRP
New solution:
Depot (0)
vehicle 1 tour

Optimal tours:
z = 10 + 10 = 20

vehicle 2 tour

2
2

1
(80)

6
6
1

4
(50)

6
1

2
(100)

3
(30)
vehicle capacity = 130
customer demand = (i)

k = 0 0-14-0,
k = 1 0-23-0,
...more expensive but feasible.

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Major VRP Variants

Vehicle capacity and customer demand (CVRP)
Heterogeneous fleet of vehicles (HVRP)
Tour duration constraint (DVRP)
Time windows for deliveries (VRPTW)
Vehicle routing over a period (PVRP)
Multi-Depot scenario (MDVRP)
Arc Routing Problem (ARP)

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Solution Methods
1

Heuristics
Problem-Specific (Tree Network, Schedule Assignment,...)
Nodes Clustering
Minimum Spanning Tree algorithms can be used to determine

bounds on TSP relaxation

2

Metaheuristics

Genetic Algorithms
Ant Colony Optimization
Tabu Search
Swarm Particles

Exact Algorithms
Branch & Bound & Cut (CPLEX)
Branch & Price
Decomposition Methods

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

In the VRP Workshop

Solution approach:
Start by solving a VRP model without any subtour elimination

constraints
Study how we can incrementally add subtour elimination

constraints to a VRP model:

1
2

detect existing subtours

add the corresponding constraints

Exact solution method but could be relatively slow in complex

VRP instances

The Vehicle Routing Problem

Mathematical Formulation

Outline

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Applications

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Fuel Delivery

Capacitated
Time Windows: operate at night time

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Waste Management

Capacitated
Arc Routing: visit streets instead of points

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Post Logistics

Mail pick-up and delivery

Node and Arc Routing: visit streets and points

Applications

The Vehicle Routing Problem

Mathematical Formulation

Ready-Mixed Concrete Delivery

Multiple visits
Tour duration: perishable good

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Medical Supply

Periodic visits
Emergency dispatching

Extensions of the VRP

Applications

The Vehicle Routing Problem

Mathematical Formulation

Extensions of the VRP

Bibliography

The Vehicle Routing Problem: An overview of exact and

approximate algorithms, [Link] (EJOR, 2001)

The Vehicle Routing Problem, P. Toth and D. Vigo (SIAM,

2002)
The Vehicle Routing Problem: Latest Advances and New

Challenges, B. Golden, S. Raghavan, E. Wasil (Springer

OR/CS, 2008)

Applications