En la situación inicial el algoritmo de C-W calcula la distancia total recorrida desde el CD hasta una tienda, regresar al CD e ir hasta la otra tienda y regresar. La distancia total queda expresada en la siguiente expresión: Luego, el algoritmo de C-W considera el ahorro que podría significar unir dos puntos, es decir, ir desde el CD hasta una de las tiendas, luego a la segunda y finalmente regresar al CD. Esta ruta ahorra el viaje de regreso de la tienda 1 al CD, así como el viaje desde el CD hasta la tienda 2. La nueva distancia recorrida es la siguiente: El ahorro neto A12, ganado por unir las dos tiendas dentro de la misma ruta, resulta de restar la distancia total (1) – distancia total (2): Este sencillo ejemplo nos sirve muy bien para ilustrar el concepto del ahorro del algoritmo. En la práctica los problemas son mucho más complejos, la cantidad de puntos es considerablemente mayor y el manejo de las restricciones más problemático. Fitzsimmons y Fitzsimmons (1998, pp. 95-99) nos explican la utilización del algoritmo a través de cinco pasos sencillos descritos en el siguiente ejemplo. Un almacén central abastece a cuatro franquicias de comidas rápidas en Lima, las cuales están ubicadas según el siguiente gráfico: Figura 7.27: Distancias en kilómetros entre el almacén central y las franquicias El diseño de la ruta de reparto, utilizando el método del algoritmo C-W, es el siguiente: Paso 1. Se construye una matriz de distancias mínimas entre cada par de puntos. Para el problema propuesto, dicha matriz es la siguiente: 1 2 3 4 446
RkJQdWJsaXNoZXIy MjgwMjMx