Almundo Challenge
Esta semana, Melanie y yo participamos del Almundo Challenge organizado por almundo.com.ar. Por suerte pudimos ganar después de un final que nos dejó temblando (ranking), y como varios nos preguntaron qué algoritmo usamos escribimos un resumen. ¡Acá va!
Autores: Melanie Sclar y Gabriel Poesia
Este post es sobre el problema descripto aquí.
Nuestra solución se basó en utilizar programación dinámica para asignar agencias sobre un camino TSP dado por la heurística de Lin-Kernighan (LKH) y luego hacer modificaciones locales en el camino de forma tal de mejorar la solución final, aunque posiblemente empeorando la longitud del camino original. Esto fue realizado con varios caminos que LKH nos fue proveyendo y nos quedamos con el que mejor respondía a nuestras modificaciones. El approach fue elegido teniendo en cuenta que el tiempo de cómputo era limitado ya que la competencia duraba una semana. La implementación de LKH que usamos fue la de K. Helsgaun. Llegamos a probar otras implementaciones y heurísticas, pero esta fue la que nos dió los mejores resultados. Notamos que lo más importante para llegar al rango de las mejores soluciones de la competencia (con costo menor que $68000$) era tener un buen camino base para el TSP. Sin embargo, no siempre un camino menor para el TSP nos daba una solución mejor para el problema del desafío al combinar el camino con las técnicas que describimos a continuación.
Primero que nada es importante notar que fijado un camino, la asignación de agencias se podría realizar de manera óptima con programación dinámica si no existiera la agencia D. La función recursiva que deberíamos utilizar es la siguiente:
$dp(i,j,k) =$ solución de menor costo utilizando hasta la $i$-ésima ciudad del camino dado que en este paso utilicé la agencia $j \in \{A, B, C\}$ y que llevo $k \in \{0, 1, 2\}$ agencias $A$ consecutivas como últimas agencias usadas (incluyendo esta). Notar que en realidad $k$ es el resto en la división por 3 de la cantidad de agencias $A$ consecutivas.
Escribiremos la función recursiva pensando cuáles son los posibles estados inmediatamente anteriores al estado $(i,j,k)$ para todos los posibles estados. Los estados imposibles se inicializan en infinito para que esa rama nunca sea tomada en cuenta.
$dp(i,A,0) = dp(i-1, A, 2) + dist(i-1,i) \cdot 0.65$
$dp(i,A,1) = \min\limits_{j \in \{A, B, C\}}dp(i-1, j, 0) + dist(i-1,i)$
$dp(i,A,2) = dp(i-1, A, 1) + dist(i-1,i)$
$dp(i,B,0) = \left\{ \begin{array}{lr}
\min\limits_{\substack{j \in \{A, B, C\} \\ k \in \{0, 1, 2\}}} dp(i-1,j,k) + dist(i-1,i) \cdot 0.85 & si \ dist(i-1,i) > 200 \\
\min\limits_{\substack{j \in \{A, B, C\} \\ k \in \{0, 1, 2\}}} dp(i-1,j,k) + dist(i-1,i) & si \ no
\end{array}
\right. $
$dp(i,C,0) = dp(i-1,B,0) + dist(i-1,i) \cdot 0.8$
Sin embargo está faltando considerar la existencia de la agencia D, que da $15 de descuento cada $10000km$ viajados. A un costo de $0.01/km, da un descuento de $15, por cada $10000km \cdot \$0.01/km = \$100$ viajados. O sea, un descuento del 15%. Claro que no siempre se puede obtener un descuento del 15% en todos los viajes, porque solo nos devuelven dinero cuando la cantidad de kilómetros pasa un múltiplo de $10000$. Por un momento, pensemos que la agencia D da $d\%$ de descuento en todos sus viajes, entonces la programación dinámica se reescribiría como:
$dp(i,A,0) = dp(i-1, A, 2) + dist(i-1,i) \cdot 0.65$
$dp(i,A,1) = \min\limits_{j \in \{A, B, C, \mathbin{\color{red}D}\}}dp(i-1, j, 0) + dist(i-1,i)$
$dp(i,A,2) = dp(i-1, A, 1) + dist(i-1,i)$
$$dp(i,B,0) = \left\{ \begin{array}{lr}
\min\limits_{\substack{j \in \{A, B, C, \mathbin{\color{red}D}\} \\ k \in \{0, 1, 2\}}} dp(i-1,j,k) + dist(i-1,i) \cdot 0.85 & si \ dist(i-1,i) > 200 \\
\min\limits_{\substack{j \in \{A, B, C, \mathbin{\color{red}D}\} \\ k \in \{0, 1, 2\}}} dp(i-1,j,k) + dist(i-1,i) & si \ no
\end{array}
\right. $$
$dp(i,C,0) = dp(i-1,B,0) + dist(i-1,i) \cdot 0.8$
$\mathbin{\color{red}{dp(i,D,0) = \min\limits_{\substack{j \in \{A, B, C, D\} \\ k \in \{0, 1, 2\}}} dp(i-1,j,k) + dist(i-1,i) \cdot \big(1-\frac{d}{100}\big)}}$
Ahora lo que hacemos es dado un camino, buscar el $d$ que mejor ajuste a los datos haciendo búsqueda lineal en el intervalo $[0.145, 0.155]$. De esta forma nos aseguramos de que no sobren kilómetros recorridos con la agencia $D$ por los que no ganaremos descuento. Es importante notar que ahora nuestro algoritmo ya no es exacto sino una heurística.
Hecha la dinámica, lo que restó fue hacer modificaciones al camino de forma tal de aprovechar las características de los descuentos. Listamos las modificaciones que más nos ayudaron. Hicimos hill climbing hasta encontrar el mejor mínimo local.
- 2-opt: intuitivamente puede ser útil empeorar la longitud del camino total si haciéndolo hacemos que un viaje de $190km$ pase a ser de más de $200km$, porque ahí podremos utilizar la agencia $B$ y obtener descuento del $15\%$.
- Shuffles de secuencias de $k$ ciudades consecutivas: esto engloba muchos intentos de mejoras locales como invertir la dirección en que es recorrido un subcamino, invertir dos ciudades, etcétera. Hacia el final de la competencia decidimos probar todas las permutaciones de subcaminos de hasta 5 ciudades.
- Simulated Annealing: El SA es una metaheurística simple que busca soluciones mejores haciendo cambios en la solución actual, pero a veces acepta una solución peor probabilisticamente con el objetivo de salir de un mínimo local. Nos fue muy útil para mejorar muchas de las soluciones que tuvimos en el medio del desafío. Inicialmente, nuestros cambios en la solución inicial eran simplemente cambiar la posición de dos ciudades consecutivas en el camino. Después, empezamos a hacer shuffles de intervalos más largos. En el último día de la competencia, el SA nos bajó 50 centavos de una solución intermedia que teníamos. Como ganamos por menos que eso, ¡se ve que cada una de las técnicas que usamos terminó siendo importante!
- Cambio de la ciudad inicial: si bien a simple vista puede parecer que no importa la ciudad donde se comienza, podemos ver que es desventajoso comenzar con un viaje muy largo - no podríamos aprovechar los descuentos de la agencia $A$ ni de la $C$. Así, probamos diferentes ciudades iniciales.
- Programación Genética: Otra metaheurística ampliamente aplicable, especialmente cuando uno no tiene más ideas (lo que nos pasó después de probar todo el resto). La principal dificultad de aplicar GP fue definir un crossover que fuera útil. En nuestro caso, definimos una función probabilística que empezaba siguiendo uno de los dos caminos siendo combinados, y con una cierta probabilidad cambiaba de camino (ignorando los nodos ya visitados, claro). Como en el final los caminos que estábamos usando eran todos muy parecidos, esa función llegó a resultar en combinaciones que las otras técnicas no consideraron, algunas siendo mejores (siempre por menos de un peso). Sin embargo, la secuencia de pasos que nos llevó a la última solución que tuvimos no pasó por este algoritmo.
Además, sobre esto corrimos otra programación dinámica (cortesía de Sebastián Prillo!) que se focaliza en mejorar el camino en sí y no en mirar las agencias. Esto fue efectivo para poder sacarnos del mínimo local donde estábamos atascados ($63794.05$) y llevarnos a la solución que enviamos de $63790.55$. ¡Todo esto en la última media hora de competencia! Por suerte nuestros competidores mandaron soluciones marginalmente mejores que la nuestra faltando poco tiempo para el cierre de la competencia. De no haber ocurrido seguramente no habríamos ganado, porque estábamos por irnos de casa cuando vimos una solución 5 centavos mejor que la nuestra.
Finalmente, dejamos un link a la mejor solución que obtuvimos, que es de $63790.26$. Están invitados a mejorarla y enviarnos mejores soluciones, las vamos a ir agregando acá abajo.
PD: Germán Guzelj, de Almundo, nos envió una linda imágen que hizo con nuestra mejor solución para visualizar qué agencias fueran usadas en el camino. ¡Gracias, Germán!
