# PROGRAM FOR MONDAY, JUNE 30TH

View: session overviewtalk overview

09:00 | Stochastic and Robust Vehicle Routing with Deadlines SPEAKER: unknown ABSTRACT. see pdf file for an extended abstract |

09:30 | Strategies for Handling Temporal Uncertainty in Pick-up and Delivery Problems with Time Windows SPEAKER: unknown ABSTRACT. Uncertainty in vehicle routing problems can be classified along two dimensions -- spatial and temporal. Spatial uncertainty refers to situations in which the exact location of a job is not known (or known inaccurately) during planning, but becomes known at some point in operations. Temporal uncertainty, on the other hand, refers to situations in which the exact service time or service time window of a job is not known (or known inaccurately) until operations are underway. In the context of pick-up and delivery problems, the first category of uncertainty, spatial uncertainty, has been well studied in the literature. Multiple solution techniques exist ranging from reactive, on-line/dynamic, rolling horizon strategies to stochastic strategies. The second category of uncertainty, temporal uncertainty, is far less present in the literature. We seek to fill this gap by undertaking a study of the relationship between strategies for coping with time window uncertainty and the (known) spatial structure in a set of pick-up and delivery problems with time windows. |

10:00 | Benders Decomposition for Production Routing Under Demand Uncertainty SPEAKER: unknown ABSTRACT. We consider the stochastic production routing problem with demand uncertainty in two-stage and multi-stage settings. The decisions in the first stage include production setups and customer visit schedules, while the production and delivery quantities are determined in the subsequent stages. We have developed a solution algorithm based on Benders decomposition for the two-stage problem and we explain how this approach can be extended to the multi-stage case. We also show how solving the two-stage problem in a rolling horizon framework can provide good solutions to the multi-stage problem. |

10:30 | Approximate Dynamic Programming for Vehicle Routing Applications: Introducing the Dynamic Lookup Table SPEAKER: Marlin W. Ulmer ABSTRACT. In many transportation problems, customers are not known in advance, but request service during the day. For private households the locations of the requests are unknown until their appearance. Therefore, the anticipation of future customer requests is challenging. Even though the research of stochastic dynamic vehicle routing is vast, there is only few research regarding unknown future customers. Psaraftis [1] and Bertsimas [2] for the first time modeled customers in the Euclidean plane. Later, amongst others, Gendreau [3] , Swihart [4], Branke [5], Hvattum [6] and Ichoua [7] created new or adapted existing routing problems, where possible customer locations are not known beforehand. Recently, we successfully adapted the method of approximate dynamic programming (ADP) to problems with unknown customer locations [8] using a lookup table. Even though, to expand the problem complexity and to achieve efficient solutions in reasonable runtime, we have to modify the initial PDS space design significantly. Therefore, we introduce the concept of ADP using a dynamic lookup table (ADP_DL). We compare its results with genuine ADP for an exemplary problem setting. By means of state-based simulation ADP measures the value, i.e., the ob-servable system performance of a system appearance. It updates this value after each simulation run. In every decision point, ADP chooses the decision leading to the most valuable appearance considering the immediate decision impact. ADP has been successfully applied to stochastic vehicle routing problems with known possible customer locations. To apply ADP to problems with requests of arbitrary customers, a virtually infinite number of system appearances are mapped to a finite set of PDSs. Aim is to map equivalent appearances to identical PDSs. Therefore, a system-specific selection and aggregation of the appearance-attributes are necessary. Hence, a PDS consists of a subset of aggregated attributes. For different aggreagtion levels we experience a trade-off between learning time and solution quality. On the one hand, a high aggregation leads to a fast learning process. On the other hand, a low aggregation increases the solution quality due to a more detailed PDS space design. However, the learning process is slow or even computational intractable. To combine a high solution quality and a reasonable runtime, we introduce ADP_DL. ADP_DLs relatively high aggregated initial PDS space design results typically in a fast learning process. During the course of learning, it differentiates the attributes of certain PDSs from a high to a subsequently lower aggregation level. The PDS-selection depends on the number of PDS-occurrences and the spread of the PDS-value realizations of the single simulation runs. Hence, “interesting” PDSs are automatically considered more detailed, whereas the remaining PDSs stay in their original coarse design. To this end, a high solution quality is reached within an efficient calculation time. We apply ADP_DL to an exemplary problem: A single vehicle has to visit customers in a service region considering a time limit. The tour starts and ends in a depot. A set of customers is known in advance. When reaching a customer, new customers may request service. The locations of the new customers are not known before the time of their request. For each request the driver has to decide whether to permanently confirm or reject it. The objective is to maximize the number of confirmations and return to the depot within the given time limit. For this problem setting we select purely temporal attributes to describe the PDSs. We map an appearance to a PDS described by a vector containing intervals of daytime and slack in the lookup table. We test ADP_DL for different customer distributions, degrees of dynamism and traffic volumes. The instance sizes match the dimensions of a real-world courier and parcel service provider. We compare ADP_DL with genuine ADP using static lookup tables with different aggregation levels plus a set of classical heuristics. ADP_DL outperforms all other approaches in terms of solution quality. Additionally, it decreases the calculation time compared to genuine ADP using the lowest level of aggregation by 90%. References 1. Psaraftis, H.N. Dynamic vehicle routing: Status and prospects. annals of Operations Research 61, 143–164 (1995). 2. Bertsimas, D.J. & Van Ryzin, G. Stochastic and dynamic vehicle routing in the Eu-clidean plane with multiple capacitated vehicles. Operations Research 41, 60–76 (1993). 3. Gendreau, M., Guertin, F., Potvin, J.-Y. & Taillard, E. Parallel tabu search for real-time vehicle routing and dispatching. Transportation science 33, 381–390 (1999). 4. Swihart, M.R. & Papastavrou, J.D. A stochastic and dynamic model for the single-vehicle pick-up and delivery problem. European Journal of Operational Research 114, 447–464 (1999). 5. Branke, J., Middendorf, M., Noeth, G. & Dessouky, M. Waiting strategies for dy-namic vehicle routing. Transportation science 39, 298–312 (2005). 6. Hvattum, L.M., Løkketangen, A. & Laporte, G. Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transportation Science 40, 421–438 (2006). 7. Ichoua, S., Gendreau, M. & Potvin, J.-Y. Exploiting knowledge about future de-mands for real-time vehicle dispatching. Transportation Science 40, 211–225 (2006). 8. Ulmer, M.W., Brinkmann, J. & Mattfeld, D.C. Anticipatory planning for courier, express and parcel services. Proceedings of Logistic Management 2013 (2014). |

11:30 | Unifying the Fields of Stochastic Optimization for Transportation and Logistics SPEAKER: Warren B. Powell ABSTRACT. Mathematical programming has given us a widely used canonical framework for modeling deterministic optimization problems. However, if we introduce a random variable, the field fragments into a number of competing communities with names such as stochastic programming, dynamic programming, stochastic search, simulation optimization, and optimal control. Differences between these fields are magnified by notation and terminology, which hide subtle but more important differences in problem characteristics. Complicating matters further is a misunderstanding of basic terms such as dynamic program, policy, and state variable. While deterministic optimization problems are defined by solving for decisions, sequential stochastic optimization problems are characterized by finding functions known as policies. I will identify four fundamental classes of policies which unify the competing subcommunities into a common framework I call computational stochastic optimization. These ideas will be illustrated using a variety of applications drawn from transportation and logistics. |

14:00 | Analysis of Machine Learning Algorithms to Predict Bus Arrivals and its Impact on Real-Time Bus Control SPEAKER: unknown ABSTRACT. 1. Introduction The bus-bunching problem has been largely studied in the literature since [1] and [2], for updated reviews see among others [3], [4] and [5]. This phenomenon causes degradation of the level of service experienced by users of transit systems, increasing their waiting times and the likelihood of traveling on a crowded bus. In addition, bus-bunching could increase the fleet required by the operator to provide the same supply [6]. This phenomenon is very hard to avoid since is the result of two stochastic factors: (i) the variability on travel time between stops, and (ii) variations in passenger demand. In order to tackle this problem, a wide range of control strategies have been proposed. According to [3], such control strategies may be divided into three categories: (i) station control, including bus holding, stop skipping and boarding limits; (ii) interstation control, such as operating speed control, bus overtaking and traffic signal priority mechanisms; and (iii) other control measures such as adding vehicles along the route. Among all of them, the most commonly studied and implemented is bus holding. This strategy relies on an accurate online forecast of bus arrivals to stops, since we would like to avoid holding a bus that after the retention is delayed in traffic. In such cases, holding can cause the bus to arrive later than desired to the next stop and therefore should be avoided. In this work we study the impact of improving online forecast for bus arrivals to stops when using real-time holding strategies. Many researchers have studied the topic of predicting the arrival of a bus to the following stop, including [7], [8], [9] and [10]. All of them use Machine Learning Algorithms (MLAs), like Artificial Neural Networks (ANN) or Support Vector Machines/Regression (SVM/SVR) to process the real-time data collected. Usually they obtain information about the current position of the bus using the GPS or DGPS of the Automated Vehicle Location (AVL) systems. This work differs from previous approaches in the following aspects: • We consider explicitly the current traffic states to make the predictions, while previous work assumed that the information would be available while training the MLA. • We apply the results obtained on the prediction of bus arrivals to control bus regularity. We implemented a holding control scheme that takes into account the online forecast of bus arrivals. • We study scenarios with high frequency and unscheduled services, common in big cities, unlike most previous research that deal mainly with scheduled services. We tested scenarios with real data from Transantiago (the transit system of Santiago, Chile) • We included among the methods evaluated a Bayes Network approach, also known as probabilistic graphical model. We are not aware of previous references using this method to estimate bus arrivals. 2. Methodology and approaches The methodology proposed and studied in this work is a comparison between three different MLAs for predicting bus arrivals: (i) ANNs; (ii) SVM/SVRs; and (iii) Bayes Networks. In addition, for comparison purposes, we considered as a benchmark a forecast of bus arrivals computed using an exponential smoothing method. To train the MLAs real data from a line in the Transantiago system was used. Each bus is programmed to send data every 30 seconds, providing its position and instant speed. Using that data, average speed on different route segments (segments between stops) are calculated for different times of the day. We set each time interval at 30 minutes. These segment/time interval speeds are then used as the inputs for the models. The output is the prediction of the speed on the next segment. In order to improve MLAs we considered traffic flow theory´s shock waves. In Figures 1 and 2, x-t diagrams present the shock waves and their influence in the route segment that we seek to predict (blue-filled square). Figure 1 shows how a traffic jam downstream affects our upstream segment. Figure 2 shows how the shock waves on a liberation of a traffic jam affect the studied segment. Therefore, as shown in Figure 3, we use segments numbers 1, 2 and 3 as inputs of the models, to obtain as output travel speed on segment number 0. Thus, the training and validation have three input variables and one output variable. This is an ongoing research and we do not have the results yet. We expect to obtain better results with the SVM/SVR and/or with Bayes Networks models. Figure 1) Downstream traffic jam impacts on the Figure 2) Liberation of traffic jam downstream studied segment impacts on the studied segment Figure 3) Inputs and outputs of the model 3. References [1] Newell, G. F. & Potts, R. B.. (1964). Maintaining a bus schedule. In: Proceedings of the 2nd Australian Road Research Board, 388-393. [2] Potts, R. & Tamlin, E. Pairing of buses. (1964). In: Proceedings of the 2nd Australian Road Research Board, 3–9. [3] Eberlein, X.-J. (1995). Real Time Control Strategies in Transit Operations: Models and Analysis. PhD, Massachusetts Institute of Technology. [4] Cats O., Larijani A.N., Burghout W. and Koutsopoulos H.N. (2011). Impacts of holding control strategies on transit performance: A bus simulation model analysis. Transportation Research Record, 2584, 51-58. [5] Muñoz, J.C., Cortés, C.E., Giesen, R., Saéz, D., Delgado, F. Valencia, F. & Cipriano, A. (2013). Comparison of dynamic control strategies for transit operations. Transportation Research Part C: Emerging Technologies, 28, 101–113 doi:10.1016/j.trc.2012.12.010 [6] Delgado, F., Muñoz, J.C., Giesen, R. (2012). How much can holding and/or limiting boarding improve transit performance? Transportation Research Part B 46 (9), 1202–1217. [7] Jeong, R., & Rilett, R. (2004). Bus arrival time prediction using artificial neural network model. The 7th International IEEE Conference on, 988–993. Retrieved from http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1399041 [8] Sun, D., Luo, H., Fu, L., Liu, W., Liao, X., & Zhao, M. (2007). Predicting Bus Arrival Time on the Basis of Global Positioning System Data. Transportation Research Record, 2034(-1), 62–72. doi:10.3141/2034-08 [9] Yu, B., Lam, W. H. K., & Tam, M. L. (2011). Bus arrival time prediction at bus stop with multiple routes. Transportation Research Part C: Emerging Technologies, 19(6), 1157–1170. doi:10.1016/j.trc.2011.01.003 [10] Zheng, C.-J., Zhang, Y.-H., & Feng, X.-J. (2012). Improved iterative prediction for multiple stop arrival time using a support vector machine. Transport, 27(2), 158–164. doi:10.3846/16484142.2012.692710 |

14:30 | An approximate dynamic programming approach for designing train timetables SPEAKER: unknown ABSTRACT. Railway transportation has become a rapid, clean and efficient way to transport passengers and freight within a modern economy. Planning railway capacity to satisfy the expected demand is one of the critical tasks of railway management. One of the central problems to calculate the capacity of a railway system and plan its use is the train timetabling problem. This problem consists of determining a complete timetable (passing, arrival and departure times of each train at every point of the line) for a given mix of trains running under specific operational and safety constraints along a given infrastructure. Traditional approaches to solving the train timetabling problem have relied on Mixed-Integer Linear Programming (MILP) approaches such as multi-mode resource constrained project scheduling models or multi-commodity flow models. We propose an alternative formulation for this problem based on the modeling and algorithmic framework of approximate dynamic programming (ADP), see (Bertsekas, 2006; Powell, 2007). This formulation allows decomposing the problem in sub-problems that correspond to different decision stages. In our formulation, each decision stage represents a station. The state variable is the timetable of all the trains at that station. This state is Markovian; i.e., knowing the state variable at one station (decision stage) is sufficient to compute the timetable for all the following stations (the states and actions at previous stations provide no additional information to compute the rest of the timetable). The control variable is the total travel time from the current station to the following station. The set of feasible controls for a specific state is determined ensuring all the operational and safety constraints. A stochastic exogenous disturbance representing the total delay that occurs during the travel to the next station is also modeled. The timetable at the following station is determined adding the timetable at the station, the total travel time, and the delays. The cost function associated to each decision stage will depend on the objective of the problem (e.g. energy consumption in the interstation or capacity utilization). We present a Q-learning algorithm based on (Bertsekas and Tsitsiklis, 1996) in order to tractably solve the high-dimensional problem. We compare the performance of several variants of this approach, including discretizing the state and the action spaces, and continuous function approximation with global basis functions. We demonstrate the algorithms calculating the timetable for two railway system case studies, 1) to maximize capacity subject to safety constraints on a commuter railway system, and 2) to minimize energy consumption subject to punctuality constraints on a high-speed railway system. These case studies are inspired in the Spanish railway system. We demonstrate that the ADP algorithm converges rapidly to an optimal solution, and that the number of iterations required increases linearly in the size of the rail system (trains to schedule and stations), in contrast with general purpose MIP solvers whose computation time grows exponentially. We also show that an additional benefit to the ADP approach is the intuition gained from visualizing the Q-factor functions, which graphically capture the intuitive tradeoffs between efficiency and constraints in both examples. Finally, we discuss how this approach can be generalized for more complex train timetabling problems in which there are different types of trains travelling along different parts of the same infrastructure (such as commuter and intercity trains). In this case, a similar ADP approach using the different trains as different decision stages seems to be a promising strategy. References: Bertsekas, D.P. 2006. Dynamic programming and optimal control (3rd ed.), Cambridge, MA: Athena Scientific. Bertsekas, D.P., J. Tsitsiklis. 1996. Neuro-dynamic programming. Cambridge, MA: Athena Scientific. Powell, W. B. 2007. Approximate dynamic programming: Solving the curses of dimensionality. Hoboken, NJ: John Wiley and Sons, Inc. Note: See the pdf attached for a version of this abstract with figures. |

15:00 | INTEGRATING PASSENGER AND FREIGHT TRANSPORTATION: MODEL FORMULATION AND INSIGHTS SPEAKER: Tom Van Woensel ABSTRACT. Integrating passenger and freight flows creates attractive business opportunities because the same transportation needs can be met with fewer vehicles and emissions. This paper seeks an integrated solution for the transportation of passenger and freight simultaneously, so that fewer vehicles are required. The newly introduced problem concerns scheduling a set of vehicles to serve the requests such that a part of the journey can be carried out on a scheduled passenger transportation service. We propose an arc-based mixed integer programming formulation for the integrated transportation system. Computational results on a set of instances provide a clear understanding on the benefits of integrating passenger and freight transportation in the current networks, considering multi-modality of traditional passenger-oriented transportation modes, such as taxi, bus, train or tram. |

14:00 | Stochastic Bin Packing for Logistics Capacity Planning SPEAKER: unknown ABSTRACT. We address the tactical planning problem of firms negotiating capacity contracts, represented in number of bins of various types and costs, to use over a given planning horizon. We propose the Stochastic Variable Cost and Size Bin Packing (\emph{SVCSBP}) model, which explicitly takes into account the uncertainty related to a) the availability and costs of bins of various types, and b) demand as represented by the number and dimension of the items to be consolidated into the bins. The model is based on a two-stage stochastic programming formulation, the first stage separating selecting the set of appropriate bins given a point estimate of the future items one will need to pack, while the second stage concerns the packing of the items one discovers at operation time into the bins contracted initially plus, eventually, the extra bins that must be secured at the premium price to perform the operations. To efficiently address the proposed model, we develop a parallel progressive hedging based meta-heuristic that includes a number of algorithmic enhancements, in terms of fixed-cost adjustment and soft variable fixing, as well as asynchronicity into the information exchanges and the consensus update process. The results of extensive experiments are used to evaluate the efficiency of the proposed methodology and of the impact of volatility in the spot market (availability and cost of bins) on the capacity planning. |

14:30 | A multistage stochastic programming model for long-term biofuel supply chain design under uncertainty SPEAKER: unknown ABSTRACT. Please see attached PDF. |

15:00 | Extreme value distributed performance measures for look-ahead algorithms in large-scale adaptive network design problems SPEAKER: Joseph Chow ABSTRACT. Please see attached. |

16:00 | The Impact of Operating Stochasticity on the Optimal Allocation and Utilization of Airport Capacity SPEAKER: unknown ABSTRACT. Airport congestion is one of the primary challenges faced by contemporary air transportation systems. In the United States, the nationwide impact of flight delays was estimated at over $30 billion for the year 2007 [1]. Most of these delays originate in demand-capacity mismatches resulting from airlines scheduling more flights than available capacity at the busiest airports. Absent opportunities for airport capacity expansion, flight delays can only be substantially reduced through improvements in the efficiency in airport operations and through the implementation of a schedule coordination mechanism. The problems of allocating and utilizing airport capacity are complicated by (a) the stochasticity of airport operations and (b) the different time scales of scheduling and operations. First, airport operations are subject to considerable uncertainty, including weather variations, wind variations, variations in operating efficiency, etc. Second, the schedules of flights are produced by the airlines months in advance, well before operating uncertainty is resolved. But airport operating procedures and the magnitude of flight delays depend, in large measure, on flight schedules. It is thus crucial to integrate operating uncertainty in the design of operating procedures and in the generation of flight schedules. We therefore develop an original integrated approach to airport congestion mitigation that jointly optimizes the utilization of airport capacity, at the tactical level, and the rescheduling of flights through schedule coordination, at the strategic level, under stochastic queue dynamics at the airport. The airport capacity utilization problem involves minimizing congestion costs, for any given schedule of flights and given capacity estimates. We optimize the joint control of the runway configuration and of the balance of arrival and departure service rates. Given the stochasticity of airport operations, we formulate the problem as a stochastic Dynamic Programming model. The control is exercised over the course of the day as a function of arrival and departure queue lengths, of the runway configuration in use and of weather and wind conditions. The schedule coordination problem involves finding a schedule of flights that reduces peak-hour scheduling levels while, at the same time, minimizing interference with airline competitive scheduling. We formulate it as an Integer Programming model based on the Demand Smoothing model from Pyrgiotis and Odoni [2]. Given an original schedule of flights produced by the airlines, the model produces a modified schedule that minimizes the displacement from the original one, while ensuring that no flight is eliminated and that airline networks of flights and passenger itineraries are left unchanged. It is based on the well-known observation that, for a given number of flights scheduled in a day, the more evenly they are distributed over its course, the lower expected delays will be. We formulate an Integrated Schedule Coordination and Capacity Utilization Model (ISCCUM) that combines (a) a stochastic and dynamic queuing model of airport congestion; (b) the Dynamic Programming model of capacity utilization; and (c) the Integer Programming model of schedule coordination (see Figure 1 in the attached document). We integrate delay reduction objectives within the scheduling model instead of applying predetermined schedule limits. At the same time, we integrate the endogenous control of service rates into the evaluation of arrival and departure delays. We believe that it represents the first attempt to integrate airport stochastic queue dynamics and operating procedures into a flight scheduling model. A schematic formulation of the ISCCUM is provided below, where AMAX and DMAX denote the limits that are placed on peak expected arrival and departure queue lengths, respectively. minimize Schedule Displacement subject to No flight eliminated, Scheduled block times unchanged Aircraft connections maintained, Passenger connections maintained Peak expected arrival (resp. departure) queue length smaller than AMAX (resp. DMAX) We develop an original iterative solution algorithm to integrate endogenous stochastic queue dynamics and the dynamic control of operating procedures into an Integer Programming scheduling model. First, we integrate a deterministic queuing model into the scheduling model, which provides an optimal schedule of flights under deterministic queue dynamics. Second, we determine the optimal control of runway configurations and of service rates under the proposed schedule of flights. Third, we simulate resulting delays using a stochastic queuing model. Iterating between these three phases determines, in turn, the optimal schedule of flights and optimal operating procedures under stochastic queue dynamics. The application of the model to JFK Airport yields three important results. First, the control of runway configurations and of arrival and departure service rates can yield significant congestion cost savings, estimated at 15%-20% – without any change in the schedule of flights. Moreover, optimal policies are path-dependent, i.e. they depend on prior decisions and on prior stochastic evolution of queue lengths. This, in turn, underscores the importance of integrating the stochasticity of queue dynamics into the decision-making framework. Second, substantial delay reductions can be achieved with limited interference with airlines’ schedules of flights. Peak arrival and departure delays can be reduced by 35% and 55%, respectively, while (i) no flight is eliminated, (ii) all aircraft and passengers connections are maintained, (iv) the scheduled time of 80% of the flights arriving at or departing from JFK is not modified and (v) no flight is displaced by more than 30 minutes. Finally, the integrated approach to congestion mitigation developed in this paper is shown to provide significant benefits as compared to a typical sequential approach where flight schedules and airport operations are optimized consecutively. References 1. Ball, M. et al., “Total Delay Impact Study”, Technical Report, National Center of Excellence for Aviation Operations Research, 2010. 2. Pyrgiotis, N. and Odoni, A., “On the Impact of Scheduling Limits: A Case Study at Newark International Airport”, Transportation Science, 2014, Forthcoming. |

16:30 | Managing Terminal Airspace Demand Uncertainty with En-Route Speed Control SPEAKER: unknown ABSTRACT. Air traffic flow management represents a problem domain where implicit or explicit modeling of uncertainty is crucial due to the strong role played by minor and major variations in weather, the human elements involved in both air traffic control and the operation of an aircraft, the complexity of airport surface operations as well as others. In the paper we describe models that adjust the speed of airborne flights so as to reduce the congestion in the terminal area near an airport and thereby both reduce fuel usage and increase throughput. We model the uncertainty of the departure time of close-in flights that cannot be controlled and the variability the planned flight times. The core model is an integer program that includes stochastic penalties in the objective functions; the model is executed in a rolling horizon fashion in order to dynamically adjust to changing conditions. The model was used to identify a restricted pool of candidate slots to reduce the overall terminal delay. A secondary integer programming model was then solved to improve the allocation of slots by positioning flights in slots corresponding to lower aggregate fuel burn. Analysis suggests that the incorporation of uncertainty planning into our model yields substantial improvement over deterministic intervention. |

17:00 | Efficient Stochastic Integer Programming Formulations Arising in Air Traffic Management SPEAKER: Michael Ball ABSTRACT. Over the past 10 years a body of research [1,2,3,4,5] has developed integer programming (IP) formulations and efficient algorithms for a stochastic integer programs arising in ground delay program planning. In all cases, the deterministic version of the problem can be modeled as an assignment problem. Scenario-based stochastic IPs have been developed to model stochastic variants [1,2,5]. The simplest version of these are 2-stage stochastic programs with special structure that allows formulations with all integer extreme points. Certain more complex versions do not lead to integral polyhedral but nonetheless have IP formulations that can be solved very quickly. A closely related body of work has modeled multi-stage problems with recourse [3,4]. The nature of the underlying scenario tree and recourse actions is such that the problem can be converted to an equivalent 2-stage stochastic program. An important variant of this problem can be solved by a Greedy algorithm [3]. Recent work has shown a relationship between this property and Monge matrices and sequences [4]. In this paper we explore related integer programs with the goal of producing efficient formulations that can be applied to broader problems. In fact, strong integer programming formulations have been developed for the models addressed in [3,4]. These formulations suggest a novel strategy for formulating a class of structured multi-stage stochastic programs that in turn can be solved very quickly using off-the-shelf IP solvers. 1. Ball, M.O., R. Hoffman and A. Mukherjee, 2010, “Ground Delay Program Planning under Uncertainty Based on the Ration-by-Distance Principle”, Transportation Science, 44, 1-14. 2. Ball, M.O., R. Hoffman, A. Odoni and R. Rifkin, 2003, “A Stochastic Integer Program with Dual Network Structure and its Application to the Ground-Holding Problem”, Operations Research. 51, 167 – 171 3. Churchill, A., D. Lovell, A. Mukherjee and M. Ball, “Determining the Number of Airport Arrival Slots”. 2013, Transportation Science, 47, 526-541 4. Glover, C. and M. Ball, 2013, “Sparse Monge Matrices Arising from Scheduling Problems”, OR Letters.41, 246-248 5. Kotnyek, B. and O. Richetta. 2006. “Equitable models for the stochastic ground holding problem under collaborative decision making”, Transportation Science, 40, 133–146. |