To access the full text documents, please follow this link: http://hdl.handle.net/2117/27676

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
Heuristic
Computer algorithms
Optimization
Combinatorial optimization
Networks
Graphs
Trees
Spanning trees
Capacitated minimumspanningtree
Heuristics
Biased random-keygeneticalgorithm
Optimització combinatòria
Heurística
Algorismes genètics
info:eu-repo/semantics/submittedVersion
Article
         

Show full item record

Related documents

Other documents of the same author

Albareda Sambola, Maria; Fernández Aréizaga, Elena; Hinojosa, Yolanda; Puerto Albandoz, Justo
Albareda Sambola, Maria; Fernández Aréizaga, Elena; Nickel, Stefan
Albareda Sambola, Maria; Díaz, Juan A.; Fernández Aréizaga, Elena
Albareda Sambola, Maria; Alonso Ayuso, Antonio; Escudero Bueno, Laureano; Fernández Aréizaga, Elena; Pizarro Romero, Celeste
Martínez Martínez, María del Rosario; Cadenato Matia, Ana María; Graells Sobré, Moisès; Pérez Cabrera, María José; Amante García, Beatriz; Jordana Barnils, José; Gorchs Altarriba, Roser; Salán Ballesteros, Maria Núria; Raventós Santamaria, Mercè; Algaba Joaquín, Inés María; Albareda Sambola, Maria; Bohigas Janoher, Xavier; González Azón, M. Carmen; Pérez Morales, Isabel; Sainz García, Daniel; Portet Cortés, Esperanza; Periago Oliver, M. Cristina; Gallego Fernández, María Isabel; García-Almiñana, Daniel; Jorge Sánchez, Juan; Pérez Poch, Antoni
 

Coordination

 

Supporters