AI strategies for daily helicopter planning

This article describe our custom approach to complex business challenges.

As a use case, we will take a look at daily helicopter planning.

The problem

Imagine you are in charge of the daily planning of helicopter transportation.

Every day, you receive a list of flight requests. Every request has information on how many people need to go to what location, and by what time. Your job is to decide what requests to plan when.

Because you (pick at least one reason)

1. like your job
2. like puzzles
3. like to please your passengers
4. like to use the helicopter as efficient as possible

you ask yourself the question: What planning strategy should I choose?

But you also realize that doing this by hand is no fun - there are way too many options to consider!

Fortunately, we are here to help. We will show you how to design an AI algorithm to assist you in coming up with great strategies.

The rules

Let's start with some data basics.

First, your helicopter has a capacity, both in seats and in flight time. The former means you can't fit more people than the number of seats you have available. The latter means that you need to make sure you refuel in time. Also, fuel isn't available anywhere - you can only refuel at designated locations.

Second, your helicopter is very popular (good for you!) and the number of requests vastly outnumbers your capacity. You won't be able to plan everything. (If the number of requests was small, you wouldn't have to decide what to plan - only when.)

Third, requests contain information on group size, time window, locations, and priority.

The group size represents how many people wish to travel together. Groups can't be split. (Imagine booking a family holiday flight, only to find out at check-in you got put on different planes. Not cool.)

The time window represents the earliest and/or latest date on which each group wishes to travel. You can't plan a group outside of their window.

The locations represent the origin and destination of each trip. Though your passengers prefer direct connections (who doesn't?) they can tolerate detours and stopovers.

Finally, the priority dictates the relative importance of this request over other requests. All other things being equal, higher priority requests should be chosen over lower priority ones. (Though in practice, all other things are seldom equal. Figuring out what to do with these trade-offs is part of the fun of this puzzle.)

The score

Now imagine you have come up with a planning strategy that obeys all the above rules. You could, for instance, take your request list and plan on a first-come first-served basis. (Keeping in mind to plan all high priority requests first.)

How do you figure out how good this approach is?

To answer that, you need metrics. In the case of helicopter planning, a few ideas come to mind:

• You want to schedule as many requests as possible
• High priority requests are more important than lower priority ones
• You wish to plan your route as efficiently as possible

Based on this, you could opt for the following metrics:

• The number of requests scheduled, per day
• The number of high-priority requests scheduled, per day
• The total distance traveled, per day

Note that there are natural trade-offs between these metrics. Planning all high-priority requests may mean planning fewer total requests. Traveling as little as possible does not guarantee you're planning many requests. (Imagine not traveling at all - great for the distance metric, not so for the other two.)

The algorithm - first attempt

With the rules and metrics in place, let's focus on the design of our planning algorithm.

A daily plan aims to answer two questions: what requests are being planned, and when?

The first approach we could take is to look at this problem from the perspective of a single request. This seems obvious since the what and when questions both pertain to individual requests.

For every request, the algorithm should answer two questions

• Is this request planned?
• If so, when?

Imagine that we can answer the first question for every request. We can then keep the planned requests and remove the other ones. (How exactly we figure out what requests to keep is not clear yet, but bear with us. Let's call this method Black Box One.)

With our list of planned requests, we now need to figure out when to plan them. This timing is dependent on the sequence in which requests are planned. More specifically, the request timing depends on the sequence of locations that the heli visits. This sequence, the heli route, allows us to verify whether all routing constraints are met. For instance, we need to ensure that we have enough fuel to plan all requests. (How we turn our request list into a route isn't clear either. We'll call this Black Box Two.)

To summarise, we have

• An algorithm (Black Box One) that selects what requests to plan
• Another algorithm (Black Box Two) that takes its output and constructs routes

This approach has at least three challenges.

First, there are 2^N (N being the number of requests) options for Black Box One to select. Given that you are facing a lot of requests (think of N as being of the order of a hundred) this is not looking good.

Second, constructing routes from request lists (Black Box Two) is non-unique, so we will need a recipe to help us out. (How do we know whether that recipe is any good?)

Third, the feedback from Black Box Two to Black Box One is rather narrow. Black Box Two mainly says whether requests can be turned into a route for that day, and how good that route is. Turning that information into something to guide Black Box One is far from trivial. (Let's make this practical. Imagine Black Box One has selected 50 requests. They are fed to Black Box Two who tells you they can't be turned into a route for the day. How do you figure out which of the 50 you should drop to get a successful route?)

Considering the above challenges, we are not exactly set up for success. Let's change tactics.

The algorithm - second attempt

Instead of deriving routes from requests, let's turn things around. Let's imagine having

• An algorithm to select a route (i.e., a series of locations to be visited).
• Another algorithm that, for a route, decides what requests to assign to that route.

Both algorithms could work in tandem. First, the routing algorithm decides on a route. Then, the assignment algorithm plans requests for that route, leading to a score. This score is then fed back to the routing algorithm, which updates its routing decisions. This process repeats until convergence.

This approach has several advantages:

• Routes can be partial. This means the first algorithm can receive feedback while constructing routes. Also, routing constraints can be naturally incorporated.
• Planning requests for a given route can be framed as a well-known assignment problem. Also, we only need to consider requests that are compatible with the route. This greatly lowers the number of requests to plan.

An ideal candidate for the routing algorithm is a Monte Carlo Tree Search [ref 1]. An MCTS is a flexible framework to navigate large decision trees. It exhibits exploration/exploitation trade-offs, intermediate-decision feedback, and the use of prior information. All three are relevant to our use case.

The assignment problem can be solved with a constrained optimization solver [ref 2]. Such solvers use integer programming techniques and are very flexible in handling constraints - ideal for our use case.

The algorithm - final design

So, to design our AI assistant, we propose to use a hierarchy of two solvers.

The first element is an MCTS. It aims to answer the following question:

• Given a list of possible locations,
• And given routing constraints (such as fuel constraints),
• And given a score per candidate route (from the assignment solver + distance traveled),
• Return the optimal route

The reason the MCTS works is that it acquires information about routing options through self-learning. The MCTS makes thousands of routes. The first ones are typically quite bad. However, every new (partial) route provides the MCTS with some useful information about the quality of that route. The beauty of the MCTS design is that it can use those little pieces of information to gradually optimize its overall routing strategy.

The information that drives the MCTS is provided by our second solver - the assignment solver. It answers the following question:

• Given a route (from the MCTS),
• And given a set of requests,
• And given constraints (such as the heli capacity, time windows, start/end locations, etc),
• And given a score function (# of requests scheduled + # of high-priority requests scheduled),
• Return the requests that fit the sequence,
• Such that our score is optimized

This design of a solver hierarchy is very powerful. It has been used in many other problems like AlphaZero [ref 3] and is able to produce results a single solver could never achieve.

Closing comments

This article gives an idea of how to break down a complex business problem and build an AI assistant to guide business decisions. In this example, we landed on a dual-solver strategy to tackle daily helicopter planning. This strategy has shown to perform really well in practice, leading to significant performance improvements over existing baselines.

References

[ref 1] https://en.wikipedia.org/wiki/Monte_Carlo_tree_search

[ref 2] https://developers.google.com/optimization/cp

[ref 3] https://www.deepmind.com/blog/alphazero-shedding-new-light-on-chess-shogi-and-go

Image credits

[heli] shutterstock id 1409943038, Monumasud

[algorithms by complexity] source: https://xkcd.com/1667/

[chaos] shutterstock id 1980068852, Mironov Konstantin