Problema del viajante con beneficio dependiente del tiempo.

E. Barrena, D. Canca, G. Laporte, L. Coelho

Sobre la base de la definición del problema del viajante selectivo (STSP), definimos y analizamos el problema del viajante selectivo con beneficio dependiente del tiempo (STSP-TDP). Dado un grafo ponderado con ganancias dependientes del tiempo asociadas con los vértices, el STSP-TDP consiste en seleccionar un circuito simple de beneficio total máximo, cuya longitud no exceda un límite predeterminado y cuyo tiempo de inicio y final debe estar dentro de un intervalo predefinido. La longitud del horizonte de planificación es mayor que la longitud del circuito, por lo que los tiempos de inicio y fin del circuito son variables del problema. Este problema surge, por ejemplo, en la planificación de itinerarios turísticos y en la recolección postal. Analizamos variantes del problema dependiendo de la forma de las funciones de beneficio. Proponemos tres formulaciones matemáticas y calculamos soluciones óptimas para algunas instancias de referencia.

Palabras clave: Problema del viajante beneficio dependiente del tiempo optimización

L. Cadarso Morga, A. Serrano Hernandez, J. Faulin Fajardo

D. Canca, A. De Los Santos Pineda, G. Laporte, J. A. Mesa López-Colmenar

A. De Los Santos Pineda, D. Canca, E. Barrena, A. García Hernández- Díaz