Building a courier from scratch, Part II: The vehicle routing problem

In a previous post, we wrote about how we transitioned a major part of Packfleet from running on Bubble to our own systems. This was a big project, one which we’re glad worked out as smoothly as it did. The work we did set a proper baseline for our delivery service that we can iterate upon.

After the migration, there remained another big part of our operations that we constantly felt limited by: vehicle routing and our day-to-day operations.

Building our own routing tools

Our vision is to be the best courier in the world and it’s crucial that we have systems that know about the entire lifecycle of a shipment. The tooling we used at the time (Circuit) was a fantastic solution to get us up and running, but the lack of tight integration with our systems was becoming a problem.

To give you an example of something that makes Packfleet different: we decided early on to have “tracking numbers” which, instead of long numbers, are two or three-word phrases. Words are so much easier to recognise and remember than a long string of random characters that most other couriers provide for tracking, and can easily provide a similar amount of entropy.

Just compare AB0002230754520752, a modified tracking number I got from another courier, with guitar-date, an example tracking phrase from Packfleet (don’t worry, this particular phrase will never be assigned to a real shipment!).

We’ve always been frustrated by how internal abstractions and terminology from traditional couriers leak out into their products, and this is one of them. We think there are much clearer ways to communicate.

So, we wanted full control over the notifications and e-mails we send to customers, from the content of the e-mails to the format of the tracking link and layout of the tracking page. There’s also lots we’d like to do on giving recipients full control of their deliveries: delaying the delivery date, changing the address, or even changing a delivery to same-day in some cases where our real-time routing deems that to be possible.

It was unavoidable that we needed to build our own vehicle routing software to achieve all of this.

Solving the Vehicle Routing Problem

Finding an efficient route for a vehicle between multiple stops is well-studied in computer science and applied maths called the Vehicle Routing Problem (VRP). A quick search gives hundreds of papers written on the subject since the 1960s, although there has been an explosion of content in the past 10-15 years since app-based delivery services really took hold.

You may be familiar with the travelling salesman problem (TSP): find the optimal order in which a salesman can visit N locations. The VRP is a generalisation of the TSP to multiple “salespeople” — delivery vehicles in our case — and usually has added constraints to what the vehicles can do.

The TSP and VRP are both NP-hard for finding the optimal route as there is neither a polynomial time solution for finding an optimal route, nor a polynomial time solution for checking that a given route is optimal. The brute-force approach therefore is factorial in time complexity (O(n!)) and even the best known exact algorithms tend to run in exponential (O(2^n)) time. Consider that a single driver trying to find the best way to visit just 20 delivery locations would take proportional to 20! (~10^18) operations to brute-force, taking years to compute on a modern CPU.

In a real VRP it’s also essential to consider all the real-world constraints. Some collections and deliveries have a time-window they must take place in, drivers need to complete their shifts within a reasonable amount of time, and there are only so many boxes you can fit into a single vehicle. With all that in mind, finding an exact solution to this problem is almost always infeasible.

So VRPs are practically always solved using heuristics (for example using simulated annealing, genetic algorithms, and others), yielding good-enough solutions with run-times restricted to a few seconds or minutes. There are plenty of off-the-shelf solvers to achieve this: End-to-end hosted APIs (Graphhopper, Routific) to open-source, self-hosted equivalents (Jsprit, VROOM), or bare-metal solutions like Google’s OR-tools which is closer to a pure constraint solver that can be generalised to any optimisation problem.

We opted to use Graphhopper’s route optimisation API to power Pathfinder. Routing vehicles is a core competency for us and eventually we’re going to need something more custom. But there is no need to try to boil the ocean and do everything at the same time!

Modelling the real world

Difficult as NP-hard optimisation problems are, modelling the real world is harder still. Our daily operations are dependent on accurate traffic and travel-time information, correctly parsing and geocoding addresses, good predictions on how long each delivery or collection will take, adhering to parking and traffic restrictions, drivers and warehouse staff starting their shifts on time, and so on.

Given we usually can’t model all of this perfectly, we also need to periodically update travel times and ETAs for our customers’ benefit, and if needed re-optimise the routes on-the-fly to deal with significant changes.

Our solution needed to not just come up with a good route, but also to make it easy to manage it throughout the day in response to real-life events. Seeing drivers on a map, tracking ETAs and delays in real-time, updating customers with changes to their delivery, or being able to add or remove a stop from a driver’s route were all strict requirements we needed to solve for.

Building Pathfinder

As with our previous post on replacing Bubble, this seemed like an all-or-nothing transition where we would spend a long time building, then switch in one go. This time the problem was even harder: route optimisation, geocoding, a driver app, and some relatively complex tooling which had to seamlessly replace all our existing operations.

A key idea changed the assumption that we had to do this all in one go: we realised we could output a *pre-optimised* CSV file for Circuit with every stop already assigned to a driver. We could apply our own rules and restrictions on how to assign drivers, before using Circuit as the tracking interface and driver app.

This approach let us start using parts of our new tool (codenamed “Pathfinder”) within weeks instead of months. And the earlier we put our code into production, the earlier we could learn from using it. As an added bonus, our morning operations became easier sooner as we eliminated some of the manual work by leveraging our own route optimisation logic.

With all that in mind, we had an idea of what it would take to build the first version to get us up and running:

• Integrating a VRP solver with support for time windows, vehicle capacities, traffic, driver breaks and so on
• A way to reliably geocode addresses into coordinates

• Persisting planned routes to a database

• Exporting routes as a CSV, to be ingested by Circuit

Once part 1 was complete, we could start using it immediately with Circuit, and meanwhile focus on the rest of the work:

• A routing API to compute accurate travel times on an ongoing-basis (we integrate with Google’s Directions API for this)

• A driver app for drivers to check in for their shift, see their route, scan packs and capture proof of delivery (built using SwiftUI — Josh plans to write a blog post on this soon!)

• An internal web app with support for planning and viewing routes, and showing everything on a map

• A new tracking page for recipients, with live information on the driver

• E-mail / SMS notifications to let customers know about the status of their shipment

• A backend + API to power all of this

Once again, we set ourselves an ambitious goal of running the first deliveries fully on our own software by mid-December. We didn’t quite meet this deadline, but mostly because December is a wild time for deliveries!

Architecture

We introduced Pathfinder as a new service into our stack, with a separate backend and frontend codebase. This made it a lot easier to build and iterate on, without affecting critical customer-facing systems. For simplicity, we share our main database, authentication and some other infrastructure between our backend services.

The Results

We begun operating fully on Pathfinder sometime in early January 2022, running 100% of our operations using our own software for the first time!

Web app

Pathfinder’s web app helps us plan routes, track our vehicles and manage the deliveries and collections for the day. It’s built on our usual frontend stack (React, Apollo, Next.js).

We also created our own React mapping library to wrap the Google Maps JavaScript SDK which supports the new vector maps SDK and also lets us draw arbitrary React components on the map very easily.

These tools help us operate using Packfleet-native concepts, like tracking phrases to identify shipments:

Tracking pages

Pathfinder powers our tracking pages with a live ETA and route, and an emoji based on on what’s coming your way:

Driver app

We built an iOS app for our drivers (a counterpart to "Pathfinder" codenamed “Sojourner” of course – don’t sue us NASA).

It’s built around how we work: drivers can start their shifts, see their route, scan Packfleet labels and take pictures for proof of delivery.

We’re just getting started

Operating fully on our own software is a huge milestone for a small company like us, but we already have so much more to build. We’ve barely scratched the surface of our mission to create the best courier company on Earth, and to empower all businesses with better deliveries!

We need help in taking things even further. Are you interested in solving complex operational problems in a way that makes the user experience delightfully simple? Join us!

We’ve just begun hiring for full-stack engineers. Weʼre looking for strong generalists who are focused on either the frontend or the backend, but comfortable diving into both. You can apply here or reach out to @rbilgil or @jgarnham on Twitter to chat more if you’re interested.

We hope you enjoyed reading this engineering story as we build Packfleetʼs systems in the open. There will be many more to come!