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, 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 aircraft and 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 called FAR's, 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 manually 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. But, bid line offers 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 mathematic 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. 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. It is actually like a real-time line builder which asks every crew member to bid at same time in order to know what the other senior bidders' preferences are and encourage to bid left over pairings with little optimization involved. Because, in the end, every crew member submits the preferences without the conflict with the other crew members', it gives every crew member the "highest satisfaction", but not their real best interest. It is a relatively new approach. Currently (June 2010), it seems that there are only two companies providing dynamic real-time PBS application; Crewing Solutions based in California, founded by Christian Boegner, and Kernel Software, which provides the PBS used by Lufthansa.

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 and the SBS was eventually sold to Boeing.

This dynamic real-time PBS uses heuristic algorithm running as an externally hosted Web application. The feedback from other crew members during the bidding process combines with a bidding crew member's preferences to create the pairings and to generate the best quality crewing solution available at the time they bids. If his preferences produce a poor line because of conflicts with the senior crew members, the bidding crew member must change his preferences until he bid what he CAN get and until he gets a line which is also compatible by compromising his interests. Giving the problem of solving conflicted interests to crew members which leads to a much simpler design in system. 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. 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.

Without the interactive recalculation during the bid period, if crew members bid for certain pairings and days off heavily over others, at the end of the bid period, either an advanced algorithm need to be implemented to solve the conflicts automatically or a manual manipulation is needed to fill the open time (unassigned pairings). With the interactive PBS, it only offers left over pairings for junior crew members and naturally force junior crew members to cover them.

Implement PBS

PBS is not a new concept and the products have been available in the market and used in 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

AIMS, AOS/Advanced Optimization Systems, CrewingSolutions, Jeppesen/CarmenSystems, Kernel Software, Kronos/Ad-Opt, Navtech, Sabre

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