VRPTW PDF Imprimir E-mail

Problema del Ruteo Vehicular con Ventanas de Tiempo.

El problema de ruteo de vehículos con ventana de tiempo (VRPTW, por sus siglas en inglés) es un problema basado en asignación de rutas a vehículos para atender a diferentes clientes, este problema se caracteriza por utilizar un rango de tiempo de atención asignado a cada cliente, conocido como ventana de tiempo, la ventana de tiempo incrementa el número de restricciones en el problema lo que complica la búsqueda de la solución. El modelo que representa al VRPTW [Toth and Vigo, 01] se presenta a continuación.

Modelo NP-Completo VRPTW.

La función objetivo que se presenta en (1), representa el costo total, el cual se puede interpretar como el tiempo de viaje o distancia recorrida total de todos los vehículos que interviene en el suministro. Se requiere encontrar la  mínima  distancia de recorrido total utilizando el menor número de vehículos. La variable xijk, toma valor de uno cuando el vehículo k atiende la ruta que va del cliente i al cliente j. El depósito se representa como i = 0 ó i = 1 + n. Las restricciones que se deben cumplir se presentan de (2) a (11).


  •  Restricciones en (2), indican que un cliente será atendido por un sólo vehículo.
  •  Restricciones de (3) a (5), dan las características de  la ruta a seguir por cada vehículo k.
  • Restricciones en (3), indican que para cada vehículo k, sólo un cliente j se puede alcanzar partiendo del depósito.
  • Restricciones en (4), indican que el número de vehículos que llegan a un cliente  es el mismo número de vehículos que sale.
  • Restricciones en (5), indica que cada ruta vehicular tiene un sólo cliente que conecta al depósito.
  •  Restricciones (6) a (8) y (9), garantizan la factibilidad de la secuencia con respecto a condiciones de tiempo y aspectos de capacidad respectivamente.
  • Restricciones en (6), indican que no se puede iniciar un servicio en cliente j si el cliente i no ha sido atendido y el vehículo no ha llegado al cliente j. Aquí M es una constante muy grande.
  • Restricciones en (7), indican para cada unidad vehicular y cada cliente i, que el tiempo inicial del servicio wik debe iniciar dentro de la ventana de tiempo [ai, bi].
  • Restricciones en (8), indican para cada unidad vehicular y en el depósito 0, que el tiempo inicial del servicio wik debe iniciar dentro de la ventana de tiempo [E, L], el cual es el intervalo de atención del deposito.
  • Restricciones en (9),  indican que para todo vehículo k, la suma de las demandas de todos los clientes atendidos no debe exceder la capacidad del vehículo.
  •  Restricciones (10), son restricciones de no negatividad de las variables x.
  •  Restricciones (11), son restricciones que definen al modelo lineal como un modelo lineal entero binario. Estas restricciones definen la dureza del problema.


A continuación se presenta la metodología desarrollada para el presente proyecto para dar solución a ciertas instancias del VRPTW definidas por Solomon [Solomon, 1987].

Algoritmo Genético híbrido.

La figura 1, presenta la metodología de solución [Díaz-Parra and Cruz-Chávez, 08] que está formada de un algoritmo genético que contiene un operador de selección “the best”, un operador de cruzamiento “crossover-k” y un operador de mutación “mutation-S” con multi poblaciones iniciales generadas con la técnica de k-means comúnmente utilizada en técnicas de minería de datos. En el algoritmo genético propuesto se crean las poblaciones mediante agrupación k-means donde los individuos se crean factibles de acuerdo a su distribución geográfica. El operador “the best”, selecciona de acuerdo a su aptitud en un porcentaje a los mejores individuos de cada población y cruza estos por población. Con el cruzamiento k, se mantiene el tamaño de cada población y permite la exploración del espacio de soluciones. El mutador inteligente optimiza la función de aptitud, de tal forma que se reacomode cada gen en su respectivo cromosoma para llegar a un individuo-mejor-solución; lo que significa que la agrupación de genes en ese individuo es la que reportará la menor distancia total recorrida ya que la agrupación será entre genes cercanos a él en el espacio euclidiano, este mutador realiza una búsqueda local hasta mejorar la aptitud del individuo del que se parte. El procedimiento anterior se repite en cada generación multi poblacional.


Procesamiento distribuido del Algoritmo.

El procesamiento distribuido aplicado al algoritmo se presenta en la figura 2. En cada nodo de la MiniGRID Tarántula, se crea una población factible. Cada nodo realiza de manera independiente la selección, cruzamiento y mutación. Antes del inicio de una nueva generación los nodos se comunican para intercambiar parte de su población. Esto es una representación de la realidad de lo que pasa con los grupos de inmigrantes, en este caso existe migración de una población a otra.

 


 



 

Patrocinadores


CIICAp
Maestrías y Doctorados en: Tecnología Eléctrica, Tecnología Química, Tecnología de Materiales y Tecnología Mecánica.




 

 

Links Relacionados

Mapa de visitas de esta página

Springer
Revista Programación Matemática

Springer

Artículo Mini Grid Morelos
Artículo Mini Grid Morelos

Contador de visitas

mod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_counter
mod_vvisit_counterHoy67
mod_vvisit_counterAyer53
mod_vvisit_counterEsta semana67
mod_vvisit_counterÚltima semana318
mod_vvisit_counterEste més275
mod_vvisit_counterUltimo més1980
mod_vvisit_countertodos los dìas431874