Solución a The Team Orienteering Problem mediante algoritmo Backtracking

Inteligencia Artificial
Estado del Arte: Team Orienteering Problem
[Orlando San Martin Carre˜
no]
26 de mayo de 2014

Evaluaci´
on
Resumen (5 %):
Introducci´
on (5 %):
Definici´
on del Problema (10 %):
Estado del Arte (35 %):
Modelo Matem´
atico (20 %):
Conclusiones (20 %):
Bibliograf´ıa (5 %):
Nota Final (100 %):

Resumen
Resumen del informe en no m´
as de 10 l´ıneas.

1.Introducci´
on

Una explicaci´
on breve del contenido del informe. Es decir, detalla: Prop´osito, Estructura del
Documento, Descripci´
on (muy breve) del Problema y Motivaci´on.
Los problemas de ruteo son los m´as estudiados en la optimizaci´on combinatoria, estos problemas consideran una cantidad de entidades que deben visitar lugares exactamente una vez,
bajo este contexto, en elpresente informe se mostrar´a el estado del arte del Team Orienteering
Problem(TOP). Este problema radica en una cantidad determinada de lugares que conllevan
una puntuaci´
on, junto a esto se tiene un team de tama˜
no M para hallar M rutas en estos lugares, con el objetivo de tener las mayores puntuaciones en un tiempo espec´ıfico. El documento
presenta la definici´
on formal del problema,algunas de sus variantes y objetivos, le sigue el estado del arte, n´
ucleo del informe, en el cu´al se ver´a un poco de la historia de TOP, sus inicios,
m´etodos de resoluci´
on, aplicaciones y actualidad. El documento sigue con uno de los modelos
matem´
aticos de Team Orienteering Problem, adem´as se incluir´a el espacio de b´
usqueda de este,
y para finalizar las conclusiones.Motivacion.....

1

2.

Definici´
on del Problema

Explicaci´
on del problema que se va a estudiar, en que consiste, cuales son sus variables,
restricciones y objetivos de manera general. Variantes m´as conocidas que existen.
Team Orienteering Problem trata la problem´atica de una cantidad M de personas, veh´ıculos,
camiones, etc, que conforman un equipo, un team, ´estas deben seguir M caminosdistintos,
estos caminos est´
an basados en N puntos o lugares los cuales cada uno tiene una puntuaci´on Si
asociada, estas puntuaciones pueden ser iguales, la idea es crear estas rutas con el objetivo de
maximizar la puntuaci´
on en un determinado tiempo Tmax , considerando que cada una de estas
rutas tiene el mismo punto de inicio y fin, evidentemente estos puntos no tienen puntuaci´onasociada.
El problema cl´
asico cuenta con las siguientes variables:
M : N´
umero de rutas y entidades del equipo.
N : N´
umero de v´ertices o lugares.
Tmax : Tiempo m´
aximo para cada ruta.
Si : Puntuaci´
on del lugar i.
ti j: Tiempo desde lugar i a lugar j.
Las restricciones [5] son las siguientes:
Cada ruta debe comenzar en el v´ertice 1 y terminar en el v´ertice M .
Un v´ertice puedeser visitado una vez como m´aximo en cada ruta.
Se debe garantizar conectividad en cada ruta.
No debe superarse el tiempo Tmax .
En cuanto a variantes, se tiene al Team Orienteering Problem con ventanas de tiempo, esta
variaci´
on indica que ahora los lugares a los que se visitan conllevan adem´as de una puntuaci´on,
un tiempo de estancia, es decir, se debe mantener un tiempo determinado enel lugar [6]. Adem´as,
es factible agregar preferencias a cada v´ertice, por sobre la puntuaci´on, complejizando a´
un m´as la
resoluci´
on, a esta variante se le llam´
o Multi-agent Orienteering Problem With Time-Dependent
Capacity Constraints [2], que junto a lo anterior considera una constante extra, cantidades de
objetos o personas en cada v´ertice, por lo que si esos l´ımites yafueron superados, no podr´ıa
pasar por este v´ertice.

3.

Estado del Arte

Lo m´
as importante que se ha hecho hasta ahora con relaci´on al problema. Deber´ıa responder
preguntas como las siguientes: ¿cuando surge?, ¿qu´e m´etodos se han usado para resolverlo?,
¿cuales son los mejores algoritmos que se han creado hasta la fecha?, ¿qu´e representaciones han
tenido los mejores resultados?,...