Actividad de Ruteo

Universidad Andrés Bello

Facultad de Ingeniería

Actividad Gestión Logística 2016: Ruteo Vehicular - Heurísticas

1.- Una empresa fabricante de sillones suministra sus productos por las ciudades de Viña del Mar y Valparaíso. Para el próximo miércoles, necesita hacer la distribución de 8 sillones a 8 clientes. Es decir, cada cliente demanda 1 sillón. Para ello, dispone de una flota de 8 camiones para llevar, como máximo, 3 sillones cada uno. La empresa desea minimizar las distancias recorridas por sus vehículos y el número de vehículos utilizados.

Previamente, dado que el programador de rutas, tiene algún conocimiento de ruteo vehicular, ha calculado las distancias entre nodos y los ahorros, pero no sabe cómo utilizarlos para construir rutas:

[pic 1]      [pic 2]

1. Utilizando la heurística de ahorros (Clarke & Wright), determine rutas eficientes de despacho y calcule la distancia total recorrida por los vehículos.

1. El programador se entera que existe otra heurística llamada Procedimiento del Vecino más cercano (Nearest Neighbor Procedure, NNP). Esta heurística voraz (golosa) El NNP construye un tour basado en el costo o distancia de viajar desde el último nodo visitado hacia el nodo más cercano no visitado. El procedimiento es el siguiente:

1. Comenzar con el nodo inicial en el tour (depósito).
2. Encontrar el nodo más cercano al último nodo agregado en el tour y agregar (respetando capacidad).
3. Volver al paso 2 hasta que no hayan más nodos por agregar.
4. Conectar los nodos para formar uno o más tours.

[pic 3]

1. Suponga que ahora desea considerar ventanas de tiempo para la distribución. Cada cliente sugiere (y paga) por tener los productos dentro de la ventana de tiempo señalada.

Si no es posible cumplir con el límite horario, la empresa es penalizada con $1000 por minuto de retraso. Cada minuto recorrido se estima en $50. Con una velocidad promedio de 30km/h, los tiempos de traslado (y ahorros) son los siguientes:

[pic 4] [pic 5]

Además, existe un tiempo de carga de 10 minutos y un tiempo de descarga de 15 minutos (en promedio). Utilizando la heurística de C&W, determine la estrategia de distribución considerando estas ventanas de tiempo, de modo de minimizar los costos totales.

Pauta I

Parte a)

[pic 6]

Parte b)

[pic 7]

Parte c)

[pic 8]

[pic 9]

Notar que si se elige la ruta D-7-6-5-D, que en tiempo es equivalente a D-5-6-7-D, los tiempos son distintos.

2 (Tarea).- Una empresa distribuidora de medicamentos a hogares de ancianos y centros de rehabilitación. Parte de este servicio es entregar cada pedido en el lugar donde se encuentran los clientes. Para el reparto, se usan camionetas que tienen una capacidad máxima de 63 cajas. Las ubicaciones de los clientes se codificaron mediante una cuadrícula lineal con un factor de graduación de mapas de 4.6 por unidad de coordenada. Los datos de los clientes para un día típico de reparto se dan en la Tabla. Las coordenadas 0,0 de la cuadrícula están en la esquina sur-oeste.

Los repartos pueden empezar a las 8:00 a.m. (hora en que los choferes dejan el depósito) y los conductores tienen que regresar a la farmacia a las 6.00 p.m. La velocidad promedio de conducción es de 50 km/hora. Los conductores tienen permitido un descanso de 1 hora para comer después de las 12 del mediodía. La mayoría de los clientes reciben sus repartos entre las 9AM y las 5PM, aunque existen algunas excepciones. La farmacia base se ubica en X=13.7 e Y=21.2. Si un conductor regresa pronto a la farmacia base, la camioneta puede volver a cargarse y se envía a una segunda ruta.

1. Diseñe un plan de ruta de envío que minimice la distancia total recorrida.
2. ¿Puede asignarse alguna ruta a la misma camioneta para reducir el número total de conductores y vehículos necesarios para el servicio a los clientes? En caso contrario ¿hay algo que pueda hacerse para lograrlo?

...