A Branch-and-cut Algorithm for the Hub Location and Routing Problem

Cataloged from PDF version of article.We consider the Partitioning-Hub-Location-Routing Problem (PHLRP), a hub location problem involving graph partitioning and routing features. 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 describe an Integer Programming (IP) formulation for solving PHLRP. We also explore some valid inequalities for the IP formulation, which we take from the graph partitioning literature. We test effectiveness of the IP formulation and the valid inequalities. Our experiments show that the valid inequalities perform better than the XPRESS proprietary cuts