Hop is a decision modeling and optimization tool that uses decision diagrams to find solutions to business problems. A problem might be how to optimally pack a pallet in a warehouse (a packing problem) or how to route drivers for a food delivery service (also known as a vehicle routing problem or VRP).
When a Hop model runs, it first reads JSON input that describes the state of a system. In the case of a food delivery service, for example, the initial (or root) state of a system might describe a single driver who needs to visit four locations. Hop reads this input and generates a decision diagram expressing all the possible resulting (or child) states. This is called an “exact diagram” because it exactly represents a problem’s search space. As part of this expression, the Hop model generates various attributes for each possible state: locations left to visit, the route, the value of the state, and whether or not it is feasible.
While being thorough has its advantages, generating an exact diagram for every possible decision can get very unwieldy very quickly. The resulting state explosion impacts Hop’s overall performance by lengthening the time to first feasible solution and increasing memory use. In practice, this means certain poorly performing models can take minutes to return a good delivery route instead of seconds. And with real-time operations, that matters.
The good news is that there are techniques to manage this such as restrictors, reducers, and bounds. In Hop v0.7.0, we've introduced another: expanders.
What are expanders?
Expanders are a technique for limiting how many child states a parent state can create at a time. Essentially, they cap the number of child states immediately generated by each node in a decision diagram, mitigating state explosion and managing performance impact.
To understand this a bit better, let’s have a closer look at the vehicle routing problem from earlier in this post: one vehicle, four locations. Without any limits imposed on it, Hop creates an exact diagram. It begins with the root state (S0) and goes to work generating child states. At each layer in the diagram, Hop adds a location to the route and experiments with the position of that location within the route. Some of the child states will be feasible (the resulting route visits all four locations) and some will not (the resulting route does not visit all four locations). In this example, you can see that we don’t reach feasible states until the fourth layer.
Another consideration in this process is the value calculated for each state. In this example, lower values are better than higher values. Of the 24 feasible states, Hop will select the one with the lowest value as the solution. In this case, S23 is our solution.
This walkthrough showed an unlimited scenario. Within Hop, this corresponds to `expansion.Limit = 0`. So what would happen if we did impose a limit? Let’s try setting `expansion.Limit = 1`, where the integer value represents the number of child states Hop will explore at a time.
We start at S0, our root state, and walk the diagram like we did before. S0 produces one child state, S1, in Layer 1. This is within our defined expansion limit. Hop keeps exploring. Layer 2 of our diagram generates two child states. We can’t explore both because we set our expansion limit to 1.
Which does Hop choose? Hop looks at the value of each state and will pursue the one with the lower value. (This is known as a “greedy search.”) In this case, S2 has the lower value so the model generates S2’s child states but not S3’s. S2 results in three child states. The expansion limit tells Hop to pick one. Hop looks for the lowest value, in this case S5, and keeps going. S5 generates four child states. Hop selects a state with the lowest value. But this time there are no further child states to explore. Hop can return S15 as the solution for how to route our driver. Decision made.
By setting an expansion limit, we reduce the state space that Hop must explore to find an operational solution. This is particularly apparent at larger scale — tens or hundreds of drivers visiting hundreds to thousands of locations. The expansion limit technique gets us to a first feasible solution more quickly and uses less memory.
The expansion limit implementation we just described is called `Eager`. It’s one of two expansion implementations we’ve developed with the v0.7.0 release. The second one is called `Lazy`, and it’s even more efficient in returning the first feasible solution and managing memory use.
Gaining more efficiency with the Lazy expander
The Lazy expander has an edge over the Eager expander. We’ve engineered Lazy to be more clever in helping Hop generate and navigate the state space. Where Eager gives you the option to generate all child states up front, Lazy lets you generate them on demand, therefore limiting the number of overall states generated.
The Lazy expander implementation accomplishes this by calculating the values of child states before generating the complete state (and all of its attributes).
The Lazy implementation of expansion limits comes with demonstrated performance improvements. We’ve compared previous Hop releases to v0.7.0 running internal benchmark sets configured with a time limit of 10 seconds and an expansion limit of 1.
Fleet Model
* +8 solved instances that were previously unsolved
* 7.32x geomean speed increase to (same) first solution
Here is a capacitated fleet example with 30,000 customers and 256 vehicles. Hop found an operational solution after 3.7 seconds.
Vehicle model
* +12 solved instances that were previously unsolved
* 4.33x geomean speed increase to (same) first solution
Here is an example with 4,461 locations for which hop found this first solution after 6.6 seconds:
Best is the enemy of good
After walking through the examples above, you might be trying to reconcile the solution we got when the expansion limit was set to 0 (S23, V=15) compared to when it was set to 1 (S15, V=25). The solution in the first scenario is better than the second. In fact, it is the optimal solution. While this is true, that doesn’t mean that the second scenario returned a bad result. It returns a first solution very quickly and improves on that solution over time. And if given enough time, it will also find the optimal solution.
Let’s take a step back to understand why. The example we’ve explored in this post looks at a single driver and four locations. Imagine what our diagram would like at scale with more drivers and locations?
When dealing with real-time operations, it’s important to keep in mind that best is the enemy of good. For a food delivery service, for example, you might have mere seconds to determine how to route a driver in order to keep up with your business needs. Finding the best solution could take minutes or hours. By that time, the moment has passed, the pizzas are cold, and your customers aren’t happy. Hop can deliver a good route that aligns with your business goals within the seconds needed to keep operations going.
Try it out today
As of Hop v0.7.0, all Hop models have configurable expansion limits. All Hop models (except for knapsack) use the Lazy implementation by default to make our models as efficient as possible.
Enterprise customers who are upgrading to v0.7.0 will need to migrate their models to use expansion limits. Learn more about the migration details in our documentation.
If you’re interested in trying out our Fleet Routing model for free on Nextmv Cloud, you’ll experience this new capability at work behind the scenes.
.jpeg)
