Vehicle routing optimisation in ZIO 2 / Scala 3
Introduction
This article describes a toy implementation of the capacitated vehicle routing problem in scala 3 / ZIO 2.0.
ZIO is a purely functional, type-safe, composable library for asynchronous, concurrent programming in Scala
Vehicle routing problem
The vehicle routing problem (VRP) is a 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 travelling salesman problem (TSP). Determining the optimal solution to VRP is NP-hard. Simply put, it will take an extremely long time to calculate the optimal solution if your problem context (routes / customers / constraints) becomes large. This is a typical exponential problem.
We see examples of VRP every day:
- Meal prep companies delivering food from central kitchens to hungry homes
- Delivery vans that bring you groceries from local stores
- Couriers who deliver packages to your office
Essentially, you have a fleet of vehicles and a collection of stops. You’re trying to figure out:
- Which vehicle should I assign to each stop?
- What order should the vehicles visit those stops to minimize distance (while satisfying any other constraints you might have)
The problem statement is easy to put together. It’s the solutions that are difficult to find. So.. It’s okay if you’ve been struggling to plan your routes efficiently.
Planning routes isn’t hard, which is why people have been able to do things manually for so long. The difficult part is planning optimized routes, and when you add constraints that are important for your business, planning optimized routes gets nearly impossible for a human to do without some help.
Constraints
In this example we are going to optimise the total distance and you can define the following constraints in our example:
General constraints:
- How long can our optimisation algorithm take in seconds?
Customer specific constraints:
- What capacity in grams in needed for serving the customer that day?
Vehicle specific constraints:
- What is the capacity of the vehicle in grams?
Fleet constraints:
- What is the maximum kilometers a vehicle can drive on one day?
- What is the maximum stop count for a vehicle on one day?
Architecture
The code is written in the ZIO 2.0 ecosystem and consists of the following main components:
- ZIO HTTP : Webserver
- ZIO-JSON : Parsing / generating JSON
- Google OR-tools : Optimisation library
- Radar Backend : To optimize we need distances between the depot and the customers. In this implementation we are using the Radar.com (https://radar.com/) API for getting distance matrices. The free account is limited with 100,000 monthly calls and you can pass the key as an environment variable with the name GEO_KEY to the application / docker image.
Code
All the code can be found on my github https://github.com/kristofsl/VRS and inside the src/resources/instruction.txt you can find the detailed instructions for compiling / running the container
Usage
- clean : sbt clean
- compile : sbt compile
- assembly of fat jar : sbt assembly
- creation docker container : docker buildx build — platform linux/amd64 -f ./project/dockerfile -t zio-vrs:1.0 .
- run the container : docker run -d — name zio-vrs — restart unless-stopped -e “GEO_KEY=?” zio-vrs:1.0
Remark : replace the ? with a free valid radar API key
Example request / response
In the below example you can find a sample request / response. All the fields are required.
Request:
{
"locations": [
{
"location": {
"latitude": 51.24601563591366,
"longitude": 4.416294928800372
},
"name": "customer_1",
"uid": "c_1",
"weightInGramConstraint": 20000
},
{
"location": {
"latitude": 50.93021966123263,
"longitude": 5.36893267535137
},
"name": "customer_2",
"uid": "c_2",
"weightInGramConstraint": 30000
},
{
"location": {
"latitude": 51.10163546963735,
"longitude": 5.789792511606002
},
"name": "customer_3",
"uid": "c_3",
"weightInGramConstraint": 70000
}
],
"depotLocation": {
"location": {
"latitude": 50.907600055332146,
"longitude": 5.345893584612312
},
"name": "depot",
"uid": "d_1"
},
"vehicles": [
{
"vehicleIdentifier": "small_truck_0002",
"driverName" : "Pierre",
"capacityInGrams": 4000000
},
{
"vehicleIdentifier": "small_car_0003",
"driverName" : "Jef",
"capacityInGrams": 200000
}
],
"maxCustomerStops": 10,
"maxKm": 400,
"secondsOptimizationLimit": 60
}Response:
{
"objectiveValue": 16945094,
"usedVehicleCount": 2,
"totalKm": 267.0,
"availableVehicleCount": 2,
"maxKmVehicle": 400,
"maxCustomerStopCount": 10,
"routes": [
{
"vehicleId": 0,
"vehicleIdentifier": "small_truck_0002",
"driverName": "Pierre",
"distanceKm": 100.0,
"customerStopCount": 2,
"tour": [
{
"location": {
"latitude": 50.9076,
"longitude": 5.3458934
},
"name": "depot",
"uid": "d_1",
"weightInGramConstraint": 0
},
{
"location": {
"latitude": 51.101635,
"longitude": 5.7897925
},
"name": "customer_3",
"uid": "c_3",
"weightInGramConstraint": 70000
},
{
"location": {
"latitude": 50.93022,
"longitude": 5.3689327
},
"name": "customer_2",
"uid": "c_2",
"weightInGramConstraint": 30000
},
{
"location": {
"latitude": 50.9076,
"longitude": 5.3458934
},
"name": "depot",
"uid": "d_1",
"weightInGramConstraint": 0
}
],
"totalWeightInGrams": 100000,
"vehicleCapacityInGrams": 4000000
},
{
"vehicleId": 1,
"vehicleIdentifier": "small_car_0003",
"driverName": "Jef",
"distanceKm": 166.0,
"customerStopCount": 1,
"tour": [
{
"location": {
"latitude": 50.9076,
"longitude": 5.3458934
},
"name": "depot",
"uid": "d_1",
"weightInGramConstraint": 0
},
{
"location": {
"latitude": 51.246017,
"longitude": 4.416295
},
"name": "customer_1",
"uid": "c_1",
"weightInGramConstraint": 20000
},
{
"location": {
"latitude": 50.9076,
"longitude": 5.3458934
},
"name": "depot",
"uid": "d_1",
"weightInGramConstraint": 0
}
],
"totalWeightInGrams": 20000,
"vehicleCapacityInGrams": 200000
}
],
"durationMinutes": 0
}