Open Collections

Algorithm for estimating the medians of a weighted graph subject to side constraints, and an application to rural hospital locations in British Columbia

University of British Columbia

Plant location as a centralized planning objective in which some agency has control over most of the system elements can be reduced, in many circumstances, to the problem of finding the medians of a weighted graph. This concept is feasible if it can be assumed that each location sought is constrained to a subset of p nodes on an n node network. This combinatorial programming problem can be formally stated as follows: if G is a weighted graph, [formula omitted] the weighted distance of node [symbol omitted] to node [symbol omitted], and Xp is any set of p nodes on G (x₁, x₂, •••,Xp), then the required set of p nodes Xp∗ on G is the p median of the graph if it satisfies the expression [formula omitted]. Although this objective can be explicitly optimized by branch bound algorithms, those developed to date can become computationally infeasible for some large scale problems. A fast method for estimating the medians of a weighted graph is given which will provide optimal or near optimal solutions on any type of network. The heuristic procedures adopted in this study can be generalized in terms of three basic steps; 1) partition the graph to obtain an initial feasible solution, 2) re-iterate over; step 1 to achieve a local minimum, and 3) perturb this convergence to test for a lower bound. The design of steps 1 and 3 are crucial to the success of the algorithmic method. Two procedures are given for the basic partitioning of the graph, one of which is a modification of a criterion originally developed by Singer (1968) . The other method introduces a node elimination recursion which appears, experimentally, to be the more efficient procedure for certain types of weighted networks. Efficient perturbation methods are developed for testing the lower bounds obtained. The basic model structure is modified by the introduction of heuristics for the constrained plant location problem under a wide variety of restrictions. Numerical procedures are suggested for restricting the search to a subset of m potential plant sites among all n nodes on the network. Heuristics are developed for forcing certain locations into solution, for placing upper bound constraints on plant sizes, and for restricting the maximum link distance over which a particular allocation might be made. Attention is given to the problem of estimating the joint minimization of plant and transportation cost functions over a network surface. For dynamic location-allocation systems an explicit dynamic programming formulation is developed for the optimal sequencing of plant locations over time subject, if necessary, to periodic variations in all cost functions and node weights. An application of the basic median algorithm to the problem of rural hospital locations in Southeast British Columbia is demonstrated, and computer codes are listed for all the specified models.

Text

2011-04-29

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/34175

Geography

University of British Columbia

Graduate