Codificado Mixto Entero-Lineal para el Problema de Ruteo de Vehículos (VRP)

DONDO, RODOLFO; CERDÁ, JAIME

Buenos Aires

Congreso; Cuarto Congreso de Matemática Aplicada, Computacional e Industrial; 2013

Asociación Argentina de Matemática Aplicada, Computacional e Industrial

El heurístico de barrido propuesto por Gillet y Miller [1] es un procedimientos popular y efectivo para la resolución de problemas de programación de flotas homogéneas de vehículos (VRP). El mismo construye una solución factible en dos etapas: (1) se asignan nodos a vehículos y luego (2) se los secuencia sobre cada ruta para determinar el orden de visita a los clientes. Para llevar a cabo la primera etapa, se identifica a los clientes por medio de sus coordenadas polares respecto del depósito central en el que se alojan los vehículos. Considerando al depósito como pívote, se “barren” los nodos a asignar a un vehículo mediante un rayo que se desplaza en sentido antihorario y que inicialmente conecta el origen con un nodo “semilla” elegido arbitrariamente. Al desplazarse el rayo de barrido genera un sector angular creciente cuyos nodos serán servidos por el mismo vehículo, y este proceso de inclusión de nuevos clientes al sector continúa mientras la demanda total asignada no exceda la capacidad del vehículo. Cuando la restricción de capacidad es violada por la incorporación de un nuevo nodo, el procedimiento de asignación de cargas al vehículo actual se detiene y el nodo responsable de la activación del criterio de parada se toma como nodo semilla para iniciar el barrido del siguiente sector. La aplicación del método culmina cuando el rayo de barrido” alcanza nuevamente su posición de partida. El número de sectores angulares generados indica la cantidad de rutas que componen la solución del problema y los nodos de cada sector representan los clientes a ser visitados por un mismo vehículo. En una segunda etapa se procede a determinar el orden de visita de nodos sobre cada recorrido mediante la resolución del problema del viajante (TSP). Aunque el heurístico de barrido produce soluciones de buena calidad, no garantiza la obtención del óptimo porque el nodo inicial ha sido adoptado arbitrariamente y porque el método supone que no se produce ninguna superposición o solapamiento de rutas en el óptimo. Previamente se ha presentado [2] una formulación matemática del problema VRP que resulta de modelar el heurístico de barrido con dos ventajas adicionales. El modelo optimiza la elección de la posición inicial del rayo de barrido (el nodo semilla) así como el tamaño angular de las franjas resultantes. Ligeramente modificado, permite la generación de recorridos con algún grado de solapamiento. En el presente trabajo, se realiza una modificación al mismo para evitar las dificultades de exploración del árbol de “branch-and-bound” que surgen a consecuencia del número exponencial de soluciones simétricas que caracterizan al VRP.