Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center; and, (S.M. in Transportation)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering, 2010. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 142-144). / A myriad of uncontrollable factors in airline operations make delays and disruptions unavoidable. Most conventional scheduling models, however, ignore the presence of uncertainties in actual operations in order to limit the complexity of the problem. This leads to schedules that are prone to delays and disruptions. As a result, there has been wide interest recently in building robustness into airline schedules. In this work, we investigate slack allocation approaches for robust airline schedule planning. In particular, we propose three models: aircraft re-routing model, flight schedule re-timing model, and block time adjustment model, together with their variants. Using data from an international carrier, we evaluate the impacts of the resulting schedules on various performance metrics, including passenger delays. The results show that minor modifications to an original schedule can significantly improve the overall performance of the schedule. Through empirical results, we provide a comprehensive discussion of model behaviors and how an airline's characteristics can affect the strategy for robust scheduling. / by Virot Chiraphadhanakul. / S.M.in Transportation / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering; and, (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2010. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (p. 150-156). / Increases in car ownership and usage have resulted in serious traffic congestion problems in many large cities worldwide. Innovative travel modes and services can play an important role in improving the efficiency and sustainability of transportation systems. In this study, we evaluate the preferences for some new modes and services (one-way car rental, shared taxi, express minibus, school bus service for park and ride, and congestion pricing) in the context of Lisbon, Portugal using stated preferences (SP) techniques. The survey design is challenging from several aspects. First of all, the large number of existing and innovative modes poses a challenge for the SP design. To simplify choice experiment, sequential approaches are used to divide the large choice set into car-based, public transport, and multimodal groups. Secondly, there is a large set of candidate variables that are likely to affect the mode choices. The findings of focus group discussion are analyzed to identify the key variables. Thirdly, the innovative modes and services are likely to affect not only the mode choices but also the choices of departure time and occupancy (in case of private modes). A multidimensional choice set of travel mode, departure time, and occupancy is considered. Two types of models are used to investigate the preferences and acceptability of innovative modes and services -- nested logit models and mixed logit models. The main attributes in the systematic utilities include natural logarithm of travel time and cost, schedule delay, size variables for unequal departure time intervals, and inertia to revealed preferences (RP) choices of travel mode, departure time, and occupancy. The values of willingness to pay (WTP) are found to depend on trip purpose, market segment, and the magnitude of travel cost and time. Mixed logit models can address complex correlation and heterogeneity problems in the SP data better than nested logit models. Based on the estimation results, mixed logit models are found more efficient and reliable. They can provide important information for transportation planners and policy makers working to achieve sustainable transportation systems in Portugal as well as in other countries. / by Lang Yang. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center; and, (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (p. 75-77). / We consider the problem of protection in multilayer networks. In single-layer net- works, a pair of disjoint paths can be used to provide protection for a source-destination pair. However, this approach cannot be directly applied to layered networks where disjoint paths may not always exist. In this thesis, we take a new approach which is based on finding a set of paths that may not be disjoint but together will survive any single physical link failure. First, we consider the problem of finding the minimum number of survivable paths. In particular, we focus on two versions of this problem: one where the length of a path is restricted, and the other where the number of paths sharing a fiber is restricted. We prove that in general, finding the minimum survivable path set is NP-hard, whereas both of the restricted versions of the problem can be solved in polynomial time. We formulate the problem as Integer Linear Programs (ILPs), and use these formulations to develop heuristics and approximation algorithms. Next, we consider the problem of finding a set of survivable paths that uses the minimum number of fibers. We show that this problem is NP-hard in general, and develop heuristics and approximation algorithms with provable approximation bounds. We also model the dependency of communication networks on the power grid as a layered network, and investigate the survivability of communication networks in this layered setting. Finally, we present simulation results comparing the different algorithms. / by Marzieh Parandehgheibi. / S.M.

Thesis (S.M. in Transportation)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering; and, (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2010. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 159-163). / This thesis evaluates the performance of Dynamic Programming (DP) models as applied to airline Revenue Management (RM) compared to traditional Revenue Management models like EMSRb as DP models offer a theoretically attractive alternative to traditional RM models. In the first part of this thesis, we develop a simplified simulator to evaluate the effects of changing demand variance on the performance of standard DP on a single flight leg. This simulator excludes the effects of forecast quality and competitive effects like passenger sell-up and inter-airline spill. In the next part of the thesis, we introduce two network based DP methods that incorporate the network displacement costs in the standard DP based optimizer and perform simulation experiments in a larger competitive network using the Passenger Origin Destination Simulator to study the performance of DP methods in airline Revenue Management systems. The results of single flight leg experiments from the simplified simulator show that DP methods do not consistently outperform EMSRb and the sensitivity analysis show that the performance of DP relative to EMSRb depends on the demand variability, demand factor, fare ratios and passenger arrival pattern. The results from the PODS competitive network simulations show that DP methods, despite not showing any significant benefits in the simplified simulator, can outperform EMSRb when used in a competitive environment because DP's aggressive seat protection policy helps DP generate more revenues than EMSRb due to competitive feedback effects like inter-airline passenger spill-in, and passenger sell-up within the airline. / by Sarvee Diwan. / S.M. / S.M.in Transportation

Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 1998. / Includes bibliographical references (p. 325-338) and indexes. / by John Douglas Ruark. / Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 1999. / Includes bibliographical references (leaves 103-106). / In this thesis, we develop practical solution methods for a supply chain optimization problem: a multi-echelon, un capacitated, time-expanded network of distribution cen­ters and stores, for which we seek the shipping schedule that minimizes total inventory, backlogging, and shipping costs, assuming deterministic, time-varying demand over a fixed time horizon for a single product. Because of fixed ordering and shipping costs, this concave cost network flow problem is in a class of NP-hard network design problems. We develop mathematical programming formulations, heuristic algorithms, and enhanced algorithms using approximate dynamic programming (ADP). We achieve a strong mixed integer programming (MIP) formulation, and fast, reliable algorithms, which can be extended to problems with multiple products. Beginning with a lot-size based formulation, we strengthen the formulation in steps to develop one which is a variation of a node-arc formulation for the network design problem. In addition, we present a path-flow formulation for the single product case and an enhanced network design formulation for the multiple product case. The basic algorithm we develop uses a dynamic lot-size model with backlogging together with a greedy procedure that emulates inventory pull systems. Four re­lated algorithms perform local searches of the basic algorithm's solution or explore alternative solutions using pricing schemes, including a Lagrangian-based heuristic. We show how approximate dynamic programming can be used to solve this sup­ply chain optimization problem as a dynamic control problem using any of the five algorithms. In addition to improving all the algorithms, the ADP enhancement turns the simplest algorithm into one comparable to the more complex ones. Our computational results illustrate that our enhanced network design formula­tion almost always produces integral solutions and can be used to solve problems of moderate size (3 distribution centers, 30 stores, 30 periods). Our heuristic methods, particularly those enhanced by ADP methods, produce near optimal solutions for truly large scale problems. / by Carl E. Wike. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 1999. / Submitted to the Dept. of Electrical Engineering and Computer Science, MIT. / Includes bibliographical references (p. 110-114). / In the automobile manufacturing industry, vehicle production is an assembly-line process. Automobile companies typically sequence vehicle production based on workload balancing factors, with little consideration of vehicle colors. The resulting sequence usually has a small average paint block size. Because automobile manufacturers use expensive and sometimes pollutant chemicals to clean out old paint at each color change, they would like to increase the size of the paint blocks, while maintaining the original workload-balanced vehicle sequence. To achieve this goal, Ford and other automobile manufacturers are considering automated vehicle storage and retrieval systems that would allow them to perturb the original sequence around the vehicle painting station, creating larger paint blocks and then restoring the original sequence after painting. To evaluate these systems, it is necessary to develop a method for re sequencing cars and for calculating the resulting savings in paint cleanings. The problem of resequencing can be cast as a traveling salesman problem with time windows. For a real-life sequence size of 750 cars and windows of 75 slots per car in either direction, direct modeling using the strongest known ... formulation yields an integer program with up to 200,000 constraints and 14,000,000 variables. Reduced formulations. We exploit special problem structure to solve the LP relaxation of this problem quickly using Lagrangean relaxation. We prove and use an order-within-color property to construct an enumerative formulation, and use a greedy approach to bound the LP optimum. We decompose the problem and solve smaller enumerative formulations sequentially to generate a heuristic solution that empirically is within 2.5% of optimality. Because our heuristic and bounding procedure runs in a total of one minute, an automobile manufacturer could use the process to adjust the resequencing process in real time to compensate for vehicles that have been delayed in the original sequence due to production defects or other disruptions. We also establish worst-case bounds ranging from 2.5 to 6 for another related heuristic. / by Joel Scott Sokol. / Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering; and, (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007. / Includes bibliographical references (p. 129-131). / We consider large-scale, network-based, resource allocation problems under uncertainty, with specific focus on the class of problems referred to as multi-commodity flow problems with time-windows. These problems are at the core of many network-based resource allocation problems. Inherent data uncertainty in the problem guarantees that deterministic optimal solutions are rarely, if ever, executed. Our work examines methods of proactive planning, that is, robust plan generation to protect against future uncertainty. By modeling uncertainties in data corresponding to service times, resource availability, supplies and demands, we can generate solutions that are more robust operationally, that is, more likely to be executed or easier to repair when disrupted. The challenges are the following: approaches to achieve robustness 1) can be extremely problem-specific and not general; 2) suffer from issues of tractability; or 3) have unrealistic data requirements. We propose in this work a modeling and algorithmic framework that addresses the above challenges. / (cont.) Our modeling framework involves a decomposition scheme that separates problems involving multi-commodity flows with time-windows into routing (that is, a routing master problem) and scheduling modules (that is, a scheduling sub-problem), and uses an iterative scheme to provide feedback between the two modules, both of which are more tractable than the integrated model. The master problem has the structure of a multi-commodity flow problem and the sub-problem is a set of network flow problems. This decomposition allows us to capture uncertainty while maintaining tractability. Uncertainty is captured in part by the master problem and in part by the sub-problem. In addition to solving problems under uncertainty, our decomposition scheme can also be used to solve large-scale resource allocation problems without uncertainty. As proof-of-concept, we apply our approach to a vehicle routing and scheduling problem and compare its solutions to those of other robust optimization approaches. Finally, we propose a framework to extend our robust, decomposition approach to the more complex problem of network design. / by Lavanya Marla. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering; and, (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2008. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Includes bibliographical references (p. 99-102). / In this thesis we consider a multi-period truckload pick-up and delivery problem dealing with real-time requests over a finite time horizon. We introduce the notion of postponement of requests, whereby the company can postpone some requests to the next day in order to improve its operational efficiency. The postponed requests must then be served on the next day. The daily costs of operation include costs associated with the trucks' empty travel distances and costs associated with postponement. The revenues are directly proportional to the length of job requests. We evaluate the profits of various re-optimization policies with the possibility of postponement. Another important notion of trucking operation corresponds to repositioning strategies which exploit probabilistic knowledge about future demands. A new repositioning strategy is proposed here to provide better decisions. For both notions, extensive computational results are provided under a general simulation framework. / by Tanachai Limpaitoon. / S.M.

Thesis (S.M. in Transportation)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering; and, (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2008. / Includes bibliographical references (p. 91-93). / The purpose of this thesis is to explore various harmonization scenarios for North Atlantic en route user charges. The current charging system involves eight countries, each with their own method for computing user charges. The scope of the research is limited to revenue neutral approaches for service providers, meaning each air navigation service provider (ANSP) receives constant total charges in 2006. Therefore, the viability of different scenarios is compared in terms of its impact on airspace users. Two different interpretation of a "harmonized" system are considered. The first explores the harmonization of only the charging methodology, allowing service providers to set and collect their own charges. The second harmonization alternative fully harmonizes the North Atlantic user charges resulting in a single charge per flight. Within each of these alternatives four different charge scenarios were modeled using 2006 data. The four alternatives are a flat charge, distance-based rate, a combination weight and distance charge, and a fixed-plus-variable charge. Utilizing 47,516 North Atlantic flights drawn from a systematic random sampling of days in 2006, the average North Atlantic user charge was determined to be $393 and ranged from less than $1 to $3,868. The magnitude of the average North Atlantic user charge is small relative to the total flight costs airlines incur, thus all harmonization approaches will have only second order effects on the airlines' bottomline. Thus, the harmonization of the regions' user charges allows for the unique opportunity to develop a more rational system of charges without large disruptions to the majority of users. The thesis explores the impact of the various charge scenarios on user stakeholder groups in terms of aircraft size, North Atlantic distance, and origin-destination regions. / (cont.) The results show a distance-based rate imposed at the ANSP-level would result in the smallest disruption to users' charges compared to the baseline system. However, any semi-independent harmonization approach sacrifices the efficiencies which could be realized under a fully harmonized system. Of the fully harmonized methods, the Eurocontrol formula with a service unit rate of $7.28 is the least disruptive to the baseline user charges. / by Megan Brett Gaudet. / S.M. / S.M.in Transportation