CNPq

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.

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.

Prof. Subramanian e alunos trabalham nas pesquisas que geraram os algoritmos. Foto: Bruno Petrato Bruck/Divulgação

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.

Produção do Programa de Divulgação e Disseminação Científica do CNPq