Note: All notebooks need theenvironment dependenciesas well as anopenrouteservice API key to run
Routing optimization generally solves theVehicle Routing Problem(a simple example being the more widely knownTraveling Salesman Problem).A more complex example would be the distribution of goods by a fleet of multiple vehicles to dozens of locations,where each vehicle has certain time windows in which it can operate and each delivery location has certain time windowsin which it can be served (e.g. opening times of a supermarket).
In this example we'll look at a real-world scenario ofdistributing medical goods during disaster responsefollowing one of the worst tropical cyclones ever been recorded in Africa:Cyclone Idai.
Cyclone Idai floods in false color image on 19.03.2019; © Copernicus Sentinel-1 -satellite (modified Copernicus Sentinel data (2019), processed by ESA, CC BY-SA 3.0 IGO),source
In this scenario, a humanitarian organization shipped much needed medical goods to Beira, Mozambique, which were thendispatched to local vehicles to be delivered across the region.The supplies included vaccinations and medications for water-borne diseases such as Malaria and Cholera,so distribution efficiency was critical to contain disastrous epidemics.
We'll solve this complex problem with theoptimization endpoint ofopenrouteservice.
importfoliumfromfolium.pluginsimportBeautifyIconimportpandasaspdimportopenrouteserviceasors
In total 20 sites were identified in need of the medical supplies, while 3 vehicles were scheduled for delivery.Let's assume there was only one type of goods, e.g. standard moving boxes full of one medication.(In reality there were dozens of different good types, which can be modelled with the same workflow,but that'd unnecessarily bloat this example).
Thevehicles were all located in the port of Beira and had the same following constraints:
Thedelivery locations were mostly located in the Beira region, but some extended ~ 200 km to the north of Beira.Their needs range from 10 to 148 units of the arbitrary medication goods(consult the file located at../resources/data/idai_health_sites.csv). Let's look at it in a map.
# First define the map centered around Beiram=folium.Map(location=[-18.63680,34.79430],tiles='cartodbpositron',zoom_start=8)# Next load the delivery locations from CSV file at ../resources/data/idai_health_sites.csv# ID, Lat, Lon, Open_From, Open_To, Needed_Amountdeliveries_data=pd.read_csv('../resources/data/idai_health_sites.csv',index_col="ID",parse_dates=["Open_From","Open_To"])# Plot the locations on the map with more info in the ToolTipforlocationindeliveries_data.itertuples():tooltip=folium.map.Tooltip("<h4><b>ID{}</b></p><p>Supplies needed: <b>{}</b></p>".format(location.Index,location.Needed_Amount))folium.Marker(location=[location.Lat,location.Lon],tooltip=tooltip,icon=BeautifyIcon(icon_shape='marker',number=int(location.Index),spin=True,text_color='red',background_color="#FFF",inner_icon_style="font-size:12px;padding-top:-5px;")).add_to(m)# The vehicles are all located at the port of Beiradepot=[-19.818474,34.835447]folium.Marker(location=depot,icon=folium.Icon(color="green",icon="bus",prefix='fa'),setZIndexOffset=1000).add_to(m)m
Now that we have described the setup sufficiently, we can start to set up our actual Vehicle Routing Problem.For this example we're using the FOSS library ofVroom, which hasrecently seen support foropenrouteservice and is available through our APIs.
To properly describe the problem in algorithmic terms, we have to provide the following information:
We defined all these parameters either in code above or in the data sheet located in../resources/data/idai_health_sites.csv.Now we have to only wrap this information into our code and send a request to openrouteservice optimization service athttps://api.openrouteservice.org/optimization.
# Define the vehicles# https://openrouteservice-py.readthedocs.io/en/latest/openrouteservice.html#openrouteservice.optimization.Vehiclevehicles=list()foridxinrange(3):vehicles.append(ors.optimization.Vehicle(id=idx,start=list(reversed(depot)),# end=list(reversed(depot)),capacity=[300],time_window=[1553241600,1553284800]# Fri 8-20:00, expressed in POSIX timestamp))# Next define the delivery stations# https://openrouteservice-py.readthedocs.io/en/latest/openrouteservice.html#openrouteservice.optimization.Jobdeliveries=list()fordeliveryindeliveries_data.itertuples():deliveries.append(ors.optimization.Job(id=delivery.Index,location=[delivery.Lon,delivery.Lat],service=1200,# Assume 20 minutes at each siteamount=[delivery.Needed_Amount],time_windows=[[int(delivery.Open_From.timestamp()),# VROOM expects UNIX timestampint(delivery.Open_To.timestamp())]]))
With that set up we can now perform the actual request and let openrouteservice calculate the optimal vehicle schedulefor all deliveries.
# Initialize a client and make the requestors_client=ors.Client(key='your_key')# Get an API key from https://openrouteservice.org/dev/#/signupresult=ors_client.optimization(jobs=deliveries,vehicles=vehicles,geometry=True)# Add the output to the mapforcolor,routeinzip(['green','red','blue'],result['routes']):decoded=ors.convert.decode_polyline(route['geometry'])# Route geometry is encodedgj=folium.GeoJson(name='Vehicle{}'.format(route['vehicle']),data={"type":"FeatureCollection","features":[{"type":"Feature","geometry":decoded,"properties":{"color":color}}]},style_function=lambdax:{"color":x['properties']['color']})gj.add_child(folium.Tooltip("""<h4>Vehicle {vehicle}</h4> <b>Distance</b> {distance} m <br> <b>Duration</b> {duration} secs """.format(**route)))gj.add_to(m)folium.LayerControl().add_to(m)m
Plotting it on a map is nice, but let's add a little more context to it in form of data tables.First the overall trip schedule:
# Only extract relevant fields from the responseextract_fields=['distance','amount','duration']data=[{key:route[key]forkeyinextract_fields}forrouteinresult['routes']]vehicles_df=pd.DataFrame(data)vehicles_df.index.name='vehicle'vehicles_df
| amount | distance | duration | |
|---|---|---|---|
| vehicle | |||
| 0 | [284] | 492789 | 25411 |
| 1 | [300] | 452186 | 25725 |
| 2 | [296] | 374466 | 27243 |
So every vehicle's capacity is almost fully exploited. That's good.How about a look at the individual service stations:
# Create a list to display the schedule for all vehiclesstations=list()forrouteinresult['routes']:vehicle=list()forstepinroute["steps"]:vehicle.append([step.get("job","Depot"),# Station IDstep["arrival"],# Arrival timestep["arrival"]+step.get("service",0),# Departure time])stations.append(vehicle)
Now we can look at each individual vehicle's timetable:
df_stations_0=pd.DataFrame(stations[0],columns=["Station ID","Arrival","Departure"])df_stations_0['Arrival']=pd.to_datetime(df_stations_0['Arrival'],unit='s')df_stations_0['Departure']=pd.to_datetime(df_stations_0['Departure'],unit='s')df_stations_0
| Station ID | Arrival | Departure | |
|---|---|---|---|
| 0 | Depot | 2019-03-22 08:08:44 | 2019-03-22 08:08:44 |
| 1 | 2 | 2019-03-22 08:30:00 | 2019-03-22 08:50:00 |
| 2 | 18 | 2019-03-22 08:59:05 | 2019-03-22 09:19:05 |
| 3 | 11 | 2019-03-22 09:38:50 | 2019-03-22 09:58:50 |
| 4 | 10 | 2019-03-22 10:08:38 | 2019-03-22 10:28:38 |
| 5 | 9 | 2019-03-22 11:02:14 | 2019-03-22 11:22:14 |
| 6 | 20 | 2019-03-22 16:52:15 | 2019-03-22 17:12:15 |
df_stations_1=pd.DataFrame(stations[1],columns=["Station ID","Arrival","Departure"])df_stations_1['Arrival']=pd.to_datetime(df_stations_1['Arrival'],unit='s')df_stations_1['Departure']=pd.to_datetime(df_stations_1['Departure'],unit='s')df_stations_1
| Station ID | Arrival | Departure | |
|---|---|---|---|
| 0 | Depot | 2019-03-22 08:50:59 | 2019-03-22 08:50:59 |
| 1 | 4 | 2019-03-22 09:01:58 | 2019-03-22 09:21:58 |
| 2 | 5 | 2019-03-22 09:26:47 | 2019-03-22 09:46:47 |
| 3 | 7 | 2019-03-22 10:00:00 | 2019-03-22 10:20:00 |
| 4 | 6 | 2019-03-22 10:33:11 | 2019-03-22 10:53:11 |
| 5 | 3 | 2019-03-22 10:58:02 | 2019-03-22 11:18:02 |
| 6 | 16 | 2019-03-22 16:59:54 | 2019-03-22 17:19:54 |
| 7 | 15 | 2019-03-22 17:59:44 | 2019-03-22 18:19:44 |
df_stations_2=pd.DataFrame(stations[2],columns=["Station ID","Arrival","Departure"])df_stations_2['Arrival']=pd.to_datetime(df_stations_2['Arrival'],unit='s')df_stations_2['Departure']=pd.to_datetime(df_stations_2['Departure'],unit='s')df_stations_2
| Station ID | Arrival | Departure | |
|---|---|---|---|
| 0 | Depot | 2019-03-22 08:07:55 | 2019-03-22 08:07:55 |
| 1 | 13 | 2019-03-22 08:40:30 | 2019-03-22 09:00:30 |
| 2 | 12 | 2019-03-22 09:13:42 | 2019-03-22 09:33:42 |
| 3 | 14 | 2019-03-22 10:00:00 | 2019-03-22 10:20:00 |
| 4 | 8 | 2019-03-22 12:22:39 | 2019-03-22 12:42:39 |
| 5 | 17 | 2019-03-22 14:34:13 | 2019-03-22 14:54:13 |
| 6 | 1 | 2019-03-22 17:21:58 | 2019-03-22 17:41:58 |