Problema de roteamento de veículos - Vehicle routing problem

Uma figura ilustrando o problema de roteamento de veículos

O problema de roteamento de veículos ( VRP ) é um problema de otimização combinatória e programação inteira que pergunta "Qual é o conjunto ideal de rotas para uma frota de veículos percorrer a fim de entregar a um determinado conjunto de clientes?". Ele generaliza o conhecido problema do caixeiro viajante (TSP). Ele apareceu pela primeira vez em um artigo de George Dantzig e John Ramser em 1959, no qual a primeira abordagem algorítmica foi escrita e aplicada a entregas de gasolina. Freqüentemente, o contexto é o de entrega de mercadorias localizadas em um depósito central para clientes que fizeram pedidos para tais mercadorias. O objetivo do VRP é minimizar o custo total da rota. Em 1964, Clarke e Wright aprimoraram a abordagem de Dantzig e Ramser usando uma abordagem gananciosa efetiva chamada algoritmo de economia.

Determinar a solução ótima para VRP é NP-difícil , então o tamanho dos problemas que podem ser resolvidos, de forma otimizada, usando programação matemática ou otimização combinatória pode ser limitado. Portanto, os solucionadores comerciais tendem a usar heurísticas devido ao tamanho e à frequência das VRPs do mundo real que precisam resolver.

O VRP tem muitas aplicações diretas na indústria. Na verdade, o uso de programas de otimização de computador pode gerar uma economia de 5% para uma empresa, já que o transporte é geralmente um componente significativo do custo de um produto (10%) - na verdade, o setor de transporte representa 10% do PIB da UE . Conseqüentemente, qualquer economia gerada pelo VRP, mesmo inferior a 5%, é significativa.

Configurando o problema

O VRP diz respeito ao serviço de uma empresa de entrega. Como as coisas são entregues a partir de um ou mais depósitos que têm um determinado conjunto de veículos domésticos e operados por um conjunto de motoristas que podem se deslocar em uma determinada rede rodoviária para um conjunto de clientes . Ele pede a determinação de um conjunto de rotas , S , (uma rota para cada veículo que deve começar e terminar em seu próprio depósito) de forma que todos os requisitos dos clientes e restrições operacionais sejam atendidos e o custo global de transporte seja minimizado. Este custo pode ser monetário, à distância ou outro.

A rede de estradas pode ser descrita usando um gráfico onde os arcos são estradas e vértices são junções entre eles. Os arcos podem ser direcionados ou não direcionados devido à possível presença de ruas de mão única ou custos diferentes em cada direção. Cada arco tem um custo associado que geralmente é sua duração ou tempo de viagem, que pode depender do tipo de veículo.

Para saber o custo global de cada rota, o custo da viagem e o tempo de viagem entre cada cliente e o depósito devem ser conhecidos. Para fazer isso, nosso gráfico original é transformado em um onde os vértices são os clientes e o depósito, e os arcos são as estradas entre eles. O custo em cada arco é o custo mais baixo entre os dois pontos da rede rodoviária original. Isso é fácil de fazer, pois os problemas do caminho mais curto são relativamente fáceis de resolver. Isso transforma o gráfico original esparso em um gráfico completo . Para cada par de vértices i e j , existe um arco (i, j) do grafo completo cujo custo é escrito como e é definido como sendo o custo do caminho mais curto de i a j . O tempo de viagem é a soma dos tempos de viagem dos arcos no caminho mais curto de i para j no gráfico rodoviário original. ${\ displaystyle C_ {ij}}$ ${\ displaystyle t_ {ij}}$

Às vezes, é impossível satisfazer todas as demandas de um cliente e, em tais casos, os solucionadores podem reduzir as demandas de alguns clientes ou deixar alguns clientes sem atendimento. Para fazer face a estas situações pode ser introduzida uma variável prioritária para cada cliente ou associadas penalidades pela parcial ou falta de serviço de cada cliente prestado

A função objetivo de um VRP pode ser muito diferente, dependendo da aplicação particular do resultado, mas alguns dos objetivos mais comuns são:

Minimize o custo de transporte global com base na distância global percorrida, bem como os custos fixos associados aos veículos e motoristas usados
Minimize o número de veículos necessários para atender todos os clientes
Menor variação no tempo de viagem e carga do veículo
Minimize as penalidades por serviço de baixa qualidade
Maximize um lucro / pontuação coletado.

Variantes VRP

Um mapa que mostra a relação entre subproblemas comuns de VRP.

Existem várias variações e especializações do problema de roteamento de veículos:

Problema de Roteamento de Veículos com Lucros (VRPP): Um problema de maximização em que não é obrigatório visitar todos os clientes. O objetivo é visitar uma vez os clientes maximizando a soma dos lucros arrecadados, respeitando o limite de tempo do veículo. Os veículos devem começar e terminar no depósito. Dentre os VRPP mais conhecidos e estudados, citamos:
- O Problema de Orientação de Equipes (TOP) que é a variante mais estudada do VRPP,
- O Problema de Orientação de Equipes Capacitadas (CTOP),
- O TOP com janelas de tempo (TOPTW).
Problema de roteamento de veículos com coleta e entrega (VRPPD): Uma série de mercadorias precisa ser movida de determinados locais de coleta para outros locais de entrega. O objetivo é encontrar rotas ideais para uma frota de veículos visitar os locais de coleta e entrega.
Problema de roteamento de veículos com LIFO : Semelhante ao VRPPD, exceto que uma restrição adicional é colocada no carregamento dos veículos: em qualquer local de entrega, o item sendo entregue deve ser o item retirado mais recentemente. Este esquema reduz os tempos de carga e descarga nos locais de entrega, pois não há necessidade de descarregar temporariamente outros itens além dos que devem ser entregues.
Problema de Roteamento de Veículos com Janelas de Tempo (VRPTW): Os locais de entrega possuem janelas de tempo dentro das quais as entregas (ou visitas) devem ser feitas.
Problema de roteamento de veículos capacitados: CVRP ou CVRPTW. Os veículos têm uma capacidade limitada de carga das mercadorias que devem ser entregues.
Problema de roteamento de veículos com viagens múltiplas (VRPMT): Os veículos podem fazer mais de uma rota.
Problema de Roteamento de Veículo Aberto (OVRP): Os veículos não são obrigados a retornar ao depósito.
Problema de roteamento de estoque (IRP): os veículos são responsáveis por atender às demandas em cada ponto de entrega
Problema de roteamento de veículos com vários depósitos (MDVRP): Existem vários depósitos a partir dos quais os veículos podem começar e terminar.

Vários fornecedores de software criaram produtos de software para resolver vários problemas de VRP. Numerosos artigos estão disponíveis para mais detalhes sobre suas pesquisas e resultados.

Embora o VRP esteja relacionado ao Job Shop Scheduling Problem, os dois problemas são normalmente resolvidos usando técnicas diferentes.

Métodos de solução exata

Existem três abordagens principais diferentes para modelar o VRP

Formulações de fluxo de veículos - usa variáveis inteiras associadas a cada arco que contam o número de vezes que a borda é percorrida por um veículo. Geralmente é usado para VRPs básicos. Isso é bom para os casos em que o custo da solução pode ser expresso como a soma de todos os custos associados aos arcos. No entanto, ele não pode ser usado para lidar com muitas aplicações práticas.
Formulações de fluxo de commodities - variáveis inteiras adicionais são associadas aos arcos ou bordas que representam o fluxo de commodities ao longo dos caminhos percorridos pelos veículos. Isso só recentemente foi usado para encontrar uma solução exata.
Definir o problema de particionamento - Estes têm um número exponencial de variáveis binárias, cada uma associada a um circuito viável diferente. O VRP é então formulado como um problema de particionamento de conjuntos que pergunta qual é a coleção de circuitos com custo mínimo que satisfaz as restrições do VRP. Isso permite custos de rota muito gerais.

Formulações de fluxo de veículos

A formulação do TSP por Dantzig, Fulkerson e Johnson foi estendida para criar as duas formulações de fluxo de veículo de índice para o VRP

{\ displaystyle {\ text {min}} \ sum _ {i \ in V} \ sum _ {j \ in V} c_ {ij} x_ {ij}}

sujeito a

{\ displaystyle \ sum _ {i \ in V} x_ {ij} = 1 \ quad \ forall j \ in V \ barra invertida \ esquerda \ {0 \ direita \}}

( 1 )

{\ displaystyle \ sum _ {j \ in V} x_ {ij} = 1 \ quad \ forall i \ in V \ barra invertida \ esquerda \ {0 \ direita \}}

( 2 )

{\ displaystyle \ sum _ {i \ in V} x_ {i0} = K}

( 3 )

{\ displaystyle \ sum _ {j \ in V} x_ {0j} = K}

( 4 )

{\ displaystyle \ sum _ {i \ notin S} \ sum _ {j \ in S} x_ {ij} \ geq r (S), ~~ \ forall S \ subseteq V \ setminus \ {0 \}, S \ neq \ emptyset}

( 5 )

{\ displaystyle x_ {ij} \ in \ {0,1 \} \ quad \ forall i, j \ in V}

( 6 )

Nesta formulação representa o custo de ir de nó a nó , é uma variável binária que tem valor se o arco que vai de a for considerado parte da solução e caso contrário, é o número de veículos disponíveis e corresponde ao número mínimo de veículos necessário para servir o conjunto . Também estamos assumindo que é o nó do depósito. ${\ displaystyle c_ {ij}}$ ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle x_ {ij}}$ ${\ displaystyle 1}$ ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle 0}$ ${\ displaystyle K}$ ${\ displaystyle r (S)}$ ${\ displaystyle S}$ ${\ displaystyle 0}$

As restrições 1 e 2 afirmam que exatamente um arco entra e exatamente um sai de cada vértice associado a um cliente, respectivamente. As restrições 3 e 4 dizem que o número de veículos que saem do depósito é o mesmo que o número que entra. As restrições 5 são as restrições de corte de capacidade, que impõem que as rotas devem ser conectadas e que a demanda em cada rota não deve exceder a capacidade do veículo. Finalmente, as restrições 6 são as restrições de integralidade.

Uma restrição arbitrária entre as restrições está, na verdade, implícita nas demais , para que possa ser removida. Cada corte definido por um conjunto de cliente é atravessado por um número de arcos não menor que (número mínimo de veículos necessários para servir o conjunto ). ${\ displaystyle 2 | V |}$ ${\ displaystyle 2 | V | -1}$ ${\ displaystyle S}$ ${\ displaystyle r (S)}$ ${\ displaystyle S}$

Uma formulação alternativa pode ser obtida transformando as restrições de corte de capacidade em restrições de eliminação de subtour generalizadas (GSECs).

{\ displaystyle \ sum _ {i \ in S} \ sum _ {j \ in S} x_ {ij} \ leq | S | -r (S)}

o que impõe que pelo menos arcos saiam de cada conjunto do cliente . ${\ displaystyle r (S)}$ ${\ displaystyle S}$

GCECs e CCCs têm um número exponencial de restrições, portanto é praticamente impossível resolver a relaxação linear. Uma maneira possível de resolver isso é considerar um subconjunto limitado dessas restrições e adicionar o restante, se necessário.

Um método diferente é usar uma família de restrições que têm uma cardinalidade polinomial, que são conhecidas como restrições MTZ, elas foram propostas pela primeira vez para o TSP e posteriormente estendidas por Christofides, Mingozzi e Toth.

{\ displaystyle u_ {j} -u_ {i} \ geq d_ {j} -C (1-x_ {ij}) ~~~~~~~ \ forall i, j \ in V \ barra invertida \ {0 \}, i \ neq j ~~~~ {\ text {st}} d_ {i} + d_ {j} \ leq C}

{\ displaystyle 0 \ leq u_ {i} \ leq C-d_ {i} ~~~~~~ \ forall i \ in V \ barra invertida \ {0 \}}

onde é uma variável contínua adicional que representa a carga deixada no veículo após a visita ao cliente e é a demanda do cliente . Isso impõe os requisitos de conectividade e capacidade. Quando a restrição, então, não é vinculativa 'desde e enquanto eles impõem isso . ${\ displaystyle u_ {i}, ~ i \ in V \ barra invertida \ {0 \}}$ ${\ displaystyle i}$ ${\ displaystyle d_ {i}}$ ${\ displaystyle i}$ ${\ displaystyle x_ {ij} = 0}$ ${\ displaystyle i}$ ${\ displaystyle u_ {i} \ leq C}$ ${\ displaystyle u_ {j} \ geq d_ {j}}$ ${\ displaystyle x_ {ij} = 1}$ ${\ displaystyle u_ {j} \ geq u_ {i} + d_ {j}}$

Estes têm sido usados extensivamente para modelar o VRP básico (CVRP) e o VRPB. No entanto, seu poder é limitado a esses problemas simples. Eles só podem ser usados quando o custo da solução pode ser expresso como a soma dos custos dos custos do arco. Também não podemos saber qual veículo atravessa cada arco. Portanto, não podemos usar isso para modelos mais complexos, onde o custo e / ou a viabilidade dependem da ordem dos clientes ou dos veículos usados.

Roteamento ideal manual versus automático

Existem muitos métodos para resolver problemas de roteamento de veículos manualmente. Por exemplo, o roteamento ideal é um grande problema de eficiência para empilhadeiras em grandes armazéns. Alguns dos métodos manuais para decidir sobre a rota mais eficiente são: Maior gap, formato em S, corredor a corredor, Combinado e Combinado +. Embora o método Combinado + seja o mais complexo e, portanto, o mais difícil de ser usado por operadores de empilhadeiras, é o método de roteamento mais eficiente. Ainda assim, a diferença percentual entre o método de roteamento ótimo manual e a rota ótima real era em média de 13%.

Metaheurística

Devido à dificuldade de resolver para otimalidade em grande escala instâncias de problemas de roteamento de veículos, um esforço significativo de pesquisa tem sido dedicado a metaheurísticas, tais como algoritmos genéticos , pesquisa Tabu , recozimento simulado e pesquisa adaptativa de grande vizinhança (ALNS). Algumas das metaheurísticas mais recentes e eficientes para problemas de roteamento de veículos alcançam soluções dentro de 0,5% ou 1% do ideal para instâncias de problemas que contam com centenas ou milhares de pontos de entrega. Esses métodos também são mais robustos no sentido de que podem ser mais facilmente adaptados para lidar com uma variedade de restrições laterais. Como tal, a aplicação de técnicas metaheurísticas é frequentemente preferida para aplicações em grande escala com restrições complicadas e conjuntos de decisão.

Veja também

Referências

Leitura adicional

Oliveira, HCBde; Vasconcelos, GC (2008). “Um método de busca híbrido para o problema de roteamento de veículos com janelas de tempo”. Annals of Operations Research . 180 : 125–144. doi : 10.1007 / s10479-008-0487-y . S2CID 32406011 .
Frazzoli, E .; Bullo, F. (2004). "Algoritmos descentralizados para o roteamento de veículos em um ambiente estocástico variável no tempo". 2004 43ª Conferência IEEE sobre Decisão e Controle (CDC) . 43ª Conferência IEEE sobre Decisão e Controle, 14-17 de dezembro de 2004, Nassau, Bahamas. Proceedings of the ... IEEE Conference on Decision & Control . 4 . IEEE. doi : 10.1109 / CDC.2004.1429220 . ISBN 0-7803-8682-5. ISSN 0191-2216 .
Psaraftis, HN (1988). "Problemas de roteamento de veículos dinâmicos" (PDF) . Roteamento de Veículos: Métodos e Estudos . 16 : 223–248.
Bertsimas, DJ; Van Ryzin, G. (1991). "Um problema de roteamento de veículos estocástico e dinâmico no plano euclidiano". Pesquisa Operacional . 39 (4): 601–615. doi : 10.1287 / opre.39.4.601 . hdl : 1721,1 / 2353 . JSTOR 171167 .
Vidal T, Crainic TG, Gendreau M, Prins C (2013). "Heurísticas para problemas de roteamento de veículos com vários atributos: um levantamento e uma síntese". European Journal of Operational Research . 231 (1): 1–21. doi : 10.1016 / j.ejor.2013.02.053 .
Hirotaka, Irie; Wongpaisarnsin, Goragot; Terabe, Masayoshi; Miki, Akira; Taguchi, Shinichirou (2019). "Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity". arXiv : 1903,06322 [ quant-ph ].

Languages

In other projects