Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. / Includes bibliographical references (p. 155-166). / A practical approach for solving computationally intractable problems is to employ heuristic (approximation) algorithms that can find nearly optimal solutions within a reasonable amount of computational time. An improvement algorithm is an approximation algorithm which starts with a feasible solution and iteratively attempts to obtain a better solution. Neighborhood search algorithms (alternatively called local search algorithms) are a wide class of improvement algorithms where at each iteration an improving solution is found by searching the "neighborhood" of the current solution. This thesis concentrates on neighborhood search algorithms where the size of the neighborhood is "very large" with respect to the size of the input data. For large problem instances, it is impractical to search these neighborhoods explicitly, and one must either search a small portion of the neighborhood or else develop efficient algorithms for searching the neighborhood-implicitly. This thesis consists of four parts. Part 1 is a survey of very large scale neighborhood (VLSN) search techniques for combinatorial optimization problems. In Part 2, we concentrate on a VLSN search technique based on compounding independent simple moves such as 2-opts, swaps, and insertions. We show that the search for an improving neighbor can be done by finding a negative cost path on an auxiliary graph. We show how this neighborhood is applied to problems such as the TSP, VRP, and specific single and multiple machine scheduling problems. / (cont.) In Part 3, we discuss dynamic programming approximations for the TSP and a generic set partitioning problem that are based on restricting the state space of the original dynamic programs. Furthermore, we show the equivalence of these restricted DPs to particular neighborhoods that we had considered earlier. Finally, in Part 4, we present the results of a computational study for the compounded independent moves algorithm on the vehicle routing problem with capacity and distance restrictions. These results indicate that our algorithm is competitive with respect to the current heuristics and branch and cut algorithms. / by Özlem Ergun. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2015. / 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 (pages 171-178). / This thesis discusses optimization problems and equilibrium in networks. There are three major parts of the thesis. In the first part, we discuss optimization in dynamic networks. We focus on two fundamental optimization problems in dynamic networks: the quickest flow problem and the quickest transshipment problem. The quickest flow problem is to find a minimum time needed to send a given amount of flow from one origin to one destination in a dynamic network. The quickest transshipment problem is similar to the quickest flow problem except with multiple origins and multiple destinations. We derive optimality conditions for the quickest flow problems and introduce simplified and more efficient algorithms for the quickest flow problems. For the quickest transshipment problem, we develop faster algorithms for several special cases and apply the approach to approximate an optimal solution more efficiently. In the second part, we discuss equilibrium in dynamic networks. We extend equilibrium results in static networks into dynamic networks and show that equilibria exist in a network where players either have the same origin or the same destination. We also introduce algorithms to compute such an equilibrium. Moreover, we analyze the average convergence speed of the best-response dynamics and connect equilibria in discrete network models to equilibria in continuous network models. In the third part, we introduce a new traffic information exchange system. The new system resolves the dilemma that broadcasting traffic predictions might affect drivers' behaviors and make the predictions inaccurate. We build game theoretic models to prove that drivers have incentives to use this system. In order to further test the effectiveness of such system, we run a series of behavioral experiments through an online traffic game. Experimental results show that drivers who use the system have a lower average travel time than the general public, and the system can help improve the average travel time of all drivers as the number of drivers who use this system increases. / by Maokai Lin. / Ph. D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2011. / 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. 243-247). / Our work is motivated by real-world planning challenges faced by a manufacturer of industrial products. In the first part of the thesis, we study a multi-product serial-flow production line that operates in a low-volume, long lead-time environment. The objective is to minimize variable operating costs, in the face of forecast uncertainty, raw material arrival uncertainty and in-process failure. We develop a dynamic-programming-based tactical model to capture the key uncertainties and trade-offs, and to determine the minimum-cost operating tactics. The tactics include smoothing production to reduce production-related costs, and segmenting the serial-flow line with decoupling buffers to protect against variance propagation. For each segment, we specify a work release policy and a production control policy to manage the work-in-process inventory within the segment and to maintain the inventory targets in the downstream buffer. We also optimize the raw material ordering policy with fixed ordering times, long lead-times and staggered deliveries. In the second part of the thesis, we examine a multi-product assembly system that operates in a high-volume, short lead- time environment. The operating tactics used here include determining a fixed-length cyclic schedule to control production, in addition to smoothing production and segmenting the system with decoupling buffers. We develop another dynamic-programming-based tactical model that determines optimal policies for production planning and scheduling, inventory, and raw material ordering; these policies minimize the operating cost for the system in the face of forecast and raw material arrival uncertainty. We tested these models on both hypothetical and actual factory scenarios. The results confirmed our intuition and also helped develop new managerial insights on the application of these operating tactics. Moreover, the tactical model's factory performance predictions were found to be within 10% of simulation results for the testbed systems, thus validating the models. / by Pallav Chhaochhria. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from PDF student-submitted version of thesis. / Includes bibliographical references (pages 165-172). / First, we describe a general framework called online customer selection that describes natural settings where suppliers must actively select which customer requests to serve. Unlike traditional revenue management models that have sunk costs, we assume there are supply chain costs that depend on the demand being served. Specifically, customers arrive in an online manner, each with a set of requirements and associated revenue, and are either accepted or rejected upon arrival. Rejected customers incur a lost-sales cost, while accepted customers are satisfied with minimum possible production cost. The goal of the supplier is to minimize the total cost of lost sales and production. We provide algorithms with strong performance guarantees that are based on new variants of repeated optimization as well as concepts from mechanism design. Second, we study the use of opaque products in a retail setting. A product is said to be opaque when one or more of its attributes are hidden until the transaction is complete. Opaque products have been used in the hotel and airline industry where customers purchase rooms or airfare without a priori knowledge of the brand name. In this work, we propose the use of opaque product selling in the retail industry, where there are nonperishable goods and supply chain costs. We show that a small amount of opaque selling can achieve significant ordering and holding costs savings for the supply chain. Moreover, we describe settings when a stationary opaque selling strategy can outperform a common dynamic pricing strategy. Third, we focus on a variant of the joint replenishment problem, which arises in the previous two parts as well as in inventory management, logistics, and maintenance scheduling. In this problem, there are multiple item types that each has a given time-dependent sequence of demands that need to satisfied. Every time an order of item types is placed, there is an associated fixed setup cost that is submodular in the subset of item types ordered. The overall goal is to minimize the total fixed ordering costs plus inventory holding costs. We provide a variety of approximation algorithms for this problem and some special cases. / by Adam Nabil Elmachtoub. / Ph. D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2008. / Includes bibliographical references (p. 79-87). / This thesis explores how operations research methods can be applied in the emergency response community by looking at two recent tropical storm disasters; tropical cyclone Yemyin in Pakistan, June 2007 and super typhoon Durian in the Philippines, Nov 2006. The case studies are used to highlight three common problem areas; determining the scope of the disaster, agency coordination, and relief logistics. The thesis identifies some operational models and applicable research and suggests that these ideas should be formulated as emergency management decision making tools particularly for use in the developing world. / by Maurice D. Murphy. / S.M.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017. / 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 (pages 55-60). / We build on existing operations and marketing research focusing on the effect of information transparency on consumers by studying how transparency into the levels and changes of relative sustainability performance affects consumer behavior. Our work considers two forms of transparency: process transparency and customer transparency. We operationalize process transparency, in which information about the company's sustainability performance relative to competitors is revealed to the customer, in the product purchase domain. We operationalize customer transparency, in which the customer receives information about their own sustainability performance relative to other customers, in the energy consumption domain. In a series of online consumer choice experiments, we find that within the product purchase domain, transparency into the company's current levels of sustainability performance has a more powerful effect on influencing consumer purchase behavior than transparency into the company's changes in relative sustainability performance over time. Conversely, in the energy consumption domain, we find that transparency into the customer's changes in sustainability performance over time, relative to other customers, has a more dominant effect in motivating energy conservation than transparency into the customer's relative levels of sustainability performance. We employ structural equation models to identify the underlying mechanisms that drive these results. / by Shwetha Paramananda Mariadassou. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2008. / Includes bibliographical references (p. 115-116). / We present in this work a unified approach and provide the optimal solution to the pricing problem of option contracts for a supplier of an industrial good in the presence of spot trading. Specifically, our approach fully and jointly endogenizes the determination of three major characteristics in contract design, namely (i) Sales contracts versus options contracts; (ii) Flat fee versus volume- dependent contracts; and (iii) Volume discounts versus volume premia; combining them together with spot market trading decisions and also the option of delaying production for the seller. We build a model where a supplier of an industrial good transacts with a manufacturer who uses the supplier's product to produce an end good with an uncertain demand. We derive the general non-linear pricing solution for the contracts under information asymmetry of the buyer's production flexibility. We show that confirming industry observations, volume-dependent optimal sales contracts always demonstrate volume discounts (i.e., involve concave pricing). On the other hand the options contracts are more complex agreements, and optimal contracts for them can involve both volume discounts and volume premia. Further, we find that in the optimal contracts, there are three major pricing regimes. First, if the seller has a higher discount rate than the buyer and the production costs are lower than a critical threshold value, the optimal contract is a flat fee sales contract. Second, when the seller is less patient than the buyer but production costs are higher than the critical threshold, the optimal contract is a sales contract with volume discounts. Third, if the buyer has a higher discount rate than the seller, then the optimal contract is a volume-dependent options contract and can involve both volume discounts and volume premia. We further provide links between industry and spot market characteristics, contract characteristics and efficiency. Last, we look into an extension of our basic model, where we give an analysis for the case when the seller is given a last minute production option. / by Pamela Pen-Erh Pei. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2012. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 137-140). / The cost of air traffic delays is well documented, and furthermore, it is known that the significant proportion of delays is incurred at airports. Much of the air traffic flow management literature focuses on traffic flows between airports in a network, and when studies have focused on optimizing airport operations, they have focused largely on a single aspect at a time. In this thesis, we fill an important gap in the literature by proposing unified approaches, on both strategic and tactical levels, to optimizing the traffic flowing through an airport. In particular, we consider the entirety of key problems faced at an airport: a) selecting a runway configuration sequence; b) determining the balance of arrivals and departures to be served; c) assigning flights to runways and determining their sequence; d) determining the gate-holding duration of departures and speedcontrol of arrivals; and e) routing flights to their assigned runway and onwards within the terminal area. In the first part, we propose an optimization approach to solve in a unified manner the strategic problems (a) and (b) above, which are addressed manually today, despite their importance. We extend the model to consider a group of neighboring airports where operations at different airports impact each other due to shared airspace. We then consider a more tactical, flight-by-flight, level of optimization, and present a novel approach to optimizing the entire Airport Operations Optimization Problem, made up of subproblems (a) - (e) above. Until present, these have been studied mainly in isolation, but we present a framework which is both unified and tractable, allowing the possibility of system-optimal solutions in a practical amount of time. Finally, we extend the models to consider the key uncertainties in a practical implementation of our methodologies, using robust and stochastic optimization. Notable uncertainties are the availability of runways for use, and flights' earliest possible touchdown/takeoff times. We then analyze the inherent trade-off between robustness and optimality. Computational experience using historic and manufactured datasets demonstrates that our approaches are computationally tractable in a practical sense, and could result in cost benefits of at least 10% over current practice. / by Michael Joseph Frankovich. / Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2013. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / "June 2013." Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 155-157). / collect information. This may include taking pictures of the ground, gathering infrared photos, taking atmospheric pressure measurements, or any conceivable form of data collection. Often these separate organizations have overlapping collection interests or flight plans that are sending sensors into similar regions. However, they tend to be controlled by separate planning systems which operate on asynchronous scheduling cycles. We present a method for coordinating various collection tasks between the planning systems in order to vastly increase the utility that can be gained from these assets. This method focuses on allocation of collection requests to scheduling systems rather than complete centralized planning over the entire system so that the current planning infrastructure can be maintained without changing any aspects of the schedulers. We expand on previous work in this area by inclusion of a learning method to capture information about the uncertainty pertaining to the completion of collection tasks, and subsequently utilize this information in a mathematical programming method for resource allocation. An analysis of results and improvements as compared to current operations is presented at the end. / by Eric John Robinson. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. / Includes bibliographical references (leaves 61-62). / We consider a single product multistage serial inventory system with several installations, say N - I, ... , l. Installation N - I intakes exogenous supply of a single commodity. For i E {I, ... N - 2}, installation i is supplied by shipments from installation i + 1. Demands for the finished good occur at installation l. Demands that cannot be filled immediately are backlogged. We assume holding costs at each installation which are linear functions of inventory, as well as a constant cost for each unit of backlogged demand, per period. Clark and Scarf {1960) showed that over a finite horizon an echelon basestock policy is optimal. Federgruen and Zipkin (1984) extend their result to the infinite-horizon case for both discounted and average costs. We present a new approach to this multistage serial inventory management problem, and give new proofs of these results by introducing and solving a simple Travel Time problem, using Dynamic Programming. This approach is motivated by the fact that the exact cost-to-go function of the related Travel Time problem can be easily computed using a straightforward recursive procedure (instead of using the typical value iteration or policy iteration methods). Moreover, this cost-to-go function gives various insights useful for a group of more complex multistage inventory problems. In this regard, we discuss how this cost-to-go function can be used to develop good Approximate Dynamic Programming algorithms for a number of complex multistage serial inventory problems. The results obtained suggest that the idea of introducing a related "Travel Time" problem and our algorithm to solve this problem can be used as a building block of a new approach to solve large scale multistage inventory management problems. This thesis was part of a research effort to find a fast algorithm to get very good robust suboptimal solutions to large scale multistage inventory management problems. / by Aristide C.E. Achy-Brou. / S.M.