Hop is a decision modeling and optimization tool that finds solutions to a variety of operational problems. This includes delivery and distribution of many things — from meals to rides to raw milk — where determining routes for multiple vehicles is a key outcome. As a result, we call these routing problems.
But before you can answer questions like “What’s the best route between pickup and drop off locations for food delivery?” or “Which passenger should get picked up or dropped off first in a shared ride service?” you sometimes have to solve an assignment problem. If I have to deliver ice cream, which vehicles are eligible to transport that product with refrigerated storage? Or in a ride sharing example, I might need to know which vehicles in the fleet have at least two empty seats to fulfill a request to pick up two passengers.
At this point, you probably feel like we’ve wrapped a problem in a problem, and you'd be right. But don’t worry. Nextmv's fleet engine (you might know it as a vehicle routing model or VRP) solves multi-vehicle routing problems and accounts for this problem-in-problem scenario. It does this by framing the routing piece as the "inner" decision and the assignment piece as the "outer" decision and solves from there.
In this post, we’re going to take a quick look at the outer decision — the assignment problem — and explore assignment problems in general, how Nextmv handles assignment, and how our assigner framework makes solving these types of problems faster, easier, and more flexible.
Assignment problems are everywhere
In the most general form, an assignment problem involves assigning tasks (e.g., food orders) to agents (e.g., drivers) while minimizing a cost (e.g, time to complete delivery). In this case, assignment is typically limited such that, in a food delivery scenario, a driver can only deliver at most one order and an order can only be assigned to one driver. But with multi-vehicle routing problems, one vehicle can be assigned to many orders and orders can even be assigned to many vehicles through handoffs.
Nextmv optimization engines include `Assigner` functions that take the current state of a fleet of vehicles as input (e.g., any attributes needed to determine potential assignments such as how many seats are available). All possible assignments (e.g., for each vehicle, the set of locations it could be assigned to) are then returned. Then `Routing` uses this information to find the best route for each vehicle based on the vehicle’s start and end location, and the locations of its potential assignments.
The decision of whether or not a location can be assigned to a given vehicle can depend on several factors. Some of the most common factors considered include, for example:
- Capacity of the vehicle (e.g., how many seats are available?)
- Compatibility of the vehicle and location (e.g., delivery from a location with an order requiring refrigeration can only be picked up by a vehicle with refrigerated storage)
- Maximum route length a vehicle can travel (in terms of distance or time)
- The speed at which a vehicle can travel
In Nextmv’s fleet engine, factors such as these are called “filters” because they do just that — they filter out potential assignments that are not feasible *before* optimization. Incorporating filters such as these has the added benefit of reducing time to first solution, as it simplifies the search space of the problem.
With the release of Hop v0.7.1, we are introducing a new assigner framework. This framework provides a faster and easier way to incorporate filters such as these when making a potential assignment decision (and take advance of performance improvements). Previously, adding even commonly used filters required writing custom code. Now we provide enhanced flexibility to easily add them via pre-built functions. You can use these functions like lego bricks — adding only the ones that make sense for your business and building on them if you need something more custom. We launched the new assigner framework with pre-built vehicle capacity, vehicle and location compatibility, and maximum route length filters and we are adding more all the time.
Try it out today
To learn more about the new assigner framework, check out the package docs.
If you’re interested in trying out our fleet routing app for free on Nextmv Cloud, you can experience the new assigner framework behind the scenes and see some filters in action.
.jpeg)
