Fast and effective real world routing for a milk startup

In this post, I illustrate how readily available open-source tools can be used to quickly and effectively solve real-world routing problems.

Friends of mine successfully completed a crowdfunding campaign for their organic milk alternative drink Pläin. As the drinks need to be refrigerated, their original plan was to give away the crowdfunding rewards during a locally hosted event. Due to the lockdown resulting from the COVID pandemic, this was unfortunately not possible. Professional delivery of refrigerated goods would have broken the campaign budget. Instead, the founding team decided to deliver the product themselves to those backers living in the Munich metropolitan area.

As a PhD student in operations research, I offered to help plan the tours. My primary research focus is on designing and operating charging infrastructure for electric vehicle fleets, so I have in-depth knowledge of routing problems and the appropriate algorithms. The delivery problem was defined by a list of customers, their addresses, and the number of crates of the drink they would receive. Several vehicles of different sizes were available. The problem can be represented as the well-known Capacitated Vehicle Routing Problem (CVRP): We are to decide for each vehicle on a customer sequence, such that all customers are visited, The vehicle’s capacity is not exceeded, and the total travel time is minimized.

Before implementing a heuristic for the problem myself, I searched for existing open-source implementations for the CVRP and found the very impressive Vroom Project. It implements heuristics for typical routing problems, such as the CVRP and variants, including pickup and deliveries or delivery time windows. It can easily be connected to an OSRM routing server to work with real-world road network data. The OSRM project uses OpenStreetMaps data to compute the best routes between two addresses. I heavily relied on the OSRM project within my main research project and thus had a fully configured routing server available.

The Vroom project has abstracted typical routing problems into a JSON-based configuration language. I wrote a small Python script that reads the Excel file of customers, geocodes the addresses, and creates the configuration file. This file is then passed to the Vroom engine to obtain the optimal tours.

config = {
   "vehicles" : [{
           id : "example1", 
           start : depot_loc, finish : depot_loc,  # start address and finish address
           capacity : [50],  # number of crates loaded
           time_windows : [ delivery_start, delivery_finish] # time horizon available 
       }],
   "jobs"  : []
}
for c in customers:
   config["jobs"].append({
       "id" : c.id,
       "service" : 600, # service time at customer [s]
       "delivery" : [c.amount],
       "location" : c.location, # geocoded address
       "time_windows" : [
           [delivery_start, delivery_end] # can deliver over full horizon
       ]
   })

Even though the configuration seems minimal, it accurately captures most real-world requirements in routing. It was an absolute joy to be able to react to changing customer requirements, such as varying operating hours or starting locations, by simply adjusting the JSON data. While a small homegrown heuristic would have been effective for the basic CVRP, those special requirements would have immensely complicated the implementation, especially if raised late into the project.

As output i generated an overview (Fig 1) and invidual tour plans for the drivers. The tour plans were complemented with a multi-stop route link, that would load all stops into a routing app. The generated routing plan was well received, and all tours were successfully completed. This again outlines the impressive quality of open-source software for routing projects. The combination of flexible and performant routing engines combined with high-quality road network data from OpenStreetMaps allows us to solve tangible real-world problems.