PROGRAM FOR TUESDAY, JULY 1ST

ABSTRACT. See attached file.

ABSTRACT. We study rollout policies for the vehicle routing problem with stochastic demand and duration limits (VRPSDL). We build on the VRPSDL literature by studying the impact of restricted policy classes and heuristic search procedures on rollout policy performance. Specifically, we expand the restricted policy class from a priori to restocking fixed-route policies and enlarge the heuristic search procedure from first-improve local search to variable neighborhood search. Computational experiments suggest a better restricted policy class can improve rollout policy performance, but more intricate heuristic search procedures for fixed-route policies do not necessarily lead to better dynamic decisions.

ABSTRACT. The vehicle routing problem with stochastic demands (VRPSD) consists in designing transporta- tion routes of minimal expected cost to satisfy a set of customers with random demands of known probability distributions. In this research we present two strategies to deal with route duration con- straints in the VRPSD. To solve the resulting problem, we proposed a greedy randomized adaptive search procedure (GRASP) with a post optimization procedure. The GRASP component uses a set of randomized route-first, cluster-second heuristics to generate starting solutions and a variable neighborhood descent (VND) procedure to carry on the local search phase. The post optimizer selects the best possible routes to assemble the final solution from the set of all routes found in the local optima reached by the GRASP. We discuss extensive computational experiments analysing the cost of con- sidering route duration constraints on the VRPSD. In addition, we report state-of-the-art solutions for a established set of benchmarks for the classical VRPSD.

ABSTRACT. In this paper, we study a robust inventory routing problem with time windows (IRPTW) for deliveries with uncertain disruptions, where the length and placement of the time windows are also decision variables. We consider the problem faced by a single vendor who must simultaneously decide routes for all of his vehicles and time windows at all customers. Various types of disruptions that affect the travel time or availability of vehicles to deliver in certain time periods are taken into account. We propose a two-phased approach to generate robust routes and delivery time windows to this problem. Our simulation results show that for a small increase in the initial planning cost, our robustness strategies generate plans that are far more robust than those that neglect the possibility of disruptions.

ABSTRACT. Transportation planning forecasts often differ widely from forecasted conditions. For instance, transit ridership is often lower than forecasted, toll revenue is lower, and construction costs and duration are higher. Many people assume that this occurs because transportation models are biased to favor selection of particular projects or alternatives for political reasons or to reflect personal biases. However, an old adage is to ``never ascribe to malice that which is adequately explained by incompetence'' --- but rather than incompetence, this paper suggests that neglecting uncertainty in future demand may result in systematically over-optimistic forecasts, even if the modeling and prediction processes are completely unbiased.

In particular, this paper shows that even if the forecasting process is unbiased, two factors combine to produce systematically optimistic forecasts for the selected project: (1) the inability to forecast future conditions perfectly, and (2) the fact that projects are chosen to maximize one or more measures of effectiveness. The combination of this uncertainty and choice process suggest that the chosen project is likely one for which the forecast is overly optimistic. This paper studies the issue by evaluating multiple project alternatives using static traffic assignment with uncertainty in the OD matrix. Key implications for planning are: (1) introducing a large number of alternatives for comparison may in fact hinder selection of the optimal alternative, and (2) the use of multi-scenario or sampling techniques can be useful to identify overly optimistic forecasts despite imperfect knowledge of future conditions.

ABSTRACT. We can consider a novel repair kit inventory problem in which field technicians must make part replacement repairs to machines with many parts. Each technician has a part kit, but if a required repair part is not in the kit the technician can travel to a central inventory location to collect one. This location, known as the Forward Stocking Location, allows for risk pooling and to decrease the cost of holding inventory in each technician kit. Since trips to the FSL take time, and this time reduces the technicians capability to serve future jobs, we model this recourse action explicitly for the first time. We develop an optimization model for deciding whether to carry a part in kit or at the FSL, minimizing the cost of holding inventory while satisfying a job fill rate chance constraint. Heuristic solution approaches are developed and analyzed for this problem.

ABSTRACT. See attached pdf-file.

ABSTRACT. Sensor Placement for Stochastic Traffic Congestion Observation

Presenter: Siqian Shen Dept. of Industrial and Operations Engineering, Univ. of Michigan Email: siqian@umich.edu Co-author: Zhili Zhou IBM laboratory in Singapore Email: zhilizhou@gmail.com

Traffic congestion is a growing problem in many metropolitan areas, resulting in the increase of travel time, air pollution, carbon dioxide (CO2) emissions and fuel use. The congestion problem arises for various reasons, including accidents, road maintenance, peak hours, etc. To better monitoring traffic at real time, static sensors are placed on segments in traffic networks for traffic information collection, vehicle counting, and incident detection. However, traffic flows often have multiple origins and destinations, and the amounts between each pair of origin and destination are random with known or ambiguous distributions.

In this paper, we consider deploying sensors on a subset of arcs in a given network with existing sensors located in a subset of locations. The goal is to minimize the number of new sensors deployed and to maximize the coverage of the network in terms of obtainable arc information. In particular, we study sensor deployment in large-scale transportation systems, where we deploy new sensors on a set of “highly congested” arcs so that traffic congestion on each arc can be observed by a sensor or inferred from adjacent nodes that are monitored by an existing sensor.

The resulting set covering problem is computationally expensive if we consider a large-scale network with many nodes and arcs. Therefore, we formulate a two-stage stochastic optimization model: we minimize the number of sensors at the first stage but only on a subset of arcs that are the “most likely” to be congested, identified by solving an optimization problem at the second stage, which is formulated as a stochastic program with a joint chance constraint, where we allow (i) traffic congestion on certain arcs and (ii) traffic losses due to congestion. By assuming that all travelers are rational and can fully observe the system, the chance-constrained program minimizes the number of congested arcs subject to a small and controllable risk of having traffic flow losses of multiple travelers. We then feed the calculated set of congested arcs back to the 1st-stage-sensor deployment problem and only decide whether to allocate new sensors on arcs with congestion (i.e., the amount of flows on these arcs exceeding their capacities).

To optimize the aforementioned chance-constrained program, we employ Monte Carlo sampling techniques to generate a finite number of realizations of random traffic supply-demand between each origin-and-destination (O-D) pair. We reformulate the joint chance constraint as mixed-integer programming constraints by defining 0-1 binary variables for each realized scenario, indicating whether or not any traffic is lost in the scenario so that we guarantee the probability by restricting the number of violated scenarios via a 0-1 knapsack constraint. The resulting mixed-integer program is generally intractable for which we develop valid inequalities to perform a cutting-plane algorithm for solving the 2nd-stage problem.

The foregoing analysis using chance-constrained programming models requires the knowledge of exact distribution of the uncertainty, i.e., the random traffic supply-demand between O-D pairs. In practice, such information is rarely known and we study a variant of the previous problem by taking into account distribution ambiguity. We tailor different types of stochastic optimization models in the literature to formulate this variant depending on how much information we know about the traffic uncertainty as well as the tradeoff criteria. In particular, we demonstrate distributionally robust formulations by using moment- and divergence-function-based confidence sets of the ambiguous distribution, such that optimal sensor deployment solutions yielded by the formulations can guarantee that the worst case probability of having any traffic losses is smaller than a given risk tolerance, for any possible distributions of the traffic demand. Such results fully utilize “the value of data,” but are relatively conservative compared with solutions obtained by assuming full knowledge of the uncertainty, which is often unrealistic. The resulting arcs with high congestion probability under traffic demand ambiguity are taken as candidate arcs for deploying new sensors and we will evaluate the results especially from the economic and risk perspectives.

For reformulation the distributionally robust variants of the 2nd-stage congestion identification problem, we mainly employ results in Jiang and Guan (2013) for solving general data-driven chance-constrained programs. In particular, if using the divergence-function-based confidence set, we retain a chance-constrained program with an updated risk parameter, which can be solved by reusing all approaches we developed for solving the non-ambiguous case.

We apply our models and approaches by testing large-scale datasets based on 5-minute-interval traffic flow information in the traffic network of Singapore. We also differentiate the risk targets associated with flow losses of different travelers. Via extensive computational studies, we aim to demonstrate (i) the computational efficacy of our inequalities and the cutting-plane algorithm for solving NP-hard chance-constrained programs, (ii) the relationship between sensor deployment locations and the distribution of congested arcs, (iii) optimal deployment solutions under traffic uncertainty and probabilistic guarantees, and (iv) the effect of considering ambiguous traffic demand distributions, and comparisons of the stochastic programs and their corresponding distribuitonally robust models formulated based on different statistical inference techniques.

[1] R. Jiang and Y. Guan “Data-driven chance-constrained stochastic programs.” Available at Optimization Online, http://www.optimization-online.org/DB_FILE/2013/09/4044.pdf. 2013.

ABSTRACT. In many examples in transportation and logistics, solutions in terms of prices and quantities for goods produced and consumed at different locations can be observed, while routing and cost information remains unknown. Assuming the agents responsible these decisions made decisions according to optimality or other equilibrium conditions, inverse optimization techniques can be used to infer the hidden information from the observations. This talk will describe how these inverse problems can find the right questions for which various answers can be observed. The discussion will include examples where the network connection structure is not observed, results from uncovering the structure of a large electric power system, and implications for network security and global trade.

ABSTRACT. Please see attached file for abstract.

ABSTRACT. This work considers hub networks from the perspective of a logistics’ customer. We device an optimization method capable of deciding on renting hubs and routing several different goods from multiple sources to multiple sinks in a large scale network with realistic multi-property transportation costs. As the planning must be completed before the actual demand is known, our solutions are robust optimal, i.e., have lowest cost under restricted worst-case demand fluctuation. In terms of size and modelling precision this robust method is very close to state-of-the-art deterministic methods.

ABSTRACT. We present a novel strategy aimed at enhancing the Benders decomposition approach when it is applied to integer stochastic programs. This strategy, which we refer to as partial Benders decomposition, can considerably reduce the number of cuts that are generated by the algorithm. Numerical results obtained on a set of stochastic network design problems clearly show the advantages of the proposed strategy.

ABSTRACT. The concept of predictability, reflecting the uncertainty in flight time or flight schedule in air transportation has received increased attention in recent service quality assessments. Among various benefits that could be achieved through improved flight predictability, in this paper we investigate the benefit of reduced fuel cost. The unpredictability under flight performance may cause airline dispatchers to load more fuel onto aircraft, and thus causing extra fuel consumed to carry this excessive fuel, which is a significant amount and the airlines are concerned with this cost. In this study, we have a large and recent dataset with flight-level fuel loading and consumption information from a major US airline. With these data, firstly the relationship between the amount of loaded fuel and flight predictability performance is estimated using statistical model. Then the impact on loaded fuel is translated into fuel consumption and, ultimately, fuel cost for US domestic operations. We find that a one minute increase in the standard deviation of airborne time, within a month for the same OD pair and dispatcher work shift of day would lead to 0.88 minutes increase of loaded contingency fuel and 1.66 minutes of loaded contingency and alternate fuel. If there is no uncertainty in the aviation system, captured in our model by standard deviation in flight time, the reduction in the loaded fuel would be 6.12 and 11.28 minutes per flight, respectively. This ultimately would translate into cost savings for US domestic airlines on the order of $120 – $452 million per year.

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.

ABSTRACT. Please see attachment.