Problema de capacidad de flota de vehículos

[pic 1]

[pic 2]

[pic 3]

1. 1.- Introducción

(Describe el contexto de la problemática general y particular del estudio que le ha sido asignado y presenta la estructura del informe profesional. 10%)

1. 2.- Definición del Problema.

 (Explica el problema abordado a través de un esquema o gráfico que detalla todas las variables del estudio y las casuísticas. 25%)

        Este trabajo está basado en la búsqueda de una solución óptima enfocado en un problema de enrutamiento de vehículos para una empresa de re-tailer del Reino Unido.

Se tiene una flota de vehículos, ubicados en un depósito, y un conjunto de clientes, cada uno con una demanda y una ventana de tiempo. Los camiones están programados para cargar y salir del depósito en la mañana y provisionar  sus tiendas de comestibles.  Al no considerar el número limitado de muelles disponibles  para cargar los vehículos, se genera una congestión en el depósito y como consecuencia, retrasos en los despachos. Cada recorrido comienza y termina en el depósito. Se debe considerar entonces que la demanda total a lo largo de cada recorrido no exceda  la capacidad del vehículo. Por otra parte, el servicio de cada cliente comienza dentro de una ventana de tiempo dada. Si el vehículo llega antes de la hora señalada, debe esperar. Estos tiempos son considerados dentro del trabajo como “tiempos de espera evitables” y se eliminan optimizando la hora de inicio de cada ruta.

        Se considera entonces que este es un problema de enrutamiento de vehículos clásico con ventana de tiempo (VRPTW). El Objetivo es : 1) Completar la ruta lo antes posible y 2) minimizar la extensión de la ruta. Una forma gráfica de un VRPTW del problema se presenta en la figura 1.-.

[pic 4]

Figura 1.- Forma gráfica del VRP con ventana de tiempo (VRPTW)

        Esta extensión del VRP, se considera una extensión de CVRP (Capacited Vehicle Routing Problem) , donde aparte de considerar la capacidad del vehículo , se considera que cada cliente se puede visitar en un intervalo de tiempo, denominado ventana de tiempo, es decir atender a un cliente en un horario prefijado. En el problema presentado se deben considerar:

• Los tiempos de los clientes son costosos por lo que son incluidos en la función objetivo.
• Se considerar las regulaciones de conducción y horas de trabajo, que requieren de descansos de suficiente duración después de una cantidad máxima de tiempo de conducción/ trabajo acumulado.
• El tiempo de trabajo incluye todas las actividades después de comenzar la ruta, es decir, la carga, el viaje, la espera y el tiempo de servicio.
• El depósito tiene cierto número de muelles. El número total de actividades de carga simultáneas nunca puede exceder este número.
• En el caso presentado, hay dos tipos de vehículos, cada uno con su propio muelle. La restricción en el número de actividades de carga simultáneas se define luego por tipo de vehículo.

3.-(Presenta el modelo matemático descrito en la literatura que aborda el problema, explicando : variables, función objetivo y restricciones. 35%)

3.- Presentación del Modelo Matemático

3.1 Modelando los muelles de carga del depósito.

        La restricción en el número de muelles es una restricción entre rutas (inter-route). Cambiar la hora de inicio de una ruta puede reducir el número de violaciones de la restricción en el número de muelles de carga. Sin embargo, las restricciones dentro de la ruta (en este caso, tiempo) de la ruta en cuestión también deben respetarse, que pueden evaluarse localmente.

Para separar la evaluación de las restricciones entre rutas (inter-route) y dentro de la ruta (intra-route), se propone  modelar los tiempos de carga de la siguiente manera:

1. Primero, se discretiza el tiempo en intervalos de muestra de tamaño apropiado. Estos intervalos de muestra representan períodos de tiempo que un vehículo ocupa un muelle de carga.

1. A continuación, para cada intervalo de muestra, contamos todas las actividades de carga durante este período.

1. El número total de actividades de carga no debe exceder el número de muelles disponibles. La Figura x muestra un ejemplo de este modelo con 3 vehículos cargando en el depósito.

        [pic 5]

Figura X : Ejemplo de un intervalo de muestra

         Se debe tomar en cuenta, que con este modelo se puede perder capacidad de carga, ya que se considera que, aunque los vehículos que cargan solo ocupan una parte del intervalo de muestra, se les asigna el tiempo del intervalo completo. Al hacer que el intervalo de muestra sea lo suficientemente pequeño, se puede resolver esta perdida de capacidad de carga.

        El modelo de intervalo de muestra permite una separación de inquietudes con respecto a las restricciones entre rutas (inter-route) y en la ruta (intra-route). Las restricciones entre rutas se evalúan contando el número de actividades de carga para cada intervalo de muestra. Luego, las horas de inicio relevantes de cada ruta son limitadas, La primera hora de inicio relevante es la hora de inicio de la ruta compacta (Se define que una ruta es compacta si el tiempo de finalización es mínimo, y la extensión  de la ruta es mínima dado este mínimo tiempo de finalización). Las otras horas de inicio relevantes son las horas de inicio de los intervalos de muestreo sucesivos posteriores a la hora de inicio relevante más temprana, y para los cuales la ruta aún es factible. La determinación de los tiempos de inicio relevantes, que requieren una reevaluación de las restricciones de tiempo dentro de la ruta, es limitada y puede realizarse sin un conocimiento explícito de las restricciones entre rutas.

...