Uma análise sobre o problema do caixeiro viajante alugador com passageiros e seus subproblemas / An analysis of the traveling car renter with passengers and its subproblems

Authors

  • Gustavo de Araujo Sabry
  • Bruno de Castro Honorato Silva
  • Marco Cesar Goldbarg
  • Elizabeth F. Gouvêa Goldbarg
  • Matheus da Silva Menezes
  • Zailton Sachas Amorim Calheiros

DOI:

https://doi.org/10.34117/bjdv5n11-129

Keywords:

Problema do Caixeiro Viajante Alugador com Passageiros, Problema do Caixeiro Viajante, Aluguel de Veículos e Compartilhamento de Veículos.

Abstract

 Neste artigo apresentamos uma análise sobre o Problema do Caixeiro Viajante Alugador com Passageiros (CaRSP) e seus subproblemas. O CaRSP é uma variante do clássico Problema do Caixeiro Viajante (PCV) que leva em consideração duas tendências atuais no sistema de transportes: o aluguel e o compartilhamento de veículos. A variante do PCV que trabalha com aluguel de veículos se chama Problema do Caixeiro Alugador (CaRS). Este trabalho apresenta uma correção de um modelo matemático já relatado na literatura para o CaRS. Também é proposta uma versão do PCV que trabalha apenas com o compartilhamento de veículos chamada de Problema do Caixeiro Viajante com Passageiros (PCV-P). Estas variantes tem o potencial de aumentar a taxa de ocupação dos automóveis em estradas ou cidades e minimizar custos a partir da divisão de despesas. Além disso, também podem reduzir a quantidade de veículos transitando e, consequentemente, os impactos ambientais causados pela poluição, os engarrafamentos e áreas ocupadas por carros estacionados. O trabalho apresenta a descrição, o estado da arte e a formulação matemática de três problemas: CaRS, PCV-P e CaRSP. Cada problema envolve decisões no que se refere à sequência de cidades visitadas, à ordem de veículos utilizados e/ou ao esquema de embarque de passageiros ao longo do percurso. Estes modelos são implementados em um solver e submetidos para solucionar um grupo de 30 instâncias. Os resultados obtidos são analisados e conclusões são tecidas à cerca do desempenho de cada modelo.    

 

 

References

Abla apresenta o Anuário Brasileiro do Setor de Locação de Veículos 2019. Diário Indústria & Comércio, Curitiba/PR, 20 de mar. de 2019. Disponível em: <https://www.diarioinduscom.com/abla-apresenta-o-anuario-brasileiro-do-setor-de-locacao-de-veiculos-2019/>. Acesso em: 10 de abr. de 2019.

APPLEGATE, D. L.; BIXBY, R. E.; CHVATAL, V.; COOK, W. J. The Traveling Salesman Problem. Princeton University Press, New Jersey, 2007.

ARAÚJO, G. F. Algoritmos Meta-heurísticos Para a Solução do Problema do Caixeiro Viajante com Múltiplas Caronas. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal do Rio Grande do Norte, Natal/RN, 2016.

ASCONAVIETA, P. H. O Problema do Caixeiro Alugador: Um Estudo Algorítmico. Tese (Doutorado em Ciência da Computação) – Universidade Federal do Rio Grande do Norte, Natal/RN, 2011.

BASTOS, R. E. M. O Problema do Caixeiro Viajante com Passageiros e Lotação. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal do Rio Grande do Norte, Natal/RN, 2017.

BRASIL. Ministério da Saúde. Saúde Brasil 2018: Uma análise da situação de saúde e das doenças e agravos crônicos: desafios e perspectivas. Brasília, 2019.

CALHEIROS, Z. S. A. Algoritmos Evolucionários na Solução do Caixeiro Viajante com Caronas. Monografia (Bacharelado em Ciência da Computação) – Universidade Federal do Rio Grande do Norte, Natal/RN, 2015.

CALHEIROS, Z. S. A. O Problema do Caixeiro Viajante com Passageiros. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal do Rio Grande do Norte, Natal/RN, 2017.

Curitiba é a quarta cidade mais congestionada do Brasil. Jornal Gazeta do Povo, Curitiba/PR, 07 de jul. de 2019. Disponível em: <https://www.gazetadopovo.com.br/curitiba/curitiba-quarta-cidade-mais-congestionada-do-brasil/>. Acesso em: 10 de jul. 2019.

DANTZIG, G. B.; FULKERSON, D. R.; JOHNSON, S. M. Solution of a large-scale traveling salesman problem. Journal of the Operations Research v. 2, n. 4, p. 393–410, 1954.

Dia do Meio Ambiente: veículos são os principais culpados pela poluição do ar em centros urbanos. Jornal O Estado do Maranhão, São Luís/MA, 09 de jun. de 2019. Disponível em: <https://imirante.com/oestadoma/noticias/2019/06/09/dia-do-meio-ambiente-veiculos-sao-os-principais-culpados-pela-poluicao-do-ar-em-centros-urbanos/>. Acesso em: 10 de jun. de 2019.

DIJKSTRA, E. A note on two problems in connexion with graphs. Numerische Mathematik, v. 1, p. 269-271, 1959.

GOLDBARG, M. C.; ASCONAVIETA, P. H.; GOLDBARG, E. F. G. Memetic algorithm for the traveling car renter problem: an experimental investigation. Memetic Computing, Springer-Verlag, v. 4, n. 2, p. 89–108, 2012.

GOLDBARG, M. C.; GOLDBARG, E. F. G.; LUNA, H. P. L.; MENEZES, M. S.; CORRALES, L. Integer programming models and linearizations for the traveling car renter problem. Optimization Letters v. 12, n. 4, 743–761, 2017.

GOLDBARG, M. C.; GOLDBARG, E. F. G.; MENEZES, M. S.; LUNA, H. P. L. A transgenetic algorithm applied to the Traveling Car Renter Problem. Expert Systems with Applications, v. 40, p. 6298–6310, 2013.

GOLDBARG, M. C.; LUNA, H. L. P. Otimização Combinatória e Programação Linear. 3ª ed., Elsevier, Rio de Janeiro/RJ, 2005.

LAPORTE, G. The Traveling Salesman Problem: An overview of exact and approximate algorithms. European Journal of Operational Research, v. 59, n. 2, p. 231–247, 1992.

MENEZES, M. S. O Problema do Caixeiro Alugador com Coleta de Prêmios: Um Estudo Algorítmico. Tese (Doutorado em Ciência da Computação) – Universidade Federal do Rio Grande do Norte, Natal/RN, 2014.

MILLER, C. E.; TUCKER, A. W.; ZEMLIN, R. A. Integer programming formulation of traveling salesman problems. Journal of the Association for Computing Machinery, v. 7, n. 4, p. 326–329, 1960.

RIOS, B. H. O.; GOLDBARG, E. F. G.; QUESQUÉN, G. Y. O. A hybrid metaheuristic using a corrected formulation for the Traveling Car Renter Salesman Problem. 2017 IEEE Congress on Evolutionary Computing, p. 2308–2314, 2017.

RIOS, B. H. O. Hibridização de Meta-Heurísticas com Métodos Baseados em Programação Linear para o Problema do Caixeiro Alugador. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal do Rio Grande do Norte, Natal/RN, 2018.

SABRY, G. A.; GOLDBARG, M. C.; GOLDBARG, E. F. G. Problema do Caixeiro Viajante Alugador com Passageiros: Uma Abordagem Algorítimica. XVIII Congresso Latino-Iberoamericano de Investigación Operativa, p. 764–771, 2016.

SABRY, G. A.; GOLDBARG, M. C.; GOLDBARG, E. F. G.; MENEZES, M. S.; CALHEIROS, Z. S. A. Models and Linearizations for the Traveling Car Renter with Passengers. Optimization Letters, 2019. [Submetido para Publicação]

SILVA, J. G. S. Algoritmos de Solução para o Problema do Caixeiro Viajante com Passageiros e Quota. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal do Rio Grande do Norte, Natal/RN, 2017.

Published

2019-11-12

How to Cite

Sabry, G. de A., Silva, B. de C. H., Goldbarg, M. C., Goldbarg, E. F. G., Menezes, M. da S., & Calheiros, Z. S. A. (2019). Uma análise sobre o problema do caixeiro viajante alugador com passageiros e seus subproblemas / An analysis of the traveling car renter with passengers and its subproblems. Brazilian Journal of Development, 5(11), 24449–24470. https://doi.org/10.34117/bjdv5n11-129

Issue

Section

Original Papers