×

A biased random-key genetic algorithm for the capacitated minimum spanning tree problem. (English) Zbl 1348.90553

Summary: This paper focuses on the capacitated minimum spanning tree (CMST) problem. Given a central processor and a set of remote terminals with specified demands for traffic that must flow between the central processor and terminals, the goal is to design a minimum cost network to carry this demand. Potential links exist between any pair of terminals and between the central processor and the terminals. Each potential link can be included in the design at a given cost. The CMST problem is to design a minimum-cost network connecting the terminals with the central processor so that the flow on any arc of the network is at most \(Q\). A biased random-key genetic algorithm (BRKGA) is a metaheuristic for combinatorial optimization which evolves a population of random vectors that encode solutions to the combinatorial optimization problem. This paper explores several solution encodings as well as different strategies for some steps of the algorithm and finally proposes a BRKGA heuristic for the CMST problem. Computational experiments are presented showing the effectiveness of the approach: Seven new best-known solutions are presented for the set of benchmark instances used in the experiments.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahuja, R. K.; Orlin, J. B.; Sharma, D., Multiexchange neighborhood structures for the capacitated minimum spanning tree problem, Math Progr, 91, 71-97 (2001) · Zbl 1051.90019
[2] Ahuja, R. K.; Orlin, J. B.; Sharma, D., A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem, Oper Res Lett, 31, 185-194 (2003) · Zbl 1064.90039
[3] Amberg, A.; Domeschke, W.; Voss, S., Capacitated minimum spanning treesalgorithms using intelligent search, Comb Optim Theory Pract, 1, 9-33 (1996)
[4] Amberg, A.; Domeschke, W.; Voss, S., Multiple center capacitated arc routing problemsa tabu search algorithm using capacitated trees, Eur J Oper Res, 124, 360-376 (2000) · Zbl 0967.90017
[6] Bean, J. C., Genetic algorithms and random keys for sequencing and optimization, ORSA J Comput, 6, 154-160 (1994) · Zbl 0807.90060
[7] Buriol, L. S.; Resende, M. G.C.; Ribeiro, C. C.; Thorup, M., A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing, Networks, 46, 36-56 (2005) · Zbl 1072.90528
[8] Buriol, L. S.; Hirsch, M. J.; Querido, T.; Pardalos, P. M.; Resende, M. G.C.; Ritt, M., A biased random-key genetic algorithm for road congestion minimization, Optim Lett, 4, 619-633 (2010) · Zbl 1202.90025
[9] Chow, A.; Kershenbaum, W., A unified algorithm for designing multidrop teleprocessing networks, IEEE Trans Commun, COM-22, 1762-1772 (1974)
[11] Esau, L. R.; Williams, K. C., On teleprocessing system design, Part IIa method for approximating the optimal network, IBM Syst J, 5, 142-147 (1966)
[12] Frederickson, G. N., Approximation algorithms for some postman problems, J Assoc Comput Mach, 26, 538-554 (1979) · Zbl 0405.90076
[13] Frederickson, G. N.; Hecht, M. S.; Chul, K., Approximation algorithms for some routing problems, SIAM J Comput, 7, 178-193 (1979)
[14] Gavish, B., Topological design of centralized computer networks formulations and algorithms, Networks, 12 (1982) · Zbl 0493.94021
[15] Gavish, B., Formulations and algorithms for the capacitated minimal directed tree problem, J Assoc Comput Mach, 30, 118-132 (1983) · Zbl 0504.90052
[16] Gavish, B., Augmented Lagrangean based algorithms for centralized network design, IEEE Trans Commun, 33, 1247-1257 (1985)
[18] Glover, F.; Laguna, M., Tabu search (1997), Kluwer: Kluwer Boston · Zbl 0930.90083
[19] Gonçalves, J. F.; Resende, M. G.C., Biased random-key genetic algorithms for combinatorial optimization, J. Heuristics, 17, 487-525 (2011)
[20] Gonçalves, J. F.; Resende, M. G.C., A parallel multi-population biased random-key genetic algorithm for a container loading problem, Comput Oper Res, 39, 179-190 (2012) · Zbl 1251.90238
[21] Gonçalves, J. F.; Resende, M. G.C.; Mendes., J. J.M., A biased random-key genetic algorithms with forward-backward improvement for the resource constrained project scheduling problem, J Heuristics, 17, 467-486 (2011)
[22] Gonçalves, J. F.; Resende, M. G.C.; Toso, R. F., An experimental comparison of biased and unbiased random-key genetic algorithms, Pesqu Oper, 34, 143-164 (2014)
[23] Gouveia, L., A comparison of directed formulations for the capacitated minimal spanning tree problem, Telecommun Syst, 1, 51-76 (1993)
[24] Gouveia, L., A 2n-constraint formulation for the capacitated minimal spanning tree problem, Oper Res, 43, 130-141 (1995) · Zbl 0830.90049
[25] Gouveia, L., Multicommodity flow models for spanning trees with hop constraints, Eur J Oper Res, 95, 178-190 (1996) · Zbl 0947.90513
[26] Gouveia, L.; Hall, L., Multistars and directed flow formulations, Networks, 40, 188-201 (2002) · Zbl 1035.90097
[27] Gouveia, L.; Lopes, M., The capacitated minimum spanning tree problem: on improved multistar constraints, Eur J Oper Res, 160, 47-62 (2005) · Zbl 1067.90141
[28] Gouveia, L.; Martins, P., A hierarchy of hop-indexed models for the capacitated minimal spanning tree problem, Networks, 35, 1-16 (2000) · Zbl 0938.90067
[29] Gouveia, L.; Martins, P., The capacitated minimum spanning tree problemrevisiting hop-indexed formulations, Comput Oper Res, 32, 2435-2452 (2005) · Zbl 1066.90102
[30] Gouveia, L.; Paixão, J., Dynamic programming based heuristics for the topological design of local access networks, Ann Oper Res, 33, 305-327 (1991) · Zbl 0736.90032
[31] Hall, L., Experience with a cutting plane algorithm for the capacitated spanning tree problem, INFORMS J Comput, 8, 219-234 (1996) · Zbl 0871.90032
[32] Kruskal, J. B., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc Am Math Soc, 7-1, 8-50 (1956) · Zbl 0070.18404
[33] Martinez, C.; Loiseau, I.; Resende, M. G.C.; Rodriguez, S., BRKGA algorithm for the capacitated arc routing problem, Electron Notes Theor Comput Sci, 281, 69-83 (2011)
[34] Martins, P., Enhanced second order algorithm applied to the capacitated minimum spanning tree problem, Comput Oper Res, 34, 2495-2519 (2007) · Zbl 1144.90501
[36] Mendes, J. J.M.; Gonçalves, J. F.; Resende, M. G.C., A random key based genetic algorithm for the resource constrained project scheduling problem, Comput Oper Res, 36, 92-109 (2009) · Zbl 1163.90500
[37] Neville, E. H., The codifying of tree-structure, Math Proc Camb Philos Soc, 49, 381-385 (1953) · Zbl 0050.17904
[38] Noronha, T. F.; Resende, M. G.C.; Ribeiro, C. C., A biased random-key genetic algorithm for routing and wavelength assignment, J Glob Optim, 50, 503-518 (2011)
[39] Papadimitriou, C., The complexity of the capacitated tree problem, Networks, 8, 217-230 (1978) · Zbl 0405.68043
[40] Prim, R. C., Shortest connection matrix network and some generalizations, Bell Syst Tech J, 36, 1389-1401 (1957)
[41] Prüfer, H., Neuer Beweis eines Satzes über Permutationen, Arch Math Phys, 27, 742-744 (1918) · JFM 46.0106.04
[42] Raidl, G. R.; Julstrom, B. A., Edge sets: an effective evolutionary coding of spanning trees, IEEE Trans Evol Comput, 7, 225-239 (2003)
[43] Rego, C.; Mathew, F., A filter-and-fan algorithm for the capacitated minimum spanning tree problem, Comput Ind Eng, 60, 187-194 (2011)
[44] Rego, C.; Mathew, F.; Glover, F., RAMP for the capacitated minimum spanning tree problem, Ann Oper Res, 181, 661-681 (2010) · Zbl 1209.90085
[45] Reimann, M.; Laumanns, M., Savings based ant colony optimization for the capacitated minimum spanning tree problem, Comput Oper Res, 33, 1794-1822 (2006) · Zbl 1087.90012
[46] Reis, R.; Ritt, M.; Buriol, L. S.; Resende, M. G.C., A biased random-key genetic algorithm for OSPF and DEFT routing to minimize network congestion, Int Trans Oper Res, 18, 401-423 (2011) · Zbl 1219.90035
[47] Resende, M. G.C.; Toso, R. F.; Gonçalves, J. F.; Silva, R. M.A., A biased random-key genetic algorithm for the Steiner triple covering problem, Optim Lett, 6, 605-619 (2012) · Zbl 1262.90151
[48] Rothlauf, F.; Goldberg, D.; Heinzl, A., Network random keys—a tree representation scheme for genetic and evolutionary algorithms, Evol Comput, 10, 75-97 (2002)
[50] Sharaiha, Y. M.; Gendreau, M.; Laporte, G.; Osman, I. H., A tabu search algorithm for the capacitated shortest spanning tree problem, Networks, 29, 161-167 (1997) · Zbl 0874.68243
[51] Souza, M. C.; Duhamel, C.; Ribeiro, C. C., A GRASP heuristic for the capacitated minimum spanning tree problem using memory-based local search strategy, Appl Optim, 86, 627-658 (2003)
[53] Thompson, E.; Paulden, T.; Smith, D. K., The dandelion codea new coding of spanning trees for genetic algorithms, IEEE Trans Evol Comput, 11, 91-100 (2007)
[54] Toso, R. F.; Resende, M. G.C., A C++ application programming interface for biased random-key genetic algorithms, Optimization Methods and Software, 30, 81-93 (2015)
[55] Uchoa, E.; Fukasawa, R.; Lysgaard, J.; Pessoa, A.; Poggi de Aragão, M.; Andrade, D., Robust branch-cut-and-price algorithm for the capacitated minimum spanning tree problem over a large extended formulation, Math Progr, 112, 443-472 (2008) · Zbl 1146.90059
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.