Preferential bidding system

Preferential bidding system, or PBS, is a computer program providing Crew scheduling a method of solving airlines workforce schedules consisting of specific flights and certain qualified crew members while allowing those crew members to request periodic work schedules using weighted preferences. The solution must be as efficient as possible while respecting crew member preferences, honoring seniority, conforming regulations, and operation coverage requirements.

Pairings

Work schedules in the airlines industry must cover not just a shift or a day, as workers in other industries might. Airlines work schedules consist of assignments called "crew pairings" or simply "pairings", which is a sequence of flights or legs that starts and then ends at the same domicile. Parings are usually created by another computer program called pairing optimizer.

Bidding and Line

The process of requesting a certain schedule is called "bidding". Generally this is done on a monthly basis. The monthly schedule called "line" which a crew member gets will consist of a series of "pairings". Each month the airlines crew planning sets the new pairings due to new locations being added or removed, new times, or changes in the aircraft flown. These new pairings are then made available for assignment or bidding. In the United States, crew members are often working under a union's collective bargaining agreement, and sometimes including non-union workplaces, seniority is used to give senior crew member the right to override junior crew member requests. A line itself must also satisfy legal and contractual constraints. Ideally it should also satisfy the crew members choices and preferences.

Constraints

Each month, airlines crew planning must generate legal crewing solutions. These crewing solutions strive to achieve a minimum-cost of operation by matching specific aircraft, the routes they fly and crew pairings in a manner that each leg is covered by one crew that is capable of flying that aircraft at that time and in that place. The factors that must be respected when assigning a crew member line are called "Constraints" which include a number of federal regulations imposed by the FAA, as well as conform to any collective bargaining agreements. These include requirements for time flying, time between flights, total time flown in the month or week, and any leave, pay value, time credit, and training. Constraints imposed by the crew members' predetermined activities must also be respected.

Crew scheduling methods

There are two general approaches to solving this complex crewing challenge; Bid Lines and PBS.

Bid Lines

In the Bid Lines approach, pairings are placed within pre-built lines by Line Optimizer, a computer program that puts the pairings into "legal" lines, and does not take into account the individual crew members' preferences, nor the constraints imposed by crew members. The generic set of lines are then published for bidding. A crew member is free to choose any line and it will be awarded as long as no other senior crew member who also wants this same line. Unless the most senior in the bid package, crew member needs to submit multiple preferred lines in order to guarantee a preferred line; otherwise, a left over line will be awarded. By the bidding process, the preferred line may not be awarded completely, because the line was created without reference to specific crew member constraints, it may conflict with crew members' predetermined activities. The conflicting pairings must then be re-assigned to other crew members resulting in a wide range of inefficiencies. Clearly this post-award reallocation is costly to the airlines, and frustrating to crew members. These inefficiencies also force airlines to hire more crew members. However, bid line does offer a transparent and easy process to bid and to award, and in a lot cases the conflict itself actually benefits the crew members that being paid without the work according to the contracts. Though airlines management is eager to streamline operations and use their resources as best they can, crew members may still prefer the bid lines.

PBS

In the PBS approach, the lines have not been created at the bidding, and the crew members have the ability to designate what kind of pairings, the properties of the line, and days off they prefer, thereby building a line themselves. PBS also allows crew members to bid reserve duties mixed with the pairings biddings. PBS provides a one-step process from the pairings to the lines that each crew member prefers and can legally cover.

The real challenge for PBS is that it tries to solve two innately conflicted goals, honoring preferences without violating seniority and awarding all pairings.

Conventional PBS

In a conventional PBS, crew members make their bids and chooses their preferences based upon their own best interests. Once all the bids are made and the bid period ends, the program attempts to create the solution by an "optimization" process. Each crew member will be awarded the best line of his own definitions from available pairings at his seniority. For each crew member, when there are many best lines, the one with the least interest conflict to the junior crew members will be awarded, which is an advantage that interactive PBS cannot achieve. By the optimization, system finds a way to satisfy both senior and junior crew members while still honoring seniority and operation coverage requirement. The optimization process itself is complicated which may take many hours and multiple runs to achieve the optimal solution. A rejected preference happens when the pairing is awarded to senior, or overall coverage issue, or legality violation, and the reason for rejection will be provided.

Interactive PBS

Dynamic and interactive PBS, in contrast, changes the process of bidding into a "continuous" process, where crew members can see the status of other crew member bids reflected as they bid. The web based presentation of this live and continuous schedule status is currently (as of 1-2010) a Patent Pending process of Mr. Christian Boegner. It is this live awareness which allows crew members to bid realistically because they see and can only bid for trips and days off that are available to them at their seniority. In the end the schedule which is solved is very efficient since crew members submit the preferences free of conflict with the other crew members, though not their best interests. It gives every crew member the "highest satisfaction". It is a relatively new approach. Currently (February 2011), there is only one company providing a dynamic real-time PBS application; Crewing Solutions based in California, founded by Christian Boegner.

A somewhat similar interactive Preference Request System offered by Kernel Software is used by Lufthansa. It does not build complete schedules as does the Crewing Solutions PBS.

”Kernel Software strongly disagrees with this statement. It also thinks that Wikipedia is not the appropriate place for such discussions, and refers the interested reader of PBS to its web site for detailed information about this specific Crewing Solution PBS”.

Mr. Boegner is an expert in Heuristic algorithms. He is respected worldwide and regarded as the "Father of PBS" having introduced the concept in the 70's and eventually implemented in SmartPref, the Crewing Solutions product. There is competing school of thought that Linear Logic is the best approach to solving the "problem" efficiently. The company SBS, he headed, installed over 100 scheduling systems with airlines. SBS was eventually sold to Boeing.

This dynamic real-time PBS uses heuristic algorithm running as a hosted Web application offers live current status of other crew members bids during the bidding process. A crew member designates their preferences, both globally and specifically, based on seeing real availability at that moment, at their seniority and submits a "Bid" for trips and work days. The PBS then assesses these new preferences and immediately builds a new schedule/solution, and presents this in the web based GUI to any viewing crew member. That solution combines a bidding crew member's preferences with the existing data to create the pairings and to generate the best quality crewing solution available at the time they bid. The PBS attempts to determine what is in the bidders best interest based on those preferences previously input and continues to consider all crew member preferences throughout the remaining bidding window.

As bidders continue to enter bids, the schedule begins to take shape. In the LIVE PBS environment a crew member can return to view the status of their choices at any time. They can elect to change their preferences and resubmit them if the environment has changed such that they now wish to try to improve their situation. During the bidding process, in order to have a realistic line, crew member has to constantly adjust his bids until all his senior crew members finalize their bids. Some crew members will come back later after bidding and see a less desirable line mainly due to overriding conflicts with the senior crew members. In these cases the bidding crew member must change his preferences until he bids what he CAN get and until he gets a line which is also compatible with the data at hand by compromising his interests.

The interactive PBS gives the problem of solving conflicted interests to crew members which leads to a much simpler design in system in comparison to a conventional PBS. The resulting bid is considered optimal in that the bid preference parameters are the most accurate and efficient with respect to constraints and preferences at the present state of the solution and the seniority of the crew member. However, at the beginning of the bid period even before choices or bids are made, a reliable initial base solution must be generated from the standby or default bids, of each crew member. Although at this initial stage, the results are far from real, in the end when every one submits their bids, the results will become realistic.

Without a LIVE PBS's interactive recalculation during the bid period, if crew members bid for certain pairings and/or days off heavily over others, at the end of the bid period either an advanced, time consuming algorithm needs to be implemented to solve the resultant conflicts automatically, or manual manipulation is used to fill the "open time" (unassigned pairings).

With the live interactive PBS, it only offers "left over" pairings to crew members and naturally forces the crew members to cover them with the advantage knowing of what their schedule will likely be.

Implement PBS

PBS is not a new concept and the products have been available in the market and used in many airlines for many years. The algorithms used may be very different and usually lead to very different results and satisfactions. In addition, the user interfaces that provided for crew members to enter the preferences are also very different from vendor to vendor. The evaluation of the PBS products and the negotiation between the management and crew members are the most important and critical steps of a successful implementation of the PBS.

List of a few PBS Software Vendors

AD OPT, division of Kronos, AIMS, AOS/Advanced Optimization Systems, CrewingSolutions, Jeppesen/CarmenSystems, Kernel Software, Navtech, Sabre, IBS Software,

References

• Barnhart, Cynthia; Belobaba, Peter and Odoni, Amedeo R.; 2003. "Applications of Operations Research in the Air Transport Industry." Transportation Science 37(4) 368-391.
• Gamache, Michel; Soumis, François;, Villeneuve, Daniel; Desrosiers, Jacques; Gélinas, Éric; 1998. "The Preferential Bidding System at Air Canada." Transportation Science 32(3) 246-255.
• Tumpson, Daniel; Optimized Preferential Bidding Systems: Models and Implementations 2005 - Crewing Solutions, LLC Transportation Science