A branch-and-cut algorithm for the partitioning-hub location-routing problem
A branch-and-cut algorithm for the partitioning-hub location-routing problem
复制标题
一种解决分区集线器位置路由问题的分支剪切算法
DOI：
10.1016/j.cor.2010.07.014
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
F. A. Özsoy
中科院分区：
文献类型：
--
作者：
D. Catanzaro;É. Gourdin;M. Labbé;F. A. Özsoy
我们介绍了划分-枢纽-位置-路线问题(PHLRP)，这是一个涉及图划分和路线特征的枢纽选址问题。PHLRP包括将给定网络划分为子网络，在每个子网络中定位至少一个集线器，并以最低成本在网络内对流量进行路由。这一问题在部署称为中间系统-中间系统(ISIS)的互联网路由协议以及LTL地面货运配送系统的战略规划中得到了应用。我们提出了一个整数规划(IP)模型来精确地求解PHLRP，并探索了可能的有效的不等式来加强它。计算实验证明了该模型的有效性，该模型能够处理包含多达20个顶点的PHLRP实例。
We introduce the Partitioning-Hub-Location-Routing Problem (PHLRP), a hub location problem involving graph partitioning and routing features. The PHLRP consists of partitioning a given network into sub-networks, locating at least one hub in each sub-network and routing the traffic within the network at minimum cost. This problem finds applications in deployment of an Internet Routing Protocol called Intermediate System–Intermediate System (ISIS), and strategic planning of LTL ground freight distribution systems. We present an Integer Programming (IP) model for solving exactly the PHLRP and explore possible valid inequalities to strengthen it. Computational experiments prove the effectiveness of our model which is able to tackle instances of PHLRP containing up to 20 vertices.