At Nextmv, we’re building a different kind of optimization product. We’re building a product that works better with modern microservice and serverless architectures. A product that feels more like regular software. A product that’s multi-paradigm and lets you apply the best optimization approach to the particular decision at hand.
We call it the Nextmv Decision Stack, and it’s inspired by several established operations research techniques. One of them is decision diagrams(DDs), which are layered, directed multigraphs that represent a set of choices. Compared to other approaches, they allow us to more easily represent optimization problems and search across a solution space very quickly. This is why DDs were the first solving paradigm we implemented within our stack. But we also knew it wouldn’t be the last.
So we’re happy to share that with the release of version 0.8.0, we’ve added support for another solving paradigm: Adaptive Large Neighborhood Search (ALNS). ALNS is a heuristic solving technique that effectively lets you look at a feasible solution produced by a solver (a DD, for instance) and ask, "Are there better solutions in the neighborhood?" ALNS does this by iteratively modifying a first feasible solution in order to seek out better solutions in the neighboring search space. It has the ability to navigate (or “jump”) across the solution space to find improving solutions in a way that DDs do not. This makes DDs and ALNS a great pair: DDs generate the first feasible solution that ALNS needs to do its job, and ALNS quickly explores other parts of the diagram.
This addition of ALNS to our fleet engine in the Nextmv Decision Stack increases the chances of finding improving solutions for optimization problems such as routing particularly large and complex ones. And we’re pleased to make this powerful solving paradigm more accessible and approachable to developers. Let’s have a closer look!
A world without ALNS
To understand the power of ALNS, let’s look at how we solve a routing problem without it. Let’s say we have a single vehicle that needs to visit four locations while minimizing its total travel time. Which route should our vehicle take? The Nextmv solver gets to work by first generating a decision diagram consisting of all the various states (or routes our vehicle could take). The DD solver starts at the root state (no stops visited) and methodically builds out a diagram with all the possible solutions. Then the solver searches the diagram for the best operational solution it can find in the runtime it has. In this example, there are a total of 33 states, 18 of which are feasible (meaning all stops are visited).
As it stands, finding a solution to this particular problem isn’t especially challenging or computationally expensive. That changes dramatically when you look to scale your fleet and distribution into the tens, hundred, thousands, and beyond, and when you have to account for business logic such as vehicle capacity, compatibility attributes, time windows, delivery precedence, or penalties. Just imagine the diagrams!
Fortunately, there are useful techniques for managing and optimizing your search for operational solutions in large and complex problems. For example, expanders help the Nextmv solver make smart decisions about how to reduce the number of states (or solutions) it needs to generate and search in a diagram. This reduces the time to first operational solution and memory use.
*An example of expanders at work on a one-vehicle-four-stops decision diagram. As you can see, this technique gets to an operational solution by exploring less than 20% of the tree.*
Expanders are a nifty and powerful technique. But in looking at the diagram above for our simple one-vehicle-four-stops routing problem, we know there is a better operational solution in the neighborhood of S15 at S23. (As a side note: The DD still found a good first solution quickly and would have improved that solution by further exploring the diagram.) Is there another complementary way to arrive at this better solution? Yes, there is — with ALNS.
Enter, ALNS
ALNS is a heuristic derived from large neighborhood search (LNS). LNS is defined by the ability to search for solutions in the space surrounding an existing solution — in other words, the neighborhood. It does this by using operators that iteratively modify the existing solution. These operators remove and add (or “destroy and repair”) parts of the solution in an attempt to arrive at a better one.
Let’s look at how this might work in the context of our routing example. Beginning at S15, which has a route of 0,2,4,3,1,0), a destroy operator may remove stops 2 and 4 from its route. This leaves us with a “destroyed” state that has a route of 0,3,1,0. Next, a repair operator adds stops 2 and 4 back into the route, but in a different sequence. This transports you to S23.
So how do we go from regular LNS to the “adaptive” variety as the ALNS name suggests? ALNS uses a dynamic weighting system that serves as an adaptive feedback mechanism for how the search employs each of its operators. For example, one combination of operators might be really successful at finding improving solutions as they destroy and repair their way through the diagram. But then they might hit a spell where they only find worse solutions compared to other operators. As a result, ALNS can assign a new (lesser) weight for how it uses those less successful operators. In effect, the weighting allows ALNS to make reasoned decisions about how to invest in operators with the most potential for success.
A more creative way to think about this is imagining ALNS navigating shortcuts or wormholes between solutions in the decision diagram. Where the decision diagram on its own can navigate a series of branches to arrive at a good solution, ALNS can jump around to states in the diagram located in completely different branches.
ALNS with Nextmv
ALNS is a well established technique in the optimization space, and has broad applicability within routing, scheduling, and other optimization problems.
In the Nextmv context, there are a few unique aspects to our implementation that are worth highlighting. First, we’ve written ALNS in a way so that it operates on the same structure as our decision diagram solver. As a result, this creates a common framework for the two solvers to work from and exchange information about the solutions they find. On top of this, the repair operator used in ALNS is actually a decision diagram under the hood.
Second, ALNS in the Nextmv context becomes just another way to configure the building blocks of your decision stack. It’s easy to apply ALNS to another optimization problem like scheduling and also allow customers to write their own operators for their custom app.
The road ahead
ALNS is a powerful technique for finding more improving solutions to optimization problems such as routing. We’re thrilled to make this capability available to all of our self-managed customers running v0.8.0.
In the near future, we will release this capability on Nextmv Cloud. If you’re new to Nextmv, we encourage you to create a free account and test drive our route optimization app.
