Design of hub systems in the transportation network

Abstract

The first model considered the single allocation problem in the two-hub network. We transform the quadratic 0-1 integer program of the problem into a linear program and show that all extreme points of the polytope defined by the LP are integral. We also remark that it can be transformed into a minimum cut problem. As a result, we can observe that the two-hub location problem cab be solved in polynomial time. The second model considers the single allocation problem in the three-hub network. We show that the single allocation problem of p-hub network is NP-hard as soon as the number of hubs is three. We provide a mixed integer formulation and consider the polyhedral properties of it. Next, we also provide another mixed integer formulation which can be used for the cases where the number of hubs are more than three. The final model considers the multiple allocation problems in the p-hub network. We observe that the multiple allocation problem with no fixed costs can be solved efficiently by using the shortest path algorithm. We also observe that the multiple allocation problem with fixed costs for opening links can be thought as one of the uncapacitated network design problem. We modify the formulation of uncapacitated network design problem to be appropriate to our problem and show that when the number of hubs is two the LP relaxation of it provides integral optimal solutions. We also provide another mixed integer formulation based on path.