Identifying Critical Facilities in Hub‐and‐Spoke Networks: A Hub Interdiction Median Problem

The hub location problem has been widely used in analyzing hub‐and‐spoke systems. The basic assumption is that a large number of demands exist to travel from origins to destinations via a set of intermediate transshipment nodes. These intermediate nodes can be lost, due to reasons such as natural disasters, outbreaks of disease, labor strikes, and intentional attacks. This article presents a hub interdiction median (HIM) problem. It can be used to identify the set of critical facilities in a hub‐and‐spoke system that, if lost, leads to the maximal disruption of the system's service. The new model is formulated using integer linear programming. Special constraints are constructed to account for origin‐to‐destination demand following the least‐cost route via the remaining hubs. Based on the HIM problem, two hub protection problems are defined that aim to minimize the system cost associated with the worst‐case facility loss. Computational experiment results are presented along with a discussion of possible future work. El problema de la ubicación de la central (hub) ha sido ampliamente analizado para el caso de los sistemas de sistemas radiales (hub‐and‐spoke). La presunción inicial es que existe un gran número de demandas que viajan desde puntos de origen hasta sus puntos de destino a través de un set de nodos intermedios de trasbordo. Estos nodos intermedios pueden perderse por diferentes motivos, como desastres naturales, brotes de enfermedades, huelgas de trabajadores, o ataques intencionales. Este artículo presenta un problema de tipo mediana de interdicción de hub, conocido como hub interdiction median‐HIM. Puede usarse para identificar un set de instalaciones críticas de un sistema tipo hub‐and‐spoke que, si se pierde, conduce a la máxima interrupción del servicio del sistema. El nuevo modelo se ha formulado utilizando programación entera lineal, (integer linear programming‐ILP). El modelo construye restricciones especiales para dar cuenta de la demanda de “origen‐a‐destino” (O‐D), siguiendo la ruta de menor costo, a través de los hubs restantes. Basándonos en el problema de HIM, se definen dos problemas de protección de hub que buscan minimizar el costo asociado al peor caso posible de pérdida de instalaciones. Se presentan además, resultados de experimentos computacionales, así como a una discusión sobre posibles futuros trabajos en la materia. 枢纽区位研究已广泛应用于中枢辐射型系统分析,其基本假设条件为起始点到目的地之间存在大量旅行需求的中间转运节点。但自然灾害、突发疾病、劳务罢工和蓄意攻击等因素可能导致中间转运节点的丧失。本文提出了一种枢纽封闭中心模型（HIM）,可用于识别中枢辐射型系统的重要节点,一旦这些节点丧失,将导致整个系统服务最大程度的瓦解。新模型通过整数线性规划公式建立。模型特殊约束条件的建立基于最小成本路径通过余下枢纽的花费来解释始发到目的地（ origin‐to‐destination）需求量。基于HIM问题,双枢纽保护问题被定义为旨在最小化系统花费及其与之关联的最坏情况下节点丢失问题。最后,根据计算的经验结果讨论未来可能深入的研究。     

Activity Levels at Hub Facilities in Interacting Networks

Hubs are a special type of central facility which are designed to act as switching points for intemodal flows. For instance, a set of ten interacting cities might all be connected to one of two major hubs. All flows between the cities would then be routed via the hubs. There is an obvious saving in the number of routes necessary to interconnect the cities when hubs are utilized, with a concomitant high level of activity at the facilities. This paper takes a heuristic approach to the evaluation of networks and hub locations to find locally optimal designs. It is shown that minimization of transportation costs may require assignment of nodes to a facility other than the nearest. A discount on the interhub transportation costs promotes a wider spacing of facilities. In a system with several hubs, minimization of total hub usage tends to concentrate demand very heavily into one central facility.     

Spatial Characteristics and Comparisons of Interaction and Median Clustering Models

Cluster analysis has been pursued from a number of directions for identifying interesting relationships and patterns in spatial information. A major emphasis is currently on the development and refinement of optimization‐based clustering models for the purpose of exploring spatially referenced data. Within this context, two basic methods exist for identifying clusters that are most similar. An interesting feature of these two approaches is that one method approximates the relationships inherent in the other method. This is significant given that the approximation approach is invariably utilized for cluster detection in spatial and aspatial analysis. A number of spatial applications are investigated which highlight the differences in clusters produced by each model. This is an important contribution because the differences are in fact quite significant, yet these contrasts are not widely known or acknowledged.     

Testing Policy Theory with Statistical Models of Networks

This article presents a conceptual framework for clarifying the network hypotheses embedded in policy theories and how they relate to macrolevel political institutions and microlevel political behavior. We then describe the role of statistical models of networks for testing these hypotheses, including the problem of operationalizing theoretical concepts with the parameters of statistical models. Examples from existing theories of the policy process and empirical research are provided and potential extensions are discussed.     

A Note on Trip Benefits in Spatial Interaction Models

We extend the well-known transport users' benefits measure (TUB) for the doubly-constrained spatial interaction model derived by Williams (1976). The original formula expresses the TUB as composed by two terms associated with the origin and the destination zones. First, the TUB is associated here with trips instead of zones, providing a natural interpretation as a rule-of-a-half measure of benefit under inelastic demand (for the short-run case). Second, a TUB formula for the long-run case is derived, that is, when the total number of trips, trip origins, and trip destinations change. We then propose updated measures of accessibility for location behavior.     

Dynamic Models of Agricultural Location in a Spatial Interaction Framework

Recent research demonstrates that spatial interaction models may also be made to function as location models by the addition of appropriate hypotheses about structural adjustment. An appealing feature of the approach is that dynamics are explicitly incorporated. In this paper, the attempt is made to recast a problem from classical economic-geographic theory—that of agricultural location—within a spatial interaction framework. It is shown that a wide variety of models is potentially available, and the properties of a range of these models are selectively explored.     

Using Simple Genetic Algorithms to Calibrate Spatial Interaction Models

The paper investigates the use of two genetic algorithms in an attempt to obtain globally optimal parameter estimates for a mix of simple and complex spatial interaction models. The genetic algorithms work well and are strongly advocated as a more robust approach particularly for use with the more complex multiparameter models where the differences in both performance and parameter values are judged to be significant.     

A New Method of Adaptive Zoning for Spatial Interaction Models

Spatial interaction models commonly use discrete zones to represent locations. The computational requirements of the models normally arise with the square of the number of zones or worse. For computationally intensive models, such as land use–transport interaction models and activity‐based models for city regions, this dependency of zone size is a long‐standing problem that has not disappeared even with increasing computation speed in PCs—it still forces modelers to compromise on the spatial resolution and extent of model coverage as well as on the rigor and depth of model‐based analysis. This article introduces a new type of discrete zone system, with the objective of reducing the time for estimating and applying spatial interaction models while maintaining their accuracy. The premise of the new system is that the appropriate size of destination zones depends on the distance to their origin zone: at short distances, spatial accuracy is important and destination zones must be small; at longer distances, knowing the precise location becomes less important and zones can be larger. The new method defines a specific zone map for every origin zone; each origin zone becomes the focus of its own map, surrounded by small zones nearby and large zones farther away. We present the theoretical formulation of the new method and test it with a model of commuting in England. The results of the new method are equivalent to those of the conventional model, despite reducing the number of zone pairs by 96% and the computation time by 70%. Los modelos de interacción espacial suelen utilizar zonas discretas para representar áreas o puntos de interés. Los requisitos computacionales de estos modelos normalmente aumentan a razón del número de zonas elevadas al cuadrado o más. Para modelos computacionalmente intensivos como los modelos de interacción entre uso de suelo y transporte y los modelos basados en actividades para ciudades‐región, el impacto del tamaño de la zona es un problema persistente no superado aun. Esta limitación persiste a pesar de los grandes avances en la velocidad de procesamiento en computadoras, pues obliga a los modeladores a hacer concesiones entre la resolución espacial y la extensión que abarca el modelo, así como en el rigor y profundidad del análisis. En este artículo se presenta un nuevo tipo de sistema de zonas discretas que: a) tienen como objetivo reducir el tiempo de estimación de la aplicación de modelos de interacción espacial; y b) al mismo tiempo mantienen su nivel de precisión. La premisa que gobierna este nuevo sistema es que el tamaño apropiado de las zonas de destino depende de la distancia a su zona de origen: a distancias cortas, la precisión espacial es importante y las zonas de destino deben ser pequeño; a distancias mas largas, conocer la ubicación precisa es progresivamente menos importante y las zonas pueden ser mayores. El nuevo método define un mapa específico de zonas para cada zona de origen; cada zona de origen se convierte en el foco de su propio mapa, rodeada de zonas cercanas pequeñas y zonas grandes a mayor distancia. El estudio presenta la formulación teórica del nuevo método y su demostración vía un modelo de desplazamientos residencia‐trabajo en Inglaterra. Los resultados del nuevo método son equivalentes a las del modelo convencional, a pesar de reducir del número de pares de zonas en un 96% y el tiempo de cálculo en un 70%. 空间相互作用模型通常采用离散区域代表区位。模型的计算量往往与区域数量呈平方甚至更高阶增长。对于可计算的精细模型,如土地利用‐交通相互作用模型和基于行为的城市区域模型,区域尺度的依赖性是长期存在的问题,即使计算机的计算速度增加,该问题仍无法消除。因此,建模者需在模型空间分辨率和覆盖范围以及模型分析的严谨性和深度上做出权衡。本文介绍了一种新型的离散分区系统,目的在于减少空间相互作用模型估算和计算时间,同时维持其精度。新系统的前提是目标区域的适当尺度取决于与初始区域的距离：在短距离范围内,空间精确性是重要的,且目标区域必须是小的;在更远距离上,位置精度的重要性降低,目标区域可以变大。该方法为每个初始区域制定了具体的尺度地图。每个初始区域成为其自身地图的中心,被近邻的小区域和更远距离的大区域所包围。本文给出了新方法的理论公式,并以英格兰地区的通勤模型进行检验。结果显示,尽管区域对的数量减少了96%,计算时间缩短了70%,但新方法的计算结果等效于常规模型。     

Explorations and Syntheses of Linear Programming And Spatial Interaction Models of Residential Location

Various “linear programming” models of residential location are explored in some detail. It is then shown that entropy maximizing “sub-optimal” versions of these can be developed, which may be more realistic at typical levels of resolution used for analysis but can still be given some of the interpretations of the programming models. Further, any programming model can be seen as a limiting case of some entropy maximizing model in which some of the parameters tend to infinity. Some empirical tests of both kinds of models are presented, and the limiting relationships are discussed.     

Analysis of Dynamic Spatial Interaction Models by Means of Optimal Control

This paper deals with the design of general classes of dynamic spatial interaction models. On the basis of a general (well-behaved) multiperiod objective function and of a dynamic model representing the evolution of a spatial interaction system, an optimal control model is constructed. Particular attention is given to the equilibrium and stability conditions. It turns out that it is possible to identify steady-state solutions for a dynamic spatial interaction model. Furthermore, it can also be demonstrated that the entropy model is a specific case of this spatial interaction system. A simple illustration for urban dynamics is given as well.     

Connecting Points to Spatial Networks: Effects on Discrete Optimization Models

To accommodate network allocation, population polygons are frequently transformed into singular, weighted centroids which are then integrated into the network either by snapping each centroid to the nearest network segment or by generating an artificial connector that becomes part of the network. In this article, an investigation of the connection method of network allocation is undertaken with two primary foci: (1) how the density of centroid connectors effects travel cost along the network; and (2) how the algorithms utilized to determine the placement of connectors are affected by the density of connectors. We hypothesize that both issues have an effect on network travel cost and, therefore, on network-based modeling. These hypotheses are tested on three nested spatial networks in the New England region of the United States. Two fundamental facility location models, the p-median problem, and p-center problem, are solved at each spatial extent while varying the density of connectors from one to four. When generating more than one connector thought must be given to the method of connection, the angle of dispersion, the acceptable tolerance of connector length, segment crossing, and saturated connectivity. A novel and thorough framework is proposed to address these concerns.     

Integration Processes in European Research and Development: A Comparative Spatial Interaction Approach Using Project Based Research and Development Networks,Co‐Patent Networks and Co‐Publication Networks

This study focuses on integration processes in European Research and Development (R&D) by analyzing the spatiotemporal dimension of three different R&D collaboration networks across Europe. The studied networks cover different types of knowledge creation, namely project‐based R&D networks within the European Union (EU) Framework Programmes (FPs), co‐patent networks, and co‐publication networks. Integration in European R&D—one of the main pillars of the EU Science Technology and Innovation policy—refers to the harmonization of fragmented national research systems across Europe and to the free movement of knowledge and researchers. The objective is to describe and compare spatiotemporal patterns at a regional level and to estimate the evolution of separation effects over the time period 1999–2006 that influence the probability of cross‐region collaborations in the distinct networks under consideration. The study adopts a spatial interaction modeling perspective, econometrically specifying a panel generalized linear model relationship, taking into account spatial autocorrelation among flows using eigenfunction spatial filtering methods. The results show that geographical factors are a lower hurdle for R&D collaborations in the FP networks than in co‐patent networks and co‐publication networks. Furthermore, it is shown that the geographical integration is higher in the FP network.     

Learning in Single Hidden-Layer Feedforward Network Models: Backpropagation in a Spatial Interaction Modeling Context

Learning in neural networks has attracted considerable interest in recent years. Our focus is on learning in single hidden-layer feedforward networks which is posed as a search in the network parameter space for a network that minimizes an additive error function of statistically independent examples. We review first the class of single hidden-layer feedforward networks and characterize the learning process in such networks from a statistical point of view. Then we describe the backpropagation procedure, the leading case of gradient descent learning algorithms for the class of networks considered here, as well as an efficient heuristic modification. Finally, we analyze the applicability of these learning methods to the problem of predicting interregional telecommunication flows. Particular emphasis is laid on the engineering judgment, first, in choosing appropriate values for the tunable parameters, second, on the decision whether to train the network by epoch or by pattern (random approximation), and, third, on the overfitting problem. In addition, the analysis shows that the neural network model whether using either epoch-based or pattern-based stochastic approximation outperforms the classical regression approach to modeling telecommunication flows.     

Building an Automated Modeling System to Explore a Universe of Spatial Interaction Models

A methodology is described for harnessing the power of supercomputer hardware to build an automated modeling system. The problems of applying this new approach to mathematical modeling in geography are discussed by reference to the design of better performing spatial interaction models. It is also possible that the results may provide clues about new theories and knowledge.