Gostaria de saber se existem abordagens que formulam um problema de roteamento de veículo com Windows de tempo ( VRPTW ) (como um problema de decisão) como uma instância de SAT / SMT? (alternativa: TSP)
Por exemplo:
"Existe uma solução válida para visitar todos os clientes dentro de suas janelas de tempo com n = 10 veículos?"
Esse problema de decisão pode ser útil para uma primeira etapa, minimizando o número de veículos usados.
Eu não tenho nenhuma experiência com SMT, mas espero que seja necessário se quisermos lidar com coordenadas / horas como números reais.
Normalmente, todas as formulações de TSP / VRP são feitas no domínio de programação de número misto, mas eu me pergunto se uma formulação sat / smt poderia ser competitiva (em termos de resolução de tempo na prática) para o problema de decisão acima.
Então, o que você acha:
- você conhece alguma referência?
- você acha que uma abordagem sat / smt poderia ser competitiva?
- mais alguma coisa que você queira mencionar?
Obrigado por toda a sua contribuição.
Sascha
Edit : Como eu mencionei o TSP como um problema mais comum no TCS relacionado ao VRPTW, também devo mencionar o problema de Job Shop Scheduling , que é o outro "problema parcial" no VRPTW. Talvez os pesquisadores desse campo tenham tentado algo com o SAT / SMT.