Resumen

Un enfoque totalmente multiobjetivo es usado en este artículo para estudiar un problema de enrutamiento de vehículos capacitado (CVRP), estocástico y multiobjetivo. En esta versión del problema, la demanda se considera determinística, pero los tiempos de viaje son asumidos como estocásticos. Una ventana de tiempo suave es asociada con cada cliente y hay una penalización por iniciar el servicio por fuera de esta. Dos objetivos son minimizados, la distancia total recorrida y la penalización por no cumplir con la ventana de tiempo. El método de solución propuesto incluye un algoritmo genético con ordenamiento no dominado (NSGA) y una heurística de búsqueda de vecindad variable (VNS). Se probó en problemas de la literatura y se comparó con un enfoque previo de solución. El método propuesto es capaz de encontrar soluciones que dominan algunas de las mejores soluciones conocidas para el CVRP multiobjetivo.

I. INTRODUCCIÓN

El problema de enrutamiento de vehículos capacitados (CVRP) es un problema bien conocido en el transporte propuesto en 1959 [1]. Se define sobre un grafo no dirigido G(V,E), donde V=v ₀,...,v_N es un conjunto de vértices y E=(v_i,v_j ):v_i,v_j ∈V,_i < _j es un conjunto de aristas. Existe una matriz simétrica C=[ci_j ] que corresponde a los costes de viaje a lo largo de la arista (vivj ). El vértice v 0 representa el depósito donde hay una flota homogénea de m vehículos con capacidad Q. Hay que servir a un conjunto de clientes Vv ₀ con una demanda conocida no negativa di. Una solución al CVRP consiste en m rutas de entrega con algunas condiciones específicas. Cada ruta debe empezar y terminar en el depósito. Cada cliente debe ser visitado una vez por exactamente un vehículo. La suma de las demandas de los clientes en una misma ruta, debe ser menor o igual a Q. Un enfoque diferente en el que la demanda corresponde a los artículos que deben ser recogidos de los clientes conduce a un problema equivalente. El objetivo clásico es la minimización de los costes totales de viaje [2].

La definición anterior es válida para el CVRP determinista, sin embargo se espera que en el mundo real uno o más de los elementos del CVRP sean inciertos. Estos elementos se incluyen en los modelos en forma de parámetros estocásticos. Esta variante del problema se conoce como problema estocástico (capacitado) de enrutamiento de vehículos (SVRP o SCVRP) [3, 4].

La fiabilidad de las entregas, definida como la entrega a tiempo de productos y servicios, es un campo competitivo importante para muchas empresas [5]. El tiempo de viaje entre dos clientes puede verse afectado por la congestión en la carretera y otras eventualidades, como los accidentes, lo que hace que el CVRP con tiempos de viaje estocásticos sea un problema relevante a estudiar. Este trabajo aborda un problema estocástico multiobjetivo de enrutamiento de vehículos con ventanas de tiempo suaves (TW).

• Materias:Algoritmos (Matemáticas) Algoritmos genéticos Fenómeno aleatorio (Matemáticas) Logística Procesos estocásticos Técnica heurística Tiempos y movimientos
• Subjects:Agorithms (Math) Genetic algorithms Random Phenomenon (Mathematics) Logistics Stochastic processes Metaheuristic technique Predetermined motion time systems
• Palabras claves:Algoritmos genéticos; Algoritmos heurísticos; Optimización multiobjetivo; Proceso aleatorio; Ruteo de vehículos.
• Keywords:Genetic algorithms; Heuristic Algorithms Multiobjective Programming; Random Processes; Vehicle Routing.