The World Food Organization (WFO) is in the business of getting food to the places that need it most. Sometimes that’s in response to a crisis, other times it’s a long-term mission to improve regional nutrition. While some of their work involves charming governments into handing over money for projects, the real heavy lifting happens on the ground, finding and delivering food to those who need it.
Now, if you're imagining that the WFO's operational costs are a major headache, you're absolutely right. It's not just about finding affordable food — they also need to figure out how to get it to the people who need it, without breaking the bank. Enter "route optimization algorithms," a subfield of operations research that’s all about making logistics run like clockwork.
These algorithms can get pretty darn complex though. Which is why the WFO gladly accepts the help of Phd's, typically from operations research departments, who have experience with these tools and offer their services for free. Before we dive into the geeky details, though, let’s take a moment to appreciate the kinds of algorithms that get used in this high-stakes game of food delivery.
The type of algorithm
There is a well known problem in operations research that is known as the "travelling salesman problem" that is related to what the WFO needs. The problem revolves around visiting a bunch of cities on a map, kind of like what a salesman might do, but to do it in such a way that the total distance travelled is a small as possible. If you are going to tour cities, you'd preferably do that without wasting all your money on gasoline.
This problem sounds simple enough, but things can get pretty complex pretty quickly. Imagine that you have 5 cities and you would like to be 100% sure that you've got the shortest possible route. One tactic could be to just loop over all the possible routes between all the cities and to pick the route that is shortest. In this case that would mean you need to go through 120 (5 x 4 x 3 x 2 x 1) different routes. To understand this number: there are 5 cities in the beginning to pick from, once that is set there are four cities to consider next, then three, etcetera.
When there are just 120 routes you can have a computer enumerate through all of them. But suppose now that we double the number of cities to ten instead. Then we would have 907,200 combinations. What about fifteen? That's more like 326,918,592,000.
Scale is really working against you here. You need to do something more clever that just "try out all combinations" simply because of how this search space explodes.
The simplest technique is to eagerly accept that you're not going to be perfect. Pragmatism, after all, beats purity. Maybe we don't care about having the shortest possible route, maybe we're also fine if we manage to get one that's short enough. If we allow ourselves this freedom, we might try some heuristic approaches. These don't guarantee us optimality, but they do help us come up with a system that doesn't need to check every possible route. One approach could have us start by just linking the cities by shortest paths first. This is known as a "greedy" approach, one that does not guarantee us optimality, but it should give us a starting point that is reasonable from which we can try to make improvements iteratively.
One of these iterative improvements revolves around detecting paths that cross. Whenever that happens you can swap two cities and get a better route as a result.
As said before, a variation of the travelling salesman problem is needed for the WHO. But it is vitally important to recognize that this variation is much more complex than what the travelling salesman needs to do! In the classic travelling salesman problem we're dealing with a single salesman who has no maximum carrying capacity that can take as long as he likes to visit all the cities. In real life you'd be dealing with a fleet of vehicles, lots of warehouses as well, maybe even a shipyard and time constraints to get the food to the right city in time. Not to mention that there are lots of different types of food, some of which can spoil.
All of these aspects make the problem much harder. Instead of searching through all the possible routes, you suddenly also have to expand the search-space to also include all those other constraints.
The field of routing algorithms, and operations for the matter, is incredibly interesting and there's a lot of useful work being done in that realm. But the field as a whole typically does rely on a family of algorithms that come with a big practical downside. You can apply iterative systems to improve the allocation of goods. But, as a result of being iterative, these algorithms typically carry a lot of state which makes it very hard to write algorithms for these problems that can execute concurrently. It's incredibly rare to find algorithms that can parallize nicely on many different machines or on a GPU. So even if you have big cloud compute at your disposal, you can still be constrained to a single machine simply because of the family of algorithms that you're stuck with.
Progress
Hopefully, with that introduction done, you can imagine how hard it can be to find an algorithm improvement. When these algorithms were introduced to the WFO, many years ago, they were able to capture a lot of low hanging fruits. But now, well over a decade later, it is much much harder for a Phd to make a dent in the system.