ABSTRACT. Network-based resource allocation problems in transportation and logistics, with their inherent complexity, large-scale nature, multiple (and discrete) heterogeneous resources, multiple stakeholders and wide societal impact, have been natural candidates for the application of optimization techniques. Conventional optimization models, however, make simplifying (and often unrealistic) assumptions, primarily along two directions. The first involves model-based uncertainty, where phenomena in the real-world (observed in data) are simplified and captured approximately by a model. The second involves parameter uncertainty, in which variation in model parameters is approximated by deterministic model inputs. Both these types of assumptions result in solutions that lack robustness [5]. Such solutions are typically not faithful to the underlying data. They often create the need to re-plan at regular intervals when realized operations differ from assumptions; resulting in added costs and increased complexity of operations.

In this research, we develop new data-driven approaches aimed at proactively generating robust solutions [8], that (i) are faithful to implicit information in the underlying data, (ii) are less fragile to disruption, and (iii) optimize the realized costs opposed to the planned costs. Robust solutions require fewer recovery actions, and/or decrease the complexity and cost of recovery.

Our research is, therefore, organized around addressing the two types of uncertainties, detailed as follows:

1. Addressing model uncertainty by building data-driven models that seamlessly incorporate historical data without making restrictive distributional assumptions and thus capture implicit system features that are not captured by existing model-based approaches to uncertainty.
2. Addressing parameter uncertainty by expanding upon the parameterized, robust optimization models developed by Charnes and Cooper [3,4] and Bertsimas and Sim [2]. Combining our enhanced models with data-driven approaches, we build an integrated framework for capturing uncertainty and building robust solutions.

We demonstrate our models and methods using the example of robust aircraft maintenance routing.

Robust Aircraft Maintenance Routing

We consider the problem of robust aircraft routing, a step in the airline scheduling process. Robustness in this context involves constructing schedules and routes with reduced levels of both flight delays and passenger and crew disruptions.

Existing approaches in robust airline scheduling are typically attribute-driven, that is, they find solutions containing attributes that make solutions robust (e.g., [1,6,9,10,11,12]). Such approaches do not allow for incorporating any data-driven insights. Our approach integrates attribute-driven approaches with data-driven approaches, by: (i) analyzing the delay distributions on the flights and routes in the network, and (ii) building enhanced robust optimization models by extending and improving on existing approaches (specifically, the approaches of Charnes and Cooper [3,4] and Bertsimas and Sim [2]) into which attributes can be incorporated.

Firstly, our empirical analysis of delay distributions on flights and routes in a network illustrates the need for data-driven approach. As shown in Figure 1, the distributions of flight delays are approximately bi-modal. For a major hub-and-spoke airline over a period of three months, Figure 1 shows the probability density functions (PDF) of flight delays for a hub-to-hub flight (shown in Figure 1(a)) and for all flights into a hub (shown in Figure 1(b)). As a result, the PDFs of cumulative delays over the aircraft routes also end up having similar bi-modality features (depending on the buffer time distribution in the route).

Secondly, we study two general classes of robust models that use attribute-driven knowledge to guide the solution process. The general classes of models are (i) extreme-value based, and (ii) chance-constrained or probability-based. Each of these classes of models uses robustness parameters that can be tuned to control the tradeoff between cost and robustness. We show that these approaches may lead to solutions that are not on the pareto-optimal frontier with respect to the robustness parameters and robustness metrics of interest. This results in repeated solving, which can be impractical for large problems. To address this issue, we present enhanced models in both these classes, which can determine the most robust solutions given a robustness budget, and that is on the pareto-optimal frontier (thus dominating other solutions). We define a robustness budget as the deviation from the optimal (deterministic) solution value that is allowed to provide a more robust solution. We model our enhanced, budget-constrained robust optimization models as non-linear integer programs and show that there exist equivalent linear, integer formulations.

We show how knowledge from our empirical investigations can be incorporated into our enhanced models to generate solutions that are faithful to underlying data as well as capture domain knowledge. We compare performances of the different models and discuss solution performance with respect to the robustness metrics of interest.

References:
1. Ball, M., C. Barnhart, G. Nemhauser and A. Odoni. (2006). “Managing Air Traffic and Airline Operations for Schedule Reliability,” Operations Research Handbook on Transportation, Gilbert Laporte and Cynthia Barnhart (co-editors), Elsevier, Amsterdam, December 2006.
2. D. Bertsimas and M. Sim. The price of robustness. Operations Research, 52(1):35–53, 2004.
3. A. Charnes and W. W. Cooper. Chance constrained programming. Management Science, 6(1):73–79, 1959.
4. A. Charnes and W. W. Cooper. Deterministic equivalents for optimizing and satisficing under chance constraints. Operations Research, 11(1):18–39, 1963.
5. H. J. Greenberg. Representing uncertainty in decision support. ORMS Today, June 2007.
6. Lan, S., J.P. Clarke, and C. Barnhart. 2006. Planning for Robust Airline Operations: Optimizing Aircraft Routings and Flight Departure Times to Minimize Passenger Disruptions. Transportation Science 40, 1, 15-28.
7. Marla, L. and C. Barnhart. Robust Optimization: Lessons from Aircraft Routing. Working paper.
8. Mulvey, J., R. Vanderbei, and S. Zeinos. 1995. Robust optimization of large-scale systems, Operations Research, Vol 43 (2).
9. Rosenberger J., E.L. Johnson, and G.L. Nemhauser (2004). A robust fleet-assignment model with hub isolation and short cycles. Transportation Science 38, 357-368.
10. Schaefer, A. J., E.L. Johnson, A.J. Kleywegt and G. L. Nemhauser (2005). Airline crew
scheduling under uncertainty. Transportation Science 39 340-348.
11. Shebalov, S. and D. Klabjan. Robust airline crew pairing: Move-up crews. Transportation Science, 40(3):300–312, 2006.
12. H. Jiang. Dynamic Airline Scheduling and Robust Airline Schedule De-Peaking. PhD thesis, Massachusetts Institute of Technology, 2006.