It’s extremely interesting how solving a hard computational problem immediately translates into the scalability of a company so often! Take for instance the meal prep delivery model, where people order a week’s worth of food that’s then delivered locally. Strangely, there’s not many good options on how to solve the logistic challenge that arises, and indeed, it shows in my clients’ competitors that they’re still solving this problem manually! The problem is that you have to make a delivery to N people on a given day, taking the routes that minimize costs like gas, vehicle wear, time etc. Even worse, you need to split the routes to scale up the number of drivers.
Examining every possible route even for 1 driver would be an exponential number of routes to try! For slow days, it’s easy enough to map this out as many companies do, but from my testing, this is a very bad idea. For my clients this gets worse since customers get to pick the hour they want a delivery!
At the most abstract levels of Computer Science lies the lofty formulations of problems as either NP or P, or maybe just an exponential-time problem versus a problem that computers can solve in reasonable time. It seems strange that I’ve never really had to solve an NP problem before given their prevalence (you can only try to solve what you think you can!), but this time the problem was a textbook case of the Traveling Salesperson (or Traveling Salesman, for the macho out there).
After some looking, I got mega lucky and came across Optiplanner, a very mature library for solving just about any NP problem using approximation tricks! Even better, it’s in Java so I can hack some Scala on top of it for that super clean feeling only Scala and Herbal Essence gives me. After lots of tuning, a custom algorithm to find best departure times for a given route, unit tests and slappin on a Play API (for the first time, big fan!), I had a fully automated routefinding server!
Optiplanner: My rediscovery of Declarative Programming
After a few days of playing with Optiplanner it struck me, this is a generic problem solver, that can solve any tractable problem! It’s a different paradigm, similar to what Quantum Computing will someday be. Instead of imperative programming where you tell the stupid computer what to do each and every step, you instead only define a cost function that encodes what you’re optimizing for, and a description of the problem. Basically you just say, here’s what I want (minimize this cost function), and here’s the mechanics of the problem (say a physics engine, or the biz rules of deliveries in my case). You then sit back and drink (lots) of coffee, and eventually get back a result that’s either right, or so close to right you don’t much care about the 2 cents you lost from optimal since you’re a pragmatic business. The only alternative here is doing it manually and losing hundreds a day!
Generic Problem Solver: The caviats
While a generic NP problem solver like Optiplanner sounds like a magical fairy that should have replaced all nerds years ago, there’s obviously some catches that makes this an obscure tech, although it shouldn’t be! For one, you need a pretty solid understanding of approximation techniques that are essentially all doing the same thing: swimming through an exponential set of solutions in a generically smart way. It’s surprising how these quite generic assumptions such as sticking close to the current best solution, most of the time, works so well! I ended up with a mix of Tabu Search and Simulated Annealing after using some of their benchmarking tools. Finally you must be willing to accept a less-than-optimal answer for your needs. And of course, the more state you throw onto the solver to swim through, the slower your results (although not exponentially slower, as you might assume!). For example, I was able to figure out an O(n*log(n)) solution to find the best delivery times given a route provided to me by the solver. This allowed me to remove the “departure time” state from the problem, and have the solver focus on only the route order. If the solver had to guess both the order and the departure times, It’d be growing the problem so exponentially I don’t even want to try figuring out how bad that would be. It’s already bad enough that every time the solver needs to evaluate a route’s cost, it takes n*log(n) work to first find the best depart times before I evaluate the route for delivery lateness, earliness, mileage etc.
“Programming” Declaratively using the Cost function
Since this setup can solve any problem, how would I tell the solver that being late to a customer time window is bad but being really late is really bad? We have two options in declarative programming: change our description of the problem, or the cost function, nothing else. Funny enough both technically work here. We could define the problem as “Customers MUST get their delivery on time”, but then the solver would pretty clearly go haywire if this weren’t physically possible with the max number of drivers. Instead of risking this and making this service too brittle, I instead decided to define lateness as a cost. I take the minutes late to a customer and fit that to a quadratic curve, so that being late is as bad as x^2 grows. I allow the biz to decide how much money they perceive losing if they were 30 minutes late, and fit the graph to that point like below:
And voila! A fairly clean way to map a biz requirement of “Assume we lose $15 of customer value if we’re 30 minutes late” into a smooth, intuitive “code” inside a declarative engine. A future improvement might be to use a neural net to learn a function that maps lateness to probability of customer churn instead, but that’d take a whole lotta data! Pretty cool though thinking about mixing an NP-solver with a neural net, my top 2 declarative programming hammers!