Um algoritmo branch-and-price para o problema de orientação de times com conjuntos
Resumo
Problemas de orientação consistem na maximização de prêmios coletados em uma rota, restrita por um limite de duração. Propõe-se um algoritmo de branch-and-price para o problema de orientação de times com conjuntos, uma generalização do problema inicial com presença de múltiplos veículos e a associação dos prêmios ao atendimento de conjuntos de clientes.Referências
Archetti, C., Carrabs, F., and Cerulli, R. (2018). The set orienteering problem. European Journal of Operational Research, 267(1):264–272.
Baldacci, R., Mingozzi, A., and Roberti, R. (2011). New route relaxation and pricing strategies for the vehicle routing problem. OPERATIONS RESEARCH, pages 1269–1283.
Bianchessi, N., Mansini, R., and Speranza, M. G. (2018). A branch-and-cut algorithm for the team orienteering problem. International Transactions in Operational Research, 25(2):627–635.
Boussier, S., Feillet, D., and Gendreau, M. (2007). An exact algorithm for team orienteering problems. 4or, 5:211–230.
Chao, I.-M., Golden, B. L., and Wasil, E. A. (1996). The team orienteering problem. European journal of operational research, 88(3):464–474.
Costa, L., Contardo, C., and Desaulniers, G. (2019). Exact branch-price-and-cut algorithms for vehicle routing. Transportation Science, 53(4):946–985.
Dang, D.-C., El-Hajj, R., and Moukrim, A. (2013). A branch-and-cut algorithm for solving the team orienteering problem. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings 10, pages 332–339. Springer.
Dror, M. (1994). Note on the complexity of the shortest path models for column generation in vrptw. Operations Research, 42(5):977–978.
Feo, T. A. and Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization, 6:109–133.
Keshtkaran, M., Ziarati, K., Bettinelli, A., and Vigo, D. (2016). Enhanced exact solution methods for the team orienteering problem. International Journal of Production Research, 54(2):591–601.
Laporte, G. and Martello, S. (1990). The selective travelling salesman problem. Discrete Applied Mathematics, 26(2):193–207.
Pessoa, A., Sadykov, R., Uchoa, E., and Vanderbeck, F. (2020). A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183(1):483–523.
Vansteenwegen, P. and Gunawan, A. (2019). Orienteering problems. EURO Advanced Tutorials on Operational Research.
Yu, V. F., Salsabila, N. Y., Lin, S.-W., and Gunawan, A. (2023). Simulated annealing with reinforcement learning for the set team orienteering problem with time windows. Expert Systems with Applications, page 121996.
Baldacci, R., Mingozzi, A., and Roberti, R. (2011). New route relaxation and pricing strategies for the vehicle routing problem. OPERATIONS RESEARCH, pages 1269–1283.
Bianchessi, N., Mansini, R., and Speranza, M. G. (2018). A branch-and-cut algorithm for the team orienteering problem. International Transactions in Operational Research, 25(2):627–635.
Boussier, S., Feillet, D., and Gendreau, M. (2007). An exact algorithm for team orienteering problems. 4or, 5:211–230.
Chao, I.-M., Golden, B. L., and Wasil, E. A. (1996). The team orienteering problem. European journal of operational research, 88(3):464–474.
Costa, L., Contardo, C., and Desaulniers, G. (2019). Exact branch-price-and-cut algorithms for vehicle routing. Transportation Science, 53(4):946–985.
Dang, D.-C., El-Hajj, R., and Moukrim, A. (2013). A branch-and-cut algorithm for solving the team orienteering problem. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings 10, pages 332–339. Springer.
Dror, M. (1994). Note on the complexity of the shortest path models for column generation in vrptw. Operations Research, 42(5):977–978.
Feo, T. A. and Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization, 6:109–133.
Keshtkaran, M., Ziarati, K., Bettinelli, A., and Vigo, D. (2016). Enhanced exact solution methods for the team orienteering problem. International Journal of Production Research, 54(2):591–601.
Laporte, G. and Martello, S. (1990). The selective travelling salesman problem. Discrete Applied Mathematics, 26(2):193–207.
Pessoa, A., Sadykov, R., Uchoa, E., and Vanderbeck, F. (2020). A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183(1):483–523.
Vansteenwegen, P. and Gunawan, A. (2019). Orienteering problems. EURO Advanced Tutorials on Operational Research.
Yu, V. F., Salsabila, N. Y., Lin, S.-W., and Gunawan, A. (2023). Simulated annealing with reinforcement learning for the set team orienteering problem with time windows. Expert Systems with Applications, page 121996.
Publicado
21/07/2024
Como Citar
LIMA NETO, Francisco Ferreira; ZANELATO, Pedro dos Santos; SILVA, Pedro Paulo A. de Paula e; HOSHINO, Edna A..
Um algoritmo branch-and-price para o problema de orientação de times com conjuntos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 9. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 43-47.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2024.2367.
