A linear program for the two-hub location problem

✍ Scribed by Jinhyeon Sohn; Sungsoo Park

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 372 KB
• Volume: 100
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(96)00233-0

✦ Synopsis

This paper considers the discrete two-hub location problem. We need to choose two hubs from a set of nodes. The remaining nodes are to be connected to one of the two hubs which act as switching points for intemodal flows. A configuration which minimizes the total flow cost needs to be found. We show that the problem can be solved in polynomial dme when the hub locations are fixed. Since there are at most ½n(n-1) ways to choose the hub locations, the two-hub location problem can be solved in polynomial time. We transform the quadratic 0-1 integer program of the single allocation problem in the fixed two-hub system into a linear program and show that all extreme points of the polytope defined by the LP are integral. Also, the problem can be transformed into a minimum cut problem which can be solved efficiently by any polynomial time algorithm.