×

Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation. (English) Zbl 1147.90421

Summary: Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
49M05 Numerical methods based on necessary conditions
49K20 Optimality conditions for problems involving partial differential equations
65K10 Numerical optimization and variational techniques
90C51 Interior-point methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdinnour-Helm, S., Venkataramanan, M.: Solution approaches to hub location problems. Ann. Oper. Res. 78, 31–50 (1998) · Zbl 0897.90091 · doi:10.1023/A:1018954217758
[2] Beasley, J.: OR-Library. Online at http://people.brunel.ac.uk/\(\sim\)mastjjb/jeb/info.html (2005)
[3] Blum, C., Dorigo, M.: The hyper-cube framework for ant colony optimization. Trans. Syst. Man Cybern. B 34, 1161–1172 (2004) · doi:10.1109/TSMCB.2003.821450
[4] Boland, N., Ebery, J., Ernst, A., Krishnamoorthy, M.: The capacitated multiple allocation hub location problem: Formulations and algorithms. J. Oper. Res. 120, 614–631 (2000) · Zbl 0985.90063 · doi:10.1016/S0377-2217(98)00395-6
[5] Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems. Sante Fe Institute Studies in the Science of Complexity, Oxford University Press, New York (1999) · Zbl 1003.68123
[6] Burkard, R.: Quadratic assignment problems. Eur. J. Oper. Res. 15, 283–289 (1984) · Zbl 0526.90064 · doi:10.1016/0377-2217(84)90093-6
[7] Campbell, J.: Integer programming formulations of discrete hub location problems. Eur. J. Oper. Res. 72, 387–405 (1994) · Zbl 0790.90048 · doi:10.1016/0377-2217(94)90318-2
[8] Campbell, J.: Hub location and the p-hub median problem. Oper. Res. 44, 923–935 (1996) · Zbl 0879.90127 · doi:10.1287/opre.44.6.923
[9] Carello, G., Yaman, H.: Solving the hub location problem with integer links. Technical Report IEOR-2003-08, Department of Industrial Engineering, Bilkent University, Turkey (2003) · Zbl 1178.90221
[10] Chamberland, S., Sanso, B., Marcotte, O.: Topological design of two-level telecommunication networks with modular switches. Oper. Res. 48, 745–760 (2000) · Zbl 1106.90315 · doi:10.1287/opre.48.5.745.12412
[11] Cheung, B., Langevin, A., Villeneuve, B.: High performing evolutionary techniques for solving complex location problems in industrial system design. J. Intell. Manaf. 12, 455–466 (2001) · doi:10.1023/A:1012248319870
[12] Chu, P., Beasley, J.: A genetic algorithm for the generalised assignment problem. Comput. Oper. Res. 24, 17–23 (1997) · Zbl 0881.90070 · doi:10.1016/S0305-0548(96)00032-9
[13] Costa, D., Hertz, A.: Ants can colour graphs. J. Oper. Res. Soc. 48, 295–305 (1997) · Zbl 0890.90174
[14] Dorigo, M., Di Caro, G.: Ant colony optimization: a new meta-heuristic. In: Congress on Evolutionary Computation, vol. 2, pp. 1470–1477 (1999)
[15] Dorigo, M., Gambardella, L.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997) · Zbl 05451865 · doi:10.1109/4235.585892
[16] Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: an autocatalytic optimizing process. Technical Report 91-016 Revised, Politecnico di Milano (1991) · Zbl 0912.90240
[17] Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B 26(1), 1–13 (1996) · doi:10.1109/3477.484436
[18] Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Boston (2004) · Zbl 1092.90066
[19] Ernst, A., Krishnamoorthy, M.: Efficient algorithms for the uncapacitated single allocation p-hub problem. Locat. Sci. 4, 139–154 (1996) · Zbl 0927.90065 · doi:10.1016/S0966-8349(96)00011-3
[20] Ernst, A., Krishnamoorthy, M.: Efficient algorithms for the uncapacitated multiple allocation p-hub median problem. Eur. J. Oper. Res. 104, 100–112 (1998) · Zbl 0955.90055 · doi:10.1016/S0377-2217(96)00340-2
[21] Ernst, A., Krishnamoorthy, M.: Solution algorithms for the capacitated single allocation hub location problem. Ann. Oper. Res. 86, 141–159 (1999) · Zbl 0918.90096 · doi:10.1023/A:1018994432663
[22] Fotheringham, A.: A new set of spatial interaction models: the theory of competing distances. Environ. Plan. A 15, 15–36 (1983) · doi:10.1068/a150015
[23] Gambardella, L., Taillard, E., Dorigo, M.: Ant colonies for the quadratic assignment problem. J. Oper. Res. Soc. 50, 167–176 (1999) · Zbl 1054.90621
[24] Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Boston (1997) · Zbl 0930.90083
[25] Goldberg, D.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading (1989) · Zbl 0721.68056
[26] Hansen, P., Mladenovic, N., Pierez-Brito, D.: Variable neighborhood decomposition search. J. Heuristics 7, 335–350 (2001) · Zbl 1041.68623 · doi:10.1023/A:1011336210885
[27] Hendtlass, T., Randall, M.: A survey of ant colony and particle swarm meta-heuristics and their application to discrete optimisation problems. In: Proceedings of the Inaugual Workshop on Artificial Life, Adelaide, Australia, pp. 15–25 (2001)
[28] Klincewicz, J.: Heuristics for the p-hub location problem. Eur. J. Oper. Res. 53, 25–37 (1991) · Zbl 0726.90042 · doi:10.1016/0377-2217(91)90090-I
[29] Klincewicz, J.: Avoiding local optima in the p-hub location problem using tabu search and GRASP. Ann. Oper. Res. 40, 283–302 (1992) · Zbl 0784.90044 · doi:10.1007/BF02060483
[30] Lawler, E., Lenstra, J., Rinnoy, A., Shmoys, D.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1990)
[31] Love, R., Morris, J., Wesolowsky, G.: Facility Location: Models and Methods. Publications in Operations Research, vol. 7. North-Holland, New York (1988) · Zbl 0685.90036
[32] Montgomery, J., Randall, M., Hendtlass, T.: Search bias in constructive metaheuristics and implications for ant colony optimisation. In: Dorigo, M., Birattari, M., Blum, C., Gambardella, L., Mondada, F., Stützle, T. (eds.) Fourth International Workshop on Ant Algorithms. Lecture Notes in Computer Science, vol. 3172, pp. 390–397. Springer, New York (2004)
[33] O’Kelly, M.: The location of interacting hub facilities. Transp. Sci. 20, 96–106 (1986)
[34] O’Kelly, M.: A quadratic integer program for the location of interacting hub facilities. Eur. J. Oper. Res. 32, 393–404 (1987) · Zbl 0627.90030 · doi:10.1016/S0377-2217(87)80007-3
[35] Osman, I.: Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann. Oper. Res. 41, 421–451 (1993) · Zbl 0775.90153 · doi:10.1007/BF02023004
[36] Pamuk, F., Sepil, C.: A solution to the hub center problem via a single relocation algorithm with tabu search. IIE Trans. 33, 399–411 (2001)
[37] Randall, M.: Scheduling aircraft landings using ant colony optimisation. In: Sixth IASTED International Conference Artificial Intelligence and Soft Computing, Banff, Canada, pp. 129–133 (2002)
[38] Randall, M.: Heuristics for ant colony optimisation using the generalised assignment problem. In: Proceedings of the Congress on Evolutionary Computing, Portland, Oregon, USA, pp. 1916–1923 (2004)
[39] Roli, A., Blum, C., Dorigo, M.: ACO for maximal constraint satisfaction problems. In: Fourth Metaheuristics International Conference (2001)
[40] Skorin-Kapov, D., Skorin-Kapov, J.: On tabu search for the location of interacting hub facilities. Eur. J. Oper. Res. 73, 502–509 (1994) · Zbl 0806.90075 · doi:10.1016/0377-2217(94)90245-3
[41] Skorin-Kapov, D., Skorin-Kapov, J.: Tight linear programming relaxations of uncapacitated p-hub median problems. Eur. J. Oper. Res. 984, 582–593 (1994) · Zbl 0947.90602
[42] Smith, K., Krishnamoorthy, M., Palaniswami, M.: Neural versus traditional approaches to the location of interacting hub facilities. Locat. Sci. 4, 155–171 (1996) · Zbl 0927.90073 · doi:10.1016/S0966-8349(96)00017-4
[43] Solnon, C.: Ants can solve constraint satisfaction problems. IEEE Trans. Evol. Comput. 6, 347–357 (2002) · Zbl 05452146 · doi:10.1109/TEVC.2002.802449
[44] Stützle, T., Hoos, H.: Improvements on the ant-system: introducing the \(\mathcal{MAX}{-}\mathcal{MIN}\) ant system. In: Proceedings of the Third International Conference on Artificial Neural Networks and Genetic Algorithms, pp. 245–249 (1997)
[45] Stützle, T., Hoos, H.: The \(\mathcal{MAX}{-}\mathcal{MIN}\) ant system and local search for combinatorial optimization problems. In: Voss, S., Martello, S., Osman, I., Roucairol, C. (eds.) Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 313–329. Kluwer Academic, Boston (1998) · Zbl 0970.90083
[46] Stützle, T., Hoos, H.: \(\mathcal{MAX}{-}\mathcal{MIN}\) ant system. Futur. Gener. Comput. Syst. 16, 889–914 (2000) · doi:10.1016/S0167-739X(00)00043-1
[47] Taillard, E., Gambardella, L.: Adaptive memories for the quadratic assignment problem. Technical Report IDSIA-87-97, Istituto Dalle Molle di Studi sull’Intelligenza Artificiale (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.