IDEAS home Printed from https://ideas.repec.org/a/inm/orinte/v29y1999i5p51-65.html
   My bibliography  Save this article

A Two-Phase Genetic Algorithm for Large-Scale Bidline-Generation Problems at Delta Air Lines

Author

Listed:
  • Ioannis T. Christou

    (Delta Technology, 1001 International Boulevard, Department 709, Atlanta, Georgia 30354)

  • Armand Zakarian

    (Delta Technology, 1001 International Boulevard, Department 709, Atlanta, Georgia 30354)

  • Jun-Min Liu

    (Delta Technology, 1001 International Boulevard, Department 709, Atlanta, Georgia 30354)

  • Helen Carter

    (Delta Air Lines, Department 028, PO Box 20706, Atlanta, Georgia 30320)

Abstract

We developed a two-phase algorithm for solving Delta Air Lines' bidline-generation problem: assigning trips (tasks) to monthly schedules for crew members (called bidlines .) The system must produce bidlines that conform to all rules, and it should maximize average total value and the quality of the bidlines as measured by their purity. The first phase of the algorithm (the purity phase) constructs as many high-quality lines as possible, and the second (the GA phase) completes the assignments by constructing high-total-value valid lines from the remaining open trips. Delta obtains significant savings in staffing by using this algorithm. The bidlines produced are of comparable quality to those built with the semiautomatic process that Delta Air Lines used before.

Suggested Citation

  • Ioannis T. Christou & Armand Zakarian & Jun-Min Liu & Helen Carter, 1999. "A Two-Phase Genetic Algorithm for Large-Scale Bidline-Generation Problems at Delta Air Lines," Interfaces, INFORMS, vol. 29(5), pages 51-65, October.
    • Handle: RePEc:inm:orinte:v:29:y:1999:i:5:p:51-65
    DOI: 10.1287/inte.29.5.51
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/inte.29.5.51
    Download Restriction: no
    File URL: https://libkey.io/10.1287/inte.29.5.51?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Kevin W. Campbell & R. Bret Durfee & Gail S. Hines, 1997. "FedEx Generates Bid Lines Using Simulated Annealing," Interfaces, INFORMS, vol. 27(2), pages 1-16, April.
    2. Ahmad I. Z. Jarrah & James T. Diamond, 1997. "The Problem of Generating Crew Bidlines," Interfaces, INFORMS, vol. 27(4), pages 49-64, August.
    3. J. Kennington & Z. Wang, 1992. "A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem," Operations Research, INFORMS, vol. 40(1), pages 178-187, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Saddoune, Mohammed & Desaulniers, Guy & Elhallaoui, Issmail & Soumis, François, 2011. "Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods," European Journal of Operational Research, Elsevier, vol. 212(3), pages 445-454, August.
    2. Quesnel, Frédéric & Desaulniers, Guy & Soumis, François, 2020. "A branch-and-price heuristic for the crew pairing problem with language constraints," European Journal of Operational Research, Elsevier, vol. 283(3), pages 1040-1054.
    3. Cynthia Barnhart & Peter Belobaba & Amedeo R. Odoni, 2003. "Applications of Operations Research in the Air Transport Industry," Transportation Science, INFORMS, vol. 37(4), pages 368-391, November.
    4. Mohammed Saddoune & Guy Desaulniers & Issmail Elhallaoui & François Soumis, 2012. "Integrated Airline Crew Pairing and Crew Assignment by Dynamic Constraint Aggregation," Transportation Science, INFORMS, vol. 46(1), pages 39-55, February.
    5. Jay M. Rosenberger & Andrew J. Schaefer & David Goldsman & Ellis L. Johnson & Anton J. Kleywegt & George L. Nemhauser, 2002. "A Stochastic Model of Airline Operations," Transportation Science, INFORMS, vol. 36(4), pages 357-377, November.
    6. Cynthia Barnhart & Amy Cohn, 2004. "Airline Schedule Planning: Accomplishments and Opportunities," Manufacturing & Service Operations Management, INFORMS, vol. 6(1), pages 3-22, November.
    7. Boubaker, Khaled & Desaulniers, Guy & Elhallaoui, Issmail, 2010. "Bidline scheduling with equity by heuristic dynamic constraint aggregation," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 50-61, January.
    8. Milind G. Sohoni & T. Glenn Bailey & Kristi G. Martin & Helen Carter & Ellis L. Johnson, 2003. "Delta Optimizes Continuing-Qualification-Training Schedules for Pilots," Interfaces, INFORMS, vol. 33(5), pages 57-70, October.
    9. Vahid Zeighami & François Soumis, 2019. "Combining Benders’ Decomposition and Column Generation for Integrated Crew Pairing and Personalized Crew Assignment Problems," Transportation Science, INFORMS, vol. 53(5), pages 1479-1499, September.
    10. Atoosa Kasirzadeh & Mohammed Saddoune & François Soumis, 2017. "Airline crew scheduling: models, algorithms, and data sets," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 111-137, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Atoosa Kasirzadeh & Mohammed Saddoune & François Soumis, 2017. "Airline crew scheduling: models, algorithms, and data sets," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 111-137, June.
    2. Vahid Zeighami & François Soumis, 2019. "Combining Benders’ Decomposition and Column Generation for Integrated Crew Pairing and Personalized Crew Assignment Problems," Transportation Science, INFORMS, vol. 53(5), pages 1479-1499, September.
    3. Mohammed Saddoune & Guy Desaulniers & Issmail Elhallaoui & François Soumis, 2012. "Integrated Airline Crew Pairing and Crew Assignment by Dynamic Constraint Aggregation," Transportation Science, INFORMS, vol. 46(1), pages 39-55, February.
    4. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    5. Helena R. Lourenço & José P. Paixão & Rita Portugal, 2001. "Multiobjective Metaheuristics for the Bus Driver Scheduling Problem," Transportation Science, INFORMS, vol. 35(3), pages 331-343, August.
    6. Pentico, David W., 2007. "Assignment problems: A golden anniversary survey," European Journal of Operational Research, Elsevier, vol. 176(2), pages 774-793, January.
    7. Volgenant, A., 2004. "A note on the assignment problem with seniority and job priority constraints," European Journal of Operational Research, Elsevier, vol. 154(1), pages 330-335, April.
    8. Andreas Dellnitz & Damian Pozo & Jochen Bauer & Andreas Kleine, 2023. "Practice Summary: Seminar Assignments in a University—MATLAB-Based Decision Support," Interfaces, INFORMS, vol. 53(4), pages 307-311, July.
    9. Boubaker, Khaled & Desaulniers, Guy & Elhallaoui, Issmail, 2010. "Bidline scheduling with equity by heuristic dynamic constraint aggregation," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 50-61, January.
    10. Jonker, R. & Volgenant, A., 1999. "Linear assignment procedures," European Journal of Operational Research, Elsevier, vol. 116(1), pages 233-234, July.
    11. Volgenant, A., 2004. "Solving the k-cardinality assignment problem by transformation," European Journal of Operational Research, Elsevier, vol. 157(2), pages 322-331, September.
    12. Nissen, Rüdiger & Haase, Knut, 2004. "Duty-period-based network model for airline crew rescheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 581, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    13. Jacques Desrosiers & Arielle Lasry & Daniel McInnis & Marius M. Solomon & François Soumis, 2000. "Air Transat Uses ALTITUDE to Manage Its Aircraft Routing, Crew Pairing, and Work Assignment," Interfaces, INFORMS, vol. 30(2), pages 41-53, April.
    14. Saddoune, Mohammed & Desaulniers, Guy & Elhallaoui, Issmail & Soumis, François, 2011. "Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods," European Journal of Operational Research, Elsevier, vol. 212(3), pages 445-454, August.
    15. Yuli Zhang & Zuo-Jun Max Shen & Shiji Song, 2018. "Exact Algorithms for Distributionally β -Robust Machine Scheduling with Uncertain Processing Times," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 662-676, November.
    16. Helena Ramalhinho-Lourenço, 2005. "Teaching metaheuristics in business schools," Economics Working Papers 806, Department of Economics and Business, Universitat Pompeu Fabra.
    17. Helena Ramalhinho-Lourenço, 2001. "Supply chain management: An opportunity for metaheuristics," Economics Working Papers 538, Department of Economics and Business, Universitat Pompeu Fabra.
    18. Andreas Kleine & Andreas Dellnitz, 2017. "Allocation of seminar applicants," Journal of Business Economics, Springer, vol. 87(7), pages 927-941, October.
    19. Larry J. LeBlanc & Dale Randels & T. K. Swann, 2000. "Heery International's Spreadsheet Optimization Model for Assigning Managers to Construction Projects," Interfaces, INFORMS, vol. 30(6), pages 95-106, December.
    20. Helena Ramalhinho-Lourenço & José Pinto & Rita Portugal, 1998. "Metaheuristics for the bus-driver scheduling problem," Economics Working Papers 304, Department of Economics and Business, Universitat Pompeu Fabra.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orinte:v:29:y:1999:i:5:p:51-65. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.