Algoritmo genético aplicado ao problema de roteamento de veículos: problema do caixeiro viajante no setor varejista
DOI:
https://doi.org/10.47385/cadunifoa.v15.n43.3273Palavras-chave:
Cadeia de suprimentos. Localização de facilidades. Heurística. Gestão adaptativa da diversidade populacional. Solução ideal.Resumo
Problemas de otimização têm como foco principal encontrar uma solução viável entre alternativas possíveis. O Traveling Salesman Problem (TSP) pertence a esta classe de problemas. No entanto, devido a existência de uma variada pluraridade de dimensões e variáveis, as quais compõe o TSP, não é possível encontrar sua solução viável em um tempo polinomial definido. E, é por isso, que é considerado um dos problemas difíceis de NP-hard. Por esses motivos, apresentamos proposta de um Genetic Algorithm (GA) híbrido para resolução do Traveling Salesman Problem (TSP), no qual o operador de crossover é empregado em uma aplicação local. Esta aplicação obteve soluções adequadas para um ambiente urbano, com um tempo computacional aceitável para o TSP, integrando o GA e as condições ambientais locais. Os resultados experimentais ilustram que a proposta apresentada além de atender as condicionantes locais da unidade de pesquisa, também, pode ser utilizada em outras situações, sendo parametrizável e adaptável a outros algoritmos genéticos, fornecendo com isso, precisão e eficiência satisfatória no processamento real da otimização.Downloads
Referências
BOARNET, M. G.; GIULIANO, G.; HOU, Y.; SHIN, E. J. First/last mile transit access as an equity planning issue. Transportation Research Part A: Policy and Practice, v. 103, p. 296-310, 2017.
BRAEKERS, K.; RAMAEKERS, K.; VAN NIEUWENHUYSE, I. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, v. 99, p. 300-313, 2016.
BRASIL. Lei nº 12.587, de 3 de janeiro de 2012. Institui as diretrizes da Política Nacional de Mobilidade Urbana. Diário Oficial [da] República Federativa do Brasil: seção 1, Brasília, DF, seção 1, p. 1, 4 jan. 2012.
CLEOPHAS, C.; COTTRILL, C.; EHMKE, J. F.; TIERNEY, K. Collaborative urban transportation: recent advances in theory and practice. European Journal of Operational Research, v. 273, n. 3, p. 801-816, 2019.
DANTZIG, G. B.; RAMSER, J. H. The truck dispatching problem. Management Science, v. 6, n. 1, p. 80-91, 1959.
DIBBLE, J.; PRELORENDJOS, A.; ROMICE, O.; ZANELLA, M.; STRANO, E.; PAGEL, M.; PORTA, S. On the origin of spaces: Morphometric foundations of urban form evolution. Environment and Planning B: Urban Analytics and City Science, v. 46, n. 4, p. 707-730, 2019.
DORIGO, M.; GAMBARDELLA, L. M. Ant colony system: A cooperative learning approach to the traveling salesman problem. Transactions on Evolutionary Computation, v. 1, n. 1, p. 53-66, 1997.
ELGESEM, A. S.; SKOGEN, E. S.; WANG, X.; FAGERHOLT, K. A traveling salesman problem with pickups and deliveries and stochastic travel times: An application from chemical shipping. European Journal of Operational Research, v. 269, n. 3, p. 844-859, 2018.
GONÇALVES, D. N. S.; GONÇALVES, C. M.; ASSIS, T. F.; SILVA, M. A. Analysis of the difference between the euclidean distance and the actual road distance in Brazil. Transportation Research Procedia, v. 3, p. 876-885, 2014.
GOOGLE INC. Company Information. Google Earth®. Disponível em: <http://www.google.com.br/intl/pt-BR/earth>. Acesso em: 24 mai. 2019.
GUERRA, E. Planning for cars that drive themselves: Metropolitan planning organizations, regional transportation plans, and autonomous vehicles. Journal of Planning Education and Research, v. 36, n. 2, p. 210-224, 2016.
HANDY, S. L.; BOARNET, M. G.; EWING, R.; KILLINGSWORTH, R. E. How the built environment affects physical activity: views from urban planning. American Journal of Preventive Medicine, v. 23, n. 2, p. 64-73, 2002.
HOLLAND, J. H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press, 1992.
IBGE - Instituto Brasileiro de Geografia e Estatística. Censo Demográfico 2010: Microdados da pesquisa. Disponível em: <https://censo2010.ibge.gov.br/resultados.html>. Acesso em: 16 jun. 2019.
IPEA - Instituto de Pesquisa Econômica Aplicada. Desafios da mobilidade urbana no Brasil. Texto para Discussão, 2016. Disponível em: <http://www.ipea.gov.br/>. Acesso em: 16 mar 2019.
JUNEJA, S. S.; SARASWAT, P.; SINGH, K.; SHARMA, J.; MAJUMDAR, R.; CHOWDHARY, S. Travelling Salesman Problem Optimization Using Genetic Algorithm. In 2019 Amity International Conference on Artificial Intelligence (AICAI), p. 264-268.
KAMARGIANNI, M.; LI, W.; MATYAS, M.; SCHÄFER, A. A critical review of new mobility services for urban transport. Transportation Research Procedia, v. 14, p. 3294-3303, 2016.
KARAKATIČ, S.; PODGORELEC, V. A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, v. 27, p. 519-532, 2015.
LAPORTE, G. The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, v. 59, n. 3, p. 345-358, 1992.
MÄKINEN, K.; KIVIMAA, P.; HELMINEN, V. Path creation for urban mobility transitions: Linking aspects of urban form to transport policy analysis. Management of Environmental Quality: An International Journal, v. 26, n. 4, p. 485-504, 2015.
MARTORELLI, M.; COSTA, A. G. V.; SÁ, A. C. B. A inclusão do transporte de cargas no sistema nacional de mobilidade urbana. Revista LOGS: Logística e Operações Globais Sustentáveis, v. 1, n.1, p. 182-197, 2019.
MCCORMICK, K.; ANDERBERG, S.; COENEN, L.; NEIJ, L. Advancing sustainable urban transformation. Journal of Cleaner Production, v. 50, p. 1-11, 2013.
MURRAY, C. C.; CHU, A. G. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, v. 54, p. 86-109, 2015.
OLIVEIRA, L. K.; HENRIQUES, R. S.; OLIVEIRA, R. S.; DENAIS, M. Análise dos benefícios de um espaço logístico urbano na distribuição urbana de mercadorias. Revista Produção Online, v.16, n. 3, p. 988-1006, 2016.
OSABA, E.; YANG, X. S.; DIAZ, F.; LOPEZ-GARCIA, P.; CARBALLEDO, R. An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Engineering Applications of Artificial Intelligence, v. 48, p. 59-71, 2016.
OYOLA, J.; ARNTZEN, H.; WOODRUFF, D. L. The stochastic vehicle routing problem, a literature review, part I: models. EURO Journal on Transportation and Logistics, v. 7, n. 3, p. 193-221, 2018.
RODRIGUE, J. P.; COMTOIS, C.; SLACK, B. The geography of transport systems. Routledge, 2016.
SCHIFFER, M.; SCHNEIDER, M.; WALTHER, G.; LAPORTE, G. Vehicle Routing and Location Routing with Intermediate Stops: A Review. Transportation Science, v. 53, n. 2, p. 319-343, 2019.
SILVA, J. G. S. Algoritmos de solução para o problema do caixeiro viajante com passageiros e quota. Dissertação (Mestrado em Sistemas e Computação). Programa de Pós-Graduação em Sistemas e Computação, Universidade Federal do Rio Grande do Norte, Natal, Brasil, 2017.
STIGLIC, M.; AGATZ, N.; SAVELSBERGH, M.; GRADISAR, M. Enhancing urban mobility: Integrating ride-sharing and public transit. Computers & Operations Research, v. 90, p. 12-21, 2018.
VARUN KUMAR, S. G.; PANNEERSELVAM, R. A study of crossover operators for genetic algorithms to solve VRP and its variants and new sinusoidal motion crossover operator. International Journal of Computational Intelligence Research, v. 13, n. 7, p. 1717-1733, 2017.
VEENSTRA, M.; ROODBERGEN, K. J.; VIS, I. F.; COELHO, L. C. The pickup and delivery traveling salesman problem with handling costs. European Journal of Operational Research, v. 257, n. 1, p. 118-132, 2017.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
CESSIONÁRIA
FUNDAÇÃO OSWALDO ARANHA - FOA, mantenedora do CENTRO UNIVERSITÁRIO DE VOLTA REDONDA - UniFOA,
entidade fundacional com personalidade jurídica sem fins lucrativos de direito privado, inscrita no CNPJ sob nº 32.504.995/0001-14, com sede na Avenida Dauro Peixoto Aragão, nº 1325, bairro Três Poços, Volta Redonda – RJ, doravante denominada FOA/UniFOA.
CLÁUSULA PRIMEIRA: O CEDENTE cede e transfere gratuitamente sem direito a remuneração, reembolso ou compensação de qualquer natureza, em caráter irrevogável e irretratável à FOA/UniFOA, todos os direitos autorais (morais e patrimoniais) relativo à obra acima intitulada, tudo em conformidade com a Lei nº 9.610/98.
PARÁGRAFO PRIMEIRO: O CEDENTE desde já, declara que a obra cedida é de sua exclusiva autoria, assumindo total responsabilidade civil e penal, quanto ao conteúdo, citações e referências que fazem parte de seu conteúdo, bem como, por eventuais questionamentos judiciais ou extrajudiciais em decorrência de sua divulgação, devendo concordar inequivocamente com a exclusão da FOA/UniFOA do polo passivo de quaisquer demandas.
PARÁGRAFO SEGUNDO: O CEDENTE assume inteira responsabilidade pelos dados pessoais tratados em função da obra acima intitulada, declarando ainda que observou sempre que possível, os critérios de anonimização ou pseudonimização dos dados para publicação final pela FOA/UniFOA, de acordo com artigo 7º, IV da Lei nº 13.709/2018.
PARÁGRAFO TERCEIRO: Na hipótese de existirem na obra acima intitulada dados pessoais identificados ou identificáveis, que não passaram por processo de anonimização, o CEDENTE declara que informou e disponibilizou aos titulares/terceiros, mecanismos de exercício dos direitos previstos na Lei nº 13.709/18.
PARÁGRAFO QUARTO: Os dados pessoais identificados ou identificáveis presentes na obra acima intitulada, ficarão disponíveis após publicação pela FOA/UniFOA, nos termos do art. 16, II da Lei nº 13.709/2018.
CLÁUSULA SEGUNDA: A FOA/UniFOA fica autorizada a utilizar, reproduzir, distribuir, divulgar, disponibilizar, publicar e licenciar a obra, sob qualquer forma e por quaisquer meios admitidos em lei, inclusive em ambiente digital, observadas as políticas editoriais da instituição e as licenças de uso adotadas para a publicação.
PARÁGRAFO ÚNICO: A utilização, reprodução, divulgação, publicação, compartilhamento, licenciamento ou qualquer outra forma de exploração autorizada da obra pela FOA/UniFOA não gerará ao CEDENTE qualquer direito à remuneração, reembolso, indenização, compensação financeira, participação em receitas ou vantagem econômica de qualquer natureza, permanecendo a presente cessão e autorização em caráter integralmente gratuito.
CLÁUSULA TERCEIRA: A FOA/UniFOA fica autorizada a promover o registro da obra na forma prevista no artigo 19 da Lei nº 9.610/1998, podendo averbar a presente autorização/cessão à margem do registro a que se refere o artigo 19 da Lei nº 9.610/1998, ou não estando a obra registrada, poderá a presente cessão ser registrada em Cartório de Títulos e Documentos, em havendo necessidade.
CLÁUSULA QUARTA: O presente instrumento é firmado por prazo indeterminado.
CLÁUSULA QUINTA: O CEDENTE outorga à FOA/UniFOA, a mais plena, geral, rasa, irretratável, irrestrita e inequívoca quitação pela presente cessão e transferência dos direitos autorais da obra intitulada acima, renunciando a todo e qualquer direito porventura existente, obrigando-se em todos os seus termos e condições, por si, seus herdeiros e sucessores.
CLÁUSULA SEXTA: O CEDENTE desde já está ciente e de acordo que:
- A obra não poderá ser comercializada e sua contribuição não gerará ônus para a FOA/UniFOA;
- A obra será disponibilizada em formato digital no sítio eletrônico do UniFOA para pesquisas e downloads de forma gratuita;
- A obra não será impressa, salvo em casos específicos cabendo à Editora FOA a definição;
- Todo o conteúdo é de total responsabilidade dos autores na sua forma e originalidade;
- Todas as imagens utilizadas (fotos, ilustrações, vetores e etc.) devem possuir autorização para uso;
- Que a obra não se encontra sob a análise em qualquer outro veículo de comunicação científica, caso contrário o CEDENTE deverá justificar a submissão à Editora FOA, que analisará o pedido, podendo ser autorizado ou não.
CLÁUSULA SÉTIMA: A obra objeto da presente cessão poderá ser disponibilizada pela FOA/UniFOA sob a licença Creative Commons Atribuição-NãoComercial (CC BY-NC), identificada na imagem abaixo - ou outra licença que venha a ser definida pela FOA/UniFOA, observados os critérios editoriais, institucionais, científicos e os requisitos estabelecidos por bases indexadoras, repositórios acadêmicos, organismos de fomento, sistemas de divulgação científica ou demais normas aplicáveis à publicação da obra.
PARÁGRAFO ÚNICO: O CEDENTE declara estar ciente e concordar que a escolha, alteração ou atualização da licença de publicação da obra constitui prerrogativa exclusiva da FOA/UniFOA, desde que observadas as finalidades acadêmicas, científicas e institucionais da publicação.
CLÁUSULA OITAVA: O CEDENTE está ciente e de acordo que tem por obrigação solicitar a autorização expressa dos coautores da obra/artigo, bem como dos professores orientadores antes da submissão do mesmo, se obrigando inclusive a mencioná-los no corpo da obra, sob pena de responder exclusivamente pelos danos causados.
