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

Abstract:

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.

• Periodical: Applied Mechanics and Materials (Volumes 209-211)
• Pages: 807-813
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.209-211.807
• Online since: October 2012
• Authors: Ji Ung Sun*, Don Ki Baek
• Keywords: Ant Colony Optimization (ACO), Direct Shipment, P-Hub Median Problem

References

[1] J. F. Campbell: Integer programming formulations of discrete hub location problems. European Journal of Operational Research. Vol. 72 (1994), p.387~405.

DOI: 10.1016/0377-2217(94)90318-2

[2] P. Hasan and J. Vaidyanathan: A multi commodity, multi plant, capacitated facility location problem: formulation and efficient heuristic solution. Computers & Operations Research. Vol. 25 (1998), p.869~878.

DOI: 10.1016/s0305-0548(97)00096-8

[3] J. Ebery, M. Krishnamoorthy, A. Ernst and N. Boland: The capacitated multiple allocation hub location problem: Formulations and algorithms. European Journal of Operational Research. Vol. 120 (2000), p.614~631.

DOI: 10.1016/s0377-2217(98)00395-6

[4] S. Chamberland, B. Sanso and O. Marcotte: Topological design of two-level telecommunication networks with modular switches. Operations Research. Vol. 48 (2000), p.745~760.

DOI: 10.1287/opre.48.5.745.12412

[5] A. Ernst and M. Krishnamoorthy: Solution algorithms for the capacitated single allocation hub location problem. Annals of Operations Research. Vol. 86 (1999), p.141~159.

[6] M. Randall: Solution approaches for the capacitated single allocation hub location problem using ant colony optimization. Computational Optimization and Applications. Vol. 39 (2008), p.239~261.

DOI: 10.1007/s10589-007-9069-1

[7] K. Lumsden, F. Dallari and R. Ruggeri: Improving the efficiency of the hub and spoke system for the SKF European distribution network. International Journal of Physical Distribution & Logistics Management. Vol. 29 (1999), p.50~64.

DOI: 10.1108/09600039910253878

[8] T. Aykin: The hub location and routing problem. European Journal of Operational Research. Vol. 83 (1995), p.200~219.

DOI: 10.1016/0377-2217(93)e0173-u

[9] G. Zpfel and M. Wasner: Planning and optimization of hub-and-spoke transportation network of cooperative third-party logistics providers. International Journal of Production Economics, European Journal of Operational Research. Vol. 78 (2002).

DOI: 10.1016/s0925-5273(00)00152-3

[10] S. Elhedhli and F.X. Hu: Hub-and-spoke network design with congestion. Computers & Operations Research. Vol. 32 (2005), p.1615~1632.

DOI: 10.1016/j.cor.2003.11.016

[11] M. Dorigo and T. , in: Ant Colony Optimization, MIT Press, Boston. (2004).

[12] C.T. Su and J.T. Wong: Integrating ant colony optimization and genetic algorithms to solve uncapacitated single allocation p-hub median problem. Journal of the Chinese Institute of Transportation. Vol. 16 (2004), p.99~114.

[13] J.E. Beasley: Or-Library: Distributing test problems by electronic mail. Journal of the Operational Research Society. Vol. 41 (1990), p.1069~1072.

DOI: 10.1057/jors.1990.166