September 27, 2021

Introduction to Vehicle Routing with Python

This tutorial provides you with an overview of the Vehicle Routing Problem(VRP) and helps you understand the core concepts. In the next tutorials we would then see how we can solve this problem using Python

  1. Overview of Vehicle Routing
  2. Travelling Salesman Problem(TSP)
  3. Types of Vehicle Routing Problem

 

1. Overview of Vehicle Routing

In a vehicle routing problem, we have a vehicle moving from point A to point B. Between these two points, there are several routes. The goal is to find the best of these routes. However, in real world scenario, we often would have not just one vehicle, but a fleet of vehicles and a set locations.

Then we need to find the best routes for these vehicles.

  • An example is a package delivery company needing to assign routes to drivers to make deliveries.
  • Another example is a taxi company that needs to assign routes to drivers to pick up and drop off passengers

There are a number of ways to approach this problem but most common is the Travelling Salesman Problem(TSP) algorithm

 

2. Travelling Salesman Problem(TSP)

The objective of the TSP is to find the shortest route for a salesman who needs to visit different customers at various locations and then return to his starting point. The TSP could be represented by a graph where the nodes correspond to the locations whiles the edges depict the travel distance (or cost) to move between the locations. A 4-node TSP is shown in below with locations labelled A, B, C and D. The cost of each edge is given by a number written against that edge.

In this example, we find the shortest route by calculating all possible routes and we see that the shortest route is A-C-D-B-D with total distance of 35 + 30 + 15 + 10 = 90.

4-Node Travelling Salesman Problem
4-Node Travelling Salesman Problem

 

If however, there are many more locations, then the problem becomes more difficult and therefore we need a more efficient approach. Certain constraints may be applied to help reduced the search space of the problem. Some are given in the next sub-section

 

3. Types of Vehicle Routing Problem

We outline six categories of the VRP that would be covering in these series of tutorials.

  • Travelling Salesman Problem – this is be basic routing problem where just one vehicle is involved
  • Vehicle Routing Problem – in this case the TSP is generalized with multiple vehicles
  • VRP with time windows – here, the vehicles are required to visit the locations only at certain time intervals
  • VRP with dropped visits – in this type, the vehicles are not required to visit all the locations. They must pay some kind of penalty for each visit dropped
  • VRP with capacity constraints – here, the vehicles have maximum capacities of the items they would carry
  • VRP with resource constraints – here the available resources (such as personnel) is limited in some way

We would now see how to solve each type of TSP problem in Python.

0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments