A branch-and-price algorithm for the team orienteering problem with sets

• Francisco Ferreira Lima Neto UFMS
• Pedro dos Santos Zanelato UFMS
• Pedro Paulo A. de Paula e Silva UFMS
• Edna A. Hoshino UFMS

DOI: https://doi.org/10.5753/etc.2024.2367

Abstract

Orienteering problems consist in the maximization of profits collected in a given route, restricted by a time limit. A branch-and-price algorithm is proposed for the set team orienteering problem, a generalization of the initial problem with the presence of multiple vehicles and the association of the profits with the service of client clusters.

References

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.