The identification of the distribution of air passengers among airports is an important task of the airport planner. It would be useful to understand how trip makers choose among competing airports. The ultimate purpose of this study is to research into , passengers' choice of airport so that the airport system can be planned on a more reliable basis. The choice of airport of passengers originating from central England in 1975 is explained by constructing multinomial disaggregate behavioural models of logit form. The data used for model calibration, were collected during two Civil Aviation Authority surveys. This work makes contribution to: -The definition of the major determinants of airport choice, -The responsiveness of passengers, choice to changes in these determinants, - The policy implications for the regional airports - The transferability of the model in time and space. The method of analysis has been selected after outlining the potential advantages and shortcomings of logit and probit models and after a test on the validity of the Independence from Irrelevant Alternatives (I.I.A.) property has been carried out. The results show that the multinomial logit model used for the airport choice is good in terms of its explanatory ability and successful in predicting the choices actually made. Travel time to the airport, frequency of flights and air fare are found to be decisive factors for a passenger to select a given airport but are not of equal importance. By influencing-these factors, it appears that there exists room for the transport planner to shift traffic from one airport to another to have an economically and/or environmentally efficient airport system. In their original form, the models have been tested and found not to be transferable to the London area in 1978. However, after a Bayesian updating procedure was applied, the business and inclusive tours models were transferable. The leisure model was not statistically transferable but had a good predictive ability while the domestic model was not transferable. Finally, subsequent directions ·for further research are outlined.

We consider how the optimal decision can be made if the optimality criterion of maximizing profit changes to that of maximizing return on investment for the general uncapacitated facility location problem. We show that the inherent structure of the proposed model can be exploited to make a significant computational reduction.

The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

We introduce two online models for the vertex k-center and the vertex k-median problems. Clients (i.e., graph vertices) and their corresponding links (i.e., graph edges) are revealed sequentially, determining the topology of a graph over time. Clients are revealed by an adversary to an online algorithm that selects existing graph vertices on which to open facilities; once open, a facility cannot be removed or relocated. We define two models: an online algorithm may be restricted to open a facility only at the location of the most recent client or at the location of any existing client. We examine these models on three classes of graphs under two types of adversaries. We establish lower bounds on the respective competitive ratios attainable by any online algorithm for each combination of model, adversary, and graph class. Finally, we describe algorithms whose competitive ratios provide corresponding upper bounds on the best competitive ratios achievable.

In this thesis, we generalize a set of facility location models within a two-stage robust optimization framework by assuming each demand is only known to lie within a continuous and bounded uncertainty region. Our approach involves discretizing each uncertainty region into a set of finite scenarios, each of which represents a potential location where the demand may be realized. We show that the gap between the optimal values of the theorized continuous uncertainty problem and our discretized model can be bounded by a function of the granularity of the discretization. We then propose a solution technique based on row-and-column generation, and compare its performance with existing solution methods. Lastly, we apply our robust location models to the problem of ambulance positioning using cardiac arrest location data from the City of Toronto, and show that hedging against demand location uncertainty may help decrease EMS response times to cardiac arrest emergencies.

In this thesis, we generalize a set of facility location models within a two-stage robust optimization framework by assuming each demand is only known to lie within a continuous and bounded uncertainty region. Our approach involves discretizing each uncertainty region into a set of finite scenarios, each of which represents a potential location where the demand may be realized. We show that the gap between the optimal values of the theorized continuous uncertainty problem and our discretized model can be bounded by a function of the granularity of the discretization. We then propose a solution technique based on row-and-column generation, and compare its performance with existing solution methods. Lastly, we apply our robust location models to the problem of ambulance positioning using cardiac arrest location data from the City of Toronto, and show that hedging against demand location uncertainty may help decrease EMS response times to cardiac arrest emergencies.

We introduce two online models for the vertex k-center and the vertex k-median problems. Clients (i.e., graph vertices) and their corresponding links (i.e., graph edges) are revealed sequentially, determining the topology of a graph over time. Clients are revealed by an adversary to an online algorithm that selects existing graph vertices on which to open facilities; once open, a facility cannot be removed or relocated. We define two models: an online algorithm may be restricted to open a facility only at the location of the most recent client or at the location of any existing client. We examine these models on three classes of graphs under two types of adversaries. We establish lower bounds on the respective competitive ratios attainable by any online algorithm for each combination of model, adversary, and graph class. Finally, we describe algorithms whose competitive ratios provide corresponding upper bounds on the best competitive ratios achievable.

The views expressed in this thesis are those of the author and do not reflect the official policy or position of the Department of Defense or the U.S. Government. / Determining the best base stationing for military units can be modeled as a capacitated facility location problem with sole sourcing and multiple resource categories. Computational experience suggests that cross decomposition, a unification of Benders Decomposition and Lagrangean relaxation, is superior to other contemporary methods for solving capacitated facility location problems. Recent research extends cross decomposition to pure integer prograrnming problems with explicit application to capacitated facility location problems with sole sourcing; however, this research offers no computational experience. This thesis implements two cross decomposition algorithms for the capacitated facility location problem with sole sourcing and compares these decomposition algorithms with branch and bound methods. For some problems tested, cross decomposition obtains better solutions in less time; however, cross decomposition does not always perform better man branch and bound due to the time required to obtain the cross decomposition bound that is theoretically superior to other decomposition bounds.

The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

No description available.