Preferential bidding system

Preferential bidding is a method of solving transport workforce schedules consisting of specific flights and certain qualified crewmembers, or "pairings", while allowing those crewmembers to request periodic work schedules using weighted preferences.

Preferential bidding systems, or PBS, as they are commonly referred to are generally used in the transportation industry and most often in the Airline industry to generate a satisfactory crewing solution. This is due to the enormous complexity of the problem that must be solved in those situations. The problem, from a mathematical and logistic approach is specific to the transportation workforce, and very complex due mainly to the personnel and aircraft movement from place to place. Moving crews and aircraft from place to place as efficiently as possible while both respecting crewmember preferences and while conforming to a number of rules and regulations requires very careful and thorough problem solving. Partly out of respect for this mathematic and logistic crewing challenge, the process of generating a PBS schedule that respects crewmember requests while remaining efficient is called "problem solving" in PBS. And the resulting schedule is called the "solution". The general term for all methods of transportation workforce scheduling is often referred to as "crew rostering", or "crewing". The results are often referred to as "crewing solutions"

Pairings

Work schedules in the airline industry must cover not just a shift or a day, as workers in other industries might. Airline work schedules consist of assignments called "crew pairings" or simply "pairings". A pairing is a sequence of flights or "legs" which starts and ends at the same location. A flight from point A to point B and back to point A is a Trip. That trip, or a leg of that trip with a certain crew is called a pairing. In this case there are 2 pairings; point A to point B - point B to point A.

Crewmember bidding

In the airline industry the process of requesting a certain schedule is called "bidding". Generally this is done on a monthly basis. The monthly schedule which a crewmember gets will consist of a series of "pairings". This complete schedule, which specifies work and non-working days is called the "line". Each month the airline sets their pairings. These change due to new locations being added or removed, new times, or changes in the aircraft flown. These trips are then made available for assignment or bidding. In the United States, flight crews are often working under a union's collective bargaining agreement. In those cases, and sometimes in non-union workplaces, seniority is used to give senior flight crew the right to override lower seniority flight crew requests. The schedule for the month for a crewmember is called the "line". At a minimum a crewmember's "line" must satisfy legal and contractual constraints. Ideally it should also satisfy the crewmembers choices and preferences. Carry-in is remaining or standing issues from the previous month that affect a crewmembers schedule. This can include, but is not limited to, overtime, or extra vacation that was accrued. Carry-in must also be respected.

Constraints and preferences

Airline scheduling must generate an accurate and legal crewing solution each month. 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 crewmembers Line are called Constraints. Many constraints must be satisfied. Each "pairing" must satisfy 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, training, vacation requests or trip preference requests. Constraints imposed by the a crewmembers personal preferences and rights 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 line approach, trips are placed within a pre-built line, and do not take into account the individual crew members preferences or any constraints. The generic set of lines are then put up for bid to the crew and awarded in seniority order. A crew member then is free to choose almost any line, no matter how legal it is. A bid line solution, since they are created without reference to specific crew constraints, do not match or respect the crew members preferences. Specifically non-trip vacation and rest activities. This lack of integration often causes crew members to be awarded lines that conflict with their predetermined activities. The conflicting trips must then be manually re-assigned to other crew members resulting in a wide range of inefficiencies. Clearly this post-optimization reallocation is costly to the airlines, and a frustration to crew members. Airline management is eager to streamline operations and utilize their resources as best they can.

PBS

PBS allows a crew member to make choices from a number of offered trips. The crew member also makes their vacation choices and submits them. The main difference between the Bid Line and the PBS is that the LINE has not been created and the crew member has the ability to designate what trips and days off they prefer, thereby building a Line themselves.

Conventional preferential bidding

In a conventional PBS, each crew member makes their bid and chooses their preferences without knowing the preferences of other crew members. As a consequence, conflicts may still result in that some trips are chosen or preferred by too many crew members and some trips are preferred by few or no crew members. Once all the Bids are made and the bid period ends, the mathematic program attempts to create the solution. This is called "optimization". In the optimization process where the "solution" is generated, PBS attempts to reconcile conflicting bids yet has to deal with the bids that cannot be assigned as requested.

Interactive preferential bidding

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. This type of PBS usually runs as an externally hosted Web application allowing constant interaction with the optimizing algorithm or program. The feedback from other crew members during the bidding process combines with a bidding crew member's preferences to create the trips and to generate the best quality crewing solution available at the time they bids. If their preferences produce a poor line because of conflicts with crew members senior to them, the bidding crew member can change their preferences until they bid what he CAN get and until they get a Line which is also compatible with other crew member bids. 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. To allow some feedback from the beginning of the bid period even before choices or bids are made, a reliable initial base solution is generated from the standby or default bids, of each crew member.

By the end of the bid period, the bidding crew members have not only generated what they consider to be the best lines that are compatible with other crew members, but also the lines that are the most realistic. Since the interactive PBS generates a solution that respects a set of preferences submitted by crew members, the interactive bidding process truly optimizes crew preferences and lines.

References

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