Addressing fairness among users and risk mitigation in the context of resource allocation in transportation systems under uncertainties poses a crucial challenge yet to be satisfactorily resolved. This dissertation attempts to address this challenge, focusing on achieving a balance between system-wide efficiency and individual fairness in stochastic transportation resource allocation problems. To study complicated fair and risk-averse resource allocation problems - from public transit to urban air mobility and multi-stage infrastructure maintenance - we develop three models: DrFRAM, FairUAM, and FCMDP. Each of these models, despite being proven NP-hard even in a simplistic case, inspires us to develop efficient solution algorithms. We derive mixed-integer linear programming (MILP) formulations for these models, leveraging the unique properties of each model and linearizing non-linear terms. Additionally, we strengthen these models with valid inequalities. To efficiently solve these models, we design exact algorithms and approximation algorithms capable of obtaining near-optimal solutions. We numerically validate the effectiveness of our proposed models and demonstrate their capability to be applied to real-world case studies to adeptly address the uncertainties and risks arising from transportation systems. This dissertation provides a foundational platform for future inquiries of risk-averse resource allocation strategies under uncertainties for more efficient, equitable, and resilient decision-making. Our adaptable framework can address a variety of transportation-related challenges and can be extended beyond the transportation domain to tackle resource allocation problems in a broader setting. / Doctor of Philosophy / In transportation systems, decision-makers constantly strive to devise the optimal plan for the most beneficial outcomes when facing future uncertainties. When optimizing overall efficiency, individual fairness has often been overlooked. Besides, the uncertainties in the transportation systems raise serious questions about the adaptability of the allocation plan. In response to these issues, we introduce the concept of fair and risk-averse resource allocation under uncertainties in this dissertation. Our goal is to formulate the optimal allocation plan that is both fair and risk-averse amid uncertainties. To tackle the complexities of fair and risk-averse resource allocation problems, we propose innovative methods and practical algorithms, including creating novel formulations as well as deriving super-fast algorithms. These solution approaches are designed to accommodate the fairness, uncertainties, and risks typically in transportation systems. Beyond theoretical results, we apply our frameworks and algorithms to real-world case studies, thus demonstrating our approaches' adaptability to various transportation systems and ability to achieve various optimization goals. Ultimately, this dissertation aims to contribute to fairer, more efficient, and more robust transportation systems. We believe our research findings can help decision-makers with well-informed choices about resource allocation in transportation systems, which, in turn, lead to the development of more equitable and reliable systems, benefiting all the stakeholders.

In this thesis, we study the role of interdiction in the Vehicle Routing Problem (VRP), which naturally arises in humanitarian logistics and military applications. We assume that in a general network, each arc has a chance to be interdicted. When interdiction happens, the vehicle traveling on this arc is lost or blocked and thus unable to continue the trip. We model the occurrence of interdiction as a given probability and consider the multi-period expected delivery. Our objective is to minimize the total travel cost or to maximize the demand fulfillment, depending on the supply quantity. This problem is called the Vehicle Routing Problem with Interdiction (VRPI). We first prove that the proposed VRPI problems are NP-hard. Then we show some key analytical properties pertaining to the optimal solutions of these problems. Most importantly, we examine Dror and Trudeau's property applied to our problem setting. Finally, we present efficient heuristic algorithms to solve these problems and show the effectiveness through numerical studies. / Thesis / Master of Science (MSc)

We present works on theory and applications for Mixed Integer Quadratically Constrained Quadratic Programs (MIQCQP). We introduce new mixed integer programming (MIP)-based relaxation and approximation schemes for general Quadratically Constrained Quadratic Programs (QCQP's), and also study practical applications of QCQP's and Mixed-integer QCQP's (MIQCQP). We first address a challenging tank blending and scheduling problem regarding operations for a chemical plant. We model the problem as a discrete-time nonconvex MIQCP, then approximate this model as a MILP using a discretization-based approach. We combine a rolling horizon approach with the discretization of individual chemical property specifications to deal with long scheduling horizons, time-varying quality specifications, and multiple suppliers with discrete arrival times. Next, we study optimization methods applied to minimizing forces for poses and movements of chained Stewart platforms (SPs). These SPs are parallel mechanisms that are stiffer, and more precise, on average, than their serial counterparts at the cost of a smaller range of motion. The robot will be used in concert with several other types robots to perform complex assembly missions in space. We develop algorithms and optimization models that can efficiently decide on favorable poses and movements that reduce force loads on the robot, hence reducing wear on this machine, and allowing for a larger workspace and a greater overall payload capacity. In the third work, we present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions and formulate this approximation using mixed-integer programming (MIP). Combining this with a diagonal perturbation technique to convert a nonseparable quadratic function into a separable one, we present a mixed-integer convex quadratic relaxation for nonconvex quadratic optimization problems. We study the strength (or sharpness) of our formulation and the tightness of its approximation. We computationally demonstrate that our model outperforms existing MIP relaxations, and on hard instances can compete with state-of-the-art solvers. Finally, we study piecewise linear relaxations for solving quadratically constrained quadratic programs (QCQP's). We introduce new relaxation methods based on univariate reformulations of nonconvex variable products, leveraging the relaxation from the third work to model each univariate quadratic term. We also extend the NMDT approach (Castro, 2015) to leverage discretization for both variables in a bilinear term, squaring the resulting precision for the same number of binary variables. We then present various results related to the relative strength of the various formulations. / Doctor of Philosophy / First, we study a challenging long-horizon supply acquisition problem for a chemical plant. For this problem, constraints with products of variables are required to track raw material composition from supply carriers to storage tanks to the production feed. We apply a mixed-integer nonlinear program (MIP) approximation of the problem combined with a rolling planning scheme to obtain good solutions for industry problems within a reasonable time frame. Next, we study optimization methods applied to a robot designed as a stack of Stewart platforms (SPs), which will be used in concert with several other types robots to perform complex space missions. When chaining these SPs together, we obtain a robot that is generally stiffer more precise than a classic robot arm, enabling their potential use for a variety of purposes. Our methods can efficiently decide on favorable poses and movements for the robot that reduce force loads on the robot, hence reducing wear on this machine, and allowing for a larger usable range of motion and a greater overall payload capacity. Our final two works focus on MIP-based techniques for nonconvex QCQP's. In the first work, we break down the objective into an easy-to-handle term minus some squared terms. We then introduce an elegant new MIP-based approximation to handle these squared terms. We prove that this approximation has strong theoretical guarantees, then demonstrate that it is effective compared to other approximations. In the second, we directly model each variable product term using a MIP relaxation. We introduce two new formulations to do this that build on previous formulations, increasing the accuracy with the same number of integer variables. We then prove a variety of useful properties about the presented formulations, then compare them computationally on two families of problems.

Evacuation planning is an important disaster management tool. A large-scale evacuation of a region by automobile is a difficult task, especially as demand is often greater than supply. This is made more difficult as the imbalance of supply and demand actually reduces supply due to congestion. Currently, most of the emphasis in evacuation planning is on supply management. The purpose of this dissertation is to introduce and study sophisticated demand management tools, specifically, staging and routing of evacuees. These tools can be used to produce evacuation strategies that reduce or eliminate congestion. A strategic planning model is introduced that accounts for evacuation dynamics and the non-linearities in travel times associated with congestion, yet is tractable and can be applied to large-scale networks. Objective functions of potential interest in evacuation planning are introduced and studied in the context of this model. Insights into the use of staging and routing in evacuation management are delineated and solution techniques are developed. Two different strategic approaches are studied in the context of this model. The first strategic approach is to control the evacuation at a disaggregate level, where customized staging and routing plans are produced for each individual or family unit. The second strategic approach is to control the evacuation at a more aggregate level, where evacuation plans are developed for a larger group of evacuees, based on pre-defined geographic areas. In both approaches, shelter requirements and preferences can also be considered. Computational experience using these two strategic approaches, and their respective solution techniques, is provided using a real network pertaining to Virginia Beach, Virginia, in order to demonstrate the efficacy of the proposed methodologies. / Ph. D.

The global energy requirement is increasing at a rapid pace and fossil fuels have been one of the major players in meeting this growing energy demand. However, the resources for fossil fuels are finite. Therefore, it is essential to develop renewable energy sources like biofuels to help address growing energy needs. A key aspect in the production of biofuel is the biomass logistics chain that constitutes a complex collection of activities, which must be judiciously executed for a cost-effective operation. In this thesis, we introduce a two-phase optimization-simulation approach to determine tactical biomass logistics-related decisions cost effectively in view of the uncertainties encountered in real-life. These decisions include number of trucks to haul biomass from storage locations to a bio-refinery, the number of unloading equipment sets required at storage locations, and the number of satellite storage locations required to serve as collection points for the biomass secured from the fields. Later, an operational-level decision support tool is introduced to aid the "feedstock manager" at the bio-refinery by recommending which satellite storage facilities to unload, how much biomass to ship, how to allocate existing resources (trucks and unloading equipment sets) during each time period, and how to route unloading equipment sets between storage facilities. Another problem studied is the "Bale Collection Problem" associated with the farmgate operation. It is essentially a capacitated vehicle routing problem with unit demand (CVRP-UD), and its solution defines a cost-effective sequence for collecting bales from the field after harvest. / Master of Science

Stochastic programming is an optimization technique that incorporates random variables as parameters. Because it better reflects the uncertain real world than its traditional deterministic counterpart, stochastic programming has drawn increasingly more attention among decision-makers, and its applications span many fields including financial engineering, health care, communication systems, and supply chain management. On the flip side, stochastic programs are usually very difficult to solve, which is further compounded by the fact that in many of the aforementioned applications, we also have discrete decisions, thereby rendering these problems even more challenging. In this dissertation, we study the class of two-stage stochastic mixed-integer programs (SMIP), which, as its name suggests, lies at the confluence of two formidable classes of problems. We design a novel algorithm for this class of problems, and also explore specialized approaches for two related real-world applications. Although a number of algorithms have been developed to solve two-stage SMIPs, most of them deal with problems containing purely integer or continuous variables in either or both of the two stages, and frequently require the technology and/or recourse matrices to be deterministic. As a ground-breaking effort, in this work, we address the challenging class of two-stage SMIPs that involve 0-1 mixed-integer variables in both stages. The only earlier work on solving such problems (Carøe and Schultz (1999)) requires the optimization of several non-smooth Lagrangian dual problems using subgradient methods in the bounding process, which turns out to be computationally very expensive. We begin with proposing a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having 0-1 mixed-integer variables in both stages. Since the second-stage problems contain binary variables, their value functions are in general nonconvex and discontinuous; hence, the classical Benders' decomposition approach (or the L-shaped method) for solving two-stage stochastic programs, which requires convex subproblem value functions, cannot be directly applied. This motivates us to relax the second-stage problems and accompany this relaxation with a convexification process. To make this process computationally efficient, we propose to construct a certain partial convex hull representation of the two-stage solution space, using the relaxed second-stage constraints and the restrictions confining the first-stage variables to lie within some hyperrectangle. This partial convex hull is sequentially generated using a convexification scheme, such as the Reformulation-Linearization Technique (RLT), which yields valid inequalities that are functions of the first-stage variables and, of noteworthy importance, are reusable in the subsequent subproblems by updating the values of the first-stage variables. Meanwhile, since the first stage contains continuous variables, whenever we tentatively fix these variables at some given feasible values, the resulting constraints may not be facial with respect to the associated bounding constraints that are used to construct the partial convex hull. As a result, the constructed Benders' subproblems define lower bounds for the second-stage value functions, and likewise, the resulting Benders' master problem provides a lower bound for the original stochastic program defined over the same hyperrectangle. Another difficulty resulting from continuous first-stage variables is that when the given first-stage solution is not extremal with respect to its bounds, the second-stage solution obtained for a Benders' subproblem defined with respect to a partial convex hull representation in the two-stage space may not satisfy the model's binary restrictions. We thus need to be able to detect whether or not a Benders' subproblem is solved by a given fractional second-stage solution. We design a novel procedure to check this situation in the overall algorithmic scheme. A key property established, which ensures global convergence, is that these lower bounds become exact if the given first-stage solution is a vertex of the defining hyperrectangle, or if the second-stage solution satisfies the binary restrictions. Based on these algorithmic constructs, we design a branch-and-bound procedure where the branching process performs a hyperrectangular partitioning of the projected space of the first-stage variables, and lower bounds for the nodal problems are computed by applying the proposed modified Benders' decomposition method. We prove that, when using the least-lower-bound node-selection rule, this algorithm converges to a global optimal solution. We also show that the derived RLT cuts are not only reusable in subsequent Benders iterations at the same node, but are also inheritable by the subproblems of the children nodes. Likewise, the Benders' cuts derived for a given sub-hyperrectangle can also be inherited by the lower bounding master programs solved for its children nodes. Using these cut inheritance properties results in significant savings in the overall computational effort. Some numerical examples and computational results are presented to demonstrate the efficacy of this approach. The sizes of the deterministic equivalent of our test problems range from having 386 continuous variables, 386 binary variables, and 386 constraints, up to 1795 continuous variables, 1539 binary variables, and 1028 constraints. The results reveal an average savings in computational effort by a factor of 9.5 in comparison with using a commercial mixed-integer programming package (CPLEX 8.1) on a deterministic equivalent formulation. We then explore an important application of SMIP to enhance the traditional airline fleet assignment models (FAM). Given a flight schedule network, the fleet assignment problem solved by airline companies is concerned with assigning aircraft to flight legs in order to maximize profit with respect to captured path- or itinerary-based demand. Because certain related crew scheduling regulations require early information regarding the type of aircraft serving each flight leg, the current practice adopted by airlines is to solve the fleet assignment problem using estimated demand data 10-12 weeks in advance of departure. Given the level of uncertainty, deterministic models at this early stage are inadequate to obtain a good match of aircraft capacity with passenger demands, and revisions to the initial fleet assignment become naturally pertinent when the observed demand differs considerably from the assigned aircraft capacities. From this viewpoint, the initial decision should embrace various market scenarios so that it incorporates a sufficient look-ahead feature and provides sufficient flexibility for the subsequent re-fleeting processes to accommodate the inevitable demand fluctuations. With this motivation, we propose a two-stage stochastic programming approach in which the first stage is concerned with the initial fleet assignment decisions and, unlike the traditional deterministic methodology, focuses on making only a family-level assignment to each flight leg. The second stage subsequently performs the detailed assignments of fleet types within the allotted family to each leg under each of the multiple potential scenarios that address corresponding path- or itinerary-based demands. In this fashion, the initial decision of what aircraft family should serve each flight leg accomplishes the purpose of facilitating the necessary crew scheduling decisions, while judiciously examining the outcome of future re-fleeting actions based on different possible demand scenarios. Hence, when the actual re-fleeting process is enacted several weeks later, this anticipatory initial family-level assignment will hopefully provide an improved overall fleet type re-allocation that better matches demand. This two-stage stochastic model is complemented with a secondary model that performs adjustments within each family, if necessary, to provide a consistent fleet type-assignment information for accompanying decision processes, such as yield management. We also propose several enhanced fleet assignment models, including a robust optimization model that controls decision variation among scenarios and a stochastic programming model that considers the recapture effect of spilled demand. In addition to the above modeling concepts and framework, we also contribute in developing effective solution approaches for the proposed model, which is a large-scale two-stage stochastic 0-1 mixed-integer program. Because the most pertinent information needed from the initial fleet assignment is at the family level, and the type-level assignment is subject to change at the re-fleeting stage according to future demand realizations, our solution approach focuses on assigning aircraft families to the different legs in the flight network at the first stage, while finding relaxed second-stage solutions under different demand scenarios. Based on a polyhedral study of a subsystem extracted from the original model, we derive certain higher-dimensional convex hull as well as partial convex hull representations for this subsystem. Accordingly, we propose two variants for the primary model, both of which relax the binary restrictions on the second-stage variables, but where the second variant then also accommodates the partial convex hull representations, yielding a tighter, albeit larger, relaxation. For each variant, we design a suitable solution approach predicated on Benders' decomposition methodology. Using certain realistic large-scale flight network test problems having 900 flight legs and 1,814 paths, as obtained from United Airlines, the proposed stochastic modeling approach was demonstrated to increase daily expected profits by about 3% (which translates to about $160 million per year) in comparison with the traditional deterministic model in present usage, which considers only the expected demand. Only 1.6% of the second-stage binary variables turn out to be fractional in the first variant, and this number is further reduced to 1.2% by using the tighter variant. Furthermore, when attempting to solve the deterministic equivalent formulation for these two variants using a commercial mixed-integer programming package (CPLEX 8.1), both the corresponding runs were terminated after reaching a 25-hour cpu time limit. At termination, the software was still processing the initial LP relaxation at the root node for each of these runs, and no feasible basis was found. Using the proposed algorithms, on the other hand, the solution times were significantly reduced to 5 and 19 hours for the two variants, respectively. Considering that the fleet assignment models are solved around three months in advance of departure, this solution time is well acceptable at this early planning stage, and the improved quality in the solution produced by considering the stochasticity in the system is indeed highly desirable. Finally, we address another practical workforce planning problem encountered by a global financial firm that seeks to manage multi-category workforce for functional areas located at different service centers, each having office-space and recruitment-capacity constraints. The workforce demand fluctuates over time due to market uncertainty and dynamic project requirements. To hedge against the demand fluctuations and the inherent uncertainty, we propose a two-stage stochastic programming model where the first stage makes personnel recruiting and allocation decisions, while the second stage, based on the given personnel decision and realized workforce demand, decides on the project implementation assignment. The second stage of the proposed model contains binary variables that are used to compute and also limit the number of changes to the original plan. Since these variables are concerned with only one quality aspect of the resulting workforce plan and do not affect feasibility issues, we replace these binary variables with certain conservative policies regarding workforce assignment change restrictions in order to obtain more manageable subproblems that contain purely continuous variables. Numerical experiments reveal that the stochastic programming approach results in significantly fewer alterations to the original workforce plan. When using a commercial linear programming package CPLEX 9.0 to solve the deterministic equivalent form directly, except for a few small-sized problems, this software failed to produce solutions due to memory limitations, while the proposed Benders' decomposition-based solution approach consistently solved all the practical-sized test problems with reasonable effort. To summarize, this dissertation provides a significant advancement in the algorithmic development for solving two-stage stochastic mixed-integer programs having 0-1 mixed-integer variables in both stages, as well as in its application to two important contemporary real-world applications. The framework for the proposed solution approaches is to formulate tighter relaxations via partial convex hull representations and to exploit the resulting structure using suitable decomposition methods. As decision robustness is becoming increasingly relevant from an economic viewpoint, and as computer technological advances provide decision-makers the ability to explore a wide variety of scenarios, we hope that the proposed algorithms will have a notable positive impact on solving stochastic mixed-integer programs. In particular, the proposed stochastic programming airline fleet assignment and the workforce planning approaches studied herein are well-poised to enhance the profitability and robustness of decisions made in the related industries, and we hope that similar improvements are adapted by more industries where decisions need to be made in the light of data that is shrouded by uncertainty. / Ph. D.

This paper presents a method that uses designed experiments and statistical models to extract information about how solver parameter settings perform for classes of mixed integer programs. The use of experimental design facilitates fitting a model that describes the response surface across all combinations of parameter settings, even those not explicitly tested, allowing identification of both desirable and poor settings. Identifying parameter settings that give the best expected performance for a specific class of instances and a specific solver can be used to more efficiently solve a large set of similar instances, or to ensure solvers are being compared at their best.

Effective aeromedical evacuation of casualties is one of the most important problems in military medical systems because high-priority casualties will not survive without timely medical care. The decision making process for aeromedical evacuation consists of the following components: (1) identifying which aeromedical evacuation asset (see figure 1) to dispatch to the casualty, (2) locating aeromedical evacuation assets strategically in anticipation of incoming demand, and (3) deciding which medical treatment facility to transport the casualty. These decisions are further complicated because prioritization of casualties is based on severity of injury while aeromedical evacuation assets and medical treatment facilities operate with varying capabilities. In this dissertation, discrete optimization models are developed to examine dispatch, delivery, and location logistics for the effective aeromedical evacuation of casualties in military medical systems.

Scheduling refinery operation promises a big cut in logistics cost, maximizes efficiency, organizes allocation of material and resources, and ensures that production meets targets set by planning team. Obtaining accurate and reliable schedules for execution in refinery plants under different scenarios has been a serious challenge. This research was undertaken with the aim to develop robust methodologies and solution procedures to address refinery scheduling problems with uncertainties in process parameters. The research goal was achieved by first developing a methodology for short-term crude oil unloading and transfer, as an extension to a scheduling model reported by Lee et al. (1996). The extended model considers real life technical issues not captured in the original model and has shown to be more reliable through case studies. Uncertainties due to disruptive events and low inventory at the end of scheduling horizon were addressed. With the extended model, crude oil scheduling problem was formulated under receding horizon control framework to address demand uncertainty. This work proposed a strategy called fixed end horizon whose efficiency in terms of performance was investigated and found out to be better in comparison with an existing approach. In the main refinery production area, a novel scheduling model was developed. A large scale refinery problem was used as a case study to test the model with scheduling horizon discretized into a number of time periods of variable length. An equivalent formulation with equal interval lengths was also presented and compared with the variable length formulation. The results obtained clearly show the advantage of using variable timing. A methodology under self-optimizing control (SOC) framework was then developed to address uncertainty in problems involving mixed integer formulation. Through case study and scenarios, the approach has proven to be efficient in dealing with uncertainty in crude oil composition.

Nesta tese é realizado um estudo de caso em uma indústria química brasileira, no qual busca-se representar características da tomada de decisões para a programação da produção em plantas de bateladas. Para isso, foi proposto um modelo matemático do tipo MIP (Mixed Integer Programming) que considerou a disponibilidade de matérias-primas, múltiplas tarefas produtivas para um mesmo produto, tanques de armazenamento multiproduto, envase de produtos e demanda de produtos a granel e envasados. O objetivo principal desse estudo era permitir a obtenção de soluções compatíveis com a prática da empresa em tempo de processamento viável. A partir desse estudo de caso, foi efetuado um segundo estudo com objetivo de avaliar o desempenho de formulações matemáticas para a resolução de um problema de programação da produção. Foram considerados modelos clássicos das comunidades científicas de pesquisa operacional e de engenharia de sistemas de processo, além de um terceiro modelo desenvolvido a partir de conceitos dessas duas comunidades. Algumas características do estudo de caso não foram retratadas, como o consumo de matérias-primas e o envase dos produtos, porém, foram consideradas duas características comumente observadas em problemas da indústria de processos: bateladas com quantidade produzida flexível e tarefas que produzem mais de um produto. Por fim, um terceiro estudo foi realizado com base no estudo de caso da indústria química brasileira, porém, com um foco decisões mais próximas ao nível tático. Sendo assim, foi considerado apenas o dimensionamento de lotes, sem o sequenciamento da produção. Por outro lado, foram acrescentadas características pertinentes à aquisição de matérias-primas, como custos das matérias-primas e descontos por quantidade adquirida. O objetivo deste último trabalho era avaliar a influência da integração das decisões de dimensionamento de lotes e de aquisição das matérias-primas nos custos da cadeia produtiva durante todo o horizonte de planejamento. / In this thesis we developed a study case in a Brazilian chemical industry, in which the aim was to represent the characteristics of decision-making for production scheduling in batch plants. For this, a mixed integer programming model was proposed to consider the availability of raw materials, multiple productive tasks for the same product, multi-product storage tanks, product packaging and demand for products in bulk and packaged. The main objective of this study was develop a model that is able to obtain solutions that clould be used in practice for this chemical industry in viable processing time. From this study case, a second work was carried out to evaluate the performance of mathematical formulations to solve a problem of production scheduling. Classic models of operational research and process system engineering communities were considered, and a third model was developed from concepts of these two communities. Some features of the case study were not modelled, such as the consumption of raw materials and the product packaging, however, two characteristics usually present in process industries were considered: flexible batch production quantity and multi-product task production. Finally, a third study developed based on the study case of the Brazilian chemical industry, but with focus on decisions more familiar to the tactical level. Thus, only lot sizing was modelled, without production scheduling. On the other hand, features relevant raw material purchasing were included, such as raw material costs and discounts for quantity purchased. The objective of this last work was to evaluate the influence of integrating lot sizing decisions and raw material purchasing decisions in the overall costs of the production chain during the entire planning horizon.