A Hierarchical Approach to the Capacitated Single Allocation p-Hub Median Problem with Direct Shipment

In this paper we consider a capacitated single allocation p-hub median problem with direct shipment (CSApHMPwD). We determine the location of p hubs, the allocation of non-hub nodes to hubs, and direct shipment paths in the network. This problem is formulated as 0-1 integer programming model with the objective of the minimum total transportation cost and the fixed cost associated with the establishment of hubs. An optimal solution is found using CPLEX for the small sized problems. Since the CSApHMPwD is NP-hard, it is difficult to obtain optimal solution within a reasonable computational time. Therefore, an ant colony optimization algorithm is developed which solves hub selection and node allocation problem hierarchically. Its performance is examined through a comparative study. The experimental results show that the proposed ant colony optimization algorithm can be a viable solution method for the capacitated hub and spoke network design problem.