Combinando abordagens quânticas e clássicas pra roteamento de entregas

Nos últimos anos, pesquisadores têm analisado como a computação quântica pode ajudar a resolver problemas de roteamento de entregas. Esses problemas envolvem descobrir a melhor forma dos caminhões de entrega traçarem suas rotas. Exemplos comuns que ouvimos falar incluem o Problema do Caixeiro Viajante e o Problema de Roteamento de Veículos. Embora estudar esses problemas seja importante, muitas vezes eles não refletem as complexidades do mundo real. Esta pesquisa adota uma nova abordagem, aiming para enfrentar essas situações reais diretamente, sem simplificar o problema demais.

O foco deste trabalho é um método chamado Q4RPD. Ele usa uma mistura de computação quântica e clássica para resolver problemas de entrega de pacotes. Alguns desafios considerados incluem ter diferentes tipos de veículos, entregas urgentes e tamanhos de pacotes.Para mostrar como o Q4RPD funciona, foram criados exemplos diferentes envolvendo situações reais de entrega.

#A Importância dos Problemas de Roteamento

Problemas de roteamento são um assunto grande em transporte e logística. O interesse nessas questões vem da sua complexidade e do quão úteis elas são na vida real. Com algoritmos de roteamento melhores, podemos melhorar muitos aspectos da sociedade, desde economizar tempo até reduzir custos no transporte.

A maioria dos métodos para resolver esses problemas precisa de muito poder computacional. Isso significa que computadores tradicionais nem sempre conseguem resolver até mesmo casos menores. Ao longo dos anos, muitas soluções mais rápidas foram desenvolvidas, sendo os métodos heurísticos alguns dos mais comuns. Até agora, a maioria dos algoritmos foi construída para rodar em computadores padrão. No entanto, a computação quântica se tornou uma alternativa promissora, especialmente para tarefas de otimização e roteamento.

Embora ainda esteja em desenvolvimento, a computação quântica tem chamado a atenção pelo seu potencial para enfrentar problemas difíceis em áreas como saúde, negócios e logística. Recentemente, muitos estudos se concentraram em aplicar métodos quânticos a problemas de roteamento, como o Problema do Caixeiro Viajante e o Problema de Roteamento de Veículos.

#Tendências de Pesquisa Atual

Pesquisas recentes mostram que muitos estudos se concentram em entender tecnologias quânticas ou a eficiência de métodos específicos. Esses estudos geralmente comparam problemas tradicionais como o Problema do Caixeiro Viajante. Enquanto isso, outras pesquisas avançaram na aplicação de métodos quânticos a questões práticas de roteamento, abordando coisas como engarrafamentos.

Um estudo notável de 2023 é relevante aqui. Ele discute o roteamento de múltiplos caminhões para cadeias de suprimento. Os autores criam um algoritmo que atribui rotas aos caminhões passo a passo, considerando várias necessidades. Esse método se alinha ao que é feito no projeto Q4RPD, garantindo que todas as limitações atuais sejam respeitadas.

O objetivo deste trabalho é desenvolver um método que possa fornecer boas soluções para problemas reais de entrega usando dispositivos quânticos de forma inteligente. Como muitos desses problemas são complexos demais para o hardware quântico atual lidar tudo de uma vez, uma mistura de processamento quântico e clássico é usada. O Q4RPD atribui rotas aos caminhões enquanto garante a adesão a todas as restrições necessárias.

#Definição do Problema

O problema está fundamentado em necessidades reais identificadas por uma empresa de transporte chamada Ertransit. Através de discussões com a equipe de pesquisa, requisitos essenciais foram estabelecidos para moldar o trabalho detalhado neste artigo.

O principal problema é sobre planejar as melhores rotas para Entregas de última milha que podem ser concluídas em um dia. Isso envolve começar de um local (depósito) e poder usar uma variedade de caminhões. O objetivo é criar rotas que atendam a todas as demandas enquanto mantêm os custos baixos. Às vezes, os clientes podem ter vários pedidos.

Uma rota é definida como o caminho percorrido por um único caminhão que começa e termina no depósito. O custo total inclui tanto a distância percorrida quanto quaisquer taxas de uso dos caminhões. Se o caminhão pertence à Ertransit, o custo é zero; se for alugado, há custos adicionais.

#Restrições

O problema tem restrições específicas a considerar:

1. Capacidade: Cada caminhão pode carregar uma quantidade limitada de peso e volume com base em suas especificações. As entregas também devem se adequar a esses limites.
2. Prioridade: Alguns pacotes devem ser entregues dentro de um prazo específico. Estes são marcados como prioridade máxima.
3. Tempo de Trabalho: A duração total de cada rota não deve exceder as horas de trabalho do motorista.

Além disso, há preferências que orientam o processo de resolução do problema, que incluem:

• Cada caminhão pode lidar com apenas uma rota por dia.
• Caminhões próprios devem ser usados quando disponíveis, mesmo que alugar possa ser mais barato.
• Quanto menos veículos usados no total, melhor.

O problema definido é referido como Entrega de Pacotes 2-Dimensional e Heterogênea com Prioridades (2DH-PDP).

#Esquema de Solução Q4RPD

O processo Q4RPD é iterativo e envolve selecionar um caminhão e calcular uma rota a cada vez. Antes de começar esse processo, o Q4RPD implementa duas heurísticas de ordenação:

1. Ordenação de Veículos: Caminhões são priorizados, com veículos próprios sendo classificados pela capacidade primeiro e depois os veículos alugados.
2. Ordenação de Entregas: Entregas prioritárias são ordenadas para garantir que sejam tratadas primeiro.

Uma vez que essa configuração está completa, o processo segue estas etapas:

#Etapa 1: Configuração do Roteamento

A computação clássica prepara a instância do problema para o dispositivo quântico. Isso inclui selecionar um caminhão e determinar quais rotas calcular. O método envolve:

• Seleção do Caminhão: Priorizar caminhões que já tenham tido uma rota anterior.
• Seleção da Rota: Dependendo das circunstâncias, diferentes tipos de rotas serão calculadas, como Depósito-TP ou rotas regulares.

#Etapa 2: Atualização de Parâmetros

À medida que as sub-rotas são criadas, é necessário ajustar parâmetros de limite superior, como capacidade do caminhão e duração da rota. Isso garante que os cálculos subsequentes estejam alinhados com o status atual do caminhão e das rotas.

#Etapa 3: Formulação do Problema CQM

Uma vez que todos os parâmetros estão prontos, o próximo passo é formular o problema como um Modelo Quadrático com Restrições (CQM) que o dispositivo quântico pode processar.

#Etapa 4: Resolução CQM

Neste estágio, o dispositivo quântico calcula a melhor rota possível com base na configuração do CQM. A saída será a sub-rota ótima, que será armazenada para as próximas etapas.

#Etapa 5: Atualização de Soluções

Usando computação clássica, o Q4RPD atualiza o estado geral do problema com base na sub-rota obtida e elimina as entregas concluídas da lista.

#Formulação do Problema

Esta seção descreve como o problema é estruturado para processamento pelo dispositivo quântico. O foco está em sub-problemas específicos, em vez de toda a entrega de pacotes de uma só vez.

#Variáveis e Parâmetros

As variáveis representam os pontos de entrega e sua ordem na rota. O objetivo é encontrar valores adequados que criem uma rota ótima enquanto minimizam a distância de viagem.

#Função Objetivo

O propósito é minimizar a distância total percorrida e maximizar o número de entregas feitas antes de chegar à última parada.

#Restrições

Os objetivos estabelecidos estão sujeitos a várias restrições fundamentais:

1. Consistência de Entrega: Cada entrega pode aparecer apenas uma vez na rota.
2. Consistência de Localização: Cada horário da programação do caminhão deve ser atribuído a no máximo um pedido.
3. Consecutividade de Entregas: As entregas devem ser consecutivas.
4. Inclusão de Destino: O ponto final deve ser incluído na rota.
5. Restrição de Tempo: A rota não pode exceder a duração máxima permitida.
6. Restrição de Peso: O peso máximo do caminhão não deve ser excedido.
7. Restrição de Dimensão: A rota não deve ultrapassar o tamanho máximo permitido para veículos.

#Resultados Experimentais

Agora que o problema e os métodos foram delineados, é essencial ver como o Q4RPD se sai na prática.

#Detalhes do Solver

O solver quântico usado nos testes é um modelo de software projetado para lidar com tipos específicos de problemas de forma eficaz. Os módulos trabalham juntos para encontrar as soluções mais adequadas rapidamente.

#Descrição do Benchmark

A pesquisa envolveu seis instâncias diferentes para avaliar o quão bem o Q4RPD funcionou. Cada cenário foi rotulado para indicar suas especificidades, como o número de entregas e atribuições de prioridade.

As instâncias variaram em complexidade:

• Casos menores tinham menos entregas, mas ainda incluíam necessidades prioritárias.
• Casos maiores pressionaram o Q4RPD a lidar com roteamentos mais complicados.

#Análise de Desempenho

Os resultados indicam que o Q4RPD conseguiu atender aos objetivos respeitando todas as restrições. Mostrou-se promissor em alcançar soluções que são eficientes e eficazes para desafios logísticos do mundo real.

De modo geral, o desempenho do solver foi satisfatório, atendendo consistentemente às restrições delineadas e demonstrando minimização competitiva de distância em comparação com métodos tradicionais. Conseguiu lidar com instâncias maiores do que o que geralmente é visto na literatura atual, mostrando seu potencial para aplicação prática.

#Conclusões e Trabalho Futuro

Em resumo, o Q4RPD demonstra uma abordagem viável para enfrentar problemas complexos de roteamento de entregas, levando em conta várias restrições do mundo real. A pesquisa destaca a capacidade deste sistema quântico-clássico de melhorar como a logística opera.

Olhando para o futuro, há várias avenidas para trabalhos futuros. Isso pode envolver o refinamento do modelo matemático para cobrir mais cenários de entrega ou integrar outras formas de transporte. O desenvolvimento futuro também pode incluir tornar o solver adaptável às diferentes necessidades e preferências das empresas.

Com um foco crescente em aplicações práticas da computação quântica, esta pesquisa serve como um passo em direção a soluções logísticas mais eficientes no futuro.