Tesis Pre-grado
Un Modelo de PLEM para Resolver el Problema de Ruteo de Vehículos con Localización de Paradas y la Asignación de Clientes
Un modelo de plem para resolver el problema de ruteo de vehículos con localización de paradas y la asignación de clientes
Autor
Obreque-Niñez, Carlos Enrique
UNIVERSIDAD DEL BIO-BIO
Institución
Resumen
El problema de ruteo de vehículos que considera conjuntamente la localización de paraderos, la
asignación de clientes a los paraderos y la determinación de las rutas ha sido considerablemente
abordado en la literatura en los últimos años. Sin embargo, ninguno de ellos ha considerado la
posibilidad de que, un vehículo en el transcurso de su recorrido, recoja además a clientes desde el
frente de su domicilio.
En esta memoria se busca resolver en forma óptima el problema de ruteo de vehículos con
localización de paraderos, la asignación de clientes y con la opción de recoger a ciertos clientes
desde su ubicación particular. Se denota por RVLPA.
EL RVLPA consiste en determinar un conjunto de rutas, para una flota de vehículos, que permitan
trasladar a un conjunto de clientes, los que se encuentran en paraderos seleccionados y los que serán
recogidos desde su domicilio, hacia un único destino predeterminado. El punto de partida de cada
ruta, los paraderos que se seleccionarán, la asignación de los clientes a los paraderos seleccionados
y los clientes que serán recogidos por los vehículos se determina minimizando el costo de las rutas
y la distancia total que recorren los clientes al paradero asignado, sin exceder la capacidad de cada
uno los vehículos disponibles para realizar el traslado. Dado que el RVLPA es un problema
multiobjetivo, en este estudio se utiliza el método de los pesos para transformarlo en un problema
de optimización mono objetivo.
Se presentan dos formulaciones de programación lineal entera, uno basado en flujo entero y el otro
basado en flujo multicommodity. Los dos modelos se ponen a prueba, utilizando el lenguaje de
programación matemática AMPL junto con el solver Cplex, en distintas instancias test de creación
propia, y otras obtenidas y adaptadas de la literatura.