Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios
Algorithms for the prize-collecting capacited location routing problem
| dc.contributor | Loiseau, Irene | |
| dc.creator | Negrotto, Daniel | |
| dc.date | 2015 09 24 | |
| dc.date.accessioned | 2017-01-24T19:42:59Z | |
| dc.date.available | 2017-01-24T19:42:59Z | |
| dc.identifier | http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_5818_Negrotto | |
| dc.identifier | http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=HASHbe5c0863b4705676646901 | |
| dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/73910 | |
| dc.description | El problema de Localización y Ruteo de Vehículos con Capacidades (CLRP) es la combinación de dos problemas muy estudiados del área de la Investigación Operativa: el problema de localización de 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 para satisfacer las demandas de un conjunto de clientes y programar las rutas que los visitan. Se busca minimizar los costos de apertura de depósitos, de utilización de vehículos y de ruteo satisfaciendo restricciones 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 Ruteo de Vehículos con Capacidades y Premios (PC-CLRP) que busca generalizar el problema CLRP permitiendo la posibilidad de que los clientes sean o no visitados. Los clientes atendidos otorgan un beneficio y la maximización de la suma de los beneficios forma parte del objetivo del nuevo problema. Se proponen en este trabajo algoritmos para el problema PC-CLRP. En primer lugar se introduce un 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 colaboran construyendo las distintas etapas de una solución PC-CLRP: localización, clusterizado y ruteo. Posteriormente, se presentan modelos de programación lineal entera basadas en modelos de flujo de 2 índices y 3 índices. Se analizan distintas familias de desigualdades válidas utilizadas para 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 algoritmos de separación. Por último, se implementa un algoritmo Branch&Cut utilizando uno de los modelos de programación lineal entera propuestos. Se reportan los resultados obtenidos por ambos algoritmos para el problema PC-CLRP sobre un conjunto de instancias especialmente dise~nadas para el nuevo problema. Se compara además los resultados frente a los reportados en otros 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. | |
| dc.format | text; pdf | |
| dc.language | Español | |
| dc.publisher | Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires | |
| dc.subject | Computación / Metaheuristica | |
| dc.subject | Computación / Optimización Combinatoria | |
| dc.subject | PROBLEMA DE LOCALIZACION Y RUTEO DE VEHICULOS | |
| dc.subject | PROGRAMACION LINEAL ENTERA | |
| dc.subject | BRANCH AND CUT | |
| dc.subject | COLONIA DE HORMIGAS | |
| dc.subject | OPTIMIZACION COMBINATORIA | |
| dc.subject | RECOLECCION DE PREMIOS | |
| dc.title | Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios | |
| dc.title | Algorithms for the prize-collecting capacited location routing problem | |
| dc.type | Tesis |