Problema de la ruta más corta

PROBLEMA DE RUTA MAS CORTA

En el problema de la ruta más corta se determina ésta, entre una fuente y un destino, en una red de transporte. Hay otras soluciones que se pueden representar con el mismo modelo.

Ejemplo:

RentCard está desarrollando un plan de reposición de su flotilla de automóviles para un horizonte de planeación de 4 años, que comienza el primero de enero del 2001 y termina el 31 de diciembre del 2004. Al iniciar cada año se debe de tomar la decisión de si un auto se debe mantener en operación o se debe sustituir. Un automóvil debe de estar en servicio 1 año como mínimo, y 3 años como máximo. La tabla siguiente muestra el costo de reposición en función del año de adquisición del vehículo y los años que tiene en funcionamiento.  

Tabla 1. Costo de Reposición en función del año de adquisición.

 

Figura 6. El problema de reemplazo de equipo como problema de Ruta más corta.

El problema se puede formular como una red, en los que los nodos 1 a 5 representan los inicios de los años del 2001 al 2005. Los arcos del nodo 1 (año 2001)  solo pueden alcanzar los nodos 2, 3 y 4 porque un vehículo debe de estar en funcionamiento de 1 a 3 años. Los arcos desde los otros nodos pueden interpretarse en forma  parecida. La longitud de cada arco es igual al costo de reposición. La solución del problema equivale a determinar la ruta más corta entre los nodos 1 y 5.

En la figura 5 se ve la red que resulta. Si se usa TORA, la ruta más corta que se indica con la ruta gruesa, es  1   ->   3   ->   5. Eso quiere decir que un automóvil adquirido al iniciar el 2001 (nodo 1) se debe reemplazar pasados 2 años, al iniciar el 2003 (nodo 3). El auto de reposición debe estar en servicio hasta el final del 2004. El costo total de esta política de reposición es $12,500 = ($5400 + 7100).

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: