Multiple ant colony system for a vrp with time windows and scheduled loading

Múltiples sistemas de colonias de hormigas para un vrp con ventanas de tiempo y programación de la carga

El problema de rutas para vehículos con ventanas de tiempo y programación de la carga no solo requiere el diseño de las rutas que satisfagan las restricciones temporales y de capacidad de los vehículos sino que también la programación de las salidas de los vehículos desde un terminal dado un tiempo de carga debido a los recursos limitados disponibles para cargar las demandas de los clientes en los vehículos.

No solo se presenta una formulación del problema de diseño de rutas para vehículos con ventanas de tiempo y programación de la carga, sino que también se propone e implementa una metaheurística basada en múltiples sistemas de colonias de hormigas, cada una con una sola función objetivo, organizadas de manera jerárquica. Se incorpora una forma de actualización de tiempo dentro del procedimiento constructivo para actualizar y programar la salida de un vehículo desde el terminal cuando cada hormiga se mueve a un nuevo cliente. Se utiliza propagación de restricciones para determinar un movimiento factible a un nuevo cliente. Como el [VRPTWSL] incorpora la programación de la salida de los vehículos, el algoritmo presentado en este artículo tiene una directa aplicación a problemas reales, de esta manera, el [VRPTWSL] se puede tomar como un importante avance para problemas de diseño de rutas para vehículos.

INTRODUCCIÓN

A lo largo de los últimos cincuenta años, la comunidad científica se ha interesado por varios problemas de enrutamiento de vehículos, sobre todo por su complejidad inherente. Además, en casi todos los problemas de la cadena de suministro se requiere algún tipo de transporte de mercancías entre los componentes internos o externos.  

El problema de enrutamiento de vehículos con ventanas de tiempo se especifica en términos de minimizar el tiempo y el coste total para que una flota de vehículos distribuya las mercancías desde un depósito a los clientes que deben ser visitados exactamente una vez dentro de sus ventanas de tiempo (intervalos de tiempo). Todas las rutas comienzan y terminan en el mismo depósito, y la demanda total de todos los clientes atendidos por un vehículo a lo largo de una ruta concreta no debe superar su capacidad total. Las funciones objetivo típicas son minimizar el número de vehículos y el tiempo total de viaje.

En este trabajo proponemos una variante del problema de enrutamiento de vehículos con ventanas de tiempo denominada Problema de Enrutamiento de Vehículos con Ventanas de Tiempo y Carga Programada [VRPTWSL]. En este problema, tenemos que tener en cuenta la característica adicional relacionada con la carga en cada vehículo en el depósito, las mercancías entregadas a los clientes en la ruta asociada.