Volume 2 Issue 3 pp. 671-688 Summer, 2011


A multi-objective imperialist competitive algorithm for a capacitated hub covering location problem


M. Mohammadi, R. Tavakkoli-Moghaddam , H. Rostami


The hub location problem appears in a variety of applications, including airline systems, cargo delivery systems and telecommunication network design. Hub location problems deal with finding the location of hub facilities and the allocation of demand nodes to these located hub facilities. In this paper, a new model for the capacitated single allocation hub covering location problem is presented. Instead of using capacity constraints to limit the amount of flow received by the hubs, the second objective function is introduced to minimize service times in the hubs. The service time in the hubs includes the waiting time of received flows in a queue and the time to get services. Due to the NP-hardness of the problem, a new weight-based multi-objective imperialist competitive algorithm (MOICA) is designed to find near-optimal solutions. To validate the performance of the proposed algorithm, the solutions obtained by the MOICA are compared by the exact solutions of the mathematical programming model.


DOI: 10.5267/j.ijiec.2010.08.003

Keywords: Hub covering location, Multi-objective problem, Capacitated single allocation Service time, Imperialist competitive algorithm
References

Alumur, S., Kara, B.Y. (2009). The design of single allocation incomplete hub networks. Transportation Research Part B, 43 (10), 936–951.

Atashpas-Gargari E. and Lucas C. (2007). Colonial competitive algorithm. IEEE Congress on Evolutionary Computation.

Aykin T. (1994). Lagrangean relaxation based approaches to capacitated hub-and-spoke network design problems. European Journal of Operational Research, 79, 501–523.

Aykin T. (1988). On the location of hub facilities. Transportation Science, 22 (2), 155–157.

Boland, N., Krishnamoorthy, M., Ernst, A., T., Ebery, J. (2004). Preprocessing and cutting for multiple allocation hub location problems. European Journal of Operational Research, 155 (3), 638–653.

Campbell, J.F. (1994). Integer programming formulations of discrete hub location problems. European Journal of Operational Research, 72, 387–405.

Campbell, J.F. (1996). Hub location and the p-hub median problem. Operations Research, 44 (6), 923–935.

Campbell, J.F., Ernst, A.T., Krishnamoorthy, M. (2002). Hub location problems. In: Z. Drezner and H. Hamacher (Eds.), Facility location: Applications and theory. Berlin: Springer, 373–406.

Campbell, J.F., Ernst, A.T., Krishnamoorthy, M. (2005). Hub arc location problems: part I – introduction and results. Management Science, 51 (10), 1540–1555.

Contreras, I., Fernández, E., Marín, A. (2009a). Tight bounds from a path based formulation for the tree of hub location problem. Computers & Operations Research, 36 (12), 3117–3127.

Contreras, I., Díaz, J., Fernández, E. (2009b). Lagrangean relaxation for the capacitated hub location problem with single assignment. OR Spectrum, 31 (3), 483–505.

Contreras, I., Fernández, E., Marín, A. (2010). The tree of hubs location problem. European Journal of Operational Research, 202 (2), 390–400.

Costa, M., Captivo, M., Clímaco, J. (2008). Capacitated single allocation hub location problem – a bi-criteria approach. Computers & Operations Research, 35 (11), 3671–3695.

Ebery, J., Krishnamoorthy, M., Ernst, A.T., Boland, N. (2000). The capacitated multiple allocation hub location problems: formulations and algorithms. European Journal of Operational Research, 120, 614–31.

Ernst, A.T., Krishnamoorthy. M. (1996). Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location Science, 4 (3), 139–54.

Ernst, A.T., Krishnamoorthy, M. (1996). An exact solution approach based on shortest paths for p-hub median problems. INFORMS Journal on Computing, 10 (2),149–62.

Ernst, A.T., Krishnamoorthy, M. (1998). Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem. European Journal of Operational Research, 104, 100–12.

Ernst, A.T., Krishnamoorthy, M. (1999). Solution algorithms for the capacitated single allocation hub location problem. Annals of Operations Research, 86, 141–59.

Ernst, A.T., Jiang, H., Krishnamoorthy, M. (2005). Reformulations and computational results for uncapacitated single and multiple allocation hub covering problems. Unpublished Report, CSIRO Mathematical and Information Sciences, Australia.

Jabal-Ameli, M.S., Aryanezhad, M.B., Ghaffari-Nasab, N. (2011). A variable neighborhood descent based heuristic to solve the capacitated location-routing problem. International Journal of Industrial Engineering Computations, 2, 141–154.

Kara, B.Y., Tansel, B.C. (2003). The single-assignment hub covering problem: Models and linearizations. Journal of the Operational Research Society, 54, 59–64.

Labbe´, M., Yaman, H. (2004). Projecting flow variables for hub location problems. Networks, 44 (2), 84–93.

Malekinezhad, A., Shirazi, E., Aryanezhad, M., B. (2011). A multi-objective set covering problem: A case study of warehouse allocation in truck industry. Management Science Letters, 1, 73–80.

Marin, A. (2005). Formulating and solving splittable capacitated multiple allocation hub location problems. Computers & Operational Research, 32 (12), 3093–3109.

Montgomery DC (2000). Design and analysis of experiments, 5th edn. Wiley, London.

Nickel, S., Schobel, A., Sonneborn, T. (2001). Hub location problems in urban traffic networks. In: Niittymaki, J., Pursula, M. (Eds.), Mathematics Methods and Optimization in Transportation Systems. Kluwer Academic Publishers, 1–12.

O’Kelly ME. (1987). A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, 32, 393–404.

O’Kelly, M.E., Skorin-Kapov, D., Skorin-Kapov, J. (1995). Lower bounds for the hub location problem. Management Science, 41 (4), 713–721.

Skorin-Kapov, D., Skorin-Kapov, J., O’Kelly, M. (1996). Tight linear programming relaxations of uncapacitated p-hub median problems. European Journal of Operational Research, 94, 582–593.

Yaman, H. Star p-hub median problem with modular arc capacities. (2008). Computers & Operations Research, 35 (9), 3009–3019.