Analytical and empirical comparison of integer programming formulations for a partitioning-hub location-routing problem

We introduce 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 introduce three Integer Programming (IP) formulations for solving PHLRP. We compare, both analytically and empiri-cally, these formulations with each other in order to identify the best-performing one among the three.