Circuitos de Hamilton y el Método del Vecino más Cercano: Herramienta Matemática para ahorrar combustible y tiempo.

En este artículo queremos seguir ofreciendo ejemplos del uso de la Matemática para alcanzar el éxito personal y laboral. Esta vez explicaremos un método matemático que puede ser empleado para optimizar nuestros recorridos y de este modo ahorrar combustible y tiempo.

En nuestras ciudades abundan las pequeñas empresas que ofrecen servicios a domicilio: plomería, electricidad, aire acondicionado, entregas, entre otras. Muchos de estos pequeños empresarios no van más allá de tener un auto o camioneta donde se transportan, junto a sus herramientas y se mueven a todo el largo y ancho de nuestro condado, e incluso hasta condados aledaños.

Por el tipo de trabajo que realizan (muchas veces reparaciones sencillas o de mediana complejidad, entregas rápidas) pueden visitar a varios clientes, separados por decenas de millas, en una jornada de trabajo. Estas son empresas que no generan grandes ingresos y cualquier pequeño ahorro de dinero y/o tiempo puede representar la diferencia entre el éxito o el fracaso.

La optimización del trayecto puede evitarnos recorrer, innecesariamente, decenas de millas diarias y por ende ahorrarnos cientos de dólares mensuales por concepto de consumo de combustible  y tiempo empleado.

Veamos el siguiente escenario: Usted tiene planificado para mañana cinco limpiezas de aires acondicionados en diferentes puntos de la ciudad, situados en lugares tan variados como: Doral, Miami, Hialeah, Cutler Bay y Kendall. La pregunta en este caso es: ¿en qué orden debo realizar mi recorrido de modo que minimice las millas a recorrer?

Lo primero es colocar las direcciones de cada sitio en una herramienta disponible para todos: Google Map. Hallamos la distancia que separa a cada uno de estos puntos (siempre nos ofrecerá más de una opción, pero vamos a elegir la que menor recorrido implique. Otro factor a considerar al elegir la ruta entre dos puntos será el horario y la densidad del tráfico por esa ruta). Terminado esto vamos a obtener un mapa como el que muestro a continuación (figura 1.1) y a partir de ese mapa vamos a crear un gráfico completo (figura 1.2.).

Un gráfico se considera completo, cuando cada par de vértices están unidos con una línea recta. Los vértices coinciden con los sitios donde realizaremos nuestro trabajo. Las longitudes asignadas a cada eje, es la distancia que separa a cada lugar de uno de los restantes sitios de trabajo.

Llamaremos Circuito de Hamilton a un camino que trazaremos, tal que: salgamos de un punto o vértice, pasemos por todos los vértices una sola vez y regresemos al punto de partida.

El numero de Circuitos de Hamilton que se forman en un grafico completo son (n – 1)!, donde n es el número de vértices. Como tenemos lugares a visitar, vamos tener (5 – 1)! circuitos posibles, esto implica 4! = 4x3x2x1 = 24. Quiere decir, hay 24 diferentes formas para hacer nuestro recorrido. Si incluyéramos solo un sitio más, los recorridos posibles se elevarían a 60. Son demasiadas combinaciones para probar recorrido por recorrido (nos tomaría demasiado tiempo). El método que analiza todos los caminos se llama “Método de la Fuerza Bruta” y es demasiado engorroso incluso para una supercomputadora cuando los vértices llegan a ser de 15, 16 o más. Es el único método realmente exacto, para encontrar el recorrido óptimo.

Ante este inconveniente vamos a explicar un método aproximado: “Método del Vecino más Cercano”. En nuestro caso partiremos del vértice A (Doral). A este vértice “A” confluyen los segmentos AB, AC, AD, AE; el de menor longitud es AB, por lo que nos iremos directo a la dirección en Hialeah (6.3 millas). Parados en “B”, encontramos que confluyen los segmentos BC, BD, BE; el de menor longitud es BD, por lo que nuestra siguiente parada será en la ciudad de Miami (13.0 millas). Ahora sobre “D” encontramos que tenemos dos opciones: DC, DE; la menor distancia es trasladándonos hasta Kendall, en el punto C (17.5 millas). El último sitio a visitar es Cutler Bay (siguiendo la vía CE de longitud 13.4 millas) y regresar al Doral (punto A) a través del segmento EA (21.4 millas). Nuestro circuito queda entonces como A, B, D, C, E, A (mostrado en la figura 2) y el total de millas a recorrer será de 6.3 + 13.0 + 17.5 + 13.4 + 21.4 = 71.6 millas.

¿Qué sucede si elegimos al azar cualquier otro circuito? Veamos:

A, B, C, D, E, A = 82.2 millas (10.6 millas más a recorrer).

A, C, B, D, E, A = 80.0 millas (8.4 millas más a recorrer).

A, D, E, C, B, A = 73.3 millas (1.7 millas más a recorrer).

Sin embargo, el inconveniente de este método es que aunque te va a ofrecer un trayecto más corto que la mayoría de los posibles trayectos, no necesariamente este va a ser el óptimo. En este caso un trayecto mejor es ir a través de:

A, C, E, D, B, A = 64 millas (7.6 millas menos a recorrer, que en el camino ofrecido por el método del Vecino más Cercano). En este caso fue sencillo definir este trayecto de menor recorrido, por la poca cantidad de sitios a visitar.

Podemos considerar que vale la pena emplear este método a pesar de sus limitaciones pues: es muy fácil de implementar (basta tener acceso a Internet y un mínimo de habilidades con Google Maps), nos va a dar una trayectoria mejor que la mayor parte de las trayectorias posibles y en la medida que aumente el número de sitios a visitar (vértices de nuestro gráfico), va a ser más difícil encontrar, tanteando, el camino óptimo.  

Para preguntas, comentarios o sugerencia de temas a tratar, pueden escribir a: felixrm1971@gmail.com