Heuristics for Hub Location Problems with Alternative Capacity Levels and Allocation Constraints

摘要

We consider the hub location problem in which the capacity of a hub restricts the amount of traffic transiting through the hub, the capacity of a hub is a decision variable, and each non-hub can only be allocated to a certain number of hubs. The objective is to determine the number of hubs, to locate the hubs, to determine the capacity level of each hub, to allocate the non-hubs to the hubs, and to determine the path for each origin-destination pair such that the total cost is minimized. Two heuristics based on the threshold accepting method are proposed to resolve this type of hub location problems. Computational characteristics of the proposed heuristics are evaluated through computational experiments using the modified CAB and AP data sets.