Um modelo estendido para o problema de roteamento em anéis de dois níveis
Resumo
Este trabalho apresenta uma abordagem branch-and-price para o projeto de uma rede hierárquica em dois níveis onde cada nível é um anel.
Palavras-chave:
programação linear inteira, branch-and-price, geração de colunas
Referências
Baldacci, R., Mingozzi, A., and Roberti, R. (2011). New route relaxation and pricing strategies for the vehicle routing problem. Operations Research, 59(5):1269–1283.
Gamrath, G., Fischer, T., Gally, T., Gleixner, A. M., Hendel, G., Koch, T., Maher, S. J., Miltenberger, M., Müller, B., Pfetsch, M. E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Vigerske, S., Weninger, D., Winkler, M., Witt, J. T., and Witzig, J. (2016). The SCIP Optimization Suite 3.2. Technical report, Optimization Online.
Irnich S., D. G. (2005). Column Generation, chapter Shortest Path Problems with Resource Constraints. Springer.
Miller, C., Tucker, A., and Zemlin, R. (1960). Integer programming formulations and traveling salesman problems. Journal of ACM, 7:326–329.
Poggi, M. and Uchoa, E. (2014). Chapter 3: New exact algorithms for the capacitated vehicle routing problem. In MOS-SIAM Series on Optimization, pages 59–86. Society for Industrial and Applied Mathematics.
Rodrı́guez-Martı́n, I., Salazar-González, J.-J., and Yaman, H. (2016a). A branch-and-cut algorithm for two-level survivable network design problems. Computers & Operations Research, 67:102–112.
Rodrı́guez-Martı́n, I., Salazar-González, J.-J., and Yaman, H. (2016b). The ring/κ-rings network design problem: Model and branch-and-cut algorithm. Networks, 68(2):130–140.
Thomadsen, T. and Stidsen, T. (2005). Hierarchical ring network design using branch-and-price. Telecommunication systems, 29(1):61–76.
Gamrath, G., Fischer, T., Gally, T., Gleixner, A. M., Hendel, G., Koch, T., Maher, S. J., Miltenberger, M., Müller, B., Pfetsch, M. E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Vigerske, S., Weninger, D., Winkler, M., Witt, J. T., and Witzig, J. (2016). The SCIP Optimization Suite 3.2. Technical report, Optimization Online.
Irnich S., D. G. (2005). Column Generation, chapter Shortest Path Problems with Resource Constraints. Springer.
Miller, C., Tucker, A., and Zemlin, R. (1960). Integer programming formulations and traveling salesman problems. Journal of ACM, 7:326–329.
Poggi, M. and Uchoa, E. (2014). Chapter 3: New exact algorithms for the capacitated vehicle routing problem. In MOS-SIAM Series on Optimization, pages 59–86. Society for Industrial and Applied Mathematics.
Rodrı́guez-Martı́n, I., Salazar-González, J.-J., and Yaman, H. (2016a). A branch-and-cut algorithm for two-level survivable network design problems. Computers & Operations Research, 67:102–112.
Rodrı́guez-Martı́n, I., Salazar-González, J.-J., and Yaman, H. (2016b). The ring/κ-rings network design problem: Model and branch-and-cut algorithm. Networks, 68(2):130–140.
Thomadsen, T. and Stidsen, T. (2005). Hierarchical ring network design using branch-and-price. Telecommunication systems, 29(1):61–76.
Publicado
30/06/2020
Como Citar
OSÓRIO, Cecília Lescano; HOSHINO, Edna Ayako.
Um modelo estendido para o problema de roteamento em anéis de dois níveis. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 89-92.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11097.
