Designing Reliable Center Systems: A Vector Assignment Center Location Problem

The p‐center problem is one of the most important models in location theory. Its objective is to place a fixed number of facilities so that the maximum service distance for all customers is as small as possible. This article develops a reliable p‐center problem that can account for system vulnerability and facility failure. A basic assumption is that located centers can fail with a given probability and a customer will fall back to the closest nonfailing center for service. The proposed model seeks to minimize the expected value of the maximum service distance for a service system. In addition, the proposed model is general and can be used to solve other fault‐tolerant center location problems such as the (p, q)‐center problem using appropriate assignment vectors. I present an integer programming formulation of the model and computational experiments, and then conclude with a summary of findings and point out possible future work.     

THE WEBER PROBLEM: FREQUENCY OF DIFFERENT SOLUTION TYPES AND EXTENSION TO REPULSIVE FORCES AND DYNAMIC PROCESSES*

ABSTRACT. The frequency of occurrence of the different types of solutions to the Weber problem is studied. These solutions are: a location at an attraction point due to a dominant force, to incompatible angles, or to concavity; a location at infinity; a location inside the polygon; and a location outside the polygon. Situations involving both attraction and repulsion points are examined in the triangle and in the more-than-three-sided polygon context, and methods for solving the corresponding problems are compared. A trigonometric solution is proposed for the triangle case involving one repulsion and two attraction points. The variation in the frequency of a location at an attraction point when the number of attraction points increases while the number of repulsion points remains the same is observed as well. Implications of the results are studied for the analysis of dynamic location processes.     

Elimination of Source A and B Errors in p-Median Location Problems

The p-median problem is a powerful tool in analyzing facility location options when the goal of the location scheme is to minimize the average distance that demand must traverse to reach its nearest facility. It may be used to determine the number of facilities to site, as well as the actual facility locations. Demand data are frequently aggregated in p-median location problems to reduce the computational complexity of the problem. Demand data aggregation, however, results in the loss of locational information. This loss may lead to suboptimal facility location configurations (optimality errors) and inaccurate measures of the resulting travel distances (cost errors). Hillsman and Rhoda (1978) have identified three error components: Source A, B, and C errors, which may result from demand data aggregation. In this article, a method to measure weighted travel distances in p-median problems which eliminates Source A and B errors is proposed. Test problem results indicate that the proposed measurement scheme yields solutions with lower optimality and cost errors than does the traditional distance measurement scheme.     

Location Modeling Utilizing Maximum Service Distance Criteria

The location set-covering problem (LSCP) and the maximal covering location problem (MCLP) have been the subject of considerable interest. As originally defined, both problems allowed facility placement only at nodes. This paper deals with both problems for the case when facility placement is allowed anywhere on the network. Two theorems are presented that show that when facility placement is unrestricted, for either the LSCP or MCLP at least one optimal solution exists that is composed entirely of points belonging to a finite set of points called the network intersect point set (NIPS). Optimal solution approaches to the unrestricted site LSCP and MCLP problems that utilize the NIPS and previously developed solution methodologies are presented. Example solutions show that considerable improvement in the amount of coverage or the number of facilities needed to insure total coverage can be achieved by allowing facility placement along arcs of the network. In addition, extensions to the arc-covering model and the ambulance-hospital model of ReVelle, Toregas, and Falkson are developed and solved.     

A Statistical Method for Analyzing the Relative Location of Points in a Bounded Region

This paper develops a statistical method for analyzing the relative location of points in a bounded region. The location of points in relation to the center of the region in which they are located is discussed. Four spatial objects called reference objects are defined to represent the relative location: (1) the boundary, (2) skeleton, (3) nucleus, and (4) global center. The distribution of distance between points and a reference object yields a cumulative distribution function (CDF). Comparison of CDFs for a reference object allows us to analyze whether the points tend to be located close to the reference object or, for instance, whether the points are clustered around the center of the region. The significance of the CDF is statistically tested by Monte Carlo simulation. The method proposed is applied to the distribution of restaurants in retail clusters.     

The Pickup Problem: Consumers' Locational Preferences in Flow Interception

This article addresses the pickup problem , wherein patrons briefly interrupt their predetermined journeys to obtain a simple good, such as fast food or a video, and then resume their journeys. This is a problem from the class known as the flow-interception location problems. Traditional flow-interception location models (FILMs) are used to select service locations such that the intercepted flows are maximized. In these traditional models, only flow quantities are considered; these models do not consider where a pickup is made in a journey. However, in the real world, consumers often wish to obtain a product or service at or near a specific location along their trips. The pickup model (PUP) proposed here considers consumers' locational preferences, providing a much broader, more realistic approach than FILM (a special case of PUP) to problems in the private and public sectors. By considering which patrons are served where, PUP transforms the FILM into a flow-interception location-allocation model, providing a fruitful garden for further research. Geographic information systems and optimization engines are integrated to investigate the PUP model in real-world transportation systems. Reported findings demonstrate that the optimal locations identified by traditional models arise solely from network flow structure, whereas the optimal locations identified by PUP result from trade-offs between network flow structure and the importance of proximity to preferred locations. One important discovery is that PUP solutions are superior to those of traditional FILMs if consumers have locational preferences. Up-to-date, real-world transportation networks provide a realistic test-bed for this and other models of the flow-interception type.     

Multi‐Type,Multi‐Zone Facility Location

The placement of facilities according to spatial and/or geographic requirements is a popular problem within the domain of location science. Objectives that are typically considered in this class of problems include dispersion, median, center, and covering objectives—and are generally defined in terms of distance or service‐related criteria. With few exceptions, the existing models in the literature for these problems only accommodate one type of facility. Furthermore, the literature on these problems does not allow for the possibility of multiple placement zones within which facilities may be placed. Due to the unique placement requirements of different facility types—such as suitable terrain that may be considered for placement and specific placement objectives for each facility type—it is expected that different suitable placement zones for each facility type, or groups of facility types, may differ. In this article, we introduce a novel mathematical treatment for multi‐type, multi‐zone facility location problems. We derive multi‐type, multi‐zone extensions to the classical integer‐linear programming formulations involving dispersion, centering and maximal covering. The complexity of these formulations leads us to follow a heuristic solution approach, for which a novel multi‐type, multi‐zone variation of the non‐dominated sorting genetic algorithm‐II algorithm is proposed and employed to solve practical examples of multi‐type, multi‐zone facility location problems.     

A SIMPLIFICATION AND GENERALIZATION OF THE EXCLUSION THEOREM: A TECHNICAL NOTE

Several researchers have proven that for the integrated production-location problem on the Weberian triangle, intermediate points on the edge of the triangle can never be optimal locations. Authors of previous proofs of this result have used cumbersome trigonometric arguments. We present a much simpler algebraic proof of the result, and present it in terms of the more general n -input model, where the feasible location space is a convex polygon rather than a triangle. In addition, the result generalizes immediately to other cases, such as (1) multifacility production-location problems, (2) stochastic versions of one-facility and multifacility production-location problems, and (3) comparable pure location problems (e.g., the Weber problem).     

关于建设我国北方集装箱枢纽港问题的思考

集装箱运输是世界交通运输发展的趋势,在这一进程中,集装箱枢纽港与支线港的形成与分化日益明显,它是集装箱运输规模效益发展的必然结果。随着我国集装箱运量的增加,合量布局我国集装箱枢纽港和支线港的问题日益突出,目前,香港和上海作为我国南方和中部集装箱枢纽港的地位已确立,而北方形成了大连、青岛、天津三足鼎立格局,合理布局北方集装箱枢纽港是我国北方各省区社会经济发展的客观要求。文章深入分析了北方主要集装箱港口的现状和潜力,并提出了我国北方集装箱枢纽港未来的发展战略。     

On Covering Problems and the Central Facilities Location Problem

A number of variations of facilities location problems have appeared in the research literature in the past decade. Among these are problems involving the location of multiple new facilities in a discrete solution space, with the new facilities located relative to a set of existing facilities having known locations. In this paper a number of discrete solution space location problems are treated. Specifically, the covering problem and the central facilities location problem are shown to be related. The covering problem involves the location of the minimum number of new facilities among a finite number of sites such that all existing facilities (customers) are covered by at least one new facility. The central facilities location problem consists of the location of a given number of new facilities among a finite number of sites such that the sum of the weighted distances between existing facilities and new facilities is minimized. Computational experience in using the same heuristic solution procedure to solve both problems is provided and compared with other existing solution procedures.     

HETEROGENEOUS TASTES AND RESIDENTIAL LOCATION*

ABSTRACT. In a simple urban model, where the only spatial distinction made is between center and suburb, we introduce a uniform distribution of preferences for land. Under a logarithmic utility function, we examine how the location and consumption decisions of individuals differ in consequence of their different preferences for land. Comparative statics indicate that the qualitative response of the city at equilibrium to changes in per capita income and transportation cost is not affected by the introduction of such heterogeneity. Possible extensions are also briefly discussed.     

Optimum Design Approaches for Improving the Seismic Performance of 3D RC Buildings

In this article, a number of design approaches for 3D reinforced concrete (RC) buildings are formulated in the framework of structural optimization problems and are assessed in terms of their performance under earthquake loading. In particular, three design approaches for RC buildings are considered in this study. In the first, the initial construction cost is considered as the objective function to be minimized. The second one is formulated as a minimization problem of the torsional response, while a combined formulation is also examined as the third design approach. The third approach is considered with two distinctive formulations. According to the first approach, the torsional behavior is minimized by minimizing the eccentricity between the mass and rigidity centers, while the second one is achieved by minimizing the eccentricity between the mass and strength centers. It is shown that the optimized designs obtained according to the minimum eccentricity of the rigidity center behave better in frequent (50/50 hazard level) and occasional (10/50 hazard level) earthquakes, while the designs obtained according to the minimum eccentricity of the strength center formulation was found better in rare (2/50 hazard level) events. Designs obtained through a combined formulation seem to behave equally well in the three hazard levels examined.     

Analysis of Errors Due to Demand Data Aggregation in the Set Covering and Maximal Covering Location Problems

In this paper, we extend the concepts of demand data aggregation error to location problems involving coverage. These errors, which arise from losses in locational information, may lead to suboptimal location patterns. They are potentially more significant in covering problems than in p-median problems because the distance metric is binary in covering problems. We examine the Hillsman and Rhoda (1978) Source A, B, and C errors, identify their coverage counterparts, and relate them to the cost and optimality errors that may result. Three rules are then presented which, when applied during data aggregation, will reduce these errors. The third rule will, in fact, eliminate all loss of locational information, but may also limit the amount of aggregation possible. Results of computational tests on a large-scale problem are presented to demonstrate the performance of rule 3.     

An Evolutionary Algorithm for Site Search Problems

The goal of solving a site search problem is to allocate a contiguous set of land parcels such that the total land acquisition cost, or other objectives, are optimized. This article describes the design and implementation of an evolutionary algorithm (EA) that can be used to solve site search problems. In this article, a graph representation is used to define the spatial structure of solutions to the problem. By using this representation, the contiguity of a site is maintained during the initialization, mutation, and local search operations of the EA. The effectiveness of the EA in finding optimal or near-optimal solutions is demonstrated by testing it on a series of problems whose optimal solutions are known.     

Dispersion of Nodes Added to a Network

For location problems in which optimal locations can be at nodes or along arcs but no finite dominating set has been identified, researchers may desire a method for dispersing p additional discrete candidate sites along the m arcs of a network. This article develops and tests minimax and maximin models for solving this continuous network location problem, which we call the added-node dispersion problem (ANDP). Adding nodes to an arc subdivides it into subarcs. The minimax model minimizes the maximum subarc length, while the maximin model maximizes the minimum subarc length. Like most worst-case objectives, the minimax and maximin objectives are plagued by poorly behaved alternate optima. Therefore, a secondary MinSumMax objective is used to select the best-dispersed alternate optima. We prove that equal spacing of added nodes along arcs is optimal to the MinSumMax objective. Using this fact we develop greedy heuristic algorithms that are simple, optimal, and efficient (O( mp )). Empirical results show how the maximum subarc, minimum subarc, and sum of longest subarcs change as the number of added nodes increases. Further empirical results show how using the ANDP to locate additional nodes can improve the solutions of another location problem. Using the p-dispersion problem as a case study, we show how much adding ANDP sites to the network vertices improves the p-dispersion objective function compared with (a) network vertices only and (b) vertices plus randomly added nodes. The ANDP can also be used by itself to disperse facilities such as stores, refueling stations, cell phone towers, or relay facilities along the arcs of a network, assuming that such facilities already exist at all nodes of the network.     

Contact Dynamics of Masonry Block Structures Using Mathematical Programming

A simple variational formulation for contact dynamics is adopted to investigate the dynamic behavior of planar masonry block structures subjected to seismic events. The numerical model is a two-dimensional assemblage of rigid blocks interacting at potential contact points located at the vertices of the interfaces. A no-tension and associative frictional behavior with infinite compressive strength is considered for joints. The dynamic contact problem is formulated as a quadratic programming problem (QP) and an iterative procedure is implemented for time integration. Applications to analytical and numerical case studies are presented for validation. Comparisons with the experimental results of a masonry wall under free rocking motion and of a small scale panel with opening subjected to in-plane loads are also carried out to evaluate the accuracy and the computational efficiency of the formulation adopted.     

Problem Definition, Agenda Access, and Policy Choice

Problem definition is fundamental to public policy making, intertwined as it is with the political process throughout the activities of issue initiation, program design, and legislative enactment. Yet problem definition remains in immature analytic construct, productive of only a modest amount of scholarship that is lacking a coherent shared framework. Seeking to address this deficiency, this article systematically examines the origins, elements, and consequences of problem definition, relating this discussion to previous literature in the area, current policymaking developments, and future research needs.     

NETWORK EQUILIBRIUM MODELS OF URBAN LOCATION AND TRAVEL CHOICES: A RETROSPECTIVE SURVEY*

ABSTRACT The origins and development of the network equilibrium problem are traced and interrelated. Two principal formulations are considered the network equilibrium problem with variable travel demand, and the combined model of trip distribution and traffic assignment. The relation of these models to subsequent developments concerning mode choice, residential location, estimation of origin-destination tables from link flows and stochastic route choice are then reviewed.     

Errors Caused by Rounded Data in Two Simple Facility Location Problems

As a rule, data to be used in locational analysis are either rounded up or rounded down. Therefore, error is incurred if such location data are used. The objective of this paper is to examine location error and cost error due to rounding in unweighted minisum and minimax problems in one-dimensional continuous space. Several conclusions on rounding effects are obtained by examining the respective mean-squared errors. First, rounding tends to exert more serious influence on the minisum problem than on the minimax problem. Second, in both location problems, the location error shows a pattern that is the inverse of that of the cost error.     

Adaptive Cell Tower Location Using Geostatistics. 基于地统计学的适应性基站发射塔选址研究

In this article, we address the problem of allocating an additional cell tower (or a set of towers) to an existing cellular network, maximizing the call completion probability. Our approach is derived from the adaptive spatial sampling problem using kriging, capitalizing on spatial correlation between cell phone signal strength data points and accounting for terrain morphology. Cell phone demand is reflected by population counts in the form of weights. The objective function, which is the weighted call completion probability, is highly nonlinear and complex (nondifferentiable and discontinuous). Sequential and simultaneous discrete optimization techniques are presented, and heuristics such as simulated annealing and Nelder–Mead are suggested to solve our problem. The adaptive spatial sampling problem is defined and related to the additional facility location problem. The approach is illustrated using data on cell phone call completion probability in a rural region of Erie County in western New York, and accounts for terrain variation using a line‐of‐sight approach. Finally, the computational results of sequential and simultaneous approaches are compared. Our model is also applicable to other facility location problems that aim to minimize the uncertainty associated with a customer visiting a new facility that has been added to an existing set of facilities.