Vendedor ambulante Representación de restricción de problemas

Question

Leí un par de artículos y un código de muestra sobre cómo resolver TSP con algoritmos genéticos y Ant Colony Optimization, etc. Pero todo lo que encontré no incluía restricciones de tiempo (ventana), por ejemplo. "Tengo que estar en el cliente x antes de las 12 a.m.)" y asumí la simetría.

¿Puede alguien dirigirme hacia algún código de muestra o artículos que expliquen cómo puedo agregar restricciones al TSP y cómo puedo representarlos en el código?

Gracias!

Answer 1

El Profesor Reinelt de la Universidad de Heidelburg en Alemania es uno de los principales expertos del TSP. Él tiene una colección de documentos sobre las diversas variantes del TSP.

ver http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

Creo que su variante se llama de rutas para vehículos Problema con ventanas de tiempo. (http://en.wikipedia.org/wiki/Vehicle_routing_problem)

Answer 2

Usted debe echar un vistazo a lo que el estado de la técnica en el dominio Diseño independiente puede hacer por usted: http://ipc.informatik.uni-freiburg.de/