Me pregunto si hay algún enfoque que formule un problema de enrutamiento de vehículos con ventanas de tiempo ( VRPTW ) (como un problema de decisión) como una instancia SAT / SMT. (alternativa: TSP)
Por ejemplo:
"¿Existe una solución válida para visitar a todos los clientes dentro de sus ventanas de tiempo con n = 10 vehículos?"
Este problema de decisión podría ser útil para un primer paso, minimizando el número de vehículos utilizados.
No tengo ninguna experiencia con SMT, pero espero que sea necesario si queremos manejar las coordenadas / tiempos como números reales.
Por lo general, todas las formulaciones de TSP / VRP se realizan en el dominio de programación de enteros mixtos, pero me pregunto si una formulación sat / smt podría ser competitiva (en términos de tiempo de resolución en la práctica) para el problema de decisión anterior.
Entonces, qué piensas:
- ¿Conoces alguna referencia?
- ¿Crees que un enfoque sat / smt podría ser competitivo?
- ¿Algo más que quieras mencionar?
Gracias por todas sus aportaciones.
Sascha
Editar : Como mencioné el TSP como un problema más común en TCS que está relacionado con el VRPTW, también debería mencionar el problema de Programación de Job Shop , que es el otro "problema parcial" en el VRPTW. Tal vez los investigadores en este campo intentaron algo con SAT / SMT.