Modelo matemático del problema VRPTW basado en el heurístico de barrido

J. CERDÁ; R. DONDO; C.A. MÉNDEZ

Cartagena de Indias, Colombia

Congreso; CLAIO 2008; 2008

INFORMS

El heurístico de barrido (“sweep heuristic”) propuesto por Gillet y Miller [1] ha sido uno de los procedimientos más populares y efectivos para la resolución de problemas de programación de flotas homogéneas de vehículos (VRP) con y sin ventanas de tiempo. Usualmente, se construye una solución factible del problema 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 pivote u origen, se “barren” los nodos a asignar a un dado vehículo mediante un rayo que se desplaza en sentido contrario a las agujas del reloj y que inicialmente conecta el origen con un nodo “semilla” elegido arbitrariamente. Al desplazarse el rayo de “barrido” genera una franja o sector de tamaño 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 sería violada por la incorporación de un nuevo nodo al sector, 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 y el procedimiento de asignación de nodos a vehículos se ha completado. El número de franjas generadas indica la cantidad de rutas que componen la solución del problema y los nodos de cada franja 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 del problema por dos razones: (a) el nodo “semilla” inicial ha sido adoptado arbitrariamente y se requeriría optimizar su elección; y (b) el método supone que no se produce ninguna superposición o solapamiento de rutas en el óptimo. A menudo, el cumplimiento de las ventanas de tiempo lleva a obtener soluciones óptimas con rutas mostrando algún grado de solapamiento o, alternativamente, la carga asignada a algunos vehículos es inferior a su capacidad máxima. Este trabajo presenta una formulación matemática del problema VRPTW 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 del “barrido”. Además, ligeramente modificado, permitiría la generación de recorridos con algún grado de solapamiento.