Incorporating congestion in preventive healthcare facility network design

Preventive healthcare aims at reducing the likelihood and severity of potentially life-threatening illnesses by protection and early detection. The level of participation to preventive healthcare programs is a crucial factor in terms of their effectiveness and efficiency. This paper provides a methodology for designing a network of preventive healthcare facilities so as to maximize participation. The number of facilities to be established and the location of each facility are the main determinants of the configuration of a healthcare facility network. We use the total (travel, waiting and service) time required for receiving the preventive service as a proxy for accessibility of a healthcare facility, and assume that each client would seek the services of the facility with minimum expected total time. At each facility, which we model as an M/M/1 queue so as to capture the level of congestion, the expected number of participants from each population zone decreases with the expected total time. In order to ensure service quality, the facilities cannot be operated unless their level of activity exceeds a minimum workload requirement. The arising mathematical formulation is highly nonlinear, and hence we provide a heuristic solution framework for this problem. Four heuristics are compared in terms of accuracy and computational requirements. The most efficient heuristic is utilized in solving a real life problem that involves the breast cancer screening center network in Montreal. In the context of this case, we found out that centralizing the total system capacity at the locations preferred by clients is a more effective strategy than decentralization by the use of a larger number of smaller facilities. We also show that the proposed methodology can be used in making the investment trade-off between expanding the total system capacity and changing the behavior of potential clients toward preventive healthcare programs by advertisement and education.     

Extensive facility location problems on networks with equity measures

This paper deals with the problem of locating path-shaped facilities of unrestricted length on networks. We consider as objective functions measures conceptually related to the variability of the distribution of the distances from the demand points to a facility. We study the following problems: locating a path which minimizes the range, that is, the difference between the maximum and the minimum distance from the vertices of the network to a facility, and locating a path which minimizes a convex combination of the maximum and the minimum distance from the vertices of the network to a facility, also known in decision theory as the Hurwicz criterion. We show that these problems are NP-hard on general networks. For the discrete versions of these problems on trees, we provide a linear time algorithm for each objective function, and we show how our analysis can be extended also to the continuous case.     

Linear facility location — Solving extensions of the basic problem

The basic problem is to locate a linear facility to minimize the sume of weighted shortest Euclidean distances from demand points to the facility. We extend the analysis to locating a constrained linear facility, a radial facility, a linear facility where distances are rectangular and a linear facility under the minimax criterion. Each case is shown to admit a simple solution technique.     

Locating semi-obnoxious facilities with expropriation: minisum criterion

This paper considers the problem of locating semi-obnoxious facilities assuming that demand points within a certain distance from an open facility are expropriated at a given price. The objective is to locate the facilities so as to minimize the total weighted transportation cost and expropriation cost. Models are developed for both single and multiple facilities. For the case of locating a single facility, finite dominating sets are determined for the problems on a plane and on a network. An efficient algorithm is developed for the problem on a network. For the case of locating multiple facilities, a branch-and-bound procedure using Lagrangian relaxation is proposed and its efficiency is tested with computational experiments.     

The single facility location problem with time-dependent weights and relocation cost over a continuous time horizon

In this study, we investigate the problem of locating a facility in continuous space when the weight of each existing facility is a known linear function of time. The location of the new facility can be changed once over a continuous finite time horizon. Rectilinear distance and time- and location-dependent relocation costs are considered. The objective is to determine the optimal relocation time and locations of the new facility before and after relocation to minimize the total location and relocation costs. We also propose an exact algorithm to solve the problem in a polynomial time according to our computational results.     

The rectilinear distance Weber problem in the presence of a probabilistic line barrier

This paper considers the problem of locating a single facility in the presence of a line barrier that occurs randomly on a given horizontal route on the plane. The objective is to locate this new facility such that the sum of the expected rectilinear distances from the facility to the demand points in the presence of the probabilistic barrier is minimized. Some properties of the problem are reported, a solution algorithm is provided with an example problem, and some future extensions to the problem are discussed.     

Optimal Positioning of a Mobile Service Unit on a Line

In this paper we address the problem of locating a mobile response unit when demand is distributed according to a random variable on a line. Properties are proven which reduce the problem to locating a non-mobile facility, transforming the original optimization problem into an one-dimensional convex program.In the special case of a discrete demand (a simple probability measure), an algorithm which runs in expected linear time is proposed.     

竞争环境下截流设施选址问题

研究企业新建设施时,市场上已有设施存在的情况下,使本企业总体利润最大的截流设施选址问题。在一般截留设施选址模型的基础上引入引力模型,消费者到某个设施接受服务的概率与偏离距离及设施的吸引力相关,同时设施的建设费用与设施吸引力正相关,建立非线性整数规划模型并使用贪婪算法进行求解。数值分析表明,该算法求解速度快,模型计算精度较高。     

Facility location for large-scale emergencies

In the p-center problem, it is assumed that the facility located at a node responds to demands originating from the node. This assumption is suitable for emergency and health care services. However, it is not valid for large-scale emergencies where most of facilities in a whole city may become functionless. Consequently, residents in some areas cannot rely on their nearest facilities. These observations lead to the development of a variation of the p-center problem with an additional assumption that the facility at a node fails to respond to demands from the node. We use dynamic programming approach for the location on a path network and further develop an efficient algorithm for optimal locations on a general network.     

On the collection depots location problem

In this paper we investigate the problem of locating a new facility servicing a set of demand points. A given set of collection depots is also given. When service is required by a demand point, the server travels from the facility to the demand point, then from the demand point to one of the collection depots (which provides the shortest route back to the facility), and back to the facility. The problem is analyzed and properties of the solution point are formulated and proved. Computational results on randomly generated problems are reported.     

Location Among Regions with Varying Norms

This paper investigates a new variation in the continuous single facility location problem. Specifically, we address the problem of locating a new facility on a plane with different distance norms on different sides of a boundary line. Special cases and extensions of the problem, where there are more than two regions are also discussed. Finally, by investigating the properties of the models, efficient solution procedures are proposed.     

A Procedure for Locating Emergency-Service Facilities for All Possible Response Distances

The problem of locating emergency-service facilities involves the assignment of a set of demand points to a set of facilities. One way to formulate the problem is to minimize the number of required facilities, given that the maximum distance between the demand points and their nearest facility does not exceed some specified value. We present a procedure for determining the numbers of such facilities for all possible values of the maximum distance. Computational results are presented for a microcomputer implementation.     

A heuristic for direct consumer participation in primary health care planning

Recent attempts at consumer participation in the health care planning process have proved weak in their ability to responsively account for consumer health welfare. This can be attributed, in large part, to the mechanisms employed for identifying and utilizing the consumer's health care views and preferences. A heuristic planning procedure designed to overcome these problems by directly incorporating consumer preferences is developed. It identifies that (primary) health care delivery system which maximizes total incremental health benefit to a community subject to a prespecified budget constraint. The model assumes a methodology (previously developed by the author) for measuring, in aggregable units, the benefit, B_ip, from some health care facility p as perceived by some consumer i. Application of the procedure and subsequent sensitivity analyses demonstrate its ability to generate valid solutions that are robust to disturbances in the planning system.     

An efficient algorithm for facility location in the presence of forbidden regions

This paper investigates a constrained form of the classical Weber problem. Specifically, we consider the problem of locating a new facility in the presence of convex polygonal forbidden regions such that the sum of the weighted distances from the new facility to n existing facilities is minimized. It is assumed that a forbidden region is an area in the plane where travel and facility location are not permitted and that distance is measured using the Euclidean-distance metric. A solution procedure for this nonconvex programming problem is presented. It is shown that by iteratively solving a series of unconstrained problems, this procedure terminates at a local optimum to the original constrained problem. Numerical examples are presented.     

A Linear Programming Approach to the Solution of Constrained Multi-Facility Minimax Location Problems where Distances are Rectangular

The problem of locating new facilities with respect to existing facilities is stated as a linear programming problem where inter-facility distances are assumed to be rectangular. The criterion of location is the minimization of the maximum weighted rectangular distance in the system. Linear constraints which (a) limit the new facility locations and (b) enforce upper bounds on the distances between new and existing facilities and between new facilities can be included. The dual programming problem is formulated in order to provide for an efficient solution procedure. It is shown that the duLal variables provide information abouLt the complete range of new facility locations which satisfy the minimax criterion.     

Upper bounds for objective functions of discrete competitive facility location problems

Under study is the problem of locating facilities when two competing companies successively open their facilities. Each client chooses an open facility according to his own preferences and return interests to the leader firm or to the follower firm. The problem is to locate the leader firm so as to realize the maximum profit (gain) subject to the responses of the follower company and the available preferences of clients. We give some formulations of the problems under consideration in the form of two-level integer linear programming problems and, equivalently, as pseudo-Boolean two-level programming problems. We suggest a method of constructing some upper bounds for the objective functions of the competitive facility location problems. Our algorithm consists in constructing an auxiliary pseudo-Boolean function, which we call an estimation function, and finding the minimum value of this function. For the special case of the competitive facility location problems on paths, we give polynomial-time algorithms for finding optimal solutions. Some results of computational experiments allow us to estimate the accuracy of calculating the upper bounds for the competitive location problems on paths.     

Global Optimization of 0-1 Hyperbolic Programs

We develop eight different mixed-integer convex programming reformulations of 0-1 hyperbolic programs. We obtain analytical results on the relative tightness of these formulations and propose a branch and bound algorithm for 0-1 hyperbolic programs. The main feature of the algorithm is that it reformulates the problem at every node of the search tree. We demonstrate that this algorithm has a superior convergence behavior than directly solving the relaxation derived at the root node. The algorithm is used to solve a discrete p-choice facility location problem for locating ten restaurants in the city of Edmonton.The research was supported in part by NSF awards DMII 95-02722 and BES 98-73586 to NVS.     

Determining an optimum location for an undesirable facility in a workroom environment

This paper deals with the problem of placing an undesirable but necessary piece of equipment, process or facility into a working environment. Locating a piece of equipment that produces contaminants or creates stresses for nearby workers, placing a storage facility for flammable materials or locating hazardous waste in the workroom environment, are all typical examples of the undesirable facility location problem. The degree of undesirability between an existing facility or worker and the new undesirable entity is reflected through a weighting factor. The problem is formally defined to be the selection of a location within the convex region that maximizes the minimum weighted Euclidean distance with respect to all existing facilities. A ‘Maximin’ model is formulated and two solution procedures introduced. A geometrical approach and an algorithmic approach are described in detail. An example is provided for each solution procedure and the computational efficiency of the algorithm is discussed and illustrated.     

A fractional model for locating semi-desirable facilities on networks

In this paper, we address the problem of locating a series of facilities on a network maximizing the average distance to population centers (assumed to be distributed in the plane) per unit transportation cost (a function of the network distances to users). A finite dominating set is constructed, allowing the resolution of the problem by standard integer programming techniques. We also discuss some extensions of the model (including, in particular, the Weber problem with attraction and repulsion in networks), for which (ε-) dominating sets are derived.