A Stochastic Integer Programming Approach to Air Traffic Scheduling and Operations

References

• Ahmed S, Sahinidis NV (2003) An approximation scheme for stochastic integer programs arising in capacity expansion. Oper. Res. 51(3):461–471.Link, Google Scholar
• Ahmed S, Tawarmalani M, Sahinidis N (2004) A finite branch-and-bound algorithm for two-stage stochastic integer programs. Math. Programming 100(2):355–377.Crossref, Google Scholar
• Angulo G, Ahmed S, Dey SS (2016) Improving the integer L-shaped method. INFORMS J. Comput. 28(3):483–499.Link, Google Scholar
• Balakrishnan H, Chandran B (2010) Algorithms for scheduling runway operations under constrained position shifting. Oper. Res. 58(6):1650–1665.Link, Google Scholar
• Baldacci R, Mingozzi A (2009) A unified exact method for solving different classes of vehicle routing problems. Math. Programming 120(2):Article 347.Crossref, Google Scholar
• Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2):351–385.Crossref, Google Scholar
• Ball M, Barnhart C, Nemhauser G, Odoni A (2007) Air Transportation: Irregular Operations and Control, vol. 14 (Elsevier, New York).Google Scholar
• Ball M, Hoffman R, Odoni A, Rifkin R (2003) A stochastic integer program with dual network structure and its application to the ground-holding problem. Oper. Res. 51(1):167–171.Link, Google Scholar
• Ball M, Barnhart C, Dresner M, Hansen M, Neels K, Odoni A, Peterson E, Sherry L, Trani A, Zou B (2010) Total delay impact study. Technical report, National Center of Excellence for Aviation Operations Research, College Park, MD.Google Scholar
• Barnhart C, Fearing D, Vaze V (2014) Modeling passenger travel and delays in the national air transportation system. Oper. Res. 62(3):580–601.Link, Google Scholar
• Benders J (1962) Partitioning procedures for solving mixed-variable programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Bertsimas D, Stock Patterson S (1998) The air traffic flow management problem with enroute capacities. Oper. Res. 46(3):406–422.Link, Google Scholar
• Bertsimas D, Lulli G, Odoni A (2011) An integer optimization approach to large-scale air traffic flow management. Oper. Res. 59(1):211–227.Link, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar
• Carlin A, Park P (1970) Marginal cost pricing of airport runway capacity. Amer. Econom. Rev. 60(3):310–319.Google Scholar
• Caroe C, Schultz R (1997) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1–2):37–45.Crossref, Google Scholar
• Caroe C, Schultz R (1999) L-shaped decomposition of two-stage stochastic programs with integer recourse. Math. Programming 83(1–3):451–464.Crossref, Google Scholar
• Carrión M, Philpott AB, Conejo AJ, Arroyo JM (2007) A stochastic programming approach to electric energy procurement for large consumers. IEEE Trans. Power Systems 22(2):744–754.Crossref, Google Scholar
• Casey MS, Sen S (2005) The scenario generation algorithm for multistage stochastic linear programming. Math. Oper. Res. 30(3):615–631.Link, Google Scholar
• Coroni L, Lulli G, Ntaimo L (2014) The time slot allocation problem under uncertain capacity. Transporation Res. Part C: Emerging Tech. 46:16–29.Crossref, Google Scholar
• Czerny A, Forsyth P, Gillen D, Niemeier H (2008) Airport Slots (Ashgate Publishing Ltd., New York).Google Scholar
• de Neufville R, Odoni A (2013) Airport Systems: Planning, Design and Management, 2nd ed. (McGraw-Hill, New York).Google Scholar
• Dempster M, Thompson R (1999) EVPI-based importance sampling solution procedures for multistage stochastic linear programmes on parallel mimd architectures. Ann. Oper. Res. 90:161–184.Crossref, Google Scholar
• Dempster MAH (2006) Sequential importance sampling algorithms for dynamic stochastic programming. J. Math. Sci. 133(4):1422–1444.Crossref, Google Scholar
• Dupačová J, Consigli G, Wallace SW (2000) Scenarios for multistage stochastic programs. Ann. Oper. Res. 100(1–4):25–53.Crossref, Google Scholar
• Dupačová J, Gröwe-Kuska N, Römisch W (2003) Scenario reduction in stochastic programming. Math. Programming 95(3):493–511.Crossref, Google Scholar
• Federal Aviation Administration (2004) Airport capacity benchmark report. Report, Federal Aviation Administration, Washington, DC.Google Scholar
• Federal Aviation Administration (2017) Aviation System Performance Metrics (ASPM) database. Accessed February 1, 2017, https://aspm.faa.gov/apm/sys/main.asp.Google Scholar
• Fischetti M, Lodi A (2003) Local branching. Math. Programming 98(1–3):23–47.Crossref, Google Scholar
• Fischetti M, Toth P (1988) An additive approach for the optimal solution of the prize collecting traveling salesman problem. Vehicle Routing: Methods Stud. 231:319–343.Google Scholar
• Fischetti M, Toth P (1989) An additive bounding procedure for combinatorial optimization problems. Oper. Res. 37(2):319–328.Link, Google Scholar
• Fischetti M, Toth P (1992) An additive bounding procedure for the asymmetric travelling salesman problem. Math. Programming 53(1–3):173–197.Crossref, Google Scholar
• Fischetti M, Toth P (1993) An efficient algorithm for the min-sum arborescence problem on complete digraphs. ORSA J. Comput. 5(4):426–434.Link, Google Scholar
• Gilbo E (1993) Airport capacity: Representation, estimation, optimization. IEEE Trans. Control Systems Tech. 1(3):144–154.Crossref, Google Scholar
• Gillen D, Jacquillat A, Odoni A (2016) Airport demand management: The operations research and economics perspectives and potential synergies. Transporation Res. Part A: Policy Practices 94(3):495–513.Crossref, Google Scholar
• Gunpinar S, Centeno G (2015) Stochastic integer programming models for reducing wastages and shortages of blood products at hospitals. Comput. Oper. Res. 54:129–141.Crossref, Google Scholar
• Heitsch H, Römisch W (2007) A note on scenario reduction for two-stage stochastic programs. Oper. Res. Lett. 35(6):731–738.Crossref, Google Scholar
• Henrion R, Römisch W (2018) Problem-based optimal scenario generation and reduction in stochastic programming. Math. Programming, ePub ahead of print, October 4, https://doi.org/10.1007/s10107-018-1337-6.Crossref, Google Scholar
• Hochreiter R, Pflug GC (2007) Financial scenario generation for stochastic multi-stage decision processes as facility location problems. Ann. Oper. Res. 152(1):257–272.Crossref, Google Scholar
• Høyland K, Wallace SW (2001) Generating scenario trees for multistage decision problems. Management Sci. 47(2):295–307.Link, Google Scholar
• Høyland K, Kaut M, Wallace SW (2003) A heuristic for moment-matching scenario generation. Comput. Optimization Appl. 24(2–3):169–185.Crossref, Google Scholar
• Jacquillat A, Odoni A (2015) An integrated scheduling and operations approach to airport congestion mitigation. Oper. Res. 63(6):1390–1410.Link, Google Scholar
• Jacquillat A, Vaze V (2018) Interairline equity in airport scheduling interventions. Transportation Sci. 52(4):941–964.Link, Google Scholar
• Jiang Y, Zografos K (2018) A bi-objective efficiency-fairness model for scheduling slots at congested airports. Transportation Res. Part C: Emerging Tech. 102:336–350.Google Scholar
• Jones J, Lovell D, Ball M (2018) Stochastic optimization models for transferring delay along flight trajectories to reduce fuel usage. Transportation Sci. 52(1):134–149.Link, Google Scholar
• Kim K, Mehrotra S (2015) A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management. Oper. Res. 63(6):1431–1451.Link, Google Scholar
• King AJ, Wallace SW (2012) Modeling with Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar
• Kleywegt A, Shapiro A, Homem-De-Mello T (2001) The sample average approximation method for stochastic discrete optimization. SIAM J. Optimization 12(2):479–502.Crossref, Google Scholar
• Laporte G, Louveaux F (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3):133–142.Crossref, Google Scholar
• Laporte G, Louveaux FV, Van Hamme L (2002) An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. 50(3):415–423.Link, Google Scholar
• Louveaux FV, Schultz R (2003) Stochastic Integer Programming, vol. 10 (Elsevier, New York).Crossref, Google Scholar
• Magnanti TL, Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Morales JM, Pineda S, Conejo AJ, Carrion M (2009) Scenario reduction for futures market trading in electricity markets. IEEE Trans. Power Systems 24(2):878–888.Crossref, Google Scholar
• Ntaimo L (2010) Disjunctive decomposition for two-stage stochastic mixed-binary programs with random recourse. Oper. Res. 58(1):229–243.Link, Google Scholar
• Odoni A (1987) The flow management problem in air traffic control. Odoni AR, Bianco L, Szegö G, eds. Flow Control of Congested Networks (Springer, Berlin), 269–288.Crossref, Google Scholar
• Pellegrini P, Castelli L, Pesenti R (2012) Metaheuristic algorithms for the simultaneous slot allocation problem. IET Intelligent Transport Systems 6(4):453–462.Crossref, Google Scholar
• Pellegrini P, Bolic T, Castelli L, Resenti R (2017) SOSTA: An effective model for the simultaneous optimisation of airport slot allocation. Transporation Res. Part E: Logistical Transportation Rev. 99:34–53.Crossref, Google Scholar
• Pflug GC (2001) Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Programming 89(2):251–271.Crossref, Google Scholar
• Pranevicius H, Sutiene K (2007) Scenario tree generation by clustering the simulated data paths. Zelinka I, Oplatková Z, Orsoni A, eds. Proc. 21st Eur. Conf. Model. Simulation, Prague, Czech Republic, 203–208.Google Scholar
• Pyrgiotis N (2011) A stochastic and dynamic model of delay propagation within an airport network for policy analysis. PhD thesis, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Pyrgiotis N, Odoni A (2016) On the impact of scheduling limits: A case study at Newark International Airport. Transportation Sci. 50(1):150–165.Link, Google Scholar
• Rassenti S, Smith V, Bulfin R (1982) A combinatorial auction mechanism for airport time slot allocation. Bell J. Econom. 13(2):402–417.Crossref, Google Scholar
• Reese J (2006) Solution methods for the p-median problem: An annotated bibliography. Networks 48(3):125–142.Crossref, Google Scholar
• Rei W, Cordeau JF, Gendreau M, Soriano P (2009) Accelerating Benders decomposition by local branching. INFORMS J. Comput. 21(2):333–345.Link, Google Scholar
• Ribeiro N, Jacquillat A, Antunes A (2019) A large-scale neighborhood search approach to airport slot allocation. Transportation Sci. 53(6):1798–1799.Link, Google Scholar
• Ribeiro N, Jacquillat A, Antunes A, Odoni A, Pita J (2017) An optimization approach for airport slot allocation under IATA guidelines. Osamu W, Thomas Z, eds. Transportation Res. Part B: Methodological 112:132–156.Crossref, Google Scholar
• Richetta O, Odoni A (1993) Solving optimally the static ground-holding policy problem in air traffic control. Transportation Sci. 27(3):228–237.Link, Google Scholar
• Römisch W (2009) Scenario reduction techniques in stochastic programming. Osamu W, Thomas Z, eds. Internat. Sympos. Stochastic Algorithms (Springer, Berlin), 1–14.Google Scholar
• Schultz R (1993) Continuity properties of expectation functions in stochastic integer programming. Math. Oper. Res. 18(3):578–589.Link, Google Scholar
• Schultz R, Stougie L, van der Vlerk M (1998) Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis reductions. Math. Programming 83(1–3):229–252.Crossref, Google Scholar
• Sen S (2005) Algorithms for Stochastic Mixed-Integer Programming Models, vol. 12 (Elsevier, New York).Crossref, Google Scholar
• Sen S, Higle J (2005) The c3 theorem and a d2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Math. Programming 104(1):1–20.Crossref, Google Scholar
• Sen S, Sherali H (2006) Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Math. Programming 106(2):203–223.Crossref, Google Scholar
• Sherali H, Lunday B (2013) On generating maximal nondominated Benders cuts. Ann. Oper. Res. 210(1):57–72.Crossref, Google Scholar
• Shetty K, Gulding J, Koelman H, Celiktin M, Koelle R (2017) Comparison of ATFM practices and performance in the US and Europe. 2017 Integrated Commun. Navigation Surveillance Conf. (ICNS) (IEEE, New York), 1–26.Google Scholar
• Simaiakis I (2012) Analysis, modeling and control of the airport departure process. PhD thesis, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Solveling G, Solak S, Clarke JP, Johnson E (2011) Runway operations optimization in the presence of uncertainties. J. Guidance, Control, Dynam. 34(5):1373–1382.Crossref, Google Scholar
• Terrab M, Odoni A (1993) Strategic flow management for air traffic control. Oper. Res. 41(1):138–152.Link, Google Scholar
• Vossen TW, Hoffman R, Mukherjee A (2012) Air Traffic Flow Management. Quantitative Problem Solving Methods in the Airline Industry (Springer, Berlin).Google Scholar
• Vranas P, Bertsimas D, Odoni A (1994) The multi-airport ground-holding problem in air traffic control. Oper. Res. 42(2):249–261.Link, Google Scholar
• Zhang M, Kucukyavuz S (2014) Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs. SIAM J. Optimization 24(4):1933–1951.Crossref, Google Scholar
• Zografos K, Androutsopoulos K, Madas M (2017) Minding the gap: Optimizing airport schedule displacement and acceptability. Transporation Res. Part A: Policy Practices 114:203–221.Crossref, Google Scholar
• Zografos K, Salouras Y, Madas M (2012) Dealing with the efficient allocation of scarce resources at congested airports. Transportation Res. Part C: Emerging Tech. 21(1):244–56.Crossref, Google Scholar
• Zou J, Ahmed S, Sun XA (2019) Stochastic dual dynamic integer programming. Math. Programming 175(1–2):461–502.Crossref, Google Scholar