Esperando a entrega de um pacote de férias? Há um problema matemático complicado que precisa ser resolvido antes que o caminhão de entrega pare na sua porta, e os pesquisadores do MIT têm uma estratégia que pode acelerar a solução.
A abordagem se aplica a problemas de roteamento de veículos, como entrega na última milha, em que o objetivo é entregar mercadorias de um depósito central para várias cidades, mantendo os custos de viagem baixos. Embora existam algoritmos projetados para resolver esse problema para algumas centenas de cidades, essas soluções tornam-se muito lentas quando aplicadas a um conjunto maior de cidades.
Para remediar isso, Cathy Wu, a professora assistente de desenvolvimento de carreira Gilbert W. Winslow em Engenharia Civil e Ambiental e o Instituto de Dados, Sistemas e Sociedade, e seus alunos criaram uma estratégia de Machine learning que acelera alguns dos mais fortes solucionadores algorítmicos de 10 a 100 vezes.
Os algoritmos do solucionador dividem o problema de entrega em subproblemas menores a serem resolvidos – digamos, 200 subproblemas para o roteamento de veículos entre 2.000 cidades. Wu e seus colegas aumentam esse processo com um novo algoritmo de Machine learning que identifica os subproblemas mais úteis para resolver, em vez de resolver todos os subproblemas, para aumentar a qualidade da solução usando ordens de magnitude menos computação.
Sua abordagem, que eles chamam de “aprender a delegar”, pode ser usada em uma variedade de solucionadores e uma variedade de problemas semelhantes, incluindo programação e localização de robôs de warehouse, dizem os pesquisadores.
O trabalho ultrapassa os limites da solução rápida de problemas de roteamento de veículos em grande escala, diz Marc Kuo, fundador e CEO da Routific, uma plataforma de logística inteligente para otimizar rotas de entrega. Alguns dos avanços algorítmicos recentes da Routific foram inspirados no trabalho de Wu, observa ele.
“A maior parte do corpo acadêmico de pesquisa tende a se concentrar em algoritmos especializados para pequenos problemas, tentando encontrar melhores soluções ao custo de tempos de processamento. Mas no mundo real, as empresas não se preocupam em encontrar as melhores soluções, especialmente se elas demoram muito para calcular “, explica Kuo. “No mundo da logística de última milha, tempo é dinheiro, e você não pode fazer com que todas as operações do armazém esperem que um algoritmo lento retorne as rotas. Um algoritmo precisa ser hiper-rápido para ser prático.”
Wu, o aluno de doutorado em sistemas sociais e de engenharia Sirui Li, e o aluno de doutorado em engenharia elétrica e ciência da computação Zhongxia Yan apresentaram suas pesquisas nesta semana na conferência NeurIPS de 2021.
Selecionando bons problemas
Problemas de roteamento de veículos são uma classe de problemas combinatórios, que envolvem o uso de algoritmos heurísticos para encontrar “soluções boas o suficiente” para o problema. Normalmente não é possível encontrar a “melhor” resposta para esses problemas, porque o número de soluções possíveis é muito grande.
“O nome do jogo para esses tipos de problemas é projetar algoritmos eficientes … que sejam ótimos dentro de algum fator”, explica Wu. “Mas o objetivo não é encontrar soluções ideais. Isso é muito difícil. Em vez disso, queremos encontrar as melhores soluções possíveis. Mesmo uma melhoria de 0,5% nas soluções pode se traduzir em um grande aumento de receita para uma empresa.”
Nas últimas décadas, os pesquisadores desenvolveram uma variedade de heurísticas para produzir soluções rápidas para problemas combinatórios. Eles geralmente fazem isso começando com uma solução inicial ruim, mas válida, e então melhorando gradualmente a solução – tentando pequenos ajustes para melhorar o roteamento entre cidades próximas, por exemplo. Para um grande problema como um desafio de roteamento de mais de 2.000 cidades, no entanto, essa abordagem leva muito tempo.
Mais recentemente, métodos de Machine learning foram desenvolvidos para resolver o problema, mas embora sejam mais rápidos, eles tendem a ser mais imprecisos, mesmo na escala de algumas dezenas de cidades. Wu e seus colegas decidiram ver se havia uma maneira benéfica de combinar os dois métodos para encontrar soluções rápidas, mas de alta qualidade.
“Para nós, é aqui que entra o Machine learning”, diz Wu. “Podemos prever quais desses subproblemas, se os resolvêssemos, levariam a mais melhorias na solução, economizando tempo de computação e despesas?”
Tradicionalmente, uma heurística de problema de roteamento de veículos em grande escala pode escolher os subproblemas a serem resolvidos em que ordem aleatoriamente ou aplicando outra heurística cuidadosamente planejada. Nesse caso, os pesquisadores do MIT rodaram conjuntos de subproblemas por meio de uma rede neural que criaram para encontrar automaticamente os subproblemas que, ao serem resolvidos, levariam ao maior ganho de qualidade das soluções. Esse processo acelerou o processo de seleção de subproblemas em 1,5 a 2 vezes, descobriram Wu e seus colegas.
“Não sabemos por que esses subproblemas são melhores do que outros subproblemas”, observa Wu. “Na verdade, é uma linha interessante de trabalho futuro. Se tivéssemos alguns insights aqui, eles poderiam nos levar a projetar algoritmos ainda melhores.”
Velocidade surpreendente
Wu e seus colegas ficaram surpresos com a eficiência da abordagem. No Machine learning, a ideia de garbage-in, garbage-out se aplica – ou seja, a qualidade de uma abordagem de Machine learning depende muito da qualidade dos dados. Um problema combinatório é tão difícil que mesmo seus subproblemas não podem ser resolvidos de forma otimizada. Uma rede neural treinada nas soluções de subproblemas de “qualidade média” disponíveis como dados de entrada “normalmente daria resultados de qualidade média”, diz Wu. Nesse caso, no entanto, os pesquisadores foram capazes de alavancar as soluções de qualidade média para obter resultados de alta qualidade, significativamente mais rápido do que os métodos de última geração.
Para roteamento de veículos e problemas semelhantes, os usuários geralmente devem projetar algoritmos muito especializados para resolver seus problemas específicos. Algumas dessas heurísticas estão em desenvolvimento há décadas.
O método de aprender a delegar oferece uma maneira automática de acelerar essas heurísticas para grandes problemas, não importa qual seja a heurística ou, potencialmente, qual seja o problema.
Uma vez que o método pode funcionar com uma variedade de solucionadores, pode ser útil para uma variedade de problemas de alocação de recursos, diz Wu. “Podemos desbloquear novos aplicativos que agora serão possíveis porque o custo para resolver o problema é de 10 a 100 vezes menor.”
Publicado em 13/12/2021 08h56
Artigo original:
Estudo original:
Artigo relacionado: