30 jan 2019
Dynamic Optimisation Insights
(with apologies to Herman Melville)
Call me Ishmael, it’s as good a name as any.
Unlike Herman Melville’s Ishmael, I am not a whaler, but an applied mathematician, and I design optimisation models for a living. Combinatorial optimisation models, if you want to be picky.
There a number of ways to define mathematical optimisation, but the one that I like is ‘choosing the best/ near-best alternative from among a set of alternatives’. The number of alternatives can range from a handful (should I have tomato soup for lunch? Clam chowder? Or go with the bisque?) to trillions (think of the number of possible routes to visit 100 cities, one after the other). In real life, it’s impractical to examine each and every alternative, and then choose the best – it would simply take too much time. That is why mathematicians developed various optimization algorithms, which efficiently find good/optimal solutions to a staggering variety of problems.
Optimisation affects your daily life in a vast number of ways, even if you don’t always realise it. That staggered sequence of green traffic lights that you hit (OK, were supposed to hit) this morning, when you drove to work? You can thank optimized traffic patterns. Ensuring that the vegetables you buy at your supermarket are fresh, with none starting to rot? Optimised shelf life for produce. The steadily shrinking size of the laptops and other electronic equipment you buy, year after year? Optimised electronic design. The list goes on, and on, and on.
The Prussian military commander Helmuth van Moltke wrote in 1880 “No plan survives first contact with the enemy”, and that piece of military wisdom holds in the world of optimisation as well. You can create a perfect weekly delivery plan for your fleet of vehicles at 6am on Monday, correct to the umpteenth decimal digit, and start to implement it – and at 0830 you receive word that because of an accident, an entire section of Route 101 has been closed down until further notice. At 1030, a customer calls in to cancel an order whose delivery has been scheduled for 1630. Oh, and at 1500 hours you get a call from one of your drivers that the truck he has been driving just hit a patch of ice, skidded off the road and is now non-operational.
Each and every one of these unplanned events requires some modification of that previously optimal plan – but which modification is best?
One alternative is to modify the input data to account for the changed circumstances, and re-optimize the plan – but this may take too much computing time. Even if it doesn’t, the structure of the new plan may look radically different from that of the old one, and if you keep hitting your drivers with one new_and_improved ‘optimal’ plan after another, they will very quickly lose faith in that black box churning out the plans, and start doing their own improvisations.
Another alternative is to keep as much of the original plan intact as you can, and make the fewest changes you need to in order to bring the solution back to feasibility. This is usually a good compromise, but will sacrifice some of the quality of the plan in order to get a quick fix.
Deciding between these alternatives is an example of dynamic optimization, where either optimal solutions need to be computed rapidly and repeatedly because the data changes frequently, or existing optimal solutions need to be modified because unplanned events happened.
There are a vast number of such problems out there, spanning the entire industrial spectrum – and developing good solutions for them can yield spectacular benefits. For example, a recent CNN article talks about an Alibaba invention called the City Brain, which uses artificial intelligence to gather information (such as video from intersection cameras and GPS data on the locations of cars and buses) across the city of Hangzhou in China. It then analyzes the information in real time as it coordinates more than 1,000 road signals around the city with the aim of preventing or easing gridlock. Usage of City Brain has reduced commuting time and helped first responders by enabling fire trucks and ambulances to halve the amount of time it takes to get to the scene of emergencies - it has also moved Hangzhou from the 5th most congested city in China to 57th.
In summary, dynamic optimization is an exciting field that can bring tangible benefits to virtually any company out there, and free up the time of skilled personnel to do things that people can do, but algorithms can’t – like make judgement calls, negotiate with customers to change the requirements for specific orders, and explore new areas of business.
After all, if Captain Ahab had just *used* that optimized whale-tracking algorithm which took wind and storm forecasts into account, ‘Moby Dick’ may have had a very different ending.
Author: K.N.Srikanth | Sri.email@example.com
The Murphy`s pub at the harbour. Film location for Moby-Dick in 1956. Youghal. county Cork. Ireland