A branch-and-cut algorithm for the partitioning-hub location-routing problem

被引：44

作者：

Catanzaro, Daniele ^{[1
]}

Gourdin, Eric ^{[2
]}

Labbe, Martine ^{[1
]}

Ozsoy, F. Aykut ^{[1
]}

机构：

[1] ULB, Dept Comp Sci, B-1050 Brussels, Belgium

[2] CORE TPN TRM, Res & Dev, Orange Labs, F-92794 Issy Les Moulineaux, France

来源：

COMPUTERS & OPERATIONS RESEARCH | 2011年 / 38卷 / 02期

关键词：

Size constrained clique partitioning; Graph partitioning; Communication networks; Hub-location; Branch-and-cut;

D O I：

10.1016/j.cor.2010.07.014

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：539 / 549

页数：11

共 11 条

[1] Network hub location problems: The state of the art [J].