Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-26T08:44:50.904Z Has data issue: false hasContentIssue false
  • English
  • Français

Hybrid ant colony optimization for capacitated multiple-allocation cluster hub location problem

Published online by Cambridge University Press:  14 August 2017

Mohammad Mirabi  and
Parya Seddighi
Mohammad Mirabi*
Affiliation:
Industrial Engineering Group, Department of Engineering, Ayatollah Haeri University of Meybod, Meybod, Iran
Parya Seddighi
Affiliation:
Department of Industrial Engineering, Eyvanekey Institute of Higher Education, Eyvanekey, Iran
*
Reprint requests to: Mohammad Mirabi, Industrial Engineering Group, Department of Engineering, Ayatollah Haeri University of Meybod, Meybod, Iran. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The hub location problems involve locating facilities and designing hub networks to minimize the total cost of transportation (as a function of distance) between hubs, establishing facilities and demand management. In this paper, we consider the capacitated cluster hub location problem because of its wide range of applications in real-world cases, especially in transportation and telecommunication networks. In this regard, a mathematical model is presented to address this problem under capacity constraints imposed on hubs and transportation lines. Then, a new hybrid algorithm based on simulated annealing and ant colony optimization is proposed to solve the presented problem. Finally, the computational experiments demonstrate that the proposed heuristic algorithm is both effective and efficient.

Keywords

Ant Colony OptimizationCluster Hub LocationSimulated AnnealingTelecommunication NetworkTransportation Network
Type
Regular Articles
Information
AI EDAM , Volume 32 , Issue 1 , February 2018 , pp. 44 - 58
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Abdinnour-Helm, S. (1998). A hybrid heuristic for the un-capacitated hub location problem. European Journal of Operational Research 106(2–3), 489–499.Google Scholar
Abdinnour-Helm, S., & Venkataramanan, M.A. (1998). Solution approaches to hub location problems. Annals of Operations Research 78, 31–50.Google Scholar
Alumur, S., & Kara, B.Y. (2008). Network hub location problems: the state of the art. European Journal of Operational Research 190, 1–21.Google Scholar
Bailey, A., Ornbuki-Berrnan, B., & Asobiela, S. (2013). Discrete PSO for the uncapacitated single allocation hub location problem. Proc IEEE Workshop on Computational Intelligence in Production and Logistics Systems, CIPLS, pp. 92–98, Singapore, April 16–19.Google Scholar
Blum, C. (2005). Ant colony optimization: introduction and recent trends. Physics of Life Reviews 2, 353–373.Google Scholar
Calık, H., Alumur, S.A., Kara, B.Y., & Karasan, O.E. (2009). A tabu-search based heuristic for the hub covering problem over incomplete hub networks. Computers and Operations Research 36(12), 3088–3096.CrossRefGoogle Scholar
Campbell, J.F. (1992). Location and allocation for distribution systems with transshipments and transportation economies of scale. Annals of Operations Research 40, 77–99.CrossRefGoogle Scholar
Campbell, J.F., Ernst, A.T., & Krishnamoorthy, M. (2002). Hub location problems. In Facility Location: Applications and Theory (Drezner, Z., & Hamacher, H.W., Eds.), pp. 373–408. New York: Springer.Google Scholar
Chen, J.F. (2007). A hybrid heuristic for the un-capacitated single allocation hub location problem. Omega 35, 211–220.Google Scholar
Chen, J.F. (2013). Heuristics for hub location problems with alternative capacity levels and allocation constraints. In Intelligent Computing Theories (Huang, D.-S., Bevilacqua, V., Figueroa, J.C., & Premaratne, P., Eds.), LNCS Vol. 7995, pp. 207–216. Berlin: Springer.CrossRefGoogle Scholar
Contreras, I., Cordeau, J.-F., & Laporte, G. (2012). Exact solution of large-scale hub location problems with multiple capacity levels. Transportation Science 46(4), 439–459.CrossRefGoogle Scholar
Contreras, I., Díaz, J.A., & Fernández, E. (2011). Branch and price for large-scale capacitated hub location problems with single assignment. INFORMS Journal on Computing 23(1), 41–55.Google Scholar
Correia, I., Nickel, S., & Saldanha-da-Gama, F. (2010). The capacitated single-allocation hub location problem revisited: a note on a classical formulation. European Journal of Operational Research 207(1), 92–96.Google Scholar
Correia, I., Nickel, S., & Saldanha-da-Gama, F. (2014). Multi-product capacitated single-allocation hub location problems: Formulations and inequalities. Networks and Spatial Economics 14(1), 1–25.Google Scholar
Cunha, C.B., & Silva, M.R. (2007). A genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil. European Journal of Operational Research 179, 747–758.Google Scholar
Damgacioglu, H., Dinler, D., Ozdemirel, N.E., & Iyigun, C. (2015). A genetic algorithm for the uncapacitated single allocation planar hub location problem. Computers & Operations Research 62, 224–236.Google Scholar
Dorigo, M., Di Caro, G., & Gambardella, L.M. (1999). Ant algorithms for discrete optimization. Artificial Life 5(2), 137–172.Google Scholar
Dorigo, M., & Gambardella, L.M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1(1), 53–66.CrossRefGoogle Scholar
Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. Cambridge, MA: MIT Press.Google Scholar
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–112.CrossRefGoogle Scholar
Ernst, A.T., & Krishnamoorthy, M. (1999). Solution algorithms for the capacitated single allocation hub location problem. Annals of Operations Research 86, 141–159.Google Scholar
Farahani, R.Z., Hekmatfar, M., Arabani, A.B., & Nikbakhsh, E. (2013). Hub location problems: a review of models, classification, solution techniques, and applications. Computers & Industrial Engineering 64(4), 1096–1109.Google Scholar
Gelareh, S. (2008). Hub location models in public transport planning . PhD Thesis. University of Kaiserslautern.Google Scholar
Geramianfar, R., Pakzad, M., Golhashem, H., & Moghaddam, R. (2013). A multi-objective hub covering location problem under congestion using simulated annealing algorithm. Uncertain Supply Chain Management 1(3), 153–164.Google Scholar
Goldman, A.J. (1969). Optimal location for centers in a network. Transportation Science 3, 352–360.Google Scholar
Granville, V., Krivánek, M., & Rasson, J.P. (1994). Simulated annealing: a proof of convergence. IEEE Transactions on Pattern Analysis and Machine Intelligence 16(6), 652–656.Google Scholar
He, Y., Wu, T., Zhang, C., & Liang, Z. (2015). An improved MIP heuristic for the intermodal hub location problem. Omega 57, 203–211.Google Scholar
Henderson, D., Jacobson, S.H., & Johnson, A.W. (2003). The theory and practice of simulated annealing. In Handbook of Metaheuristics (Glover, F., & Kochenberger, G.A., Eds.), pp. 287–319. Dordrecht: Kluwer Academic.CrossRefGoogle Scholar
Holland, J.H. (1992). Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press.Google Scholar
Jabalameli, M.S., Barzinpour, F., Saboury, A., & Ghaffari-Nasab, N. (2012). A simulated annealing-based heuristic for the single allocation maximal covering hub location problem. International Journal of Metaheuristics 2(1), 15–37.Google Scholar
Kara, B.Y. (1999). Modeling and analysis of issues in hub location problems. PhD thesis. Bilkent University.Google Scholar
Kirkpatrick, S., Gelatt, C.D., & Vecchi, M.P. (1983). Optimization by simulated annealing. Science 220(4598), 671–680.Google Scholar
Klincewicz, J.G. (1992). Avoiding local optima in the p-hub location problem using tabu search and grasp. Annals of Operations Research 40, 283–302.CrossRefGoogle Scholar
Ma, K., & Thing, C. (2008). An ant colony optimization algorithm for solving the un-capacitated multiple allocation p-hub median. Proc. 9th Asia Pasific Industrial Engineering & Management Systems Conf., pp. 61–71, Bali, Indonesia, December 3–5.Google Scholar
Marić, M., Stanimirović, Z., & Stanojević, P. (2013). An efficient memetic algorithm for the uncapacitated single allocation hub location problem. Soft Computing 17(3), 445–466.Google Scholar
Marin, A. (2005). Formulating and solving splittable capacitated multiple allocation hub location problems. Computers & Operations Research 32, 3093–3109.Google Scholar
Naeem, M., & Ombuki-Berman, B. (2010). An efficient genetic algorithm for the uncapacitated single allocation hub location problem. Proc. IEEE Congr. Evolutionary Computation, CEC, pp. 1–8, Barcelona, July 18–23.Google Scholar
O'Kelly, M.E. (1986a). The location of interacting hub facilities. Transportation Science 20(2), 92–105.Google Scholar
O'Kelly, M.E. (1986b). Activity levels at hub facilities in interacting networks. Geographical Analysis 18(4), 343–356.Google Scholar
O'Kelly, M.E. (1987). A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research 32, 393–404.Google Scholar
Parvaresh, F., Hashemi Golpayegany, S.A., Moattar Husseini, S.M., & Karimi, B. (2013). Solving the p-hub median problem under intentional disruptions using simulated annealing. Networks and Spatial Economics 13(4), 445–470.Google Scholar
Puerto, J., Ramos, A.B., & Rodríguez-Chía, A.M. (2013). A specialized branch & bound & cut for single-allocation ordered median hub location problems. Discrete Applied Mathematics 161(16–17), 2624–2646.Google Scholar
Randall, M. (2008). Solution approaches for the capacitated single allocation hub location problem using ant colony optimization. Computational Optimization and Applications 39, 239–261.CrossRefGoogle Scholar
Rasoulinejad, Z., Bashiri, M., & Mehrbanfar, M. (2013). A clustering based simulated annealing approach for solving an un-capacitated single allocation p-hub location problem. Proc. 5th Int. Conf. Modeling, Simulation and Applied Optimization, ICMSAO, pp. 1–6, Hammamet, Tunisia, April 28–30.Google Scholar
Reeves, C. (2003). Genetic algorithms. In Handbook of Metaheuristics (Glover, F., & Kochenberger, G.A., Eds.), pp. 55–82. Dordrecht: Kluwer Academic.Google Scholar
Saboury, A., Ghaffari-Nasab, N., Barzinpour, F., & Jabalameli, M.S. (2013). Applying two efficient hybrid heuristics for hub location problem with fully interconnected backbone and access networks. Computers & Operations Research 40(10), 2493–2507.Google Scholar
Sender, J., & Clausen, U. (2013). Heuristics for solving a capacitated multiple allocation hub location problem with application in German wagonload traffic. Electronic Notes in Discrete Mathematics 41, 13–20.Google Scholar
Skorin-Kapov, D., & Skorin-Kapov, J. (1994). On tabu search for the location of interacting hub facilities. European Journal of Operational Research 73, 502–509.CrossRefGoogle Scholar
Stanimirovic, Z. (2010). A genetic algorithm approach for the capacitated single allocation p-hub median problem. Computing and Informatics 29, 117–132.Google Scholar
Sun, J. (2011). An ant colony optimization algorithm for the capacitated hub location problem. Proc. 2011 New Orleans Int. Academic Conf., pp. 721–732, New Orleans, March 14–16.Google Scholar
Sung, C.S., & Jin, H.W. (2001). Dual-based approach for a hub network design problem under non-restrictive policy. European Journal of Operational Research 132, 88–105.Google Scholar
Topcuoglu, H., Corut, F., Ermis, M., & Yilmaz, G. (2005). Solving the un-capacitated hub location problem using genetic algorithms. Computers & Operations Research 32(4), 967–984.Google Scholar
Wagner, B. (2007). An exact solution procedure for a cluster hub location problem. European Journal of Operational Research 178, 391–401.Google Scholar
Xu, L., Hu, D., Xuan, D., & Lin, H. (2009). A tabu search algorithm to logistics network design for multiple hub location routing problem. In Logistics: The Emerging Frontiers of Transportation and Development in China (Liu, R., Zhang, J., & Guan, C., Eds.), pp. 889–896. New York: American Society of Civil Engineers.Google Scholar
Yaman, H. (2005). Polyhedral analysis for the uncapacitated hub location problem with modular arc capacities. SIAM Journal on Discrete Mathematics 19(2), 501–522.Google Scholar