Optimización para el ruteo dinámico de vehículos con ventanas de tiempo

Autores

Lic. Adrián Eidelman <adrianenlared(ARROBA)gmail.com>
Lic. Alejandro Valdez <avaldez(ARROBA)dc.uba.ar>

Directora

Dra. Irene Loiseau <irene(ARROBA)dc.uba.ar>

Introducción

A mediados del año 2006 comenzamos a trabajar en nuestra tesis para la carrera de Licenciatura en Ciencias de la Computación de la Facultad de Ciencias Exactas y Naturales (UBA), el trabajo tenía como objetivo el diseño e implementación de un algoritmo aproximado capaz de resolver en forma eficiente la variante dinámica del problema de ruteo de vehículos con ventanas de tiempo ( vehicle routing problem with time windows, VRPTW).

Descripción del problema

Un ejemplo de este problema es el de una empresa que venda productos y brinde el servicio de entrega a domicilio a sus clientes. Cuando un cliente compra un producto indica en que franja horaria le gustaría recibir su pedido, la empresa se compromete a realizar la entrega dentro de ese horario. El problema consiste en encontrar la mejor manera de organizar el reparto de pedidos de forma de aprovechar al máximo la capacidad de transporte de la flota de vehículos de la empresa.

El problema de ruteo dinámico de vehículos con ventanas de tiempo está compuesto de los siguientes elementos:

  • Una flota homogenea de vehículos con igual capacidad de carga.
  • Un depósito desde donde parten los vehículos con su carga y a donde vuelven una vez terminado el reparto.
  • Un área de distribución donde los vehículos realiazan la entrega de pedidos.
  • Un pedido tiene un tamaño, una dirección de entrega y una franja horaria donde el cliente espera recibirlo.
  • Una ruta es una secuencia de pedidos, cada ruta se asigna a un vehículo y el orden de los pedidos indica en que orden se visitará a los clientes para entregar la carga transportada.
El conjunto de pedidos es inicialmente vacío (no hay pedidos para entregar), y crece a medida que los clientes realizan sus pedidos. Por otro lado, cada vez que parte un vehículo a realizar una entrega se retira del conjunto de pedidos aquellos que transporta el vehículo en cuestión. De esta manera, el conjuntos de pedidos que maneja el sistema está en constante variación lo cual hace muy dificil el encontrar una solución óptima de recorridos en un instante dado.

El objetivo del problema es armar las rutas de reparto de forma de apovechar al máximo la capacidad de transporte de la flota de vehículos, mas precisamente se pretende:

  • Minimizar la cantidad de vehículos necesarios para realizar la entrega de pedidos.
  • Minimizar la distancia recorrida por la flota de vehículos.
  • Minimizar el tiempo de espera entre entregas consecutivas de una ruta.
  • Maximizar la capacidad utilizada en cada vehículo.

La optimización de estos aspectos tendría un importante impacto en los costos asociados a la distribución de productos, la reducción de costos permitiría mejorar la competitividad de la empresa. Además la automatización en el armado de los recorridos de reparto facilitaría la labor de la persona encargada de esta tarea.

Nuestra solución

Nuestro trabajo se basó en la utilización de una heurística de búsqueda local, utilizando movimientos Or-Opt para mejorar la calidad de las rutas de reparto. Además se utilizó como metaheurística la búsqueda tabú, con la intención de evitar que el algoritmo de búsqueda local se estanque en un óptimo local.

La implementación se realizó en C# utilizando un diseño orientado a objetos, que entre otras virtudes permite reemplazar en forma modular el algoritmo de búsqueda local y la metahurística lo cual facilita el experimentar y evaluar el comportamiento de otras heurísticas.

Resultados

Se probó la implementación con distintos lotes de prueba, obteniendo resultados muy alentadores que confirmaron la eficacia de nuestro algoritmo.

Trabajos futuros

A partir de este trabajo se pueden abordar los siguiente temas:

  • Desarrollo de un modelo matemático formal que ayude a comprender mejor el problema.
  • Implementación de nuevas técnicas heurísticas para la resolución del problema como submódulos del sistema.
  • Desarrollo de una interfaz gráfica que permita interactuar en tiempo real con el sistema.

Archivos

Informe de la tesis: [.doc] [.html]

Presentación de la tesis: [.ppt] [.html]

[Volver a mi página personal]

Contactanos: midnightsoret@gmail.com