Our quarantined world is even more on-demand than it used to be. We order groceries, gadgets and green goddess salad, and they all show up at our doors within minutes.
This makes social distancing a hell of a lot easier. Yet the systems behind teleporting :all_the_things: we need to our doorsteps are anything but easy. These systems rely heavily on the interestingly-named field Operations Research, or OR. OR describes routing problems with an alphabet soup of acronyms. TSP, PDTSP, PDTSPTW, VRP, CVRP, RCTVRPTW, and the like make logistics feel like a messy game of Scrabble: one big bad bag of letters. No indication what's right for you and your business.
We're here to help with that.
With Hop, nextmv's optimization platform, we translate common use cases into a suite of modular components you can select from to capture the requirements of your business.
Let's start with the Traveling Salesman Problem, or TSP. In Hop, we call our TSP the Vehicle model. Our challenge, should we choose to accept it, is simple: given a list of locations that must be visited, return the sequence that minimizes the vehicle's distance traveled.
The foundation of the solver is the Vehicle schema, shown below as a Go struct (nextmv is a Go shop!). A Vehiclehas start and end locations and a set of locations to visit. For our model, locations are represented by integers, usually list indices. For our input data that feeds the model, however, we'll just use lat/lon and (optionally) a LocationID.
The code snippet below tells Hop to create a route that starts at location 1, goes through locations 2 through 9 in the best order, and ends at location 10. The start usually corresponds to a vehicle's current location, while the end is where we want them to end up.
For Vehicle, lower scores are better. Since usually we want to minimize distance traveled, we'll need to tell Hop how to calculate distance. Here we tell Hop to calculate the "cost" of connecting two locations together as Haversine (as the crow flies!) distance.
So where do the C, PD, and TW come in? These are operational constraints! Capacity (C), Pickup and delivery sequencing (PD), and time windows (TW) are some of the most common requirements we see in delivery and distributions
In Hop, we have a constraint interface that makes it easy to add configurable constraints to the Vehicle model. As you can see from the code below, when we want to make sure each driver only carries a certain number of packages at a time, we simply add a capacity constraint to the Vehicle model. This says my vehicles can only carry 5 deliveries at a time and each potential stop impacts my carrying capacity (usually -1 for pickups and +1 for drop-offs).
Extending a Vehicle model to also consider pickup and delivery sequencing makes sure your model does not try to visit a delivery location for something that hasn't been picked up yet. This becomes very important when an order has to be picked up from a restaurant before being delivered to the customer that ordered it, for example.
Incorporating time windows lets you create routes that take into account acceptable times to arrive at different locations (ETAs!). Attempting a delivery when no one is there to receive it can definitely detract from your overall efficiency. :)
netxmv's pre-packaged constraints for pickup/delivery and time window constraints can also be layered to account for any additional business requirements.
What if you have a unique business constraint? It's just as straightforward to write your own and import it.
Hop provides standard input formats for constructing Vehicle models or you can compose your own. The JSON below is an example base input format for Vehicle. It includes coordinates, plus things like vehicle carrying capacity.
Of course, you likely want to route more than one vehicle, and you probably want to minimize the total distance traveled for those vehicles to make the most out of your fleet operations. Regardless of whether each vehicle starts or ends at a central depot or has a specific work shift, nextmv can help optimize the Vehicle Routing Problem, or VRP, using Hop's Fleet solver - a set of vehicles, requests, and assignment rules.
I hope this post helped demystify some of the ABCs of the route optimization soup as well as how those translate to what you see in nextmv's product suite. And, like we covered last time, even though we may talk about the Vehicle and Fleet models in the context of routing physical vehicles, the applications go well beyond that.
Happy Hopping!
