Abordagens Heurísticas para o p-Cabo-Trincheira com Localização de Instalações
Resumo
Apresentamos uma nova variação do Problema Cabo-Trincheira, o p-Cabo-Trincheira com Localização de Instalações, em que há custos de abertura de instalações. Propomos duas heurísticas: uma baseada em Relax-and-Fix e outra baseada em BRKGA, que avaliamos experimentalmente.
Referências
Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11):1069–1072.
Marianov, V., Gutiérrez-Jarpa, G., Obreque, C., and Cornejo, O. (2012). Lagrangean relaxation heuristics for the p-cable-trench problem. Comp. Oper. Res., 39(3):620–628.
Nielsen, R. H., Riaz, M. T., Pedersen, J. M., and Madsen, O. B. (2008). On the potential of using the cable trench problem in planning of ict access networks. In ELMAR, 2008. 50th International Symposium, volume 2, pages 585–588.
Toso, R. F. and Resende, M. G. (2015). A c++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Soft., 30(1):81–93.
Vasko, F. J., Barbieri, R. S., Rieksts, B. Q., Reitmeyer, K. L., and Jr., K. L. S. (2002). The cable trench problem: combining the shortest path and minimum spanning tree problems. Computers & Operations Research, 29(5):441 – 458.
Vasko, F. J., Landquist, E., Kresge, G., Tal, A., Jiang, Y., and Papademetris, X. (2016). A simple and efficient strategy for solving very large-scale generalized cable-trench problems. Networks, 67(3):199–208.
Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience publication.
Marianov, V., Gutiérrez-Jarpa, G., Obreque, C., and Cornejo, O. (2012). Lagrangean relaxation heuristics for the p-cable-trench problem. Comp. Oper. Res., 39(3):620–628.
Nielsen, R. H., Riaz, M. T., Pedersen, J. M., and Madsen, O. B. (2008). On the potential of using the cable trench problem in planning of ict access networks. In ELMAR, 2008. 50th International Symposium, volume 2, pages 585–588.
Toso, R. F. and Resende, M. G. (2015). A c++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Soft., 30(1):81–93.
Vasko, F. J., Barbieri, R. S., Rieksts, B. Q., Reitmeyer, K. L., and Jr., K. L. S. (2002). The cable trench problem: combining the shortest path and minimum spanning tree problems. Computers & Operations Research, 29(5):441 – 458.
Vasko, F. J., Landquist, E., Kresge, G., Tal, A., Jiang, Y., and Papademetris, X. (2016). A simple and efficient strategy for solving very large-scale generalized cable-trench problems. Networks, 67(3):199–208.
Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience publication.
Publicado
02/07/2017
Como Citar
ROCHA, Ulysses; RAMOS, Natanael; MELO, Lucas; BENEDITO, Marcelo; SILVA, André; CANO, Rafael; MIYAZAWA, Flávio; XAVIER, Eduardo.
Abordagens Heurísticas para o p-Cabo-Trincheira com Localização de Instalações. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 77-80.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2017.3196.
