To access the full text documents, please follow this link:

A biased random-key genetic algorithm for the capacitated minimum spanning tree problem
Ruiz Ruiz, Hector Efrain; Albareda Sambola, Maria; Fernández Aréizaga, Elena; Resende, Mauricio G. C.
Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa; Universitat Politècnica de Catalunya. GNOM - Grup d'Optimització Numèrica i Modelització
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-keygenetic 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 effectivenes sof the approach:Seven newbest- known solutions are presented for the set of benchmark instances used in the experiments.
Peer Reviewed
Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa
Combinatorial optimization
Computer algorithms
Combinatorial optimization
Spanning trees
Capacitated minimumspanningtree
Biased random-keygeneticalgorithm
Optimització combinatòria
Algorismes genètics

Show full item record

Related documents

Other documents of the same author

Albareda Sambola, Maria; Fernández Aréizaga, Elena; Nickel, Stefan
Albareda Sambola, Maria; Alonso Ayuso, Antonio; Escudero Bueno, Laureano; Fernández Aréizaga, Elena; Pizarro Romero, Celeste
Albareda Sambola, Maria; Fernández Aréizaga, Elena; Hinojosa, Yolanda; Puerto Albandoz, Justo
Albareda Sambola, Maria; Díaz, Juan A.; Fernández Aréizaga, Elena
Albareda Sambola, Maria; Hinojosa, Yolanda; Marín, Alfredo; Puerto Albandoz, Justo