The solution we developed generates recommendations for adjusting the flight schedule to decrease...
Rosterize Bushido - what makes us different
Bushido (武士道, "the way of the warrior") is what we chose at Rosterize.
At the outset of our research and development, it became crystal clear that Rosterize product journey would be different. Crew optimization is our domain and we are quite good at it because of doing things our own way.
Bushido is also about regulations for samurai attitudes, behavior, and lifestyle. So, we would like to share our experience and ideas why we believe our algorithm is special and how we managed to succeed, especially with so many tried and failed.
What great things a person could do if not imitating the others! (Bushido)
Rosterize is an AI add-on to any flight operations and crew management system that empowers operators with AI-assisted crew planning.
Our story started in 2019 when we were contacted by one regional charter and scheduled airline to help them with crew planning. And although our team already had years of experience in Operational Research, we did not deal with the aviation industry.
Our brief market research uncovered the absence of solutions for small and midsized airlines.
The main point is that, please, no offense, the well-known providers proudly work with the largest players and have no intention of providing optimization products and services adjusted for the smaller operators.
Smaller operators need different business approaches. This is why we decided to focus on their needs. Currently, we easily handle 50 tails.
Throughout your life advance daily, becoming more skillful than yesterday, more skillful than today. This is never-ending (Bushido)
Conventional crew planning is about going step by step. I'm sure you all know the process very well, but I'd like to give you a quick walk-through just to highlight how our approach differs from the conventional one.
All usually starts with generating and simultaneous filtering of all possible pairings, because without filtering you’ll get myriads of options. It is good filtering that matters here. If a good pairing is overlooked for some reason, a crew can't be rostered on it.
This approach is used by the majority of airlines. The key challenge here is that the generation of possible pairings and the selection of the optimal ones are two separate processes.
At the same time, each model is quite simple and makes it easy to fulfill FTL requirements for pairings, which is a great thing of course. This is why such conventional solutions are good for large airlines.
In our opinion, the vast majority of existing pairing algorithms are heuristic.
Adding more finer details to such a heuristic requires much extra effort. It is similar to the Tower of Hanoi puzzle. Eventually, developers spend a lot of time, but an algorithm still fails to perform as expected.
For example, if a certain pilot is unavailable and you have to take it into account, you might need to generate pairings for this pilot exclusively and then deal with the skyrocketing number of options.
Incorrect decomposition makes the task not challenging but cumbersome, and thus adds complexity to the entire crew planning system.
When the time comes, there is no moment for reasoning. And if you have not done your inquiring beforehand, there is most often shame.(Bushido)
Now, let me show you what we do.
Instead of crew pairings, we only generate flight duty periods. The number of options is fewer, so we can generate every single one of them without missing anything.
Then we use a solver to group flight duty periods into pairings. Basically, the solver "says" that this set of flight duty periods and, consequently, pairings works best for you.
To accomplish this, we implemented FTL requirements at the MIP level. In some cases, it was a challenge.
Generally, we now identify better options than our big-league competitors, but focus on smaller airlines, as currently we can handle up to 50 tails.
For instance, we can implement elements of robust optimization. No good pairing will be overlooked and we'll keep a bad/unstable one only if there are no other options.
However, there could be plenty of flight duty periods as well, so careful filtering is must-do here.
We use the following hints and rules:
- Positioning priorities
- Crew swap during flight duty period
- AirCraft type swap during the pairing
- Accommodation rules
- Common sense
When facing a big task, it helps if you break the task down into smaller, isolated and more manageable jobs by aircraft type, by crew base airports, or day ranges.
If a decomposed problem is still too complex for fast resolution, we solve it stepwise as follows: First, the continuous problem (LP) is solved and some variables are fixed using the reduced cost method. Then we determine the most important results for the MIP problem. For example: can we avoid violating the law or are there enough pilots for the job? Finally, we solve a dramatically simplified MIP problem given all the restrictions and look for the best solution here.
You may say now that we decompose a problem into parts similar to the classic pairing and rostering. Yes, we do decompose the problem, but differently.
A man who has never once erred is dangerous. (Bushido)
Having worked on our product for three years, we engaged a lot with customers and software companies which also tried to do something similar, but failed. Solutions from big vendors are not the best fit oftentimes, but optimization is still a vital need.
So we want to share the most remarkable insights and valuable lessons we have learned:
- Many people believe they are algorithm programmers, but they are not. One cannot simply program an algorithm. It’s a bit more complicated. So we don't do basic programming, but real computer science.
- Many people underestimate the problem and approach it as a mere travelling salesman or scheduling problem, so they start at the wrong place.
- Schedulers with a ten-year experience just feel how to make the crew roster right, but can hardly explain how exactly an optimization tool should work and under what rules.
- Getting raw data of good quality is incredibly difficult. Thorough data cleaning and preprocessing take a lot of time and effort, but otherwise the result will be of little practical use.
- Mainstream approach leads to conventional outcome. We needed more, so we went our own way to elaborate a unique solution and achieve excellent results.
- Creating such an algorithm is a continuous R&D. No guarantees, no deadlines, and no results. So if you decide to create your own algorithm, get ready to make as many mistakes as possible. When we started, we misestimated costs, which turned to be ten times more at the very least.
Matters of great concern should be treated lightly. (Bushido)
We are proud of what’s done so far and think that our crew scheduling method really works.
The tool is rather flexible, which turned out to be an advantage, because that's what in demand among airlines. Usually it takes a couple of days to implement flight rules of any particular country. Airline-specific rules are completed within a week, if something extraordinary comes up.
It turns out that calculating provable demand for crews is easy, as we can support our results with pairings and full-fledged rostering.
Various algorithm modes is a convenient thing to do and we are working on it now:
- Flight schedule adjustment
- Weekend planning
- Charter window availability
We have completed more than 20 projects globally applying the same algorithm for completely different scenarios. We work better and faster with each new project, enriching system functionality.
Even if system processing time really matters, it will heavily depend on the specifics of both source data and the problem to be solved. For example, finding the minimum number of crews for a given schedule is usually twice as slow as generating a schedule for given crews.
For clarity's sake, I can say that it takes an hour or so to generate pairings for 15 planes, 100 pilots, three bases, and 1,000 charter flights.
There is nothing outside the thought of the immediate moment.