Compartilhar no facebook
Compartilhar no whatsapp
Compartilhar no twitter
Compartilhar no linkedin
Pesquisadores desenvolvem algoritmos para reduzir custos com transportes

Pesquisadores desenvolvem algoritmos para reduzir custos com transportes

Pesquisadores desenvolvem algoritmos para reduzir custos com transportes

Pesquisadores desenvolvem algoritmos para reduzir custos com transportes – Quem nunca ouviu a expressão caixeiro-viajante? Ela designa pessoas que, no passado, quando não havia facilidade do transporte entre diferentes municípios e até regiões, eram as responsáveis por levar produtos de um lugar a outro, percorrendo distâncias hoje inimagináveis. Esse trabalho passou a ser feito por empresas especializadas, porém, a distribuição logística nos moldes atuais se depara com o Problema de Roteamento de Veículos (PRV), um dos grandes desafios nas áreas de Ciência da Computação, Engenharia de Produção e Pesquisa Operacional.

Pensando nisso, um grupo de pesquisadores brasileiros e estrangeiros, liderados pelo professor Anand Subramanian, da Universidade Federal da Paraíba (UFPB), trabalhou na construção de algoritmos para elaborar um plano de roteamento de veículos que pudesse reduzir custos com transporte de produtos, levando em conta que o preço final de uma mercadoria sofre considerável acréscimo devido aos gastos obtidos através de sua distribuição. Subramanian e sua equipe desenvolveram algoritmos “altamente competitivos” capazes de minimizar esses custos.

Mas, afinal, o que é PRV? Um dos mais estudados problemas na área da Otimização Combinatória (OC), o PRV consiste basicamente em estabelecer e organizar, por meio de algoritmos, rotas ou itinerários eficientes para veículos realizarem entrega ou captação de mercadorias, que partem de um ou mais pontos, para destinos diversos.  Em outras palavras, PRV é uma generalização do clássico Problema do Caixeiro Viajante (PCV), que, de modo simplificado, tentava determinar a menor rota para percorrer várias cidades, sempre retornando à origem (os chamados depósitos).

“Você tem uma frota de veículos e um conjunto de clientes com demanda por entrega ou coleta. Então, a ideia é atender esses clientes minimizando a soma dos custos do deslocamento dos veículos. Mas isso é muito complicado de ser resolvido”, afirma Subramanian, que é bolsista de Produtividade em Pesquisa do Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq). Justamente por sua aplicabilidade e importância, o PRV é um dos problemas de distribuição logística mais conhecidos e estudados por pesquisadores no mundo inteiro, de acordo com o pesquisador.

Leia também:

Mobilidade urbana um desafio de todos

Para se ter uma ideia do nível do complexidade, Subramanian dá o seguinte exemplo: “Imagine uma situação em que você tem 100 clientes e deseja encontrar a melhor solução para reduzir seus custos. Se, por ventura, você tentar enumerar todas as soluções possíveis, esse número ultrapassa o número estimado de átomos existentes no universo. Mesmo supercomputadores mais potentes levariam anos para enumerar todas as possibilidades de maneira explícita e encontrar a melhor solução”, diz.

O pesquisador acrescenta que, em geral, problemas de otimização combinatória podem ser resolvidos de maneira exata com a utilização de algoritmos baseados em teoremas matemáticos, através dos quais se obtém a melhor solução encontrada – “O que a gente denomina de solução ótima” – explica Subramanian. Outra possibilidade é resolvê-los de forma heurística, em que uma solução de boa qualidade é obtida, “mas sem garantia de otimalidade”, ressalta o pesquisador.

“A desvantagem dos métodos exatos, mesmo garantindo a otimalidade, é que eles possuem uma complexidade exponencial e demandam um alto tempo computacional, enquanto os algoritmos heurísticos rodam mais rápido e são bem mais escaláveis. Por isso, acabam sendo bem mais utilizados na prática”, ressaltou.

O projeto coordenado por Subramanian considerou as duas vertentes, dependendo do problema. O pesquisador explica que o PRV possui inúmeras variantes, geralmente motivadas por situações reais. Por exemplo, em uma das variantes a frota de veículos é heterogênea, ou seja, os veículos não são idênticos. Outro caso é quando o cliente possui janelas de tempo para atendimento, não podendo ser atendido a qualquer momento, ou seja, as visitas estão limitadas a um dado período. É possível ainda combinar essas e outras variantes em um plano de roteamento de veículos, diz Subramanian.

Seu estudo levou em conta as variantes “clássicas” mencionadas acima e outras recém propostas na literatura científica, e, de acordo com suas próprias palavras, “obteve êxitos em produzir algoritmos altamente competitivos, inclusive superando a maioria das abordagens existente nas variantes consideradas”. Os algoritmos desenvolvidos pelo grupo podem ser embutidos em softwares já disponíveis no mercado ou a serem desenvolvidos, e a tendência é que se obtenha uma redução considerável de custos de transporte.

“No caso de empresas de grande porte, aquelas que têm ampla carteira de clientes e de pedidos, e numerosa frota de veículos, um plano eficiente de roteamento de veículos pode levar a uma redução anual substancial de custos de transporte. Também podem ser utilizados para verificar se o tamanho da frota está adequado, dentre outras possibilidades. Os impactos econômicos da pesquisa são enormes, e a gente acredita que os algoritmos desenvolvidos podem ser bastante benéficos e interessantes se postos em prática”, acredita Subramanian.

O PRV teve sua origem associada ao trabalho The Truck Dispatching Problem (O problema do despacho de caminhões, em tradução livre), desenvolvido por Dantzig e Ramser, em 1959. “No próximo ano, completa seis décadas deste trabalho pioneiro”, observa Subramanian. Segundo ele, a resolução por meio de métodos exatos é uma tarefa extremamente árdua. Por esta razão, o PRV pertence à classe NP-difícil, isto é, a dificuldade para encontrar a solução ótima por meio dos algoritmos exatos existentes cresce exponencialmente à medida que o número de clientes aumenta, conforme explicou.

Saiba mais – Anand Subramanian é graduado em Engenharia de Produção Mecânica pela UFPB (2006), com doutorado em Computação pela Universidade Federal Fluminense – UFF (2012). Sua tese de doutorado recebeu Menção Honrosa no Prêmio Capes de Tese. Atualmente, é Professor do Departamento de Sistemas de Computação do Centro de Informática da UFPB, tem experiência na área de Pesquisa Operacional, atuando nos temas Otimização Combinatória, Algoritmos Híbridos e Roteamento de Veículos, dentre outros.

O pesquisador também bolsista de produtividade em pesquisa do CNPq, tendo publicado mais de 30 artigos científicos em periódicos internacionais renomados na área de Pesquisa Operacional. A pesquisa Algoritmos eficientes para resolução de problemas de roteamento de veículos foi desenvolvida com recursos do CNPq. O montante – R$ 16.300,00 – foi destinado à aquisição de equipamentos, materiais de consumo, além de passagens aéreas e diárias relacionadas à congressos para membros da equipe.

Fonte

agosto 2019

19ago(ago 19)08:3021(ago 21)16:30Esocial na Administração Pública incluindo os novos layoutsCurso fundamental para capacitar os profissionais a fim de prestarem corretamente as informações ao eSocial.

22ago(ago 22)08:0023(ago 23)17:00Curso completo de SISMOB agosto de 2019Conheça a nova versão do Sistema de Monitoramento de Obras (Sismob).

26ago(ago 26)08:3028(ago 28)16:30Curso de Retenção de tributos em notas fiscaisConheça de forma clara e objetiva os procedimentos das retenções dos tributos (IRRF, INSS, PIS, COFINS, CSLL e ISS)

29ago(ago 29)08:0030(ago 30)18:00Emendas Parlamentares agosto de 2019Entenda o processo de captação de recursos através de emendas parlamentares

setembro 2019

02set(set 2)08:3004(set 4)16:30Novo Projeto Básico do Siconv completo prática Setembro de 2019Teoria e prática do novíssimo projeto básico do Sistema de Gestão de Convênios do Governo Federal – Siconv.

05set(set 5)08:0006(set 6)17:00Plataforma +Brasil Setembro de 2019 Incluindo atualizações do SiconvPlataforma +Brasil Setembro de 2019 incluindo atualizações do Siconv

09set(set 9)08:0010(set 10)17:00Marco Regulatório das Organizações da Sociedade Civil – Setembro de 2019Prepare editais de seleção de organizações da sociedade civil que assegurem processos econômicos e juridicamente eficientes.

11set(set 11)08:3013(set 13)16:30Desenvolvimento e Capacitação pra Pregoeiros e Equipe de ApoioSeja capaz de realizar pregões presenciais e eletrônicos na prática.

16set(set 16)08:0020(set 20)17:00Curso Plataforma +Brasil Completo Setembro de 2019Saiba tudo sobre o funcionamento da Plataforma +Brasil e sua correta utilização. Curso com todas as atualizações do módulo de transferências Voluntárias - Siconv

23set(set 23)08:0024(set 24)17:00A nova legislação de convênios e contratos de repasse setembro de 2019Curso Completo com foco na nova legislação de convênios e contratos de repasse

25set(set 25)08:3027(set 27)16:30Gestão de Frota VeículosConhecça uma visão diferenciada das atividades de Operação, Manutenção e Planejamento e Controle de Frota de Veículos.

30set08:0018:00Tudo sobre o Sistema de Informações sobre Orçamentos Públicos em Saúde - SIOPS - Setembro de 2019O programa aqui exposto visa trazer conceitos ligados ao SIOPS e todas as recentes alterações promovidas no sistema

outubro 2019

01out08:0018:00Gerenciamento do Sistema de Informações sobre Orçamentos Públicos em Educação – SIOPE – Outubro de 2019Administrando corretamente os recursos da Educação através do SIOPE e do SIGARP

02out(out 2)08:3004(out 4)16:30Folha de Pagamento do Funcionalismo PúblicoSaiba elaborar a folha de pagamento de servidores públicos corretamente.

07out(out 7)08:0011(out 11)17:00Curso Plataforma +Brasil Completo Outubro de 2019Saiba tudo sobre o funcionamento da Plataforma +Brasil e sua correta utilização. Curso com todas as atualizações do módulo de transferências Voluntárias - Siconv

14out(out 14)08:0018(out 18)17:00SIAFI Week Avançado Outubro 2019Aprofunde os conhecimentos para atuar na área de execução orçamentária, financeira e contábil através do SIAFI

21out(out 21)08:0022(out 22)18:00Emendas Parlamentares outubro de 2019Entenda o processo de captação de recursos através de emendas parlamentares

23out(out 23)08:3025(out 25)16:30Gestão da Comunicação e Mídias Sociais para a Administração PúblicaConheça os novos paradigmas da comunicação e debata os desafios impostos pela velocidade da comunicação no mundo digital.

28out(out 28)08:0029(out 29)17:00Curso prático de elaboração de termos de referência e projetos básicos outubro de 2019Assegure-se que o processo de licitação será econômico e juridicamente eficiente.

30out01novRevisão, Reequilíbrio e Reajuste de Contratos PúblicosConheça a legislação atualizada, a visão do Tribunal de Contas da União (TCU) e Jurisprudências na prática sobre o assunto.

Conheça a relação de cursos presenciais da I9 Treinamentos para o ano de 2019. Novos cursos e professores renomados. Clique na imagem abaixo e fique sabendo muito mais…

Conheça cursos presenciais I9 Treinamentos 2019