 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 UBC Theses and Dissertations /
 Algorithm for estimating the medians of a weighted...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Algorithm for estimating the medians of a weighted graph subject to side constraints, and an application to rural hospital locations in British Columbia Whitaker, Roy Alexander
Abstract
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) reiterate 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 locationallocation 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.
Item Metadata
Title 
Algorithm for estimating the medians of a weighted graph subject to side constraints, and an application to rural hospital locations in British Columbia

Creator  
Publisher 
University of British Columbia

Date Issued 
1971

Description 
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) reiterate 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 locationallocation 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.

Genre  
Type  
Language 
eng

Date Available 
20110429

Provider 
Vancouver : University of British Columbia Library

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

DOI 
10.14288/1.0101893

URI  
Degree  
Program  
Affiliation  
Degree Grantor 
University of British Columbia

Campus  
Scholarly Level 
Graduate

Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.