Hacker News new | past | comments | ask | show | jobs | submit login
Launch HN: Nextmv (YC W20) – Developer-friendly logistics algorithms
142 points by mooneyc6 on March 19, 2020 | hide | past | favorite | 33 comments
Hey HN!

We're Carolyn and Ryan, founders of nextmv (https://nextmv.io/). We help developers build and test logistics algorithms faster. These are things like routing delivery vehicles, assigning nurses to patients, and managing supply chains.

We used to work in systems engineering and operations research on big government projects, including missile simulations and airport runway management. A few years ago, we pivoted to working on food delivery at Zoomer (YC S14) and later Grubhub. It turned out that making on-demand pizza and taco delivery efficient and reliable required the same optimization and simulation techniques, but in real time.

Real-time routing and assignment problems have a number of interesting characteristics that make them challenging. For example, they follow business rules such as pickups preceding deliveries, time windows for deliveries which may or may not be violated, and driver capacities. Their inputs are constantly changing. They can get very large (1000s of orders, 100s of drivers). And they require high-quality solutions in seconds.

People usually think of NP-hard problems like the Traveling Salesman when routing and dispatch optimization is mentioned, and we do have to solve those. But the biggest challenges turn out to be ones that are more familiar to the software engineering community. There is no easy equivalent to the software unit test for techniques such as Integer Programming and Constraint Programming. And integration into modern software stacks is nontrivial. In the end, we had to build new tools so we could work faster.

Traditional dispatch and scheduling algorithms take months to develop, integrate, and test. That is a problem when businesses change rapidly. This is happening in delivery, which has exploded over the last few years and is likely to only get bigger. Existing tools require domain experts to translate business rules into models. This makes organizations unable to keep pace with change.

During our research into appropriate techniques, we learned about Decision Diagrams (http://www.andrew.cmu.edu/user/vanhoeve/mdd/). 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 other techniques (depending, of course, on the model). We find them particularly attractive for getting started with simple models and integrating them into software stacks. Since there weren't any industrial-grade DD solvers, we built one. And we started nextmv to give companies the modeling, optimization, and simulation tools we wish we'd had.

Our tools are for software developers with deadlines. They let you flexibly model nearly any business rules, easily integrate models into software stacks, and test them so you know they're behaving as you expect.

What can you do with them? Dynamically route buses based on passenger requests. Minimize shipping cost for packages. Schedule workers based on demand forecasts. Hop (our optimizer) lets you model decision problems as state machines. Dash (our simulator) is also state-based, so you can optimize and simulate using the same code.

We've prioritized making things developer-friendly. You can write and test models like any other software. Larger, more complex models can be composed out of smaller, simpler ones. Optimization and simulation models are built from Go source into simple binary artifacts. (We think of this as Docker for decision science.) They come with pre-built runners that make going from development to testing in CI to production deployment trivial. They have JSON I/O for easy integration, and run in a CLI, over HTTP, or in Lambda.

Not all operational decisions need complex optimization, but they all benefit from simple automation and integration, fast iteration cycles, and continual visibility. We give you this from the beginning, then let you layer in fancier optimization stuff if you need it later. Here's a screen cast showing a simple routing model in Lambda: https://www.loom.com/share/65ad523138364bf7bac48524efb620e0. We've seen developers without optimization backgrounds create models to minimize delivery time and deploy them to Lambda in less than 24 hours.

We're eager to hear about your experiences in this area and/or ideas on faster ways to get automation into production. We would love any and all feedback that this community can offer, so don't hold back!

The topic you are tackling is a very hard one, but you have figured that one already. Good thing is, you have both a solid and relevant background.

A general thought, which might be important in the future. This kind of optimization tools work best at scale, I would go even as far as saying only at scale. And that can make a MVP a hard thing. I have seen people try something similar without the necessary scale, or rather density as routes were spread out over to large a region. And it didn't work out that good.

What I didn't get, but then might be just me, is who your customers are. Developers or users? If it's the latter I could provide some operational insight.

Good points! We've definitely seen delivery networks flail under certain conditions, like lack of density. Our hope is that by making both optimization and simulation more accessible to software engineers, we can help organizations understand and preempt problems like that.

Which brings up the answer to your question: We're targeting developers. Companies that build integer programming solvers and similar tech have great tools for PhDs in Operations Research who have a lot of mathematical sophistication. We think there is an underserved market of software engineers who can benefit from different technology.

Makes sense. One of my previous employers tried to develop the tools in-house, as a sideline of the operational business of running transportation (of people, in busses, like groups of people renting the whole bus). Development was guided by a guy with a media background, developers where people fresh from University. Results were predictable. Some sophisticated tool kit would have been great!

Sounds familiar!

One thing that's struck us is the lack of accessibility of optimization tools to software engineers. I worked as a developer long before I ever got into OR. When I switched over to being an analyst, it felt like there was an invisible divide between the two worlds.

A great success of the Data Science movement over the last decade seems to be making statistics and visualization easier for and more widely adopted by tech. We think optimization and simulation are about to go through the same thing.

Let's hope so!

This is an interesting and promising take on the problem. Despite being introduced already in the 60'ies, the optimization of delivery routes is still not used as widely as it should. I'd argue that this is mostly due to the complexities and challenges inherent in adapting such optimization technology to solve real world delivery route planning tasks, and, on the other hand, the high cost and low availability of operations researchers with relevant software engineering background.

In my recent PhD dissertation I tried to address the challenges from a different angle: I proposed using machine learning to predict the most suitable heuristic algorithm and its parameter values for a specific logistics planning problem. This way the developer or the user does not need to worry about the details of the optimization solver. The book is freely available for download from: https://jyx.jyu.fi/handle/123456789/65790

Thank you so much for sharing this! I will read it.

I suspect there's a lot of potential for these sorts of techniques in production systems, especially combined with decision diagrams. We've been looking at DDs partly because they are capable of optimizing problems without a lot of restrictions on problem type or representation, and also because they seem like a very nice metaheuristic structure.

Hi Founders! As a developer, I would like to see 1) API documentation, 2) code examples 3) open-source version (whatever restricted in solutions quality). 1 and 2 can quickly give me some idea if this tool match my needs (and personal taste, to be fair). Open-source version is (often mandatory) escape hatch for many cases.

So far, I found nothing like this on your site. If your target audience are CTO/managers only, then it's OK, but developers would ask for real meat)))

Thanks for reaching out! We will be posting our docs on our site in the next couple weeks (with examples). You can see one of those examples in the screencast linked above!

Also, we are considering whether to go open source with our platform in all or part and we’re still early

How does this compare with open-source software like Optaplanner [0] from RedHat or ChocoSolver? [1]

I think this is really cool, and I've recently been looking into using constraints solvers for automating some of the manual scheduling processes at our startup and optimizing them (we do a variant of events booking, so essentially booking events at the times most likely to fill up and maximizing for profit)

[0] https://www.optaplanner.org/

OptaPlanner is an AI constraint solver. It optimizes planning and scheduling problems, such as the Vehicle Routing Problem, Employee Rostering, Maintenance Scheduling, Task Assignment, School Timetabling, Cloud Optimization, Conference Scheduling, Job Shop Scheduling, Bin Packing and many more. Every organization faces such challenges: assign a limited set of constrained resources (employees, assets, time and/or money) to provide products or services. OptaPlanner delivers more efficient plans, which reduce costs and improve service quality.

OptaPlanner is a lightweight, embeddable planning engine. It enables everyday Java™ programmers to solve optimization problems efficiently. It is also compatible with other JVM languages (such as Kotlin and Scala). Constraints apply on plain domain objects and can call existing code. There’s no need to input constraints as mathematical equations. Under the hood, OptaPlanner combines sophisticated AI optimization algorithms (such as Tabu Search, Simulated Annealing, Late Acceptance and other metaheuristics) with very efficient score calculation and other state-of-the-art constraint solving techniques.

[1] https://choco-solver.org/

OptaPlanner and Choco are both very cool tech. We've been pretty religious users of Gecode (https://www.gecode.org/) over the last few years, which you should also check out if you are interested in CP and like C++.

There are a few important differences between what we're building and those tools:

A large focus of our tools is on integration with software stacks and data warehouses. They are opinionated about how decision models should read and write data, how they should be deployed and interacted with, and they make those patterns clear and consistent. We refer to this as the "decision engineering" part of the field, which is not often addressed by existing tools.

Decision Diagrams (and thus, Hop) rely on many of the same techniques as MIP or CP (search, inference, and relaxation), but they represent problems in different ways and have their own interesting characteristics. For instance, diagram restriction and reduction are both powerful techniques specific to DDs.

In our systems, we represent models as states and transitions. I believe this makes models easier to unit test and reason about. It also has the interesting side effect of making optimization and simulation look a lot closer to each other than they traditionally have, which is something we'll be exploring more in the coming months.

Take a look at the DD book if you're looking for a thorough treatment: https://www.springer.com/gp/book/9783319428475. It's really interesting stuff! We'll also be updating our blog fairly regularly now that we're launched.

Thanks for the reply! I signed up, will have a look at the book and bookmark your blog.

Unfortunately, C++ is one the only languages I'm not familiar with, so Gecode may be a bit out of my reach, but I'll check it out regardless.

I haven't used Choco myself, but I have seen it used quite successfully in some nice hybrid optimization studies. Gecode is awesome, but can be complex to get started with.

Parts of Hop's design are informed by using Gecode and SCIP (https://scip.zib.de/) a lot. They're among the best designed solvers I've seen (for those that you can see the source). Over time I'd like to add in finite domain propagation and canned algorithms from the global constraint catalog.

Congratulations on the launch! I have a few questions.

What happens when the value function for a given state is expensive? The value is the distance from one state to another right, not the 'value of that state' - what if there are a lot of states that are "feasible neighbors"?

What sort of scale of routing problem are you guys taking? How many stops? Does DD scale well when you add in additional conditions like Driver Hours, Battery/Fuel Capacity?

I'd love to hear more about Dash. Is itself a generic simulation that people have to, effectively, program themselves? Or is it implementing supply chain-specific logic like ordering or fulfillment?


Thanks for asking!

Value is actually the value of a state itself, and it can increase or decrease from one state to its successors. If the value must increase or decrease monotonically, then that (very useful) information can be given to Hop through a Bounds() method.

In the simplest cases, value is added or subtracted with each state transition, and can be stored in an attribute. However, that isn't required. It's possible to do just about anything in the value function, such as run a simulation to estimate a KPI.

If estimating value is expensive, then it's probably best to keep the diagram width low, and/or use a searcher that dives to high quality solutions before expanding the search. Hop comes with some of these capabilities built in, and most of its solver components are plug-able through interfaces so you can provide your own if you need.

When it comes to scale, we're trying to make it so Hop scales up and down well to different size problems. As you add side constraints such as precedence, time windows, driver hours, capacity, etc., you'll likely find that DDs do better since those constraints tend to support the search.

Dash is a generic discrete event simulation engine that (intentionally) looks a lot like Hop (JSON in/out, runners that package up sims as atomic binaries). Sim actors conform to a simple interface and use an event sourcing architecture to publish events, update state, and record measurements. We should have a blog post about it in the next couple weeks, as well as our docs posted online, so check back!

Congrats on the launch nextmv!

I had a chance to play with nextmv's beta when they first published it. By far the most useful aspect was the ability to bracket the decision results by calculation time. E.g., I can say, give me your best result of this choice given 100ms.

This changes the typical "train / test / deploy" ML process, to something where you can get as accurate a result as possible given some block of time. This gives you a lot more options when the value of having a super-precise decision drops off a lot after say, 80% accuracy.

For those of you familiar with rocketry, the technique is a lot similar to a Kalman runner [1]. Essentially when a rocket needs to gimbal adjust its trajectory, it has a ton of uncertainty about the nature of the environment, but it does an excellent job of making a fast educated guess for the simple purpose of "get me to this orbit and don't crash".

More generally, this gets to the core of the issues discussed in part 1 of the a16z article about AI companies [2]. Specifically that modeling to get to accurate result is a huge and hidden cost of ML, which makes it distinctly different from software startups. Decision science is an attempt to bridge that gap.

[1] https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture...

[2] https://a16z.com/2020/02/16/the-new-business-of-ai-and-how-i...

Thanks! This feature is extremely relevant to operational decisions. You can’t tell your operations team/ drivers/ etc that there is simply no plan because the algorithm is still running!

Congrats on the launch!

I've worked with Ryan a couple times over the years since 2009. I also interviewed with Carolyn once upon a time as well. These founders are the brightest in the industry!

They have developer's experiences at the top of the priority list. That's not something I see when looking at existing tooling in this domain. The problem they are solving is real and applies to so many industries both obvious and not and this is a modern toolset to bring in to your stack.

I cannot wait to see the many successes they will enjoy. I encourage anyone with an optimization / constraint solver in their stack to take a look at Nextmv.

Thanks for the love! We're learning a lot from the market already and plan to have plenty of interesting new features released in the coming weeks.

Thanks! We are excited about all the cool applications people will think of for this

I think that is a beautiful toolset you have built. Really like the way DDs fit into modelling problem domains as state machines. I have signed up and will check it out.

Thanks! Would love your feedback

Super cool and congrats on the launch! I love this idea, and if you are hiring, would consider working there just for the challenge alone. I've implemented the Held-Karp on the GPU in webgl if that counts for any bonus points :) I hope you all do well!

1-tree on GPUs? That's pretty interesting.

Ping us at tech@nextmv.io if you're seriously interested in talking more.

As far as I understand, this is for developers to develop algorithms, right? If that is the case, aren't the algorithms mature already? Or are we as developers just passing the data to existing algorithms and problem types of your system?

Thanks for the question!

In sound-byte form, this is for developers to develop algorithms.

What we really mean by that is for developers to easily automate decision making at any scale. Those can be simple rules-based decisions, or complex decisions requiring sophisticated approaches. We believe that the practice and methodology behind the automation are as important as the algorithms themselves.

Regarding your questions of maturity, it depends :). Some algorithms commonly used in decision making, such as linear sum assignment or shortest path algorithms are quite mature and (generally speaking) fast. Others are mature and often fast enough, but sometimes not. Plenty of important problems are more or less unsolvable right now.

Mixed integer programming solvers, for instance, are extremely powerful and handle large general classes of problems. They also require translation of business rules into specialized form by domain experts, and can blow up in terms of optimization time or even time to find a feasible solution.

Complicating this is the fact that most real-world problems have side constraints which may render well-studied algorithms or models useless. We are eternally searching for more flexible, more advanced techniques, and maturity depends a great deal on what you need to accomplish.

So the assumption is that the targeted developers work in an environment where business rules are translated into code and they have access to domain experts? They will use your system to develop easier.

By the way, I signed up for beta to try the system.

Awesome! We're very much looking for feedback on how we can improve it.

I'm an undergraduate who recently started entering the field of OR, and the idea of relaxing decision diagrams to make them polynomially sized sounds very interesting — the first time I hear about it.

Hey Carolyn and Ryan, how would you say this compares to the Google OR-Tools and their TSP solver? https://developers.google.com/optimization/routing/tsp

Congrats on the launch!

We haven't published any formal benchmarks yet. We will soon!

I'm not a regular OR-Tools user, but it allows you to call its own CP solver or external MIP solvers. I can provide a few general comments about what you'll find applying different techniques to TSP solving:

1. Nothing beats Concorde for solving pure TSPs: http://www.math.uwaterloo.ca/tsp/concorde.html

2. Mixed integer programming solvers do very well because you can relax the subtour elimination constraints to solve a simpler problem (such as an assignment or a 2-matching), and add them to the problem representation as they are violated in the search tree. With tight bounds the solver can fathom away most of the search space.

3. All of this breaks apart when you need to route multiple vehicles or handle side constraints (precedence, time windows, capacity). This is where CP, DDs, and Hybrid Optimization techniques start to really shine.

It's (3) that we're most interested in because realistic problems tend not follow simple, pure representations like the TSP. So when we do publish benchmarks (and their associated models) it will likely be for problems like the Li & Lim PDPTW instances (https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/).

Another important aspect is time to find high quality solutions. Most people doing on-demand routing need good solutions that are actionable quickly. DDs have already shown a lot of promise in this area.

traveling salesman as a service? interesting

I guess we're a TSaaS company. :)

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact