PROGRAM FOR MONDAY, JUNE 30TH

ABSTRACT. (see uploaded PDF file)

ABSTRACT. Package carriers such as DHL, FedEx and UPS, and many postal services, possess sophisticated automated sorting systems in their regional hubs that enable them to efficiently process inbound packages and sort them to their down line destinations. A typical hub may process up to 20,000 packages per hour, and may ship up to 150 destinations. The primary sorters in a hub perform high-level sortation of the packages and direct them to one of several secondary sorters. Each of the secondary sorters is dedicated to servicing one of the workcenters in the hub, and is used to segregate the packages to the level of the outbound loading destination. Secondary conveyors are then used to transport each package to its appropriate outbound loading door. During each day, several shifts (or “sorts”) are utilized for package sorting. The packages handled in the various sorts vary in terms of destinations served and service level.

A major challenge for planners at a hub is to determine what destinations to assign to each of the workcenters. This planning exercise is typically performed every four to five weeks to accommodate updated package volume forecasts. The overarching objective for the assignment is to balance the usage of the secondary sorters and workcenters during each of the sorts. When a hub is out of balance, some of the workcenters may have an overflow of packages while other workcenters may be operating below capacity. Also, some of the secondary sorters may be running at full capacity and unable to keep up with the inbound package flows thus creating a backlog, while other secondary sorters may be working far below capacity. Such imbalance results in costly and unnecessary service failures, and are, hence, highly undesirable. Other detrimental effects are related to uneven wear-and-tear and associated maintenance issues. Taking the make of the sorters and number of doors in the secondary workcenters into account, hub industrial engineers set target throughputs (in packages per hour) for each of the secondary sorters. The assignment of destinations should then be done in a fashion that results in throughputs that are as close as possible to the stipulated ones.

Several constraints are relevant when making the assignments, including: (1) Each destination has to be assigned to one-and-only one secondary workcenter. This is necessary because outbound load doors for a destination are required to be adjacent to enable effective loading of trailers. (2) The available number of doors for each workcenter cannot be exceeded. (3) For various operational reasons, a specific destination may have to be assigned to a specific workcenter, or a pair of destinations may have to be assigned to the same workcenter or to two different workcenters.

Traditionally, the planning of the assignment of destinations to secondary workcenters has been done in the industry using average daily flow per hour for each destination and sort. This approach fails to take into account the significant daily fluctuation in package flows. As such, a plan based on average flows may not perform well during the actual days of operation. To illustrate, if for a specific sort, on a given day, the total package flow for the destinations assigned to a workcenter is significantly higher than average, the workcenter may run out of capacity, which will make it difficult or impossible to process all the packages in a timely fashion. In situations where the processing capacities of the workcenters are not violated, the actual flow realizations may still result in the undesirable situation of having significant workload imbalances among the workcenters. A better plan would be one that ensures, with a reasonably high probability, that the sorting facility will be balanced and operating within capacity on any given day. Furthermore, the plan has to consider the significant correlations that exist between the package flows for the different destinations.

In this research, we propose a hybrid stochastic programming/robust optimization modeling and solution approaches for addressing this important planning problem that explicitly account for stochasticity in the package flows. The objective function for the general stochastic formulation seeks to minimize a random variable corresponding to the maximum deviation from the pre-established target throughputs across the workcenters and sorts. One set of constraints ensures that each destination is assigned to exactly one workcenter, while a second set restricts the number of doors used in each workcenter to those available. For this second set of constraints, since destinations cannot share doors, it is necessary to round up the fractional number of doors required by a destination to the nearest integer. Various operational side constraints are used to control the destination-to-door assignments, and, finally, binary restrictions are stipulated for the assignment variables.

Linearizing the absolute value terms in the objective function, and assuming normality for the random variables, we state the balancing requirement using chance constraints that stipulate a target probability level (e.g. 95%) for achieving an imbalance measure that is minimized. The chance constraints are then reformulated using nonlinear deterministic equivalents. The normality assumption is justified by the fact that, typically, ten to fifteen destinations are assigned to each workcenter thus resulting in a combined package flow distribution that is approximately normal. However, the rounding-up operator in the capacity constraints makes it is impossible to find a direct deterministic equivalent to model the resultant stochasticity. Instead, we resort to a robust re-formulation for these constraints that guarantees feasibility when up to a pre-specified fraction of the destinations assigned to a sort and a workcenter swing to their maximal value. This results in nonlinear robustness constraints that we linearize by introducing additional binary variables. Three alternative overall formulations are proposed: (1) Mixed Integer Nonlinear Program: The initial formulation uses the nonlinear deterministic equivalents for the chance constraints along with the linearized integer constraints required to model the desired robustness level for the capacity constraints. (2) Quadratic Mixed Integer Program: By squaring the terms involving the nonlinear deterministic equivalents in (1), adding regularity constraints and linearizing the deterministic equivalent terms, a quadratic program is obtained, which is linear for fixed values of the imbalance measure. (3) Second-Order Conic Mixed Integer Program: Through change-of-variables and introduction of additional constraints, it is possible to reformulate model (1) as a mixed integer second-order conic program.

We evaluate the three formulations using a test data set and demonstrate the consistently superior performance of the third formulation. Using the model of choice, we propose an approach for hub managers to specify the highest possible robustness level that can be achieved. The computational performance of the model of choice is comprehensively analyzed. Finally, the impact of model in terms of significantly improving a sorting facility’s operational flow is thoroughly assessed by comparing the solutions from the new proposed model of choice to those obtained from a deterministic model that assumes average package volumes, a stochastic flow balancing model with deterministic capacity constraints and a deterministic flow balancing model with robust capacity constraints. The results indicate that the proposed model can significantly improve the performance of automated package sorting centers in terms of achieving excellent flow balance along with an associated high level of robustness.

ABSTRACT. Although there exists an abundance of literature on capacitated facility location models, nearly all of these models employ hard capacity constraints. We argue that, in reality, the capacity of a processing center is often flexible. Facility managers have many operational tools to extend capacity or to allow the facility to accept demands in excess of the capacity constraint for short periods of time. For example, a facility manager may choose to utilize overtime, thus allowing the facility to process more than the specified capacity limit. Additionally, in reality, many processing facilities use inventory as a buffer against inadequate capacity. As an illustration, consider the example of a facility that has a processing capacity of 100 units per work day and a demand location that generates an average demand of 80 units per day. Suppose on one day the demand location generates 101 units of demand. The traditional hard capacity constraints would imply that the demand site could not be assigned to the processing facility because the demand exceeds capacity. Realistically, however, the assignment is possible, as the facility may choose to use overtime to process the extra unit or may hold the unit in inventory and process it the following day. As this simple example demonstrates, specifying hard capacity constraints is often unrealistic.

In this paper we formulate a stochastic extension of an earlier model that we developed in which inventory is used to mitigate hard capacity constraints. Daily demands at each demand generating site are assumed to be random variables that may exhibit temporal demand patterns.

To mitigate the effect of the hard capacity constraints we consider the following processing distribution system in which demand that is generated on a daily basis by a set of demand sites is satisfied by a set of capacitated processing facilities. Each processing facility has the ability to hold excess demand in inventory to be processed at the start of the next work day. However, we penalize the demand that is held in inventory. The problem is to determine the subset of processing facilities to establish, the allocation of demand nodes to facilities, and the magnitude of inventory to maintain at each facility on each day so as to minimize location, travel, and inventory costs. Facility location decisions are long term decisions that are expensive to alter and therefore we will assume that a facility that is opened must remain open for the duration of the planning horizon. Each demand site is assigned one processing facility to handle all of its demands and demand assignments do not change over the planning horizon. We refer to this problem as the Inventory Modulated Capacitated Location Problem (IMCLP).

By incorporating the ability to hold excess demand in inventory and process the demand at a later time, our capacitated location model better reflects actual managerial options than previous capacitated location models. In particular, variations of our model have the potential to reveal operating policies that take advantage of spatial and temporal correlations in demand that would not be evident in traditional capacitated facility location models.

In previous work documented in a working paper in which we consider deterministic demands, we compare the optimal solutions of the traditional Capacitated Facility Location Problem (CFLP) and the IMCLP with regard to facility locations, demand assignments, and total cost. We find that for a sufficiently large cost of holding inventory, the CFLP and IMCLP locate different facilities, and therefore assign demands to different facilities as well. Furthermore, as the cost of holding inventory increases it becomes more costly to approximate the optimal IMCLP solution with the CFLP solution.

Although the results for the deterministic demand case indicate important implications of using the CFLP instead of the IMCLP, in reality it is likely that demands are not known in advance. For example, demands may be generated by customer orders which are not known until the order is placed. In this paper we present a stochastic version of the IMCLP in which daily demand is uncertain. We assume a known demand distribution. The problem now is to determine the set of processing facilities to open and the assignment of demand sites to processing facilities so as to minimize the fixed location, transportation, and inventory costs under the assumption that demands are not known in advance.

We formulate the problem as a two-stage scenario-based stochastic optimization model. The facility location and assignment of demand sites to processing facilities are first stage decisions. The resulting processing and inventory variables are second stage decisions. We utilize chance-constraints to bound the joint probability of having no day in which the inventory at any facility is above a predetermined threshold. A mixed-integer programming reformulation that incorporates a finite number of scenarios from the original demand distribution is developed. Additionally, we outline various decomposition-based algorithms to solve the reformulation, including a subgradient optimization based Lagrangian relaxation method that focuses on relaxing the single sourcing assignment constraints.

Initial computational results are presented for large-scale data sets generated from 2010 U.S. census data by county and Spain data by city, including data sets with temporally correlated demands. Demands at each node are taken to be Poisson distributed with a mean relative to the population at the demand generating node. Additionally, fixed processing location costs and daily processing capacities are functions of population. Distances between nodes are calculated based on the Great Circle Distance. The results demonstrate the computational efficacy of the decomposition-based algorithms and the effect of using the stochastic IMCLP model instead of traditional capacitated location models.

ABSTRACT. The facility layout problem (FLP) -- also called the plant layout problem -- is the problem of assigning physical facilities (such as machine tools, work centers, manufacturing cells, departments, and warehouses) for a production or a delivery system to locations. FLPs arise either in the early design stage of a new facility or during improvement phases of current layouts. Layout design is one of the most fundamental and strategic issues in many manufacturing industries. Any modification or re-arrangement of an existing layout very likely involves substantial financial investment and planning efforts. An efficient layout of facilities can reduce operational costs and contribute to overall production efficiency.

Given information such as machine dimensions, capacities of machines and volumes transferred between all pairs of machines, the planner's objective is to determine an efficient facility layout according to some design criterion, often the minimization of material handling distance/costs. Such costs are incurred when moving finished parts, work-in-process parts, spares, tools and other supplies between machines or storage locations to meet production demand. A significant proportion, about 20\% to 50\%, of overall product costs can be attributed to material handling, since material handling is involved in almost all manufacturing activities from the arrival of raw materials to the packaging of finished products. In a material handling system, automation is one of the key principles since it can effectively reduce operational costs and enhance manufacturing performance. Unmanned material handling equipment such as conveyors, automatic guided vehicles (AGV), cranes and robots are deployed for automatic delivery activities. As markets have become more unpredictable since the 1990s, flexible manufacturing systems (FMS) are required to adapt to changes in product mix, demand and designs with low-cost solutions. Automatic tools including AGVs and robots are the main types of equipment in FMS. Different from conveyors which can only operate between two fixed locations, AGVs and robots have high degrees of route flexibility since they can travel between any two locations. Our research focuses on planning good layouts for completely automatic FMSs where no human workers are needed. In such a system, the material handling cost is largely affected by the travel distance of the handling tools. Shortening travel distance would help reduce the handling costs and manufacturing lead time.

The FLP was initially formulated as a quadratic assignment problem (QAP). The QAP assigns n facilities to n locations in such a way that each facility is assigned to exactly one location and each location takes exactly one facility. This QAP and its augmentations have been widely applied in solving FLPs. From this starting point, the basic model has been extended in many directions. The two most important ones for our work is the inclusion of capacitated machines, leading to potentially multiple copies of each machine type, and random demand. Randomness refers to both product mix (amounting to different sequences of machine types) and demand volume. In this paper we demonstrate how good heuristics can be developed to solve stochastic capacitated facility layout problems with random demand whenever the corresponding deterministic model (with demand equal to expected demand from the stochastic case) can be solved (exactly or heuristically). The suggested method is about two orders of magnitude faster than the best existing heuristic for the stochastic case, while producing results that are a few percent better.

ABSTRACT. see pdf file for an extended abstract

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.

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.

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).

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.

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

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.

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.

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.

ABSTRACT. Please see attached PDF.

ABSTRACT. Please see attached.

ABSTRACT. see attached.

ABSTRACT. see attachment

ABSTRACT. Abstract Disasters can occur anywhere and often without warning. One of the best ways to minimize the impact of a disaster on the well-being of the citizens is to ensure that adequate disaster supplies are available at a moment's notice. There has been a great deal of research in the past few years on stock prepositioning locations and on how much stock to keep at each location ( eg. [Campbell and Jones, 2011], [Lodree et al.,2012]) to prepare for a disaster. Delivering these supplies to citizens after a disaster occurs though, can be challenging. A major problem associated with providing supplies after a disaster is that many roads become impassible or passable at a highly reduced speed. The most recent example is Typhoon Haiyan. It ravaged the eastern and central Philippines, leaving roads blocked and thousands homeless with no access to shelter, food and other supplies. UN Humanitarian Office spokesman Matthew Cochrane stated "damaged roads and a lack of trucks and storage facilities have delayed aid distribution. It was a logistical nightmare to issue relief supplies with at least ten million people in need of basic necessities across several remote islands and communities in the central region" [abc News].

If the disaster was recent and it had a substantial impact on the local communication infrastructure, which is common, data about whether or not a road is passable or not is usually not known until the driver gets to that road. A driver delivering humanitarian aid is not likely to have on-board routing software nor can a driver depend on constant communication with the dispatchers at the depot if the planned route does not work. Thus, he or she needs to leave the depot with multiple plans, or paths, from source to destination considering potential road failures. It may be necessary to backtrack or introduce a new path from the point of the first road failure and take a very different path to the destination. We have not seen this issue addressed specifically in the literature.

It is important to realize these road failures and have an interdependent relationship with each other. For example, if one road in a neighborhood is flooded, it is likely that the other roads in that neighborhood will be flooded. Modeling this correlation is quite complicated and is usually handled through scenarios, as we will do. Each scenario represents a particular outcome in terms of which roads are passable and which are not. Scenarios capture the dependence among roads that are near each other, are at similar levels of elevation, etc. They can be created in advance of a disaster to describe the potential outcomes, so routes can be planned for first-responders. Due to the potential damage to the communication infrastructure and the size of the area impacted by the disaster, it can often take several days to establish what parts of the transportation network are functioning (which also may be changing). Thus, scenarios also can be used after a disaster to describe the potential realizations that may have occurred.

In our paper, we consider a shortest path problem from source to destination over a set of arc failure scenarios, considering the probability of different scenarios. Our aim is to create a set of paths that gives a driver an option when an impassible road is encountered. These paths should provide an efficient travel time to the destination and cover the set of scenarios. We identify a primary path and a set of alternative paths. The alternative paths are taken if there is a failure in the primary path. We introduce two different variants of the problem, allowing for different restrictions on the alternative paths and provide an integer programming model formulation for both variants. Our primary contribution is a pair of exact algorithms that can be used to help solve large instances for both the variants in a reasonable amount of time. Our presentation for the TSL conference will include results on the performance of our solution approaches for well known data-sets. These results are based on a varying number of scenarios and percentage of arcs failing.

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.

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.

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.