Search

In this paper we propose three models for locating multiple facilities anywhere in the plane. The facilities serve demand points and require raw materials from a list of available sources. Problem characteristic originally proposed in 1909 by Weber for manufacturing systems. Weber argued that optimal locations involve minimizing total transport cost which was comprised of the costs of transporting the raw materials and the delivery cost of the final product when plant production and location costs were invariant across the plane. Both the parameters of raw material sources and demand points affect the best locations for the facilities. In this paper, a special algorithm is designed to heuristically solve these three models. The algorithm exploits the special structure of the models. Problems with up to 2000 demand points and 20 facilities were tested. The results are compared with applying available non-linear solvers in a multi-start approach. The special algorithm performed better in most instances especially for a large number of facilities and a large number of demand points. [ABSTRACT FROM AUTHOR]

Total demand suitably served and facility workload balance are two important considerations in location coverage. Previous work has dealt with workload balancing issues using a number of approaches, including imposing facility capacities and the use of multiple objectives focused on workload variation. However, a facility is usually restricted to a single service unit, inconsistent with strategies that allow for increased staffing such as multiple service units in dealing with higher levels of demand. This article proposes a new bi‐objective optimization model that maximizes total demand coverage and minimizes workload differences simultaneously while allowing more than one service unit to be co‐located at a site. Since the proposed model is strongly NP hard, a heuristic algorithm is developed for efficient solution. The model is applied to support postal delivery service planning. Results show that the proposed model offers improved performance compared to approaches that do not permit co‐location. The proposed algorithm is able to produce high‐quality solutions that evenly distribute allocated service demand, and does so much faster with higher‐quality solutions compared to exact solution approaches. [ABSTRACT FROM AUTHOR]

Safe Routes to School (SRTS) programs provide funding for infrastructure improvements that encourage children to use active transportation (AT) modes such as walking for travel between home and school. In the United States, the federal government distributes funding to states that can be used for SRTS infrastructure improvements. A Safe Routes to School Infrastructure Improvement Model is proposed that can help decision makers prioritize infrastructure improvement projects. This model is applied to the pedestrian network surrounding a school in Santa Barbara, California to demonstrate how it can be used to recommend specific SRTS infrastructure improvements that minimize pedestrian risk while accounting for funding constraints. • A Safe Routes to School Infrastructure Improvement Model is proposed that can help decision makers prioritize infrastructure improvement projects that encourage active transportation and minimize pedestrian risk. • An approach to measuring pedestrian risk proposed that is based upon two simple premises: first, that infrastructure can prevent conflicts between vehicles and pedestrians, and second, that slower vehicle speeds can reduce the risk of serious injury when conflicts do occur. • This model is applied to the pedestrian network surrounding a school in Santa Barbara, California to demonstrate how it can be used to recommend specific sidewalk and crosswalk improvements while accounting for funding constraints. [ABSTRACT FROM AUTHOR]

One of the classic operations problems in forest management is to select the harvesting system and to plan the layout, which has a significant impact on overall operational and environmental efficiency. This paper addresses the design of a harvesting system in areas characterized by steep slopes requiring cable-based harvesting under central European conditions. We present two computationally efficient methods (designated as set-covering model SCM and bounded set-covering model BSCM) for solving problems of cable road layouts and comparing them with a previously developed model (CaMLOC). Formulating the problem as a type of location set-covering model allowed us to delineate a much smaller problem that was easier to solve. By applying the new model formulations, it is possible to identify mathematical optimal CR layouts for real-world forests areas up to 50 ha within a reasonable period of time and to even estimate the maximum gap in optimality (only with the BSCM approach). [ABSTRACT FROM AUTHOR]

In 1970, Tobler produced a movie simulating population growth in the City of Detroit. He argued that his model did not need to include terms for faraway places like Singapore, while still being relative accurate in his forecast by invoking what he called the first law of geography. In spatial optimization, like the general warehouse location problem (GWLP), it is assumed that all possible linkages need to be included, as arbitrarily dropping potential variables may prevent optimal solutions from being identified. In this article, it is demonstrated that it may be possible to meet such exacting standards in spatial optimization, while at the same time being guided by Tobler’s argument for being simple and frugal. This article gives a demonstration of how this might be achieved using the GWLP as an example. A new model form is proposed which distinguishes between “near” (low cost) allocations and “far” (high cost) allocations and uses both explicit and implicit variables for capacity allocations. Computational experience in using this new model is given which shows that optimal solutions can be identified and verified while eliminating a substantial number of allocation/transport variables and constraints. This article ends with a challenge for the reformulation and redevelopment of other spatial optimization problems in regional science. [ABSTRACT FROM AUTHOR]

This paper proposes a new strategic planning model for high-speed rail ventures. It is a mixed-integer optimization model that applies to a given line and focuses on two key strategic decisions: station location and fleet composition. Our purpose is to improve on previous station location models by including fleet composition decisions. In the new model, we additionally take into account in an approximate fashion the interrelationships between strategic and subsequent tactical decisions, regarding line planning, train scheduling and fleet assignment issues. The usefulness of the model is demonstrated for a case study involving a planned Lisbon-Oporto high-speed rail line. [ABSTRACT FROM AUTHOR]

Location-allocation modeling is an important area of research in spatial optimization and GIScience. A large number of analytical models for location-allocation analysis have been developed in the past 50 years to meet the requirements of different planning and spatial-analytic applications, ranging from the location of emergency response units (EMS) to warehouses and transportation hubs. Despite their great number, many location-allocation models are intrinsically linked to one another. A well-known example is the theoretical link between the classicp-median problem and coverage location problems. Recently, Lei and Church showed that a large number of classic and new location models can be posed as special case problems of a new modeling construct called the vector assignment ordered median problem (VAOMP). Lei and Church also reported extremely high computational complexity in optimally solving the best integer linear programming (ILP) formulation developed for the VAOMP even for medium-sized problems in certain cases. In this article, we develop an efficient unified solver for location-allocation analysis based on the VAOMP model without using ILP solvers. Our aim is to develop a fast heuristic algorithm based on the Tabu Search (TS) meta-heuristic, and message passing interface (MPI) suitable for obtaining optimal or near-optimal solutions for the VAOMP in a real-time environment. The unified approach is particularly interesting from the perspective of GIScience and spatial decision support systems (DSS) as it makes it possible to solve a wide variety of location models in a unified manner in a GIS environment. Computational results show that the TS method can often obtain in seconds, solutions that are better than those obtained using the ILP-based approach in hours or a day. [ABSTRACT FROM PUBLISHER]

The efficiency of public investments and services has been of interest to geographic researchers for several decades. While in the private sector inefficiency often leads to higher prices, loss of competitiveness, and loss of business, in the public sector inefficiency in service provision does not necessarily lead to immediate changes. In many cases, it is not an entirely easy task to analyze a particular service as appropriate data may be difficult to obtain and hidden in detailed budgets. In this paper, we develop an integrative approach that uses cyber search, Geographic Information System (GIS), and spatial optimization to estimate the spatial efficiency of fire protection services in Los Angeles (LA) County. We develop a cyber-search process to identify current deployment patterns of fire stations across the major urban region of LA County. We compare the results of our search to existing databases. Using spatial optimization, we estimate the level of deployment that is needed to meet desired coverage levels based upon the location of an ideal fire station pattern, and then compare this ideal level of deployment to the existing system as a means of estimating spatial efficiency. GIS is adopted throughout the paper to simulate the demand locations, to conduct location-based spatial analysis, to visualize fire station data, and to map model simulation results. Finally, we show that the existing system in LA County has considerable room for improvement. The methodology presented in this paper is both novel and groundbreaking, and the automated assessments are readily transferable to other counties and jurisdictions. [ABSTRACT FROM PUBLISHER]

The shortest covering path (SCP) problem involves finding the shortest path between an origin node and a destination node, where the path traverses the network and passes within a maximal covering distance of all nodes of the network. This problem was originally proposed by Current, ReVelle, and Cohon. Since that time researchers have proposed both heuristic and optimal approaches for this problem as well as have developed more general forms, including the maximal covering shortest path problem. From the outset, it has been assumed that any optimal covering path would never loop or double back on itself. This assumption is examined in detail. We demonstrate that this assumption can lead to longer than necessary covering paths. We also present a new, more general construct, which can be used to generate optimal SCPs and demonstrate its use on an example problem. [ABSTRACT FROM AUTHOR]

Multi-patch land allocation refers to the selection of management units to form individual patches, where each patch is contiguous and restricted in spatial extent. The purpose of a patch can vary, but often involves a coordinated activity or usage, such as species conservation, rehabilitation, treatment, waste management and others. The goal then is to identify a set of patches that provides the greatest total benefit, with strict limits on size combined with inter-patch connectivity. This paper focuses on exact mixed-integer programming solution approaches of a multi-patch problem. Methods for formulation strengthening are introduced and formally developed. Land allocation associated with wildfire fuels treatment for the USDA Forest Service is investigated. Application results highlight enhanced solution capabilities, and demonstrate planning support possible through explicit spatial optimization approaches. • Formulates the multiple patch land allocation problem. • Details formulation strengthening strategies. • Addresses wildfire mitigation planning. • Demonstrates capabilities to optimally solve planning problems involving thousands of units. [ABSTRACT FROM AUTHOR]

The vector assignment p-median problem (VAPMP) is one of the first discrete location problems to account for the service of a demand by multiple facilities, and has been used to model a variety of location problems in addressing issues such as system vulnerability and reliability. Specifically, it involves the location of a fixed number of facilities when the assumption is that each demand point is served a certain fraction of the time by its closest facility, a certain fraction of the time by its second closest facility, and so on. The assignment vector represents the fraction of the time a facility of a given closeness order serves a specific demand point. Weaver and Church showed that when the fractions of assignment to closer facilities are greater than more distant facilities, an optimal all-node solution always exists. However, the general form of the VAPMP does not have this property. Hooker and Garfinkel provided a counterexample of this property for the nonmonotonic VAPMP. However, they do not conjecture as to what a finite set may be in general. The question of whether there exists a finite set of locations that contains an optimal solution has remained open to conjecture. In this article, we prove that a finite optimality set for the VAPMP consisting of "equidistant points" does exist. We also show a stronger result when the underlying network is a tree graph. [ABSTRACT FROM AUTHOR]

The p-compact-regions problem involves the search for an aggregation of n atomic spatial units into p-compact, contiguous regions. This article reports our efforts in designing a heuristic framework- MERGE (memory-based randomized greedy and edge reassignment)-to solve this problem through phases of dealing, randomized greedy, and edge reassignment. This MERGE heuristic is able to memorize ( ME of MERGE) the potential best moves toward an optimal solution at each phase of the procedure such that the search efficiency can be greatly improved. A dealing phase grows seeded regions into a viable size. A randomized greedy ( RG of MERGE) approach completes the regions' growth and generates a feasible set of p-regions. The edge-reassigning local search (E of MERGE) fine-tunes the results toward better objectives. In addition, a normalized moment of inertia ( NMI) is introduced as the method of choice in computing the compactness of each region. We discuss in detail how MERGE works and how this new compactness measure can be seamlessly integrated into different phases of the proposed regionalization procedure. The performance of MERGE is evaluated through the use of both a small and a large p-compact-regions problem motivated by modeling the regional economy of Southern California. We expect this work to contribute to the regionalization theory and practice literature. Theoretically, we formulate a new model for the family of p-compact-regions problems. The novel NMI introduced in the model provides an accurate, robust, and efficient measure of compactness, which is a key objective for p-compact-regions problems. Practically, we developed the MERGE heuristic, proven to be effective and efficient in solving this nonlinear optimization problem to near optimality. El problema de regiones compactas tipo p ( p-compact regions) consiste en la búsqueda de la agregación de n unidades espaciales atómicas que produzca regiones contiguas de tipo p-compacto. Este artículo reporta los esfuerzos de los autores en el diseño de un marco heurístico MERGE ( memory-based randomized greedy and edge-reassignment) el cual resuelve este problema a través de las fases de la negociación (dealing), codicia aleatorizada (randomized greedy), y la reasignación de bordes ( edge reassignment). El heurístico MERGE es capaz de memorizar ( ME de MERGE) los mejo)res desplazamientos posibles hacia una solución óptima en cada fase del procedimiento de tal manera que la eficiencia de la búsqueda puede ser mejorada en gran medida. La fase de negociación crea regiones 'sembradas' aleatoriamente y las hace crecer en diferentes tamaños . El componente de codicia aleatorio (RG de MERGE) completa la fase de crecimiento de las regiones y genera un conjunto factible de regiones tipo p. La reasignación de bordes se realiza vía una búsqueda local (E de MERGE) que afina los resultados con el fin the alcanzar los objetivos. Además, el enfoque propuesto aquí utiliza el momento de inercia normalizado ( normalized momento of inertia-NMI) como método para el cálculo de la compacidad de cada región. El artículo discute en detalle el funcionamiento de MERGE y cómo esta nueva medida compacidad puede integrarse perfectamente en las diferentes fases del procedimiento de regionalización propuesto. Para ilustrar y evaluar el desempeño de MERGE, el metodo es aplicado a dos problemas de p-compact regions, uno grande y uno pequeño, basados en el modelado de la economía regional del sur de California. Los autores esperan que este trabajo contribuya a la literatura teórica y práctica de la regionalización. En términos teóricos, se formula un nuevo modelo de la familia de problemas de p-compact regions. El NMI equipa al modelo con una novedosa forma de obtener una medida exacta, robusta y eficiente de compacidad, que es un objetivo clave para los problemas región compacta tipo p. En términos prácticos, se desarrolla MERGE, un procedimiento heurístico que ha demostrado ser eficaz y eficiente en la solución de este problema de optimización no lineal de manera casi óptima. p紧凑区域问题包含寻找一种聚集方法，将n个不可分割的空间单元集合成p紧凑的邻近区域。本文阐述了一种启发式架构MERGE(基于记忆的随机贪婪和边界再赋值算法)，通过处理、随机贪婪和边界再分配这几个阶段解决p紧凑问题。MERGE启发式框架能存储 处理过程每个阶段中，向一个最优解的潜在最佳移动方式，从而可极大地提升搜索效率。一个处理阶段可将种子区域生长到可行大小。而一个随机贪婪阶段能完成区域增长并生成p区域的可行集。在边界再分配的局部搜索阶段对结果进行微调以达到更好的目标。此外，引入标准化的惯性矩作为每个区域紧凑度计算的选择方法。本文详细讨论了MERGE的工作原理，以及这种新的紧凑度测算方法如何能无缝地整合到所提出的区域化流程的不同阶段。通过在南部加州区域经济建模中一小一大两个p紧凑区域问题的应用，对MERGE的性能进行评估，期望该工作能够对区域化理论和实践作出贡献。理论上，提出了可解决p紧凑区域这类问题的新模型。在模型中引入新颖的标准化惯性矩这一精确的、鲁棒的和有效的紧凑度度量方法，是解决p紧凑区域问题的关键目标；实践上，本文发展了MERGE启发式框架，并证明了它在解决这种非线性优化问题近优性的有效性和高效性。 [ABSTRACT FROM AUTHOR]

The vector assignment p-median problem (VAPMP) and the ordered p-median problem (OMP) are important extensions of the classic p-median problem. The VAPMP extends the p-median problem by allowing assignment of a demand to multiple facilities, and a wide variety of multi-assignment and backup location problems are special cases of this problem. The OMP optimizes a weighted sum of service distances according to their relative ranks among all demands. The OMP is well known as it represents a generalization of both the p-median and the p-center problems. In this article, a new model is developed which extends both the VAPMP and OMP problems. In addition, beyond median, center, and vector assignment, this new model can resolve problems where the system objective involves maximizing distance. The new model also gives rise to meaningful special-case problems, such as a “reliable p-center” problem. Different integer linear programming (ILP) formulations of the new problem are presented and tested. It is demonstrated that an efficient formulation for a special case of the VAOMP problem can solve medium sized problems optimally in a reasonable amount of time. [ABSTRACT FROM PUBLISHER]

Corridor location for developing new infrastructure such as transmission lines, roadways, and pipelines over terrain must consider numerous factors when determining the set of optimal route candidates. Previous researchers have cast this problem as a multiobjective least cost path problem, where competing objectives represent cost, environmental impact, and other major noncommensurate objectives. To fully characterize the optimal trade-off solution set, one must be able to generate both supported and unsupported nondominated solutions. Fortunately, the supported, nondominated solutions are relatively easy to identify by using a single-objective shortest path algorithm in conjunction with the noninferior set estimation method of Cohon, Church, and Sheer. But, finding the unsupported nondominated solutions can be nondeterministic polynomial time hard. This article proposes a heuristic approach that is capable of determining a Pareto frontier that is very near exact in polynomial time. This heuristic approach uses gateway node and gateway arc paths to generate a large set of spatially diverse locally optimal candidate solutions with few shortest path solver iterations, which are shown to represent a solution set that approximates to a high degree, the exact Pareto set. The method is described within the context of a bi-objective corridor location problem and applied to several data sets that have been used in past work. A comparison between this new approach and existing exact algorithms is provided. Overall, the new method is shown to be effective at finding a sizable number of the unsupported nondominated solutions in a very small amount of computational time. [ABSTRACT FROM PUBLISHER]

Highlights: [•] Propose an extendable heuristic framework for solving large, practical, and non-linear regionalization problems. [•] Introduce NMI as a novel method and prove its effectiveness to compute compactness in a p-compact-regions problem. [•] Demonstrate the good performance of MERGE heuristic in solving real-world large p-compact-regions problem. [Copyright &y& Elsevier]

One of the important classes of facility dispersion problems involves the location of a number of facilities where the intent is to place them as far apart from each other as possible. Four basic forms of the p-facility dispersion problem appear in the literature. Erkut and Neuman present a classification system for these four classic constructs. More recently, Curtin and Church expanded upon this framework by the introduction of 'multiple types' of facilities, where the dispersion distances between specific types are weighted differently. This article explores another basic assumption found in all four classic models (including the multitype facility constructs of Curtin and Church): that dispersion is accounted for in terms of either distance to the closest facility or distances to all facilities (from a given facility), whether applied to a single type of facility or across a set of facility types. In reality, however, measuring dispersion in terms of whether neighboring facilities to a given facility are dispersed rather than whether all facilities are dispersed away from the given facility often makes more sense. To account for this intermediate measure of dispersion, we propose a construct called partial-sum dispersion. We propose four 'partial-sum' dispersion problem forms and show that these are generalized forms of the classic set of four models codified by Erkut and Neuman. Further, we present a unifying model that is a generalized form of all four partial-sum models as well as a generalized form of the original four classic model constructs. Finally, we present computational experience with the general model and conclude with a few examples and suggestions for future research. Una de las clases importantes dentro de los problemas de dispersión de instalaciones de servicios/infraestructura es el caso en el que la localización de un número de instalaciones debe cumplir la condición de maximizar la distancia entre cada par. La literatura especializada cita cuatro formas básicas del problema de dispersión llamados tipo p-instalación ( p-facility) (Shier 1977; Luna y Chaudhry 1984; Kuby 1987; Erkut y Neuman, 1991). Erkut y Neuman (1991) presentan un sistema de clasificación para estas cuatro formas clásicas. Recientemente, Curtin e Iglesia (2006) ampliaron este marco metodológico al incorporar múltiples tipos de instalaciones, permitiendo que las distancias de dispersión entre diferentes tipos específicos de instalaciones sean ponderadas de manera diferente. El artículo presente explora otro supuesto básico que se encuentra en los cuatro modelos clásicos (y las modifcaciones para acomodar instalaciones multi-tipo de Curtin e Iglesia): la dispersión es cuantificada en términos de la distancia entre una instalación dada y la instalación más cercana, o entre una instalación dada y la totalidad de las instalaciones. Este supuesto se mantiene si las distancias son aplicadas a un solo tipo de instalación o a múltiples tipos de instalaciones. Sin embargo, en realidad, tiene más sentido medir la dispersión en relación a las instalaciones vecinas, en vez de en relación a la totalidad las instalaciones. Para incorporar esta realidad a un nuevo tipo de medida intermedia de dispersión, se propone una medida llamada dispersión de suma parcial ( partial-sum dispersion). Proponemos cuatro tipos de problemas de dispersión de tipo parcial-sum y demostramos que éstas son formas generalizadas de los cuatro modelos clásicos presentados por Erkut y Neuman (1991). Además, se presenta un modelo unificado que es una forma generalizada de los cuatro modelos tipo partial-sum, así como una forma generalizada de las cuatro tipos en el modelo clásico. Por último, se presenta los resultados de pruebas computacionales usando el modelo general y se concluye con algunos ejemplos y sugerencias para investigaciones futuras. 设施分散问题中重要的一类是大量设施的布局，其意图是将它们在空间上尽可能离得更远。目前文献中主要讨论了4种基本形式(Shier 1977; Moon and Chaudhry 1984; Kuby 1987; Erkut and Neuman 1991)。Erkut and Neuman (1991)提出了这4种经典结构的一种分类系统。Curtin and Church (2006)引入设施'多种类型'对上述分类框架进行拓展，在特定类别之间的分散距离的权重存在不同。本文探索了在4种经典模型中所发现的另一种基本假设（包含Curtin and Church的多种类型设施结构）：无论是在单一类型设施或包括多种类型设施中，分散度在解释某一给定设施到最近设施的距离或到所有设施的距离方面都是合理的。然而，在现实中设施分散度度量方面，测量某一给定设施的邻近设施的分散度特征相比于测量给定设施的所有其他设施的散布特征通常更有意义。为解释这种分散度的中间度量，本文提出了一种称为'局部和整体'的结构，包括4种分散问题形式，它们是Erkut and Neuman 4种传统类型的广义形式。本文进而提出了一个统一模型，即所有 '局部和整体'模型和经典类型结构一种广义形式。最后，对统一模型进行了计算检验，并基于几个实证进行了总结，还提出了未来的研究建议。 [ABSTRACT FROM AUTHOR]

Abstract: Conserving nature in the presence of humans is especially challenging in areas where livelihoods are largely based on locally available natural resources. The restoration of forests in such contexts calls for the identification of sites and actions that improve biodiversity protection, and ensure the provision of and accessibility to other forest-related ecosystem services. This paper introduces an integer-linear programming (ILP) approach to identify reforestation priorities that achieve such goals. Applications of ILP to nature conservation are many, but only a few of them deal with the problem of restoration, and none of the available models considers the basic needs of the local population. Given constraints on a restoration budget, the potential conversion of productive lands and the travel time to reach harvestable forest, the model maximises the amount of reforestation area (weighted by priority values) and minimises the harvesting of existing forest, while ensuring the conservation of landscape diversity, the satisfaction of timber demands and the stabilisation of erosion-prone land. As an input, suitability maps, generated through a combination of ecological criteria, are used to prioritise the selection of reforestation sites. An application to a 430 km2 area in Central Chiapas (Mexico) resulted in compact patches and thus a manageable reforestation plan. Acceptable trade-offs were found between the amount of soil stabilisation possible and the prioritisation goals, while uncertainty in the prioritisation scores did not significantly affect the results. We show that restoration actions can be spatially designed to benefit both nature and people with minimal losses on both sides. [Copyright &y& Elsevier]

Abstract: This paper presents three strategic-level models for locating away-from-port storage yards for empty shipping containers. The main objective is to reduce the mileage involved in repositioning empty containers. The models presented attempt to capture the greedy behavior of individual trucking companies and provide for the first time a “user” optimal modeling approach for empty container management. An application to the port complexes of Los Angeles and Long Beach demonstrates that savings associated with storage yards could be easily overestimated when neglecting the perspective of the individual trucking companies. Strategies to encourage system optimal behavior are proposed. [Copyright &y& Elsevier]

In the classic p-median problem, it is assumed that each point of demand will be served by his or her closest located facility. The p-median problem can be thought of as a ‘‘single-level’’ allocation and location problem, as all demand at a specific location is assigned as a whole unit to the closest facility. In some service protocols, demand assignment has been defined as ‘‘multilevel’’ where each point of demand may be served a certain percentage of the time by the closest facility, a certain percentage of the time by the second closest facility, and so on. This article deals with the case in which there is a need for ‘‘explicit’’ closest assignment (ECA) constraints. The authors review past location modeling work that involves single-level ECA constraints as well as specific constraint constructs that have been proposed to ensure single-level closest assignment. They then show how each of the earlier proposed ECA constructs can be generalized for the ‘‘multilevel’’ case. Finally, the authors provide computational experience using these generalized ECA constructs for a novel multilevel facility interdiction problem introduced in this article. Altogether, this article proposes both a new set of constraint structures that can be used in location models involving multilevel assignment as well as a new facility interdiction model that can be used to optimize worst case levels of facility disruption. [ABSTRACT FROM AUTHOR]

The p-regions problem involves the aggregation or clustering of n small areas into p spatially contiguous regions while optimizing some criteria. The main objective of this article is to explore possible avenues for formulating this problem as a mixed integer-programming (MIP) problem. The critical issue in formulating this problem is to ensure that each region is a spatially contiguous cluster of small areas. We introduce three MIP models for solving the p regions problem. Each model minimizes the sum of dissimilarities between all pairs of areas within each region while guaranteeing contiguity. Three strategies designed to ensure contiguity are presented: (1) an adaptation of the Miller, Tucker, and Zemlin tour-breaking constraints developed for the traveling salesman problem; (2) the use of ordered-area assignment variables based upon an extension of an approach by Cova and Church for the geographical site design problem; and (3) the use of flow constraints based upon an extension of work by Shirabe. We test the efficacy of each formulation as well as specify a strategy to reduce overall problem size. [ABSTRACT FROM AUTHOR]

Decisions regarding the location of motorway interchanges need to be made very carefully because of their economic and political implications. In this paper, we present three optimization models aimed at assisting road administrations when they deal with motorway interchange location problems. The decisions are assumed to be made from the perspective of road users, with the objective of minimizing travel costs. Two of the models are based on existing hub location models, whereas the third one is a new model. The usefulness of the models in real-world situations is illustrated with a case study involving A25, one of the most important Portuguese motorways. When applied to this case study, the new model performed in general clearly better than the other two. [ABSTRACT FROM AUTHOR]

Abstract: Accessibility to health facilities is a critical factor in effective health treatment for people in rural areas of lesser-developed countries. In many areas accessibility is diminished by the lack of all-weather roads, making access subject to weather conditions. Location–allocation models have been used to prescribe optimal configurations of health facilities in order to maximize accessibility, but these models are based on the assumption that the underlying transport network is static and always available. Essentially, past work has ignored the potential impacts of improvements to the transport system in modeling access. In this paper we propose a model that treats the opposite side of the location/transport equation; that is, a model that treats existing facility locations as fixed and improves health service accessibility by upgrading links of the transport network to all-weather roads. This new model, called the Maximal Covering Network Improvement Problem (MC-NIP) is formulated as an integer-linear programming problem. An application of the MC-NIP model to the Suhum District of Ghana is presented, which shows that even a modest level of road improvement can lead to substantial increases in all-season access to health service. [Copyright &y& Elsevier]

The article pays tribute to Dr. Charles S. ReVelle whose research contributions are extraordinary in terms of quantity, quality, diversity and impact.

Railroads represent one of the most efficient methods of long-haul transport for bulk commodities, from coal to agricultural products. Over the past 50 years, the rail network has contracted while tonnage has increased. Service, geographically, has been abandoned along short-haul routes and increased along major long-haul routes, resulting in a network that is more streamlined. The current rail network may be very vulnerable to disruptions, like the failure of a trestle. This paper proposes a framework to model rail network vulnerability and gives an application of this modeling framework in analyzing rail network vulnerability for the State of Washington. It concludes with a number of policy-related issues that need to be addressed in order to identify, plan, and mitigate the risks associated with the sudden loss of a bridge or trestle. [ABSTRACT FROM AUTHOR]

Many systems contain bottlenecks, critical linkages, and key facilities. Such components, when lost due to a man-made or natural disaster, may imperil a system in performing its intended function. This article focuses on reducing the impact of an intentional strike against a supply system where supply facilities can be fortified in order to prevent such events. It is assumed that fortification resources are limited and must be used in the most efficient manner. In a recent article, Church, Scaparra, and Middleton (2004) introduced the r-interdiction median problem, which can be used to identify the most important facilities in a supply system. In this article, we extend that model to address the option of fortifying such sites against possible interdiction. We present a new integer-linear programming model that optimally allocates fortification resources in order to minimize the impact of interdiction. Computational results are presented in using this model for several hypothetical problems. We also discuss the general properties of fortification and demonstrate that the presence of fortification can impact which system elements are considered critical. [ABSTRACT FROM AUTHOR]

Because the threat of habitat destruction can never be entirely eliminated, there is a legitimate concern that some reserve networks, especially highly complementary ones with minimal species overlap, may be predisposed to severe losses in species representation if one or more core reserve sites are destroyed. In order to address this problem in a systematic way, we propose the use of two different optimization models for designing complementary reserve networks that are also highly robust to possible site losses. Given limited budgets, the first maximizes expected species representation over all possible site loss patterns while the second maximizes a combination of representation given all sites and remaining representation following the worst-case loss of a restricted subset of reserve sites. By incorporating reserve loss in fundamentally different ways, these two models provide a range of options in terms of information requirements, assumptions about risk aversion, and structural complexity. We compare both of these methods to a more standard approach, which completely ignores the inherent risk posed by reserve site loss. Results confirm that significantly more robust solutions can be obtained for a marginal decrease in initial species representation within the reserve system. [Copyright &y& Elsevier]

Abstract: There has been much recent interest in the development of systematic reserve selection methods that are capable of incorporating uncertainty associated with site destruction. This paper makes a contribution to this line of research by presenting two different optimization models for minimizing species losses within a planning region. Given limited acquisition budgets, the first minimizes expected species losses over all possible site loss patterns outside the reserve network while the second minimizes maximum species losses following the worst-case loss of a restricted subset of nonreserve sites. By incorporating the uncertainty of site destruction directly into the decision planning process, these models allow a conservation planner to take a less defensive and more strategic view of reserve selection that seeks to minimize species losses through the targeted acquisition of high-value/high-risk sites. We compare both of these methods to a more standard approach, which simply maximizes within reserve representation without regard for the varied level of threat faced by different sites and species. Results on a realistic dataset show that significant reductions in species losses can be achieved using either of these more intelligent modeling frameworks. [Copyright &y& Elsevier]

One of the defining objectives in location science is to maximize dispersion. Facilities can be dispersed for a wide variety of purposes, including attempts to optimize competitive market advantage, disperse negative impacts, and optimize security. With one exception, all of the extant dispersion models consider only one type of facility, and ignore problems where multiple types of facilities must be located. We provide examples where multiple-type dispersion is appropriate and based on this develop a general class of facility location problems that optimize multiple-type dispersion. This family of models expands on the previously formulated definitions of dispersion for single types of facilities, by allowing the interactions among different types of facilities to determine the extent to which they will be spatially dispersed. We provide a set of integer-linear programming formulations for the principal models of this class and suggest a methodology for intelligent constraint elimination. We also present results of solving a range of multiple-type dispersion problems optimally and demonstrate that only the smallest versions of such problems can be solved in a reasonable amount of computer time using general-purpose optimization software. We conclude that the family of multiple-type dispersion models provides a more comprehensive, flexible, and realistic framework for locating facilities where weighted distances should be maximized, when compared with the special case of locating only a single type of facility. [ABSTRACT FROM AUTHOR]

The classical Location Set Covering Problem involves finding the smallest number of facilities and their locations so that each demand is covered by at least one facility. It was first introduced by Toregas in 1970. This problem can represent several different application settings including the location of emergency services and the selection of censers)alien sites. The Location Set Covering Problem can be formulated as a 0-1 integer-programming model. Both (1969) and Toregas and BeVelle (1973) developed reduction approaches thai can systematically eliminate redundant columns and rows as well as identify essential sites. Such approaches can often reduce a problem to a size that is considerably smaller and easily solved by linear programming using branch and bound. Extensions to the Location Set Covering Model have been proposed so thai additional levels of coverage are either encouraged or required. This paper focuses on one of the extended model forms called the Multi-level Location Set Covering Model. The reduction rules of Roth and of Toregas and BeVelle violate properties found in the multi-level model. This paper proposes a new set of reduction rules that can be used for the multi-level model as well as the classic single-level model. A demonstration of these new reduction rules is presented which indicates that such problems may be subject to significant reductions in both the numbers of demands as well as sites. [ABSTRACT FROM AUTHOR]

The p-median problem was first formulated as an integer-linear programming problem by ReVelle and Swain (1970) and further revised by Rosing, ReVelle and Rosing-Vogelaar (1979). These two forms have withstood the test of time, as they have been used by virtually everyone since then. We prove that a property associated with geographical proximity makes it possible to eliminate many of the model variables through a substitution process. This new substitution technique has resulted in the elimination of up to 60% of the variables needed in either of these classic model formulations. [ABSTRACT FROM AUTHOR]

Discusses some of the inherent problems associated with measuring accessibility for people on a landscape of surfaces, barriers and travel modes. Selection of the mitigation or renovation projects that yield the greatest increase in accessibility for people with disabilities; Application of relative access measurement; Equations for the estimation of job accessibility by transportation analysis zones.

Suggests an alternative to the process described by Ramu and Kennedy (1984) for selecting a solid-waste-disposal site. View that Ramu and Kennedy allow for sitting along any road linkage of the transportation network; View that the choice of site can be arrived at without recourse to heuristic solutions.

We deal with the problem of locating a point on a network so as to maximize the sum of its weighted distances to the nodes. It is shown that there is at least one optimal point in a finite set of points which can easily be generated. An algorithm is given for locating an optimal point in this set. When the network is a tree. this set consists of the "dangling" nodes. [ABSTRACT FROM AUTHOR]

Location-allocation models may be used to focus upon a multiplicity of factors potentially underlying settlement pattern development. We describe several such maximal covering models and their applicability in understanding the degree of political centralization in the Nile Valley during the Ramessid period (ca. 1317-1070 B.C.). The results of the covering models support the contention that the main objective of the Ramessid bureaucracy in choosing sites for administrative centers was to maximize control of the Nile Valley population and the agricultural labor power they provided, to supply much needed land rent-taxes to the royal coffers. Even when a premium is placed upon centrality (i.e., spatial coverage) at the expense of maximizing the population which could be served from a set of administrative centers, capitals of eight political subdivisions (nomes) appear consistently in the solution sets. Factors not accounted for in the covering model, such as trade routes and selected resource deposits, may account for the close spacing of three nome capitals. In general, the results of the covering models tend to minimize the administrative/economic role of several east-bank towns towards the middle of the study region and those near the Faiyum Depression. Covering models demonstrate that three other nome capitals which were of minor conse- quence during the Ramesside were also inefficientiy located. Two non-capital sites appeared consistently in the optimal sets of administrative centers. Both had a mayor in residence, supporting Butzer's contention that mayors may have been more important to the functional viability of administrative centers during the Ramessid period of the New Kingdom than the traditional nome structure, which had been in place from Old Kingdom times onward. The location-allocation mod- eling results reinforce many of the contentions of field archaeologists about the nature of Egyptian society. [ABSTRACT FROM AUTHOR]

This paper deals with the location of service facilities on a transportation network where the closest (in distance, time or cost) facility is known not to service some significant portion of demand. The concept of vector assignment of demand nodes to facilities is introduced to account for non closest facility service. A generalized formulation of the p-median problem incorporating vector assignment is presented. It is shown that an optimal solution to this vector assignment p-median problem exists which consists entirely of nodes of the graph; however, there may be more than one facility per node. Three different solution procedures are discussed for the vector assignment p-median problem. Computational experiments for three different moderately sized data sets give encouraging results. A locational example is included which gives a comparison of an optimal p-median solution and an optimal p-median solution with vector assignment. [ABSTRACT FROM AUTHOR]

Two SOLUTION procedures for stochastic median location problems have been described. The first is a heuristic, which is a modification of the exchange method; and the second is a bounding procedure based on the subgradient optimization of the Lagrangian dual. Computational results are presented which indicate that moderate sized stochastic median problems should be solvable in reasonable amounts of computational time. [ABSTRACT FROM AUTHOR]

Covering path problems date from the pioneering work of Current et al. (1984, 1985). Two basic forms were defined in their work: the shortest covering path problem and the maximal covering shortest path problem. These two problems differ in that one requires complete coverage by the defined path and the other involves determining path alternatives which cover as much as possible while keeping the path length as short as possible. The latter of these two problems, the maximal covering shortest path problem, embodies the two major goals in transit planning: that is, finding efficient paths which serve as many people as possible. Often transit routes are restricted to major road segments, and when that occurs, routes do not compete with one another unless they overlap along a street segment or at an intersection. In addition, coverage distances can be quite small, barely extending to other streets. Given this type of situation, Curtin and Biba (2011) developed a model called TRANSMax (Transit Route Arc-Node Service Maximization), which maximizes node and arc service, where service coverage is defined for only those street and node segments that are part of a route. They based their model on a structure first proposed by Vajda (1961) in formulating and solving the traveling salesman problem. Because of this structure, we demonstrate that it is possible that a route generated by their original TRANSMax model may not be Pareto optimal with respect to both distance and access. In this paper, we develop a flexible TRANSMax model formulation that finds Pareto Optimal solutions when the original form does not. We also present computational experience in solving this new model on the same street network of Curtin and Biba involving Richardson, Texas. This application allows us to make comparisons between this work and the original work of Curtin and Biba. Overall, we show that this new model can identify new, improved routes over the existing TRANSMax model. • Cities often use loops in designing tranist routes. • TRANSMax prevents loops from being employed even when it may be optimal to do so. • A new model is presented that allows for the flexibility of embedded loops. • Solutions to this new model are often better than the original TRANSMax model. [ABSTRACT FROM AUTHOR]

This paper presents an analysis of the effects of cognitive agents employing selfish routing behavior in traffic networks with linear latency functions. Selfish routing occurs when each agent traveling on a network acts in a purely selfish manner, therefore the Braess Paradox is likely to occur. The Braess Paradox describes a situation where an additional edge with positive capacity is added to a given network, which leads to higher total system delay. By applying the concept of cognitive agents, each agent is able to make a range of non-selfish and selfish decisions. In addition, each agent has to cope with uncertainty in terms of travel time information associated with the traffic system, a factor in real-world traffic networks. This paper evaluates the influence of travel time uncertainty, and possible non-selfish decisions of the agents on overall network delay. The results indicate that both non-selfish behavior and uncertainty have an influence on overall travel delay. In addition, understanding the influence of cognitive agents on delay can help to better plan and influence traffic flows resulting in "closer to optimal" flows involving overall lower delays. [ABSTRACT FROM AUTHOR]

The management of competing land uses is complicated by a range of issues and considerations. This is the case because of a concern for the long-term health of the earth and the obvious negative impacts of past and present human activities. Land use planning and management efforts have recognized this broader context and accordingly have devoted much care and attention to operational-level planning support. Spatial restrictions have long been recognized as central to limiting local impacts as well as ensuring landscape shape and structure irregularity. Unfortunately, planning to meet spatial restrictions may be disrupted, by fire, pests, or even on-the-ground conditions. For example, what if a fire destroys resources in a management unit that are adjacent to a unit(s) scheduled for harvest. In fact, this new opening/disruption may prevent the planned activity of any of its neighboring units. Disruptions do occur, but have rarely been addressed in any meaningful way in planning optimization problems. This paper details spatial optimization approaches to support better understanding of the range of potential outcomes when disruption and uncertainty are taken into account in land use planning involving forest resources. Application results highlight the significance of handling disruption risk and spatial data uncertainty, indicating that identifying and selecting planning alternatives that are consistent with goals and intended outcomes are a difficult task. However, improved modeling approaches are possible that better support land use decision making. [ABSTRACT FROM AUTHOR]

The article focuses on the opportunities to be used to overcome the difficulties of spatial optimization. It sates that various techniques are used to measure problems related to location, infrastructure design and transportation. With the advent of new optimization techniques, the spatial analysis and geographical research have helped collecting, managing and visualizing the required data. Geographic Information System (GIS) and Cyberinfrastructure computing have helped solving such issues.

After initial planning and implementation, many systems evolve as a byproduct of fragmented decision-making processes and incremental change over time, with little system-wide reanalysis. This lack of reevaluation means that an originally optimal system may become suboptimal with respect to demand to be served or service performance. Assessing system design and configuration provides an opportunity to enhance overall service quality as well as reduce operational costs. This paper uses location analytics, including spatial optimization and geographic information systems (GIS), to support system reassessment and planning efforts. A case study focused on wireless Internet access across a university campus is presented. The results suggest that there are varying levels of access to wireless service, this variation is driven in part by system history and fragmented decision-making processes, and there is an opportunity to significantly enhance the quality of service through planning efforts focused on optimal system reconfiguration. These findings highlight the importance of analytics based planning in design, modification, or extension of a spatial service system. • Formulates extension of maximal covering problem with service quality degradation. • Presents case study of wireless Internet access point placement. • System assessment and evaluation utility. • Demonstrates how reconfiguration can increase demand covered and/or reduce costs. [ABSTRACT FROM AUTHOR]

Covering models have been used in a wide range of modeling and geospatial analysis applications ranging from planning emergency services to natural reserve design. One topic in coverage modeling that has received considerable research attention is addressing uncertainty due to facility unavailability and service disruptions. In this article, we propose a covering model that maximizes the expected coverage of demand by considering the possibility of facility failures. Unlike existing models that assume a uniform failure probability across all sites in an area, the proposed model can account for spatially varying failure probabilities and describes better the underlying geographic processes that cause facility failures. The model is posed as a spatial optimization problem using integer linear programming. We compare two different formulations of the covering model and discuss their properties. The proposed model formulations have been tested computationally using a warning sirens data set that has been widely used in assessing covering models. We conclude with a summary of findings as well as possible directions of future research. [ABSTRACT FROM PUBLISHER]

One of the classic operations problems in forest management is the layout of a harvesting system. This paper addresses the design of a harvesting system in areas characterized by steep slopes requiring cable-based harvesting. Layout optimization often involves numerous potential cable alignments and a small number of potential landings. In this paper we develop a model that addresses steep slope conditions found in central Europe that involve a large number of potential landings and cable alignments. In addition we extend existing work by considering variable-length alternatives for each feasible cable alignment. We construct three models, one for single-length cable options and two for variable-length alternatives and test their efficacy in solving 18 different harvesting area problems. We show that one of the variable-length alternative models can be solved in computer times that are competitive with the single-length option model. Overall, the savings that can be attributed to variable-length options are modest, but the alignments found by the variable-length options models are more realistic from forest engineers' points of view, which will aid in its use and adoption. [ABSTRACT FROM AUTHOR]

Location covering problems are important tools for supporting facility siting decisions in both the natural and built environment. However, facility workloads often vary significantly using classic coverage modeling approaches, because service allocations are not explicitly considered. In addition to capacitated extensions that are traditionally relied on, an explicit way to balance workloads in coverage modeling is to track workload difference between pairs of sited facilities, with a goal of minimizing variation. Such an approach provides an effective way to consider workload equity, but a byproduct is increased complexity and computationally difficulty in solving associated models by exact methods. This paper proposes a heuristic algorithm to address the computational difficulties in balancing workloads in coverage modeling. The proposed algorithm incorporates interchange along with simulated annealing, taking advantage of problem-specific knowledge to derive high-quality solutions in an efficient manner. Empirical studies demonstrate that the proposed algorithm is able to generate non-dominated solutions that effectively approximate the Pareto optimal frontier, but do so in a computationally efficient manner. • Addresses facility workload equity issues in coverage modeling. • A bi-objective optimization model is formulated to consider workload balance. • An efficient heuristic algorithm is proposed to address the computational difficulties. • Application results demonstrate significance of workload balance issues. [ABSTRACT FROM AUTHOR]

Rail transportation has experienced a rebirth in the last few decades, and a very large investment will certainly be made in new railway lines in the years to come--especially in high-speed rail lines. The success of such investment is heavily dependent on rail ridership, which in turn is dependent on the location of railway stations. In this paper, we present a mixed-integer optimization model that determines the optimal location (and number) of stations along a railway line that will be introduced over an existing transportation network. The stations are chosen within a set of possible locations defined a priori according to the objective of maximizing travel cost savings. The model takes into account the sensitivity of rail ridership to time losses because of stops at intermediate stations, as well as (static) competition from other modes. The practical usefulness of the model is illustrated with a case study involving a high-speed rail line expected to be built in Portugal in the future: the Lisbon-Porto line. [ABSTRACT FROM AUTHOR]

The location of motorway interchanges strongly affects the traffic motorways can capture and therefore the revenues for the concessionaires. This paper presents a set of optimization models aimed at assisting toll-motorway concessionaires when they set up the location of interchanges for a new motorway. The decisions are assumed to be made with the objective of maximizing profit. Road users select their itineraries according to the attractiveness of the routes, which is measured by travel costs (vehicle operating costs, accident costs, user time costs, and tolling costs). The choice is between the existing road network and a combination of existing road segments with new motorway segments. A deterministic model and two stochastic models are proposed. The latter models take into account the risks involved in motorway investment decisions. The usefulness of the models is illustrated for a real case study. [ABSTRACT FROM AUTHOR]

Unmanned Aerial Vehicles, often called drones, have rapidly emerged for commercial and personal use in recent years. Drones are a promising and effective transportation mode because they can travel faster than traditional ground-based vehicles, particularly when obstacles limit quick response or in cases of congestion. An important consideration for drones is that travel times are impacted in various ways by real-time local conditions, including weather and terrain. While goods and supplies can be acquired at more traditional outlets (e.g., stores, warehouses, restaurants, hospitals, fire stations, etc.), drones are being increasingly relied upon to extend access, particularly for special services associated with food, drug, and equipment delivery. The reason is that they can reliably access almost anywhere, providing quick response without the need for more expensive (and larger) vehicles that are restricted to congested roadways. How to locate drone base stations and allocate service in order to optimize overall response is a challenging task, especially given spatiotemporal heterogeneity in distributed demand and service response times/costs that can vary over a day. This paper introduces an extension of p-median problem to aid in the deployment of a drone system that accounts for continuous planar travel costs. Results show that drone travel times can be significantly reduced across a region. A key feature in this work is the representation of both demand and flight trajectories across a continuous terrain. [ABSTRACT FROM AUTHOR]

An essential location analytic method is GIS, able to support map-based display along with geographic data creation, management, manipulation in addition to functions for suitability evaluation. Location models have proven to be critical as well, with many prominent approaches found in popular GIS software. This paper reviews a class of location models and provides an overview of the methods used to solve these models. This is significant because of the broad use and application of location models in GIS to address important problems and issues facing society. Spatial analytical insights are essential. The implications of models and methods available through GIS are explored, particularly notions of solution quality. Case studies are offered to highlight ease of access to location models in GIS along with observed computational performance. [ABSTRACT FROM AUTHOR]