IDEAS home Printed from https://ideas.repec.org/a/inm/orserv/v13y2021i1p1-18.html

Airplane Seating Assignment Problem

Author

Listed:
  • John A. Pavlik

    (Department of Computer Science, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801)

  • Ian G. Ludden

    (Department of Computer Science, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801)

  • Sheldon H. Jacobson

    (Department of Computer Science, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801)

  • Edward C. Sewell

    (Department of Mathematics and Statistics, Southern Illinois University Edwardsville, Edwardsville, Illinois 62025)

Abstract

SARS-CoV-2, the virus that causes COVID-19, began infecting humans in late 2019 and has since spread to over 57 million people and caused over 1.75 million deaths, as of December 27, 2020. In response to reduced demand and travel restrictions as a result of COVID-19, airlines experienced a 94% reduction in passenger capacity worldwide in April and an estimated 60% reduction in passengers transported for all of 2020. SARS-CoV-2 has been shown to spread on airplanes by infected passengers, so minimizing the risk of secondary infections aboard aircraft may save lives. We present the airplane seating assignment problem (ASAP) to minimize transmission risks on airplanes, and we provide two models to solve ASAP. We show that both models can be effectively solved using a standard commercial solver and that seating assignments provided by these models have lower aggregate risk than the strategy of blocking the middle seats, given the same number of passengers. The available risk models for aircraft are based on influenza data, and hence risk models based on SARS-CoV-2 should be developed to maximize the benefits of our research.

Suggested Citation

  • John A. Pavlik & Ian G. Ludden & Sheldon H. Jacobson & Edward C. Sewell, 2021. "Airplane Seating Assignment Problem," Service Science, INFORMS, vol. 13(1), pages 1-18, March.
    • Handle: RePEc:inm:orserv:v:13:y:2021:i:1:p:1-18
    DOI: 10.1287/serv.2021.0269
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/serv.2021.0269
    Download Restriction: no
    File URL: https://libkey.io/10.1287/serv.2021.0269?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. Fred Glover & Gary A. Kochenberger & Bahram Alidaee, 1998. "Adaptive Memory Tabu Search for Binary Quadratic Programs," Management Science, INFORMS, vol. 44(3), pages 336-345, March.
    2. Dorit S. Hochbaum, 2004. "50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today," Management Science, INFORMS, vol. 50(6), pages 709-723, June.
    3. Salari, Mostafa & Milne, R. John & Delcea, Camelia & Kattan, Lina & Cotfas, Liviu-Adrian, 2020. "Social distancing in airplane seat assignments," Journal of Air Transport Management, Elsevier, vol. 89(C).
    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. Alessandro V. M. Oliveira & Moises D. Vassallo, 2025. "Cabin Layout, Seat Density, and Passenger Segmentation in Air Transport: Implications for Prices, Ancillary Revenues, and Efficiency," Papers 2512.08066, arXiv.org.
    2. Jonas Schwamberger & Moritz Fleischmann & Arne Strauss, 2023. "Feeding the Nation—Dynamic Customer Contacting for E-Fulfillment in Times of Crisis," Service Science, INFORMS, vol. 15(1), pages 22-40, March.
    3. Xu, Guangming & Liu, Xinyi & Zhong, Linhuan & Liu, Wei, 2025. "Group-based railway seat allocation policies considering the risk of virus transmission," Transportation Research Part A: Policy and Practice, Elsevier, vol. 199(C).

    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. Haoming Liu & Kangkang Deng & Haoyang Liu & Zaiwen Wen, 2023. "An Entropy-Regularized ADMM For Binary Quadratic Programming," Journal of Global Optimization, Springer, vol. 87(2), pages 447-479, November.
    2. Katayama, Kengo & Narihisa, Hiroyuki, 2001. "Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem," European Journal of Operational Research, Elsevier, vol. 134(1), pages 103-119, October.
    3. Gary Kochenberger & Jin-Kao Hao & Fred Glover & Mark Lewis & Zhipeng Lü & Haibo Wang & Yang Wang, 2014. "The unconstrained binary quadratic programming problem: a survey," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 58-81, July.
    4. García-Martínez, C. & Rodriguez, F.J. & Lozano, M., 2014. "Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 454-463.
    5. Punnen, Abraham P. & Wang, Yang, 2016. "The bipartite quadratic assignment problem and extensions," European Journal of Operational Research, Elsevier, vol. 250(3), pages 715-725.
    6. Wang, Yang & Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2012. "Path relinking for unconstrained binary quadratic programming," European Journal of Operational Research, Elsevier, vol. 223(3), pages 595-604.
    7. Gary Kochenberger & Fred Glover & Bahram Alidaee & Cesar Rego, 2005. "An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem," Annals of Operations Research, Springer, vol. 139(1), pages 229-241, October.
    8. Helena Ramalhinho & Thomas Stützle, 2025. "Iterated local search, iterated greedy and applications," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 33(2), pages 229-261, July.
    9. Haque, Md Tabish & Hamid, Faiz, 2023. "Social distancing and revenue management—A post-pandemic adaptation for railways," Omega, Elsevier, vol. 114(C).
    10. Tang, Ching-Hui & Hsu, Yi-Hsiang, 2025. "Stochastic infection risk models for aircraft seat assignment considering passenger vaccination status and seat location," Journal of Air Transport Management, Elsevier, vol. 122(C).
    11. Pardo González, Germán & Tabares Pozos, Alejandra & Quiroga, Camilo & à lvarez-Martínez, David, 2024. "Seat assignment recommendation in airlines purchase flow to increase ancillary revenue considering weight and balance constraints," Journal of Air Transport Management, Elsevier, vol. 117(C).
    12. Xiaoyuan Liu & Hayato Ushijima-Mwesigwa & Avradip Mandal & Sarvagya Upadhyay & Ilya Safro & Arnab Roy, 2022. "Leveraging special-purpose hardware for local search heuristics," Computational Optimization and Applications, Springer, vol. 82(1), pages 1-29, May.
    13. Tao Pham Dinh & Nam Nguyen Canh & Hoai Le Thi, 2010. "An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs," Journal of Global Optimization, Springer, vol. 48(4), pages 595-632, December.
    14. Bahram Alidaee & Haibo Wang, 2017. "A note on heuristic approach based on UBQP formulation of the maximum diversity problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 102-110, January.
    15. Taoudi, Lamiae & Tajik, Nazanin & Ermagun, Alireza, 2025. "Crash landing: Flight price elasticity induced by pandemic across America," Journal of Air Transport Management, Elsevier, vol. 124(C).
    16. Gili Rosenberg & Mohammad Vazifeh & Brad Woods & Eldad Haber, 2016. "Building an iterative heuristic solver for a quantum annealer," Computational Optimization and Applications, Springer, vol. 65(3), pages 845-869, December.
    17. You, Byungjun & Yamada, Takeo, 2007. "A pegging approach to the precedence-constrained knapsack problem," European Journal of Operational Research, Elsevier, vol. 183(2), pages 618-632, December.
    18. Kim, Myeonghyeon & Sohn, Jeongwoong, 2022. "Passenger, airline, and policy responses to the COVID-19 crisis: The case of South Korea," Journal of Air Transport Management, Elsevier, vol. 98(C).
    19. Samanci, Simge & Didem Atalay, Kumru & Bahar Isin, Feride, 2021. "Focusing on the big picture while observing the concerns of both managers and passengers in the post-covid era," Journal of Air Transport Management, Elsevier, vol. 90(C).
    20. Zheng, Shiyuan & Jiang, Changmin & Fu, Xiaowen & Huang, Ying, 2025. "Airline competition and government regulation during a global pandemic: A retrospective analysis," Transportation Research Part A: Policy and Practice, Elsevier, vol. 197(C).

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:orserv:v:13:y:2021:i:1:p:1-18. 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.