Uma abordagem exata unificada para um conjunto de variantes do problema de roteamento de veículos com coleta e entrega simultâneas
Resumo
Neste trabalho, foi desenvolvida uma formulação matemática combinada a um método baseado no algoritmo de branch-cut-and-price (BCP) para dez variantes do problema de roteamento de veículos com coleta e entrega simultâneas (PRVCES), a fim de obter soluções ótimas para instâncias em aberto ou limites duais melhores. Todas essas variantes foram modeladas como um problema unificado, denominado Problema de Roteamento e Localização com Coleta e Entrega Simultâneas Heterogêneo e com Janelas de Tempo (PRL-CESHJT). Devido à inexistência de instâncias para o problema geral, experimentos computacionais foram realizados com instâncias para cada uma das variantes separadamente, sendo obtidos resultados bastante promissores.
Referências
Avci, M. and Topaloglu, S. (2016). A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications, 53:160–171.
Baldacci, R., Christofides, N., and Mingozzi, A. (2008). An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming, 115:351–385.
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.
Braekers, K., Ramaekers, K., and Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99:300–313.
Bulhões, T., Pessoa, A., Protti, F., and Uchoa, E. (2018). On the complete set packing and set partitioning polytopes: Properties and rank 1 facets. Operations Research Letters, 46(4):389–392.
Dantzig, G. B. and Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1):80–91.
Karaoglan, I., Altiparmak, F., Kara, I., and Dengiz, B. (2011). A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery. European Journal of Operational Research, 211:318–332.
Karaoglan, I., Altiparmak, F., Kara, I., and Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40:465–477.
Koç, Ç., Laporte, G., and Tükenmez, İ. (2020). A review of vehicle routing with simultaneous pickup and delivery. Computers and Operations Research, 122.
Laporte, G. and Nobert, Y. (1983). A branch and bound algorithm for the capacitated vehicle routing problem. OR Spektrum, 5:77–85.
Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5):377–386.
Montané, F. A. T. and Galvão, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers and Operations Research, 33:595–619.
Pecin, D., Pessoa, A., Poggi, M., Uchoa, E., and Santos, H. (2017). Limited memory rank-1 cuts for vehicle routing problems. Operations Research Letters, 45(3):206-209.
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.
Petersen, B., Pisinger, D., and Spoorendonk, S. (2008). Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows, pages 397–419. Springer US, Boston, MA.
Rieck, J. and Zimmermann, J. (2013). Exact solutions to the symmetric and asymmetric vehicle routing problem with simultaneous delivery and pick-up. Business Research, 6:77–92.
Salhi, S. and Nagy, G. (1999). A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. The Journal of the Operational Research Society, 50(10):1034–1042.
Wang, H. F. and Chen, Y. Y. (2012). A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers and Industrial Engineering, 62:84–95.
Wang, H. F. and Chen, Y. Y. (2013). A coevolutionary algorithm for the flexible delivery and pickup problem with time windows. International Journal of Production Economics, 141:4–13.
Baldacci, R., Christofides, N., and Mingozzi, A. (2008). An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming, 115:351–385.
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.
Braekers, K., Ramaekers, K., and Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99:300–313.
Bulhões, T., Pessoa, A., Protti, F., and Uchoa, E. (2018). On the complete set packing and set partitioning polytopes: Properties and rank 1 facets. Operations Research Letters, 46(4):389–392.
Dantzig, G. B. and Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1):80–91.
Karaoglan, I., Altiparmak, F., Kara, I., and Dengiz, B. (2011). A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery. European Journal of Operational Research, 211:318–332.
Karaoglan, I., Altiparmak, F., Kara, I., and Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40:465–477.
Koç, Ç., Laporte, G., and Tükenmez, İ. (2020). A review of vehicle routing with simultaneous pickup and delivery. Computers and Operations Research, 122.
Laporte, G. and Nobert, Y. (1983). A branch and bound algorithm for the capacitated vehicle routing problem. OR Spektrum, 5:77–85.
Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5):377–386.
Montané, F. A. T. and Galvão, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers and Operations Research, 33:595–619.
Pecin, D., Pessoa, A., Poggi, M., Uchoa, E., and Santos, H. (2017). Limited memory rank-1 cuts for vehicle routing problems. Operations Research Letters, 45(3):206-209.
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.
Petersen, B., Pisinger, D., and Spoorendonk, S. (2008). Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows, pages 397–419. Springer US, Boston, MA.
Rieck, J. and Zimmermann, J. (2013). Exact solutions to the symmetric and asymmetric vehicle routing problem with simultaneous delivery and pick-up. Business Research, 6:77–92.
Salhi, S. and Nagy, G. (1999). A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. The Journal of the Operational Research Society, 50(10):1034–1042.
Wang, H. F. and Chen, Y. Y. (2012). A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers and Industrial Engineering, 62:84–95.
Wang, H. F. and Chen, Y. Y. (2013). A coevolutionary algorithm for the flexible delivery and pickup problem with time windows. International Journal of Production Economics, 141:4–13.
Publicado
06/08/2023
Como Citar
PRAXEDES, Rafael; BULHÕES, Teobaldo; SUBRAMANIAN, Anand; UCHOA, Eduardo.
Uma abordagem exata unificada para um conjunto de variantes do problema de roteamento de veículos com coleta e entrega simultâneas. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 144-149.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230880.
