Abstract We study two p‐center models on a network with probabilistic demand weights. In the first, which is called the maximum probability p‐center problem, the objective is to maximize the probability that the maximum demand‐weighted distance between the demand and the open facilities does not exceed a given threshold value. In the second, referred to as the β‐VaR p‐center problem, the objective is to minimize the value‐at‐risk of the maximum demand‐weighted distance with a pre‐selected confidence level. It is shown that both models are NP‐hard. We develop algorithms for solving the two models and conduct computational experiments to compare their performance. We recommend that the branch and bound algorithm be applied to solve the first model, and an ensemble optimization method to solve the second model. The solution approaches presented can be easily extended to the case where the random demand weights are not independent.

Abstract We consider the problem of locating facilities of two types at nodesof a tree network. Customers may need just one type of service, or bothtypes; in the latter case, to minimize transportation costs, the customers visit facilities of both types in a single trip. Each facility incurs a fixed cost that depends on the type of the facility and the node where it is located. It is required to minimize the sum of the total transportation and fixed costs. For the problem with a single facility of each type, we present an O( n) exact algorithm, which improves on the algorithm presented in [2]. For the problem with multiple facilities of each type, we present an algorithm. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 154–159 2014

In this article, we consider the cooperative maximum covering location problem on a network. In this model, it is assumed that each facility emits a certain “signal” whose strength decays over distance according to some “signal strength function.” A demand point is covered if the total signal transmitted from all the facilities exceeds a predefined threshold. The problem is to locate facilities so as to maximize the total demand covered. For the 2‐facility problem, we present efficient polynomial algorithms for the cases of linear and piecewise linear signal strength functions. For the p‐facility problem, we develop a finite dominant set, a mixed‐integer programming formulation that can be used for small instances, and two heuristics that can be used for large instances. The heuristics use the exact algorithm for the 2‐facility case. We report results of computational experiments. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 334–349 2014

Abstract In this article, we propose a global optimization technique (Big Segment Small Segment) for solving single facility location problems on a network when the location of the facility can either at nodes or along the links of the network. Some multiple facility location problems can be solved by recursively solving single facility problems. The technique is tested on five problems: the mixed weights 1‐median problem where the weights are a mix of positive and negative values, the obnoxious facility location problem assuming that the nuisance function declines by the square of the distance, the competitive facility location problem using the gravity model, and minimizing cover by locating two facilities while requiring a minimum distance between them. Computational experiments provided excellent results. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 1–11 2011

Abstract This paper investigates the 1‐minimax and 1‐maximin problems when demand weights are random variables with general continuous probability distributions. Properties of the optimal solutions are presented and solution procedures are developed. We also identify some known probability distributions under which it is easier to search for an optimal solution. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 127–135 2007

This paper deals with estimating performance measures, such as average response time for spatially distributed networks. Demands are generated stochastically at the nodes and the service units are stationed at service centers when available. Whenever a call arrives, a service unit will travel to the call's location. When there are no available servers, the call will enter an infinite capacity queue at that node. The service units will travel from node to node serving the calls and return to the service center only when there are no more calls waiting. In most cases, exact models are too complicated to analyze. This paper presents approximations which are tested using simulation and found to give good results.

Abstract In this article we consider four models for locating a facility on an undirected network with demand weights, which are independent discrete random variables. These problems include the probabilistic versions of two models for locating desirable facilities: the 1‐median and 1‐minimax problems and two problems for locating undesirable facilities: the 1‐antimedian and 1‐maximin problems. The article contains analysis of special cases where a solution is determined by solving deterministic versions of the problems and efficient algorithms to solve the problems in general. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 47–57 2004

Abstract We consider the 1‐median problem with uncertain weights for nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find a “minmax regret” location, that is, to minimize the worst‐case loss in the objective function that may occur because the decision is made without knowing which state of nature will take place. For this problem on a tree, the best published algorithm has complexity O(n2). We present an algorithm with complexity O(n log2 n). © 2003 Wiley Periodicals, Inc.

Abstract The generic problem studied is to locate p distinguishable facilities on a tree to satisfy upper‐bound constraints on distances between pairs of facilities, given that each facility must be located within its own feasible region, which is defined as a subtree of the tree. We present a parallel location scheme (PLS) for solving the problem that can be implemented as an NC‐algorithm. We also introduce parallel NC‐algorithms based on the PLS for the minimax versions of the problem, including the distance‐constrained p‐center problem with mutual communication. Combining the PLS and the improved Megiddo's parametric technique, we develop strongly polynomial serial algorithms for the minimax problems; the algorithms have the best complexities currently available in the literature. Efficient parallel algorithms are given for obtaining optimal regions of the facilities. © 2002 Wiley Periodicals, Inc.

Health information networks (HINs) have become increasingly important in the structure of the health care industry. In this paper, we develop decision models and decision-support systems for designing and performing cost-benefit analyses of HINs. Our models prioritize the connection of various types of health providers to the network based on the costs and benefits of all participants: the network owners, information providers and information users of the HIN. The business strategy underlying this analysis is to design the system with the maximum value for the network owner(s), while ensuring that the network provides positive added value to each of its nodes. Our framework could be used to examine the design of and to perform a cost-benefit analysis for an existing network, for the expansion of an existing network, or for the development of a new network. One can also use the models for break-even point and scenario analyses. We have used our approach to examine an existing HIN [the Wisconsin Health Information Network (WHIN)] and to perform a scenario analysis for a possible restructuring of the network. Our empirical results in this case show that HINs could be highly profitable for all network participants.

We consider the 1-median problem on a network with uncertain weights of nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find the “minimax regret” location, i.e., to minimize the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. We present the first polynomial algorithm for this problem on a general network. For the p roblem on a tree network, we discuss an algorithm with an order of complexity improved over the algorithms known in the literature.

Parallel NC-algorithms for a general class of multifacility location problems on a tree with identical facilities and the minisum objective function are presented. The class includes the p-median problem, the p-coverage problem, and the uncapacitated plant location problem.

We study generalizations of classical multifacility location problems, where customers' demand has a hierarchial structure, i.e., the set of local customers is partitioned into categories (global customers), each having its own requirements for quality of service. For the case of identical facilities, we prove that the categorized coverage, covering, p-center, and p-median problems are strongly NP-hard on trees, in contrast with their classical noncategorized versions (which are polynomially solvable on trees). Some of the problems are shown to be NP-hard even on paths. For the case of distinguishable facilities, we provide polynomial and strongly polynomial algorithms for the categorized covering, multicenter, and multimedian problems with mutual communication on a tree. © 1998 John Wiley & Sons, Inc. Networks 31:81–92, 1998

The objective is to connect a given set of terminal nodes of a network by a subnetwork of maximum bottleneck capacity. The bottleneck capacity of a subnetwork is the minimum of the capacities of its edges. For the problem with the additional requirement that the connecting subnetwork must be k-edge-connected or k-node-connected, k = 2,3, algorithms with complexities O(m + n log n) are given, where m and n are the numbers of edges and nodes of the network respectively. For the problem where the connecting subnetwork is required to be k-edge-connected or k-node-connected, k ≥ 4, the complexities of the proposed algorithms are O(m + fk(n) · log n) and O(m + gk(n) · log n) respectively, where fk(m)(gk(m)) is the complexity of finding nontrivial k-edge-connected components (k-node-connected components) of a network. The results of the paper improve known complexities for k ≥ 2 in the case of k-edge-connectivity requirement and for k ≥ 3 in the case of k-node-connectivity requirement.

The objective of this article was to find a location of a new facility on a network so that the total number (weight) of nodes within a prespecified distance R is minimized. This problem is applicable when locating an obnoxious facility such as garbage dumps, nuclear reactors, prisons, and military installations. The paper includes an analysis of the problem, identification of special cases where the problem is easily solved, an algorithm to solve the problem in general, and a sensitivity analysis of R. © 1996 John Wiley & Sons, Inc.

This paper presents optimization models for selecting a subset of software libraries, viz, collections of programs, residing on floppy disks or compact disks, available on the market. Each library contains a variety of programs whose reliabilities are assumed to be known. The objective is to maximize the reliability of the computer system subject to a budget constraint on the total cost of the libraries selected. The paper includes six models, each of which applies to a different software structure and assumptions. A detailed branch and bound algorithm for solving one of the six models is described; it contains a simple greedy-procedure for generating an initial solution.

Abstract Suppose that customers who require some service are situated at nodes of a network. Service is provided by a server who performs a service tour through all the nodes. The server has two objectives: (1) minimize the total waiting time of the customers and (2) minimize the length of the tour. It is assumed that the latter objective is of primary importance. For routing and location‐routing variants of the problem on trees and cactus networks, polynomial algorithms are presented, most of them with complexity O(n log n) or O(n). Multiserver variants of the problem on a tree are proved to be NP‐complete. Some modifications of the problem are also investigated.

Abstract Consider a network on which one or more facilities are already located. We examine how the network can be modified most efficiently in order to improve the location of the facility when the measure of facility performance is the minimax objective. The types of possible network modifications fall into two categories: reductions in the length of existing arcs or additions of some new arcs that are not currently in the network. A set of reduction and addition problems is introduced for which exact or heuristic algorithms are presented. The principal objective of the paper is in defining and formulating the problems and not in testing the efficacy of the proposed solution methodologies. © 1994 by John Wiley & Sons, Inc.

The authors present optimization models for software systems that are developed using a modular design technique. Four different software structures are considered: one program, no redundancy; one program, with redundancy; multiple programs, no redundancy; and multiple programs, with redundancy. The optimization problems are solved by using the authors' version of established optimization methods. The practical usefulness of this study is to draw the attention of software practitioners to an existing methodology that may be used to make an optimal selection out of an available pool of modules with known reliability and cost. All four models maximize software reliability while ensuring that expenditures remain within available resources. The software manager is allowed to select the appropriate model for a given situation.>

Abstract This paper focuses on the problem of locating on a tree two service units that must service each working day all the customers that require service. The paper includes an O(n2) algorithm to find the optimal locations that minimize the expected distance traveled by the two service units. This algorithm also gives the optimal service territories of the two service units. The algorithm is based on an available O(n) algorithm to find the optimal location of a single service unit on a tree and on a new method to calculate the objective function value of a given location for the single server.

The dispatch problem for a network with a general number of nonstationary service units is discussed. The possibility of dispatching a service unit to a call for service while the unit is in motion depends on the quality of the information/communication system available. Three information/communication systems are investigated: two extreme cases in which only stationary units can be dispatched from their home location or any unit can be dispatched from anywhere at any time, and an intermediate case. For each of the three systems, the dispatching policy is derived, and the systems are compared on the basis of the expected response time to a random request for service.>

Abstract This paper considers the problem of locating a single facility on a network that operates as an M/G/k queue, in which the average queueing delay is approximated by using a result in Nozaki and Ross [J. Appl. Prob. 15 (1978) 826–834]. Special consideration is given to the case of a tree network. Localization and sensitivity results are provided, together with appropriate intuitive explanations. We present an illustrative numerical example and provide a brief discussion of our computational experiences with the model. We also use discrete‐event simulation to test the effectiveness of the Nozaki and Ross approximation in the context of finding a good facility location—our results indicate that their approximation is adequate for this purpose.

Abstract In many services (e.g., delivery, or customer pickup vehicles) the service unit usually visits a number of demand points on a single multistop tour. Typically, at a specific time of the day, the unit receives the list of waiting calls and immediately starts a tour of the network that includes all waiting customers. The multistop location problem is to find the home location for the service unit. We focus on the minimax criterion for the multistop problem defined on a tree network. Each potential list of customers is associated with the length of its respective tour and with some weight. We seek for the home location of the unit that minimizes the maximum weighted tour length over all feasible customer lists. We consider several weight functions and obtain results that reveal additional properties of the classical absolute center of the tree.

Abstract In this article we deal with the problem of locating on a network a service unit that must visit all the calls that are registered in a service list. Each node can generate a call with a given probability and the service list contains the first b calls that have arrived b ≤ n (n is the number of nodes). In our problem the optimal location minimizes the expected length of a traveling salesman tour (TST) traveled. For the problem (which requires 2n calculations of probabilities), we develop an O(n) Algorithm when b = n. for a tree, and study the sensitivity of this optimal solution when b < n.

Integration of an automated manufacturing system is now recognized as one of the key issues for improving productivity. The separation of a large complex system into smaller subsystems that operate individually contributes to an efficient integration and control of the entire system. However, the overall performance of the system may be reduced if each subsystem operates independently and if no cooperation between the subsystems' resources exists. How the subsystems should cooperate to improve system performance is investigated.

Abstract This article deals with a location problem on networks that are characterized by two types of uncertainties. The first type of uncertainties relates to the travel times on the network which are not deterministic but usually undergo random changes. The second type of uncertainties relates to the demands for service which may occur at different places in the network and at random times. The consequence of the second type of uncertainties is a system which may undergo periods of intense activity as well as other periods of relative inactivity. Previous research has dealt with each one of the two types of uncertainties separately. The objective of the paper is to locate a facility that garages a single server so as to minimize the expected cost of response. Results are obtained for two models. In one model demands that occur while the server is busy are rejected whereas in the other model queueing is allowed. The special case when the network is a tree is also considered.

Abstract This article deals with some dispatching aspects of a system in which the dispatcher, in addition to stationary service units, has also the option to assign service units in motion. The nonstationary servers leave their home location at different times and move on different paths. The response time is the shortest time path of a server from the incident. The objective is to identify efficiently the appropriate unit to dispatch to a random incident. The analysis ends as soon as one of the servers is dispatched. The paper contains an efficient procedure based on the notion of the general time path. The general time path is a single path in which we superimpose the various different paths of all the moving servers. This simplifies the analysis since once the general time path is constructed it contains all the information that is provided by all those different paths. The procedure shows how to divide the general time path to disjoint segments according to the server which is closest to the incident (in each one of the segments exactly one identifiable server is closest to the incident).

Abstract The median problem has been generalized to the case in which facilities (“servers”) can be moved, at a cost, on the network in response to changes in the state of the network. Such changes are brought about by changes in travel times on the links of the network due to the occurrence of probabilistic events. For the case examined here, transitions among states of the network are assumed to be Markovian. The problem is examined for an objective which is a weighted function of demand travel times and of server relocation costs. It is shown that when these latter costs are a concave function of the time to travel from the current server location to the new server location, an optimal set of server locations exists solely on the nodes of the network. The location‐relocation problem can be formulated as an integer programming problem. The problem of locating a single server on a network which is a tree is shown to have a simple solution. A heuristic algorithm for the single server on a general network is also described. The paper develops simple bounds for the general multifacility, multistate problem and concludes with the description of a relaxed version of this model and with a discussion of the model's applicability.

The problem of repositioning urban emergency service vehicles on the transportation network is discussed. Repositioning problems deal with real-time movement of available servers to better anticipate short-term future requests for service. It is assumed that there are two distinguishable service units in the network and that repositioning can take place to any node of the network. The objective is to find the optimum repositioning policy that minimizes the long-term expected cost (total travel time) of operating the system.