Método de clusterización para el VRPTW con consideraciones de balanceo de tiempo

Abstract

Al momento de resolver el problema de ruteo de vehículos en ciertos contextos prácticos se vuelve deseable tener cierta noción de zonificación del problema, además existen estrategias que están basadas en realizar una clusterización del problema las cuales pueden ser utilizadas en varios contextos.\\

En esta tesis se aborda el problema de realizar un método de clusterización para el problema del VRPTW donde se tenga en consideraciones de balanceo de tiempo. Se presenta un algoritmo que permite clusterziar teniendo en consideración tanto las restricciones del problema de enrutamiento de vehículos como las de balanceo por tiempo. Lo propuesto consiste en remplazar el costo de una ruta por el costo de un árbol expansor y para incorporar el balanceo se realiza una aproximación del tiempo en ruta, dependiendo del problema utilizando un algoritmo o una regresión lineal de parámetros, y utilizando el rango se estima que tan balanceada es la solución. Realizando búsquedas locales se construyen las clusterizaciones y posterior a rutear cada cluster se vuelve a juntar y se realiza una última búsqueda local sobre la solución del problema de ruteo siguiendo una estructura análoga a la de la clusterización.\\

Además, se estudia como eliminar aristas de un grafo completo de forma tal que se mantenga el árbol generador de peso mínimo. Se estudian resultados en un contexto determinista y probabilista, en este ultimo se logra demostrar que el árbol generador esta contenido en el grafo de los $k$-vecinos asintoticamente en la cantidad de nodos con probabilidad $1$, en este caso $k$ es variable y depende de $n$, la función de distribución de las aristas y un parámetro arbitrario. Esto permite reducir la complejidad del algoritmo, se logra disminuir un termino de la expresión de $n^2$ a $h \sqrt{n^3 \log(n)}$, donde $h$ es un valor que depende de la función inversa de Ackermann.