Premium
Solving the hub location problem in a star–star network
Author(s) -
Labbé Martine,
Yaman Hande
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20193
Subject(s) - lagrangian relaxation , node (physics) , star (game theory) , routing (electronic design automation) , computer science , set (abstract data type) , heuristic , computer network , terminal (telecommunication) , star network , relaxation (psychology) , a* search algorithm , spoke hub distribution paradigm , topology (electrical circuits) , mathematical optimization , mathematics , network topology , engineering , transport engineering , algorithm , artificial intelligence , combinatorics , ring network , mathematical analysis , social psychology , psychology , structural engineering , programming language
We consider the problem of locating hubs and assigning terminals to hubs for a telecommunication network. The hubs are directly connected to a central node and each terminal node is directly connected to a hub node. The aim is to minimize the cost of locating hubs, assigning terminals and routing the traffic between hubs and the central node. We present two formulations and show that the constraints are facet‐defining inequalities in both cases. We test the formulations on a set of instances. Finally, we present a heuristic based on Lagrangian relaxation. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008