Ad Opt

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Ad Opt
Founded 1987 (1987)
Founder François Soumis
Headquarters Montreal, Quebec, Canada
Parent Kronos Incorporated

Ad Opt is the airline crew planning division of the U.S.-based multi-national human capital management software and services company Kronos Incorporated.[1]


Ad Opt was founded in 1987 by François Soumis and four other operational researchers from the decision analysis research group, GERAD, and the CRT (Centre de Recherche sur les Transports/ Research Center on Transportation) in Montreal, Canada. Originally, they worked on developing truck itinerary management software for mining companies.[2] It was only later that the company concentrated on developing software to manage crew planning (Altitude) and shift worker schedules (ShiftLogic).

In 1999, the company was listed on the Toronto Stock Exchange (TSX) under AOP.

With ShiftLogic, they later expanded their horizons into other industries including manufacturing, hospitality, and transportation, among others. In 2001, Ad Opt purchased Total Care Technologies to include staff scheduling in the healthcare industry to their product list. [3]

In 2004, Ad Opt Technologies Inc. was acquired by Kronos Incorporated. This acquisition was part of Kronos' expansion into the field of employee scheduling optimization.[4] Kronos' Workforce Management software that schedules hospital employees and Ad Opt's ShiftLogic scheduling engines were going to be merged to create a more efficient product.[5]

Today, Ad Opt's operational research team maintains close ties with GERAD and its teams by funding some of their research projects in the aviation scheduling domain.[6]

Crew planning optimization[edit]

The goal of crew planning optimization is to solve for the best solution at the lowest cost to the airline. In other words, airlines would like to increase their productivity while minimizing crew costs and improving, as much as possible, crew quality of life. In order to plan their monthly schedules, airlines must consider operational limits, including but not limited to: country requirements, airport regulations, union rules and collective agreements. Before the era of technology, this process was completed by hand by a team of crew planners. Often they just attempted to make all their flights fit with the number of employees that were available. Crew planning optimization was then implemented to take all of the limits and some of the crew preferences into account. Using Operations Research (OR) to develop mathematical tools, the optimizers build highly cost-efficient pairings and then assign these pairings in an efficient manner to the crew members (both in the cabin and cockpit). This technological advancement has proven to be an important cost-reducing tool for airlines and has significantly improved crew quality of life.

Ad Opt's Altitude Suite is composed of:

  • Altitude Insight
  • Altitude Pairing
  • Altitude PBS
  • Altitude Rostering
  • Altitude BLISS

Optimization technology[edit]

The software is powered by GENCOL, a general purpose column generation algorithm owned by Ad Opt, designed to solve airline scheduling problems.[citation needed] The column generation allows the software to produce real-life scheduling solutions by solving large-scale complex optimization problems.[7] Ad Opt was the first company to use column generation technology to solve what is considered to be the most complex of optimization challenges: Airline Scheduling.

GENCOL is built around a shortest path with resource constraints algorithm. The column generator (or sub problem) shares information with the master problem. Together, with other optimization algorithms, such as the Dantzig-Wolfe decomposition algorithm, these components drive optimization. Ad Opt's master problem component is generic and allows the software to use different engines to produce the dual information needed by the generator. In many cases, Cplex engines are used, but also use heuristics.[8] Because column generation does not produce integer solutions, the scheme is embedded in a Branch and Cut/Bound framework. The framework defines an interface to branching "methods" that compete to make fractional solutions more integral. Each method evaluates what it can do on a given relaxed problem and the best one gets to modify the problem.[9]

The role of the master problem is to find the optimal solution to the current restricted problem. The sub problems are used to verify if the master problem is optimal and to generate the variables that could potentially join the master problem.[10]

Crew pairing[edit]

Altitude pairing[edit]

In pairing, the goal of the optimizer is to increase productivity and minimize operational costs while maximizing operational efficiency. Its task is to pair flight legs that comply with all airline rules, contract agreements and government regulations into pairings deemed legal by these standards. A pairing is a block of one or several days of work, including periods of duty time and rest time.

The solver takes into account the number of crews at each base, costs of hotels, per diem rates, deadheads and other business costs to optimize the pairing set.[11]

Crew rostering[edit]

The goal of crew rostering is to feasibly assign all the pairings planned during the planning period. All pairings must adhere to operational constraints as well as crew preferences to a certain degree, depending on the type of scheduling.

Altitude PBS, Rostering and BLISS are different flavors of rostering systems.[12]

Altitude PBS[edit]

Altitude Preferential Bidding System (PBS) uses Ad Opt's web based iBid crew interface to gather crew requests and optimize these with the solutions from Altitude Pairing. This approach is widely used in North American airlines.

The bidding process accumulates a bidding score for each employee. The system then uses the optimizer to assign a schedule that yields the highest possible score to each employee. The optimizer also takes into account all pre-assigned activities, such as vacation or training periods, of the crewmembers.

The system uses the following rules in solving the problem. Each employee schedule must:

  1. be feasible, legal and conform with government rules and the collective agreement;
  2. ensure that the set of residual pairings can feasibly be covered by junior crew members' schedules;[13]

Altitude rostering[edit]

This method is very similar to PBS. It also uses the iBid interface to gather crew preferences. However, instead of attributing the highest score to the most senior crewmember, the optimizer aims for the highest global satisfaction score. It is based on a fair share, or equity model. This approach is widely used in European airlines.

Altitude BLISS[edit]

In Altitude BLISS, or Bidline Integrated Scheduling System, the optimizer does not build schedules for each individual employee, but instead builds anonymous bidlines. Bidlines are monthly schedules that, again, satisfy all airline rules, contract agreements and government regulations. The schedules are built and optimized following a set of recipes. Recipes are a combination of instructions/preferences such as weekends off, regularity in day of week departure, pairing ID, time of day, length of pairings, etc. Airlines will also tend to build recipes around what the crewmembers like. This approach has been largely replaced by PBS as the latter takes the crew preferences into account before rostering starts. However it is still employed by some North American airlines.

Once the bidlines are constructed, they are published to the crewmembers. The employees will then bid on the lines that they prefer. At the end of the bidding period, the optimizer will assign the lines according to seniority.[14]

Manpower planning[edit]

Altitude Insight[edit]

Altitude Insight, formerly known as Altitude Manpower Planning (MPP), is a tool that enables airlines to plan crew requirements, months or years in advance. Airlines can also use the forecasting capabilities to run "what-if" scenarios to see the impact in crew hiring of potential aircraft purchases or the opening of a new destination or base.[15]

Crewmembers can manage their career progression by bidding for open positions. Through the iBid Crew Interface, Altitude Insight also processes crewmembers’ equipment and promotional bids.

Altitude Insight also includes the Just In Time Training optimizer module. Just In Time Training plans out efficient crew training schedules so that airlines can manage which crewmembers need training for promotions or to new positions. Often, these promotions, which can result from new aircraft purchases, are accompanied by a salary increase as soon as training is complete. It is therefore not cost efficient to train employees as soon as the position is accepted. Altitude Insight takes into account the salary increases, all infrastructure costs, and the preplanned activities of all employees to be trained and constructs the training schedule that will be the most cost efficient and disrupt operations the least.

Altitude VBS[edit]

Altitude Vacation Biding System (VBS) integrates with Ad Opt's other software to manage crew vacation time. VBS takes into account the vacation time of each employee, and their vacation requests taken from iBid to grant vacations.


The iBid Crew Interface is a WEB application that enables crew members to input their scheduling requests from anywhere in the world. Using Web 2.0 technology, it has a multi-tab design and desktop application-like behavior so crewmembers can start using the Crew Interface with minimal prior training. In this interface, crew members enter their preferences and can view bid popularity.Bid popularity shows more junior employees what more senior employees are requesting the most. This enables them to get an idea of the likelihood of being granted the pairings or days off that they desire. This technology makes it easier for the crewmembers to bid more successfully.


In 2011, in order to support the introduction of FRMS (fatigue risk Management System) requirements as described in ICAO annex 6[16] and government laws such as the US HR 5900,[17] Ad Opt entered a partnership with Circadian. Circadian provides 24/7 workforce performance and safety solutions for businesses that operate around the clock, through consulting expertise, research, and software tools, Circadian helps organizations reduce the inherent risks and costs of their extended hours of operations.[18]

Circadian's Alertness Simulator (CAS) conducts root analysis and investigation of fatigue. This enables the end-user to view the data on Ad Opt's interface.[citation needed] Airlines will be able to verify how crewmember alertness will be impacted by their flight schedules through Ad Opt's planning interfaces.[19]


Some of Ad Opt's clients include:[20]

  • Air Canada
  • easyJet
  • Emirates Airlines
  • Etihad Airways
  • FedEx
  • Qantas Airways
  • South African Airlines
  • United Airlines
  • UPS
  • US Airways
  • Virgin Blue


  1. ^ "Kronos (AD OPT Division) Company Profile". ORMS Resource Directory. Lionheart Publishers. 2007. Retrieved 6 July 2011. 
  2. ^ "Partners". GENCOL. GERAD. Retrieved 6 July 2011. 
  3. ^ Desrosiers, Jacques (February 2010). "GENCOL:Une équipe et un logiciel d’optimisation" (PDF). Cahiers du GERAD (in French). GERAD. Retrieved 7 July 2011. 
  4. ^ "Kronos to buy Montreal's AD OPT for $53.9M". Boston Business Journal article. Boston Business Journal. 6 October 2004. Retrieved 6 July 2011. The acquisition is part of Kronos' growth strategy and extends the company into employee scheduling software. 
  5. ^ Bruce, Lindsay (6 October 2004). "Kronos acquires AD OPT for $68,200,000". Issues for CIOs. IT World Canada. Retrieved 6 July 2011. When Kronos become aware of AD OPT, it came to the quick realization that the Montreal-based company had been focusing on various vertical markets that Kronos hadn't when it had developed its own solution. Acquiring the company would allow Kronos to expand the number of verticals it could cover in terms of scheduling. 
  6. ^ "The Impact of Academic Research on Industrial Performance" (PDF). National Academy of Engineering of the National Academies. Washington, D.C.: The National Academies Press. 2003. p. 158. Retrieved 8 July 2011. 
  7. ^ Heykel Achour, Michel Gamache and François Soumis (May 2003). "Column Generation Approach: Application to the Airline Industry" (PDF). Cahiers du GERAD. GERAD. Retrieved 8 July 2011. 
  8. ^ Guy Desaulniers, Jacques Desrosiers, Yvan Dumas, Marius M. Solomon, François Soumis (June 1997). "Daily Aircraft Routing and Scheduling". Cahiers du GERAD. GERAD. Retrieved 7 July 2011. 
  9. ^ Guy Desaulniers, Jacques Desrosiers, Marius M. Solomon., ed. (2005). Column Generation. New York: Springer. ISBN 0-387-25485-4. Retrieved 15 July 2011. 
  10. ^ Hicks, Richard; Richard Madrid; Chris Milligan; Robert Pruneau; Mike Kanaley; Yvan Dumas; Benoit Lacroix; Jacques Desrosiers; François Soumis (2005). "Bombardier Flexjet Significantly Improves Its Fractional Aircraft Ownership Operations". Interfaces (INFORMS) 35 (1): 49–60. ISSN 0092-2102. JSTOR 27651736. 
  11. ^ Daniel V. (2000). "The Aircraft Routing Problem". ALTITUDE: An optimization system for the management of operations. Université de Montréal. p. 24. Retrieved 8 July 2011. 
  12. ^ "Crew Planning Solutions". AD OPT website. 2010. Retrieved 6 July 2011. 
  13. ^ Heykel Achour, Michel Gamache, François Soumis and Guy Desaulniers (2004). "An Exact Solution Approach for the PBS Problem" (PDF). Cahiers du GERAD. GERAD. Retrieved 7 July 2011. 
  14. ^ Khaled Boubaker, Guy Desaulniers and Issmail Elhallaoui (May 2008). "Bidline Scheduling with Equity by Heuristic Dynamic Constraint Regulation". Cahiers du GERAD. GERAD. Retrieved 7 July 2011. 
  15. ^ "Factsheet" (PDF). Altitude Insight. AD OPT. 2010. Retrieved 6 July 2011. establishing and maintaining appropriate staffing levels, managing crew member career progression, and effectively allocating training and vacation awards 
  16. ^ "Operation of Aircraft" (PDF). The Convention of International Civil Aviation. ICAO. Retrieved 22 July 2011. 
  17. ^ "Sec. 212 Pilot Fatigue". HR 5900: Airline Safety and Federal Aviation Administration Extension Act of 2010. United States Congress. Retrieved 22 July 2011. 
  18. ^ "About CIRCADIAN". Retrieved 15 July 2011. 
  19. ^ "CIRCADIAN & AD OPT to provide airlines with a world-class FRMS solution". CIRCADIAN & AD OPT Announcements. CIRCADIAN. 2010. Retrieved 7 July 2011. 
  20. ^ "Our Clients". About AD OPT. 2010. Retrieved 6 July 2011. 

External links[edit]