Identifying Critical Facilities in Hub‐and‐Spoke Networks: A Hub Interdiction Median Problem1. Issue 2 (10th April 2013) - Lei, Ting L.
<x xml:space="preserve">Abstract</x> 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问题，双枢纽保护问题被定义为旨在最小化系统花费及其与之关联的最坏情况下节点丢失问题。最后，根据计算的经验结果讨论未来可能深入的研究。