Engenharia

ASPECTOS PRÁTICOS DA APLICAÇÃO DE MODELOS DE ROTEIRIZAÇÃO DE VEÍCULOS A PROBLEMAS REAIS

O termo roteirização de veículos, embora não encontrado nos dicionários de língua portuguesa, é a forma que vem sendo utilizada como equivalente ao inglês “routing” (ou ”routeing”) para designar o processo para a determinação de um ou mais roteiros ou seqüências de paradas a serem cumpridos por veículos de uma frota, objetivando visitar um conjunto de pontos geograficamente dispersos, em locais pré-determinados, que necessitam de atendimento. O termo roteamento de veículos também é utilizado alternativamente por alguns autores (Cunha, 1997).

Segundo Laporte et al. (2000) o problema de roteirização de veículos consiste em definir roteiros de veículos que minimizem o custo total de atendimento, cada um dos quais iniciando e terminando no depósito ou base dos veículos, assegurando que cada ponto seja visitado exatamente uma vez e a demanda em qualquer rota não exceda a capacidade do veículo que a atende.

Quando a definição dos roteiros envolve não só aspectos espaciais ou geográficos, mas também temporais, tais como restrições de horários de atendimento nos pontos a serem visitados, os problemas são então denominados roteirização e programação de veículos (Cunha, 1997).

De acordo com Assad (1988), a roteirização de veículos consiste em uma das histórias de grande sucesso da Pesquisa Operacional nas últimas décadas. Isto pode ser medido pelo expressivo número de artigos que vêm sendo publicados ao longo dos anos na literatura especializada, incluindo os anais de congressos da ANPET.

O primeiro problema de roteirização a ser estudado foi o do folclórico caixeiro viajante (no inglês “traveling salesman problem” ou TSP), que consiste em encontrar o roteiro ou sequência de cidades a serem visitadas por um caixeiro viajante que minimize a distância total percorrida e assegure que cada cidade seja visitada exatamente uma vez.

Desde então, novas restrições vêm sendo incorporadas ao problema do caixeiro viajante, de modo a melhor representar os diferentes tipos de problemas que envolvem roteiros de pessoas e veículos, entre as quais: restrições de horário de atendimento (conhecidas na literatura como janelas de tempo ou janelas horárias); capacidades dos veículos; frota composta de veículos de diferentes tamanhos; duração máxima dos roteiros dos veículos (tempo ou distância); restrições de tipos de veículos que podem atender determinados clientes.

Problemas de roteirização de veículos são muitas vezes definidos como problemas de múltiplos caixeiros viajantes com restrições adicionais de capacidade, além de outras que dependem de cada aplicação.

Problemas do tipo caixeiro viajante também são encontrados em outras áreas que não a logística ou operação de frotas, tais como em linhas de montagem de componentes eletrônicos, onde se busca encontrar, por exemplo, o roteiro de mínima distância para um equipamento cuja tarefa é soldar todos os componentes de uma placa eletrônica. O menor percurso total do equipamento para percorrer todos os pontos da placa está diretamente associado ao desempenho da linha (Souza, 1993).

Sob a ótica de otimização, os problemas de roteirização de veículos, incluindo o caso particular do caixeiro viajante, pertencem à categoria conhecida como NP-difícil (do inglês “NP-hard”), o que significa que possuem ordem de complexidade exponencial. Em outras palavras, o esforço computacional para a sua resolução cresce exponencialmente com o tamanho do problema (dado pelo número de pontos a serem atendidos). A título de ilustração, até hoje não são conhecidas as respectivas soluções ótimas para algumas instâncias de problemas de roteirização com restrições de janelas de tempo com apenas 100 nós, propostos por Solomon (1986) e que vêm sendo utilizadas para a avaliação comparativa de novos algoritmos de solução propostos na literatura (Cunha, 1997).

Em termos práticos, isto significa que não é possível resolver até a otimalidade problemas reais pertencentes à classe NP-difícil. Consequentemente, os métodos de solução de todos os softwares e aplicativos comerciais encontrados no mercado para roteirização de veículos são heurísticos, isto é, não asseguram a obtenção da solução ótima do ponto de vista matemático.

Essa complexidade matemática dos problemas de roteirização, assim como a sua relevância no contexto logístico atual, explicam o constante interesse em busca de novas estratégias de solução que vem sendo observado desde a década de 60, resultando em um número muito expressivo de artigos publicados na literatura especializada.

Isto decorre do fato de que, sendo as estratégias de solução heurísticas, muitas vezes se apoiam em uma abordagem intuitiva, na qual a estrutura particular do problema possa ser considerada e explorada de forma inteligente, para a obtenção de uma solução adequada (Cunha, 1997). Assim, na maioria dos casos, as heurísticas propostas são bastante específicas e particulares, e carecem de robustez, isto é, não conseguem obter boas soluções para problemas com características, condicionantes ou restrições às vezes um pouco diferentes daquelas para as quais foram desenvolvidas.

Em outras palavras, roteirização de veículos é uma área onde uma solução para um determinado tipo de problema e dados pode não ser adequada para outro problema similar, conforme apontado por Hall e Partyka (1997). Daí, em muitos casos, a necessidade de buscar soluções customizadas para cada problema.

Por outro lado, o interesse e a demanda pela aplicação de modelos de roteirização para problema reais, através de softwares comerciais disponíveis no mercado, têm crescido muito nos últimos anos, em particular no Brasil, principalmente após a estabilização da economia, conforme discutido em detalhes por Cunha (1997). Entre as razões pode-se destacar as exigências dos clientes com relação a prazos, datas e horários de atendimento (principalmente entregas); o agravamento dos problemas de trânsito, acesso, circulação e estacionamento de veículos nos centro urbanos, em particular caminhões; o aumento da competição pelo mercado e a busca de eficiência trazidas pela eliminação da inflação; o custo de capital levando à redução de estoques e ao aumento da freqüência de entregas.

Tem se observado em diversas aplicações, principalmente no caso brasileiro, que, embora a seleção e a implantação de softwares de roteirização tenha sido feita com cuidado, os benefícios obtidos com a sua utilização resultam aquém das expectativas iniciais, mesmo em se tratando de produtos consagrados no mercado.

Isso decorre nem sempre da fragilidade dos algoritmos de solução incorporados nos softwares, na maioria das vezes extensivamente testados e validados, com inúmeras histórias de sucesso nos seus países de origem, mas principalmente de condicionantes locais e particularidades dos problemas que não podem ser considerados, assim como da fragilidade dos dados de entrada que alimentam os modelos.

Deve-se destacar ainda dificuldades na etapa de escolha do produto. O fato da maioria desses produtos serem verdadeiras caixas pretas em termos dos seus algoritmos de solução, conforme apontado por Hall e Partyka (1997), e o pouco conhecimento técnico especializado por parte dos representantes locais, acabam levando a escolhas que posteriormente se mostram equivocadas, uma vez que os softwares nem sempre conseguem atender às necessidades para os quais foram adquiridos.

Autor: Dr Claudio Barbieri da Cunha

- Dicionario De Pneus E Pneus Run Flat, Rft Ou Pax
AquaplanagemEfeito do pneus quando lisos, sem frisos, tem ao tentar freiar e derrapar deslisando no solo como se planasse como um Aircraft. Banda de rodagem Parte superior do pneu, onde se encontram os frisos. Se extende de ombro a ombro. Baquielização...

- Qual é A Diferença Entre Alinhamento E Balanceamento?
As pessoas confudem frequentemente o alinhamento e o balanceamento, mas eles são completamente diferentes.Se você percebe que seu carro puxa para a direita ou esquerda quando você libera o volante por um curto período de tempo, você precisa...

- → 10 Motivos Que Levam Engenheiros De ProduÇÃo A Adotarem Ferramentas Aps
As ferramentas APS - Advanced Planning & Schedule - são sistemas de planejamento avançado da produção, complementares aos ERPs, que se propõe a gerir melhor a capacidade de recursos produtivos e sequenciamento da produção. O engenheiro de...

- LÓgica Da ProgramaÇÃo Para AutomaÇÃo.
Iremos abordar um breve resumo sobre logica de programação voltada a Automação. Sinais elétricos servem para representar valores (sensor ou atuador) e, cabe a nós trabalharmos em cima da lógica do processo para então termos o nosso sinal elétrico...

- Novidades - Visual Studio 2013
A grande aceitação da plataforma .NET junto à comunidade de desenvolvedores foi possível, sem sobra de dúvidas, à existência de uma poderosa IDE para a implementação dos mais variados tipos de aplicações: o Visual Studio .NET. Desde os seus...

Engenharia