How Solr and Fusion Can Solve American Airlines’ Scheduling Snafu

Recently, American Airlines scheduled too many pilots off during the holiday season. This may surprise you but this too is a “search” problem.

Understanding the Technical Domain

If you visualize this as a document database (such as Apache Solr the back end to Lucidworks Fusion), there are a set number of fields associated with pilots and a set number of fields associated with flights. FAA regulations, pilot union work rules, and business rules set the conditions that make up the queries we’ll pass to Fusion and hence Solr.

Pilots have shift times, locations and vacation times. Flights have takeoff locations, takeoff times, landing locations and landing times.

In Fusion you model these locations as Solr spatial types like SpatialRecursivePrefixTreeFieldType and even simple LatLonPointSpatialField. These store essentially the X,Y coordinates of the plane, plane or anything you like. Solr can also model polygons and other “shapes” in space.

For the dates and times you have the DateRangeField. With it you can do a contains, within, or intersects operation.

Understanding the Rules

FAA regulations stipulate among other things that pilots:

• Have 10h of downtime every 24h
• Fly no more than 9h
• Not be on vacation

Pilots are in a city, have to take a flight to a city either as a pilot or passenger.

American Airlines business rules say essentially:

• A certain amount of vacation time is available based on excess pilot capacity
• Pilots get priority for that vacation time based on seniority

Modeling This in Solr Types

A pilot schema might look roughly like this:

• ID – IntPointField
• Name – text
• Date of Hire – DateRangeField
• Last Shift – DateRangeField
• Current Location – LatLong

A flight schema might look roughly like this:

• ID – IntPointField
• Model – IntPointField
• Start – LatLonPointSpatialField
• End – LatLonPointSpatialField
• Duration – DateRangeField

Available vacation time as a schema might look like this:

• ID – IntPointField
• Date – DateRangeField
• Number_allowed – IntPointField

It might be done as blocks or individual dates

Pilots “bids” on vacation time might be modeled like this:

• ID – IntPointField – IntPointField
• Time_period – IntPointField
• Pilot – IntPointField

Implementing the Rules

Implementing this is really a set of searches and adding documents to collections. When looking for a pilot, a Fusion query pipeline can be set up which takes the flight as an argument but constructs a Solr query which is essentially a search for the closest pilot who hasn’t had 9 hours of shift. If no pilot is found in range, then a wider range query is executed that finds a pilot that can be flown there (which also involves a subquery on an available flight).

For the distance queries it looks like this in Solr’s query language: &q=:&fq={!bbox sfield=store}&pt=45.15,-93.85&d=1. Essentially if you start at 45.15,-93.85 lat,long and we assume there is an airport there, then within a box including +1 and -1 (i.e. 44.15 to 46.16 and -94.85 to -92.85). Through this we can find out if a pilot is “close” enough.

For the time ranges, the Solr query looks something like datefield:[2017-12-20T17:30:00.772Z TO 2017-12-20T18:30:00.772Z].

You can also compare two date ranges using an Intersects, Contains or Within query. In Solr a query looks like this:  {!field f=Duration op=Contains}[2016-02-02T14:50 TO 2016-02-02T15:00].

For pilot vacation bids you have an orderby on hire date, that’s really it.

American: Call Me Maybe?

Clearly the rules are more complicated than what’s in the press. With that said, these are the basic sorts of problems they need to solve and Solr is super fast and well suited for that. Moreover Solr is proven, scalable, and has both high availability and disaster recovery taken care of.

When you add Fusion on top of Solr you can abstract away some of the complexity of this and even take advantage of AI to solve more advanced problems. So if you’re stuck in line this Christmas, think of this blog and think “Damn I wish they’d just use Fusion, then I wouldn’t be stuck in this line!” If you’re anyone else think about what problems you have that might be search problems and how you could use scalable, reliable and proven technology to solve them!

If you’re with American Airlines, call me maybe, we can help. You can find me on the contact page.