Doctoral Dissertations
Date of Award
8-1990
Degree Type
Dissertation
Degree Name
Doctor of Philosophy
Major
Geography
Major Professor
Bruce A. Ralston
Committee Members
Thomas L. Bell, Sidney J. Jumper, Charles E. Noon
Abstract
The problem described in this dissertation is the Flow-Resource Facility Location Problem (FRFLP). The FRFLP is the problem of determining a minimum cost distribution of flow-resource facilities at the vertices of a network, and of simultaneously determining a set of paths in the network such that a maximum amount of commodities or services can be moved from a set of origins to a set of destinations. Unlike conventional facility location models, the facilities of the FRFLP are neither origins nor destinations for commodities or services moving over the network. Rather, the flow-resource facilities are located at intermediate vertices along the paths between origin and destination pairs. For a particular route to be feasible, flow-resource facilities are required at the intermediate vertices. An example of a flow-resource facility is an aircraft refueler at an airbase. Any vertex could be both origin and a destination as well as a feasible location for flow-resource facilities. The solution to the FRFLP is a distribution of flow-resource facilities at the vertices of the network and a set of paths between the origins and destinations. A flow-resource facility in this problem is a type of facility which is used to control the loss of flow-volume between origins and destinations in the network. Typically, flow-resource facilities are used in systems where the volume of commodities or services that can be moved directly between any two vertices decreases with increasing distance. A trade-off can then be made between the distance moved and the amount of commodities or services that can be taken. Aircraft, for example, can trade-off fuel for cargo and cargo for fuel. The flow-volume for a given route is, thus, determined by the length of the longest arc traversed. Aircraft can decrease the maximum length arc of a given trip by diverting to an enroute airbase to refuel, thus, decreasing the maximum weight of fuel required for the longest arc on the route. In this dissertation, the FRFLP is formulated as a Mixed Integer Programming problem (MIP). The size of the MIP for the FRFLP is shown to be combinatorial with respect to the number of vertices in the network. To this end two specialized algorithms are proposed for solving the FRFLP. The first algorithm is based on a mathematical programming technique termed column generation which allows the FRFLP to be decomposed into a facility location problem and a routing problem submodel. The original statement of the column generation algorithm is modified into a heuristic procedure designed to solve the FRFLP by utilizing a system of surrogate costs which are used to approximate the dual costs from the optimal solution to the restricted master problem. The column generation submodel is solved using a specialized network heuristic designed to constract routes between origin-destinations pairs. The restricted master problem of the first algorithm is solved using conventional methods. The second algorithm expands on the first algorithm by utilizing a specialized heuristic to solve the facility location problem. A two-stage heuristic is illustrated which is designed to solve the restricted master problem faster and more efficiently than by conventional means. Algorithm II is applied to a real-world problem which consists of locating aircraft refuelers for a military transportation operation. The solution generated by Algorithm II is shown to be within 1.13% of the optimal solution. This problem is based on a realistic data set supplied by the United States Military Airlift Command.
Recommended Citation
Ray, Julian J., "The flow-resource facility location problem. " PhD diss., University of Tennessee, 1990.
https://trace.tennessee.edu/utk_graddiss/11485
