Motivation
Not all operational decisions need complex optimization.
But all operational decisions benefit from simple automation and integration, fast iteration cycles, and continual visibility. Nextmv helps you get this right from the beginning, then lets you layer in the fancy stuff like optimization if you need it later.
A few years ago we began applying optimization and simulation techniques to real-time routing and assignment problems in meal delivery. These problems often have a number of interesting characteristics that make them challenging for off-the-shelf modeling tools.
They follow business rules, such as pickups preceding deliveries, time windows
for deliveries which may or may not be violated, and vehicle capacities and
attributes.
Their inputs are unpredictable and constantly changing.
They can get very large (1000s of orders, 100s of drivers).
They require high quality solutions in a matter of seconds.
We found that the capabilities of a planning algorithm can have a large impact on profit and customer service levels. They impact the consistency of service in response to a changing environment (that is, its robustness). As users of these tools, we needed general purpose technologies to allow us to do several things.
Test, integrate, and deploy our models into production quickly in response
to changing business goals and requirements.
Automatically gather evidence to support or reject model changes.
Model flexibly, without restricting the business objectives or constraints
we can represent.
Find high quality solutions quickly, often in milliseconds for individual
routes, and seconds for full routes and assignments.
Prove optimality on small problems, such as an individual route, fast
enough that our systems can spend their time doing other things.
Anticipate outcomes for our key performance indicators (KPIs) in real time.
This led us to investigate different techniques for real time routing, including heuristics, Mixed Integer Programming (MIP), Constraint Programming (CP), and various hybridizations of these. Our takeaways are similar to what can be found in the academic literature.
Heuristics are the most common technology for real-time routing. They typically cannot optimize, require custom implementations, and are rarely reusable.
MIP solvers are the undisputed king of optimality reasoning. However, their focus on dual bounds can delay finding feasible plans. They work well for real time systems when warm started with another technique (e.g. heuristics). That requires implementing two or more modeling techniques for a single problem.
CP solvers are flexible and excel at finding feasible solutions. They often require custom hybridization to optimize well. This can be beneficial but is onerous and complex.
We have used all of these in on-demand routing. Our experiences exposed a number of other problems arising in development and deployment of logistics automation models to production software environments.
Modeling technologies require domain experts to translate business objectives and requirements into models. As businesses grow and change, these experts can become bottlenecks. This makes organizations less agile.
Constraint-based optimization models are extremely difficult to test. There is no easy equivalent to the software unit test for a MIP or CP model.
Integration of existing technologies into software microservices is nontrivial, and resembles that of other scientific libraries. This, again, makes organizations less agile.
Finally, discrete event simulation is the most widely used technology for predicting outcomes in complex systems. Yet simulation has traditionally been used by human analysts as an offline technique. In order to use simulation to its full potential, we must bring it into the production software stack.
Our research into modeling techniques led us to Decision Diagrams (DD). DDs represent optimization problems as the search for a shortest (or longest) path over a layered, directed graph. They are state-based, have few restrictions on problem representation, and can outperform MIP on optimization and CP on feasibility reasoning (this, of course, depends on the model).
We’ve had enormous success with DDs. Some of our pickup and delivery models are orders of magnitude faster using them. We find them particularly attractive for getting started with simple models and integrating them into software stacks. There aren’t any other industrial grade DD solvers, so we built Hop to be the first.
Further, we developed Hop with a hybrid approach to optimization in mind, leveraging DDs as a starting point for other paradigms. For example, with the addition of heuristic solvers such as Adaptive Large Neighborhood Search (ALNS) to Hop, we can now find more improving solutions faster, even for the most complex delivery and distribution problems.
As we developed our tools, we realized that both optimization and simulation models operate directly on state. This led us to a design that unifies the two techniques. In our platform, a modeler can create a single set of code that both makes decisions impacting the future and predicts outcomes. This enables testing and code reuse at the model level.
Hop and Dash are built to work well with modern technology. Optimization and simulation models come preloaded with useful features that simplify going from research and development to production.
Software developers without formal training in optimization or simulation can
build simple, effective models, and create scalable decision infrastructure.
Models are written and tested like any other software. Larger, more complex
models can be composed of smaller, simpler ones.
Models read and write input and output in JSON. They work directly on business
data. This simplifies interpreting and auditing automated decisions.
Models come with pre-built runners that make going from development to testing
in CI to production deployment trivial.
Hop and Dash are both 100% Go. Models are simple compiled binary artifacts. It doesn’t get much easier than that.
