Problema de roteamento de veículos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
Esquema gráfico de solução de um Problema de Roteamento de Veículos (PRV), com um só depósito.

O problema de roteamento de veículos (PRV) é um dos mais estudados problemas na área da otimização combinatória. Consiste no atendimento de um conjunto de consumidores por intermédio de uma frota de veículos, que partem de um ou mais pontos denominados depósitos. A restrição presente no PRV é que cada veículo v possui uma capacidade C{v} e o somatório de todas as demandas dos consumidores atendidos por um veículo v não pode ultrapassar C{v}.

O PRV, apesar do seu enunciado relativamente simples, apresenta elevada complexidade computacional, pelo que é interessante como problema no teste de diversas heurísticas.

Na literatura científica, Dantzig e Ramser foram os primeiros autores a formular o PRV, em 1959, quando estudaram a aplicação real na distribuição de gasolina para estações de venda de combustíveis no trabalho [1].

A função objetivo depende da tipologia e das características do problema. Os mais comuns são minimizar o custo total da operação, minimizar o tempo total de transporte, minimizar a distância total percorrida, minimizar o tempo de espera, maximizar o benefício, maximizar o serviço ao cliente, minimizar a utilização de veículos, equilibrar a utilização dos recursos, etc.

Motivação do tratamento do problema de roteamento de veículos[editar | editar código-fonte]

Os problemas de roteamento de veículos (PRVs) têm sido estudados com muito interesse nas últimas décadas. O foco no estudo desta classe de problema se deve à necessidade da diminuição de gastos em todo o processo que engloba desde a produção de uma mercadoria até sua venda. Pesquisas indicam que um considerável percentual do valor da mercadoria que chega aos clientes é de exclusiva responsabilidade dos gastos obtidos através de sua distribuição. Este valor é estimado no intervalo de 10% a 15% do preço dos produtos. O objetivo das pesquisas em torno dos PRVs é reduzir este percentual de gastos com transporte a um nível mais satisfatório, possibilitando reduções de preço nos produtos finais.

Basicamente, estes problemas se resumem ao atendimento de uma demanda, que pode se apresentar na forma de coleta e/ou entrega de pessoas ou mercadorias em uma determinada região geográfica ou espacial. A maioria das aplicações do PRV são geográficas e representadas por consumidores distribuídos em uma área de atendimento. Desta forma, o objetivo dos pesquisadores é desenvolver metodologias para atender as demandas do PRV de forma otimizada, visando a redução dos gastos com veículos e com o deslocamento dos mesmos.[2]

Variantes[editar | editar código-fonte]

Existe uma grande variedade de tipos de problemas PRV. Existem extensões ao PRV, como é o caso do VRP com janela de tempo (PRVJT). Este também considera o tempo para o atendimento dos consumidores. Cada consumidor c possui uma janela de tempo que o mesmo pode ser atendido (a{c}, b{c}). Além da informação da janela de tempo, o PRVJT possui um tempo de atendimento para cada consumidor (ST{c}).

Entre as extensões incluem-se assim:

Hoje devido a grande concorrência uma das grandes preocupações das empresas e indústrias é oferecer, a um custo mínimo, os melhores serviços. É sabido que no Brasil, o sistema rodoviário é usado como principal via para a coleta e/ou distribuição de mercadorias e serviços, estima-se que cerca de 10 a 15% do valor final destes produtos ou serviços esta diretamente relacionado com suas despesas de transporte, dentre elas podemos citar fatores como a alta dos combustíveis, a cobrança de pedágios, a manutenção dos veículos, a conservação das vias entre outros.

A necessidade da diminuição destes gastos tem elevado o interesse no estudo do problema de roteamento de veículos e seus derivados, isso porque seu principal foco de estudo é a diminuição dos gastos com todo o processo de distribuição de mercadorias, visando a diminuição deste percentual a níveis mais satisfatórios e mais atrativos no que se trata em termos de mercado.

Aplicações práticas[editar | editar código-fonte]

A possibilidade de aplicação para o modelo do roteamento de veículos e todas as suas derivações é muito brando, isso porque qualquer que seja o seguimento de negócio, sempre haverá a necessidade da diminuição de custos de produção e de valor final de venda, sem que para isso abra-se mão da qualidade, para que haja uma elevação no poder de negociação e de venda, esta é uma balança que deve estar sempre em equilíbrio e que pode ser a diferença entre o sucesso de uma empresa e o fracasso de outra.

Métodos utilizados para resolver o PRV[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. The Truck Dispatching Problem. DANTZIG, G. B.; RAMSER, R. H.; (1959). Management Science. 6. 80. acesso
  2. Um Modelo Híbrido Estocástico para Tratamento do Problema de Roteamento de Veículos com Janela de Tempo. Humberto César Brandão de Oliveira. Dissertação de Mestrado do Centro de Informática da Universidade Federal de Pernambuco. (2007). Texto de domínio público: download.
  3. Oliveira, H.C.B.de; Vasconcelos, G.C.. (2008). "A hybrid search method for the vehicle routing problem with time windows". Annals of Operations Research.
  4. Heuristic, Exact and Hybrid Approaches for Vehicle Routing Problems. ANAND SUBRAMANIAN. Tese de Doutorado do Instituto de Computação da Universidade Federal Fluminense. (2012). Texto de domínio público: download.


Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]