Problema de roteamento de veículos

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.

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

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

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

A utilização de modelos de roteamento de veículos em aplicações práticas é extensa. Por esse motivo, os sistemas devem possuir algoritmos de busca da solução utilizando metodologias eficientes e adaptadas para operar em diferentes tipos de operações.

No Brasil, softwares de roteirização são utilizados em empresas com operações logísticas complexas dos mais diversos setores:

Atacado e varejo;
Operadores logísticos;
Distribuidores, especialmente de alimentos;
Transporte de valores, entre outros.

As principais aplicações são o planejamento de rotas de veículos como vans, caminhões, ônibus, navios, aeronaves, etc, transportando pessoas, mercadorias ou matérias primas.

Os principais benefícios na utilização de softwares comerciais de roteirização são:^[3].

redução de até 25% da frota de veículos;
aumento do número de entregas por mês;
redução de até 20% nos custos de entrega;
aumento da ocupação da frota;
redução de distância percorrida e consumo de combustível;
diminuição de entregas duplicadas.

Existem diversos softwares comerciais que fazem a roteirização de veículos. Até os anos 2000, a maioria utilizava bases próprias de informação geográfica. Atualmente, vários softwares utilizam computação na nuvem e bases de dados geográficos do Google Maps, Bing Maps, entre outros e podem ser integrados com sistemas de rastreamento por satélite e telemetria.^[4].

Métodos utilizados para resolver o PRV

Metaheurísticas

Algoritmos genéticos: os algoritmos genéticos são procedimentos probabilísticos de busca que se baseia na teoria da evolução genética. Diferentemente das outras metaheurísticas, os algoritmos genéticos trabalham com uma população de soluções que sofrem modificações a cada geração através da aplicação de operadores genéticos. A ideia central é que a solução escolhida seja aquela que tenha melhor adaptação relativa, medida através de uma valor de fitness, que envolve o objetivo global da otimização.
Colônia de formigas
Simulated Annealing
Busca Tabu
GRASP

Heurísticas

Push-forward insertion heuristic (PFIH)

Software livre para resolver o PRV

Nome (ordem alfabética)	Licença	Linguagem da API	Breve descrição
jsprit	LGPL	Java	Ferramentas de código aberto escritas em java (lightweight) para resolver diversos tipos de PRVs. link. O jsprit foi integrado a uma interface de usuário compatível com o Excel que disponibiliza diversas funcionalidades, como edição de rotas, utilização de mapas rodoviários reais e geração de relatórios. link
Open-VRP	LLGPL	Lisp	Open-VRP para Lisp, hospedado no Github. link
OptaPlanner	Apache License	Java	Resolvedor baseado em Satisfação de restrições (optaplanner.org) com exemplos do PRV.
SYMPHONY	Common Public License 1.0		Resolvedor de código aberto para problemas de programação inteira mista com suporte para PRVs. link
VRP Spreadsheet Solver	Common Public License 1.0		Resolvedor de código aberto baseado no Microsoft Excel e em VBA. Possui conexão com um sistema público de GIS para obtenção de dados. link
vrphlibrary (VRPH)	Common Public License 1.0		Página do VRPH link.
vroom	?		Bibliotecas de código aberto para o PRV e PRV dinâmico. link

Referências

↑ The Truck Dispatching Problem. DANTZIG, G. B.; RAMSER, R. H.; (1959). Management Science. 6. 80. acesso
↑ 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.
↑ Melo, A. C. S; Filho, V. J. F. (2001). «Sistemas de Roteirização e Programação de Veículos». Produção Online vol.21, n.2. Consultado em 11 de novembro de 2015 download.
↑ «Sistema Roteirizador de Entregas». NeoInfinito. 28 de outubro de 2015. Consultado em 11 de novembro de 2015
↑ 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.
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. Consultado em 29 de janeiro de 2009
«Roteirizador RoutEasy - Roteirização e Gestão de Entregas». www.routeasy.com.br (em português). Consultado em 26 de maio de 2017

Ver também

Ligações externas

[1]

[2]

[3]

[4]