Session 6 - Vehicle Routing Problem

Session 6 - The Vehicle Routing Problem #

Dr Jose Escribano

This session expands upon the Travelling Salesman Problem (TSP) that we covered last week, focusing on the Vehicle Routing Problem (VRP). The VRP is a generalised version of TSP and incorporates decision aspects such as vehicle capacity and range in the decision-making process.

The VRP is one of the most fundamental decision problems in the field of freight distribution. A wide range of variations have been developed that incorporate practical routing considerations that arise in the logistics sector.

Today’s section will focus on VRP principles and its mathematical representation. We will also discussing a few common VRP variations, such as Fleet Mix VRP, VRP with Time Windows, and the Green VRP (commonly used to study the impacts of electric vehicle adoptions in the logistics sector).

Part 1 - Multiple Travelling Salesman Problem #

This session focuses on the Travelling Salesman problem when considering multiple tours.

Download slides

View in Panopto

Part 2 - Vehicle Routing Problem #

The generalised version of the Multiple Travelling Salesman Problem takes the form of the Vehicle Routing Problem.

We propose two heuristic methods to solve the VRP: the sweep algorithm and the savings method, analysing their advantages and drawbacks.

Download slides

View in Panopto

Part 3 - Fleet Mix #

We now consider the Fleet Mix Vehicle Routing Problem, which focuses on the determination of a specific fleet composition for a given distribution scenario.

Download slides

View in Panopto

Part 4 - Vehicle Routing Problem Extensions #

This session focuses on the formulation of the Vehicle Routing Problem with Time Windows and Speed control.

Download slides

View in Panopto

Part 5 - Green VRP #

Finally, we look at Vehicle Routing Problem with recharge.

Download slides

View in Panopto

Jupyter Notebooks #

This week’s notebooks focus on the methods to solve the different iterations of the VRP studied in this session.

These notebooks include PuLP implementations of the VRP instances seen in this session, as well as a Sweep, Savings, and Genetic Algorithm implementation.

The notebooks can be downloaded here

Tutorial session #

Tutorial 6 - Questions

Tutorial 6 - Answers

View in Panopto

Files #

You can find a list of all files that we used this week here (Box).