Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2015-09-24

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Temas:

PROBLEMA DE LOCALIZACION Y RUTEO DE VEHICULOS - PROGRAMACION LINEAL ENTERA - BRANCH AND CUT - COLONIA DE HORMIGAS - OPTIMIZACION COMBINATORIA - RECOLECCION DE PREMIOS - LOCATION ROUTING PROBLEM - INTEGER LINEAR PROGRAMMING - BRANCH AND CUT - ANT COLONY - COMBINATORIAL OPTIMIZATION - PRIZE-COLLECTING

Descripción:

El problema de Localización y Ruteo de Vehículos con Capacidades (CLRP) es la combinación dedos problemas muy estudiados del área de la Investigación Operativa: el problema de localizaciónde depósitos con capacidades (CFLP) y el problema de ruteo de vehículos con múltiples depósitos (MDVRP). Dado un conjunto de posibles localizaciones se busca determinar cuáles utilizar parasatisfacer las demandas de un conjunto de clientes y programar las rutas que los visitan. Se buscaminimizar los costos de apertura de depósitos, de utilización de vehículos y de ruteo satisfaciendorestricciones de capacidad tanto en los vehículos como en los depósitos. En este trabajo se presenta una nueva versión del problema denominada Localización y Ruteode Vehículos con Capacidades y Premios (PC-CLRP) que busca generalizar el problema CLRPpermitiendo la posibilidad de que los clientes sean o no visitados. Los clientes atendidos otorganun beneficio y la maximización de la suma de los beneficios forma parte del objetivo del nuevoproblema. Se proponen en este trabajo algoritmos para el problema PC-CLRP. En primer lugar se introduceun algoritmo metaheurístico para resolverlo basado en el método de optimización por Colonia de Hormigas. Se implementa una metaheurística de 3 colonias de hormigas que colaboranconstruyendo las distintas etapas de una solución PC-CLRP: localización, clusterizado yruteo. Posteriormente, se presentan modelos de programación lineal entera basadas en modelosde flujo de 2 índices y 3 índices. Se analizan distintas familias de desigualdades válidas utilizadaspara CLRP y se proponen nuevas versiones de las mismas para el problema PC-CLRP. Además,se definen nuevas desigualdades válidas y cortes de optimalidad junto a sus correspondientes algoritmosde separación. Por último, se implementa un algoritmo Branch&Cut utilizando uno delos modelos de programación lineal entera propuestos. Se reportan los resultados obtenidos porambos algoritmos para el problema PC-CLRP sobre un conjunto de instancias especialmentedise~nadas para el nuevo problema. Se compara además los resultados frente a los reportados enotros trabajos sobre el problema CLRP obteniendo resultados competitivos. Palabras claves: problema de localización y ruteo de vehículos, programación lineal entera,branch and cut, colonia de hormigas, optimización combinatoria, recolección de premios.

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n5818_Negrotto