Matheurísticas para o problema de roteamento de veículos com prêmios
Abstract
Profitable vehicle routing problems are optimization problems which aim towards maximizing profits without the need to attend all the customers. In this work, matheuristics proposed for the disjunctively constrained knapsack problem are analyzed to build solutions for two variants of the profitable vehicle routing problems.
References
Alves, A. R. and Hoshino, E. A. (2022). Matheurísticas para o problema da mochila com restrição de conflitos. Anais do Simpósio Brasileiro de Pesquisa Operacional, 54.
Archetti, C., Bianchessi, N., and Speranza, M. G. (2013). Optimal solutions for routing problems with profits. Discrete Applied Mathematics, 161(4-5):547–557.
Archetti, C., Feillet, D., Hertz, A., and Speranza, M. G. (2009). The capacitated team orienteering and profitable tour problems. Journal of the Operational Research Society, 60:831–842.
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.
Bolduc, M.-C., Renaud, J., Boctor, F., and Laporte, G. (2008). A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers. Journal of the Operational Research Society, 59(6):776–787.
Bulhoes, T., Ha, M. H., Martinelli, R., and Vidal, T. (2018). The vehicle routing problem with service level constraints. European Journal of Operational Research, 265(2):544–558.
Dolan, E. D. and Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Math. Progam, 91:201–213.
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 15-60, ZIB, Takustr. 7, 14195 Berlin.
IBM (2019). IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual, Version 12 Release 6. IBM Corp.
Pessoa, A., Sadykov, R., Uchoa, E., and Vanderbeck, F. (2020). A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183:483–523.
Yamada, T., Kataoka, S., and Watanabe, K. (2002). Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Information Processing Society of Japan Journal, 43(9).
Archetti, C., Bianchessi, N., and Speranza, M. G. (2013). Optimal solutions for routing problems with profits. Discrete Applied Mathematics, 161(4-5):547–557.
Archetti, C., Feillet, D., Hertz, A., and Speranza, M. G. (2009). The capacitated team orienteering and profitable tour problems. Journal of the Operational Research Society, 60:831–842.
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.
Bolduc, M.-C., Renaud, J., Boctor, F., and Laporte, G. (2008). A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers. Journal of the Operational Research Society, 59(6):776–787.
Bulhoes, T., Ha, M. H., Martinelli, R., and Vidal, T. (2018). The vehicle routing problem with service level constraints. European Journal of Operational Research, 265(2):544–558.
Dolan, E. D. and Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Math. Progam, 91:201–213.
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 15-60, ZIB, Takustr. 7, 14195 Berlin.
IBM (2019). IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual, Version 12 Release 6. IBM Corp.
Pessoa, A., Sadykov, R., Uchoa, E., and Vanderbeck, F. (2020). A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183:483–523.
Yamada, T., Kataoka, S., and Watanabe, K. (2002). Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Information Processing Society of Japan Journal, 43(9).
Published
2023-08-06
How to Cite
L. NETO, Francisco F.; PEDROTTI, Vagner; HOSHINO, Edna A..
Matheurísticas para o problema de roteamento de veículos com prêmios. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 185-189.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230071.
