Multi Objective Optimisation (MOO)| Data Science Optimisation| Vehicle Routing Problem 🚚

In this post I am going to explin and implement a VRP with demand and capacity constraint

What is Vehicle Routing Prolem?

Vehicle Routing Pictorial Illustration

The vehicle routing problem is a combinatorial optimization and integer programming problem which asks “What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?”. It generalises the well-known travelling salesman problem.

So Let me simplify a little bit with an example 👕

Lets consider you have a clothing company 👕 and you take orders online through your website 🖥️

Now you have started getting a bunch of orders (DEMAND) from nearby places ; and these places have some form of identifier which is compleately unique right? example Latitude & Longitude

Now Lets say you are a Data Scientist at the same clothing company, and there are multiple orders waiting to be delivered and the company (clothing company that you work at) have a bunch of vehicles 🚚🚚🚚🚚 🛵🛵🛵 each vehicle have its own limitation on how much packages 📦📦 that it can carry.

Lets say for example a scooter 🛵 can have a really small capacity of holding the packages ; may be around 20–25 package or even less;

Whereas a mini Delivery truck 🚚🚚 can take upto may be around 100 packages.

So the challenge is that you need to design a route for each vehicle 🚚🚚🚚🚚 🛵🛵🛵so that all customers 🧑‍🤝‍🧑🧑‍🤝‍🧑are served, and the number of vehicles (objective 1) along with the total traveled distance (objective 2) by all the vehicles are minimized;

In addition, the capacity of each vehicle 🚚 🛵should not be exceeded 📦📦 (constraint 1).

If you know about travelling salesman problem, now you might be wondering whats the difference between VRP and TSP right? 😕 😕 😕The difference is simple In Travelling Salesman ; There is only one Person who has to travel all the places and minimize his total travelling distance

Unlike TSP, VRP has to deal the same situation but for multiple vehicles/ travellers;

Maybe for convinience you can think of this like: In the initial days company had only one delivery vehicle as years went they had more than 1 vehicle to deliver the packages 📦📦.

Now the exact name for the problem that we are facing is called “Capacitated Vehicle Routing Problem” (CVRP)

The capacitated vehicle routing problem (CVRP) is a VRP in which vehicles with limited carrying capacity need to pick up or deliver items at various locations. The items have a quantity, such as weight or volume, and the vehicles have a maximum capacity that they can carry. The problem is to pick up or deliver the items for the least cost, while never exceeding the capacity of the vehicles.

Vehicle Routing Problem (VRP) is classified an NP-hard problem, which simply said the bigger your options, the cost of finding the best solution will grow tremendously.

The simplest way, and the one which will yield the best result, is to iterate all possible solutions and by appointing scores on each, pick the solution with the highest score!

How hard can it be, right?

Well, again, it’s NP-hard. Specifically in this particular problem, the complexity is at the very least “N!” (read, N factorial where N being the number of locations).

So if we’re going to find the best solution with brute iterations, we’ll be lucky if the number of locations is ≤9 which gives us 362.880 of possibilities. Going to 10 locations, we start talking in millions, 3.628.800 to be precise. And even only 25 locations, it already yields 15.511.210.043.330.985.984.000.000 possibilities,

I don’t even know how to spell it,😕 let’s not even mention >100 locations.

If you’re not keen to wait that long for the best result, and decided that you can be satisfied with the near-best result that is actually achievable, that’s where Google’s OR-Tools came in.

Google OR Tools Logo

Lets solve a problem by using Python 3.x and OR tools:

• Install OR-tools python package with following command

python -m pip install --upgrade --user ortools

This is the Data with Number of vehicle and Capacity of each vehicle being the same

• Vehicle Number: 10 (Total Number of Vehicles available to carry the packages).
• Capacity: 70 (Capacity of each vehicle)
• Customer No: Unique Number given for each customer
• X-coord, Y- cord: the Exact position of customer in term of X, Y Co-ordination system (In real world problem it might be lat, long)

We calculate the distance between the each point/ customer location in Euclidean Distance (Because they are represented in terms of (x,y) cordinates)

Import scipy to calculate euclidean distance and i have created a function to calculate the distance easily (def dist(p1,p2)) which returns euclidean distance between any 2 coordinates

Now the above code will generate a matrix which I have called Distance matrix (dist_mat); which looks ike this:

[ 0.0, 18.681541692269406, 20.615528128088304, 16.1245154965971, 18.110770276274835, 15.132745950421556, 19.0, 16.0, 18.110770276274835, 20.09975124224178, 16.76305461424021, 19.6468827043885, 38.07886552931954, 30.805843601498726, 39.35733730830886, 36.05551275463989, 40.311288741492746, 33.301651610693426, 35.35533905932738, 39.05124837953327, 10.0, 10.198039027185569, 12.165525060596439, 13.0, 15.0, 15.132745950421556] ,
[18.681541692269406, 0.0, 2.0, 3.605551275463989, 3.0, 4.242640687119285, 5.0990195135927845, 5.385164807134504, 7.0, 7.280109889280518, 10.198039027185569, 10.04987562112089, 26.248809496813376, 24.041630560342615, 28.600699292150182, 27.730849247724095, 30.23243291566195, 27.892651361962706, 30.805843601498726, 32.31098884280702, 23.430749027719962, 21.93171219946131, 23.345235059857504, 21.400934559032695, 26.90724809414742, 25.612496949731394],
[ 20.615528128088304, 2.0, 0.0, 5.0, 3.605551275463989, 5.830951894845301, 5.0990195135927845, 6.4031242374328485, 7.280109889280518, 7.0, 10.770329614269007, 10.04987562112089, 25.0, 23.53720459187964, 27.459060435491963, 26.92582403567252, 29.154759474226502, 27.459060435491963, 30.4138126514911, 31.622776601683793, 25.0, 23.430749027719962, 24.758836806279895, 22.67156809750927, 28.284271247461902, 26.90724809414742],
[16.1245154965971, 3.605551275463989, 5.0, 0.0, 2.0, 1.0, 3.605551275463989, 2.0, 4.47213595499958, 5.656854249492381, 7.0, 7.615773105863909, 25.495097567963924, 21.93171219946131, 27.586228448267445, 26.076809620810597, 29.068883707497267, 25.632011235952593, 28.460498941515414, 30.4138126514911, 20.0, 18.439088914585774, 19.79898987322333, 17.804493814764857, 23.345235059857504, 22.02271554554524],
[18.110770276274835, 3.0, 3.605551275463989, 2.0, 0.0, 3.0, 2.23606797749979, 2.8284271247461903, 4.0, 4.47213595499958, 7.280109889280518, 7.0710678118654755, 24.041630560342615, 21.18962010041709, 26.248809496813376, 25.059928172283335, 27.80287754891569, 25.0, 27.892651361962706, 29.546573405388315, 21.633307652783937, 20.0, 21.2602916254693, 19.1049731745428, 24.758836806279895, 23.345235059857504],
[15.132745950421556, 4.242640687119285, 5.830951894845301, 1.0, 3.0, 0.0, 4.47213595499958, 2.23606797749979, 5.0, 6.4031242374328485, 7.0710678118654755, 8.06225774829855, 26.248809496813376, 22.360679774997898, 28.284271247461902, 26.627053911388696, 29.732137494637012, 26.0, 28.792360097775937, 30.886890422961002, 19.209372712298546, 17.69180601295413, 19.1049731745428, 17.204650534085253, 22.67156809750927, 21.400934559032695] ,
[19.0, 5.0990195135927845, 5.0990195135927845, 3.605551275463989, 2.23606797749979, 4.47213595499958, 0.0, 3.0, 2.23606797749979, 2.23606797749979, 5.830951894845301, 5.0, 21.93171219946131, 18.973665961010276, 24.08318915758459, 22.825424421026653, 25.612496949731394, 22.80350850198276, 25.709920264364882, 27.313000567495326, 21.470910553583888, 19.72308292331602, 20.808652046684813, 18.439088914585774, 24.20743687382041, 22.67156809750927] ,
[16.0, 5.385164807134504, 6.4031242374328485, 2.0, 2.8284271247461903, 2.23606797749979, 3.0, 0.0, 2.8284271247461903, 4.47213595499958, 5.0, 5.830951894845301, 24.20743687382041, 20.12461179749811, 26.1725046566048, 24.413111231467404, 27.586228448267445, 23.769728648009426, 26.570660511172846, 28.653097563788805, 18.867962264113206, 17.204650534085253, 18.439088914585774, 16.278820596099706, 21.93171219946131, 20.518284528683193] ,
[18.110770276274835, 7.0, 7.280109889280518, 4.47213595499958, 4.0, 5.0, 2.23606797749979, 2.8284271247461903, 0.0, 2.0, 3.605551275463989, 3.1622776601683795, 21.400934559032695, 17.46424919657298, 23.345235059857504, 21.633307652783937, 24.758836806279895, 21.18962010041709, 24.041630560342615, 25.942243542145693, 19.697715603592208, 17.88854381999832, 18.867962264113206, 16.401219466856727, 22.20360331117452, 20.615528128088304] ,
[ 20.09975124224178, 7.280109889280518, 7.0, 5.656854249492381, 4.47213595499958, 6.4031242374328485, 2.23606797749979, 4.47213595499958, 2.0, 0.0, 5.0, 3.1622776601683795, 19.849433241279208, 16.76305461424021, 21.93171219946131, 20.591260281974, 23.430749027719962, 20.615528128088304, 23.53720459187964, 25.079872407968907, 21.540659228538015, 19.697715603592208, 20.591260281974, 18.027756377319946, 23.853720883753127, 22.20360331117452] ,
[ 16.76305461424021, 10.198039027185569, 10.770329614269007, 7.0, 7.280109889280518, 7.0710678118654755, 5.830951894845301, 5.0, 3.605551275463989, 5.0, 0.0, 3.0, 21.470910553583888, 15.811388300841896, 23.021728866442675, 20.518284528683193, 24.20743687382041, 19.235384061671343, 21.93171219946131, 24.413111231467404, 16.76305461424021, 14.866068747318506, 15.652475842498529, 13.038404810405298, 18.867962264113206, 17.204650534085253] ,
[ 19.6468827043885, 10.04987562112089, 10.04987562112089, 7.615773105863909, 7.0710678118654755, 8.06225774829855, 5.0, 5.830951894845301, 3.1622776601683795, 3.1622776601683795, 3.0, 0.0, 18.867962264113206, 14.317821063276353, 20.615528128088304, 18.601075237738275, 21.93171219946131, 18.027756377319946, 20.8806130178211, 22.825424421026653, 19.6468827043885, 17.72004514666935, 18.384776310850235, 15.652475842498529, 21.470910553583888, 19.72308292331602],
[38.07886552931954, 26.248809496813376, 25.0, 25.495097567963924, 24.041630560342615, 26.248809496813376, 21.93171219946131, 24.20743687382041, 21.400934559032695, 19.849433241279208, 21.470910553583888, 18.867962264113206, 0.0, 10.44030650891055, 3.0, 7.0710678118654755, 5.0, 12.206555615733702, 14.142135623730951, 11.180339887498949, 35.35533905932738, 33.37663853655727, 33.13608305156178, 30.14962686336267, 35.0, 33.0] ,
[30.805843601498726, 24.041630560342615, 23.53720459187964, 21.93171219946131, 21.18962010041709, 22.360679774997898, 18.973665961010276, 20.12461179749811, 17.46424919657298, 16.76305461424021, 15.811388300841896, 14.317821063276353, 10.44030650891055, 0.0, 10.0, 5.385164807134504, 10.198039027185569, 4.0, 7.0, 8.602325267042627, 26.248809496813376, 24.351591323771842, 23.769728648009426, 20.8806130178211, 25.179356624028344, 23.194827009486403] ,
[39.35733730830886, 28.600699292150182, 27.459060435491963, 27.586228448267445, 26.248809496813376, 28.284271247461902, 24.08318915758459, 26.1725046566048, 23.345235059857504, 21.93171219946131, 23.021728866442675, 20.615528128088304, 3.0, 10.0, 0.0, 5.385164807134504, 2.0, 10.770329614269007, 12.206555615733702, 8.602325267042627, 35.90264614203248, 33.95585369269929, 33.54101966249684, 30.59411708155671, 35.12833614050059, 33.13608305156178] ,
[ 36.05551275463989, 27.730849247724095, 26.92582403567252, 26.076809620810597, 25.059928172283335, 26.627053911388696, 22.825424421026653, 24.413111231467404, 21.633307652783937, 20.591260281974, 20.518284528683193, 18.601075237738275, 7.0710678118654755, 5.385164807134504, 5.385164807134504, 0.0, 5.0, 5.385164807134504, 7.0710678118654755, 5.0, 31.622776601683793, 29.732137494637012, 29.120439557122072, 26.248809496813376, 30.4138126514911, 28.442925306655784],
[ 40.311288741492746, 30.23243291566195, 29.154759474226502, 29.068883707497267, 27.80287754891569, 29.732137494637012, 25.612496949731394, 27.586228448267445, 24.758836806279895, 23.430749027719962, 24.20743687382041, 21.93171219946131, 5.0, 10.198039027185569, 2.0, 5.0, 0.0, 10.198039027185569, 11.180339887498949, 7.0710678118654755, 36.40054944640259, 34.48187929913333, 33.95585369269929, 31.04834939252005, 35.35533905932738, 33.37663853655727] ,
[33.301651610693426, 27.892651361962706, 27.459060435491963, 25.632011235952593, 25.0, 26.0, 22.80350850198276, 23.769728648009426, 21.18962010041709, 20.615528128088304, 19.235384061671343, 18.027756377319946, 12.206555615733702, 4.0, 10.770329614269007, 5.385164807134504, 10.198039027185569, 0.0, 3.0, 5.830951894845301, 27.730849247724095, 25.942243542145693, 25.079872407968907, 22.360679774997898, 25.96150997149434, 24.041630560342615] ,
[35.35533905932738, 30.805843601498726, 30.4138126514911, 28.460498941515414, 27.892651361962706, 28.792360097775937, 25.709920264364882, 26.570660511172846, 24.041630560342615, 23.53720459187964, 21.93171219946131, 20.8806130178211, 14.142135623730951, 7.0, 12.206555615733702, 7.0710678118654755, 11.180339887498949, 3.0, 0.0, 5.0, 29.154759474226502, 27.459060435491963, 26.419689627245813, 23.853720883753127, 26.92582403567252, 25.079872407968907],
[39.05124837953327, 32.31098884280702, 31.622776601683793, 30.4138126514911, 29.546573405388315, 30.886890422961002, 27.313000567495326, 28.653097563788805, 25.942243542145693, 25.079872407968907, 24.413111231467404, 22.825424421026653, 11.180339887498949, 8.602325267042627, 8.602325267042627, 5.0, 7.0710678118654755, 5.830951894845301, 5.0, 0.0, 33.54101966249684, 31.76476034853718, 30.870698080866262, 28.178005607210743, 31.622776601683793, 29.732137494637012],
[10.0, 23.430749027719962, 25.0, 20.0, 21.633307652783937, 19.209372712298546, 21.470910553583888, 18.867962264113206, 19.697715603592208, 21.540659228538015, 16.76305461424021, 19.6468827043885, 35.35533905932738, 26.248809496813376, 35.90264614203248, 31.622776601683793, 36.40054944640259, 27.730849247724095, 29.154759474226502, 33.54101966249684, 0.0, 2.0, 2.8284271247461903, 5.385164807134504, 5.0, 5.385164807134504] ,
[10.198039027185569, 21.93171219946131, 23.430749027719962, 18.439088914585774, 20.0, 17.69180601295413, 19.72308292331602, 17.204650534085253, 17.88854381999832, 19.697715603592208, 14.866068747318506, 17.72004514666935, 33.37663853655727, 24.351591323771842, 33.95585369269929, 29.732137494637012, 34.48187929913333, 25.942243542145693, 27.459060435491963, 31.76476034853718, 2.0, 0.0, 2.0, 3.605551275463989, 5.385164807134504, 5.0] ,
[12.165525060596439, 23.345235059857504, 24.758836806279895, 19.79898987322333, 21.2602916254693, 19.1049731745428, 20.808652046684813, 18.439088914585774, 18.867962264113206, 20.591260281974, 15.652475842498529, 18.384776310850235, 33.13608305156178, 23.769728648009426, 33.54101966249684, 29.120439557122072, 33.95585369269929, 25.079872407968907, 26.419689627245813, 30.870698080866262, 2.8284271247461903, 2.0, 0.0, 3.0, 3.605551275463989, 3.0] ,
[13.0, 21.400934559032695, 22.67156809750927, 17.804493814764857, 19.1049731745428, 17.204650534085253, 18.439088914585774, 16.278820596099706, 16.401219466856727, 18.027756377319946, 13.038404810405298, 15.652475842498529, 30.14962686336267, 20.8806130178211, 30.59411708155671, 26.248809496813376, 31.04834939252005, 22.360679774997898, 23.853720883753127, 28.178005607210743, 5.385164807134504, 3.605551275463989, 3.0, 0.0, 5.830951894845301, 4.242640687119285],
[ 15.0, 26.90724809414742, 28.284271247461902, 23.345235059857504, 24.758836806279895, 22.67156809750927, 24.20743687382041, 21.93171219946131, 22.20360331117452, 23.853720883753127, 18.867962264113206, 21.470910553583888, 35.0, 25.179356624028344, 35.12833614050059, 30.4138126514911, 35.35533905932738, 25.96150997149434, 26.92582403567252, 31.622776601683793, 5.0, 5.385164807134504, 3.605551275463989, 5.830951894845301, 0.0, 2.0],
[ 15.132745950421556, 25.612496949731394, 26.90724809414742, 22.02271554554524, 23.345235059857504, 21.400934559032695, 22.67156809750927, 20.518284528683193, 20.615528128088304, 22.20360331117452, 17.204650534085253, 19.72308292331602, 33.0, 23.194827009486403, 33.13608305156178, 28.442925306655784, 33.37663853655727, 24.041630560342615, 25.079872407968907, 29.732137494637012, 5.385164807134504, 5.0, 3.0, 4.242640687119285, 2.0, 0.0]
]

If we change the customer id to their city name and insert into a excel sheet this data would look somewhat like this:

dist_mat

To generate the matrix, there are multiple ways, some can be paid such as Google’s Direction Service or Mapbox’s Direction API, or some can be done using open source such as OpenRouteService, or you can even calculate the Great Circle Distance between the coordinates.

So Now its time to Use OR Tools; create a new .py file and import it with following commands:

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

Here I have created a JSON and added following fields:

• distance_matrix
• demands
• vehicle_capacities
• num_vehicles
• depot (Where all the vehicles starts and ends their Journey)

Result:

Expected Errors:

1.

ERROR: Could not find a version that satisfies the requirement ortools (from versions: none)
ERROR: No matching distribution found for ortools

Soln: Check for Python vresion; and if its 3.8 or above then try downgrading python version

2.

ORtools compiled against version 3.5.1 of protocol buffer, not compatible with installed version

Soln: conda install python==3.6.8

QUICK NOTE:

If you are excited about introducing Reinforcement Learning to solve this problem Please wait for my Next Post😊

If you made it till the end please dont forget to give it a clap 👏👏😊