Registro:
Documento: | Tesis Doctoral |
Disciplina: | computacion |
Título: | Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios |
Título alternativo: | Algorithms for the prize-collecting capacited location routing problem |
Autor: | Negrotto, Daniel |
Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
Filiación: | Universidad de Buenos Aires - CONICET. Instituto de Investigación en Ciencias de la Computación (ICC)
|
Publicación en la Web: | 2016-04-11 |
Fecha de defensa: | 2015-09-24 |
Fecha en portada: | 2015-09 |
Grado Obtenido: | Doctorado |
Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
Director: | Loiseau, Irene |
Jurado: | Cancela, Héctor; Pereira Lucena, Abilio; Marenco, Javier |
Idioma: | Español |
Palabras clave: | PROBLEMA DE LOCALIZACION Y RUTEO DE VEHICULOS; PROGRAMACION LINEAL ENTERA; BRANCH AND CUT; COLONIA DE HORMIGAS; OPTIMIZACION COMBINATORIA; RECOLECCION DE PREMIOSLOCATION ROUTING PROBLEM; INTEGER LINEAR PROGRAMMING; BRANCH AND CUT; ANT COLONY; COMBINATORIAL OPTIMIZATION; PRIZE-COLLECTING |
Tema: | computación/optimización combinatoria computación/metaheuristica
|
Formato: | PDF |
Handle: |
http://hdl.handle.net/20.500.12110/tesis_n5818_Negrotto |
PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n5818_Negrotto.pdf |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n5818_Negrotto |
Ubicación: | Dep.COM 005818 |
Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Negrotto, Daniel. (2015). Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n5818_Negrotto |
Resumen:
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.
Abstract:
The Capacitated Location Routing Problem (CLRP) is the combination of two well studiedproblems in Operations Research: Capacitated Facility Location Problem (CFLP) and Multiple Depots Vehicles Routing Problem (MDVRP). Given a set of available locations, the aim is tofind a subset of depots to satisfy customer demands and to determine the routes to visit thecustomers. The objective is to minimize the cost of the opened depots, the fixed cost of thevehicles in use and the cost of the routes satisfying vehicle and depot capacity constraints. In this work we present a new version of the problem named Prize-Collecting Capacitated Location Routing Problem (PC-CLRP). This problem is a generalization of CLRP where customershave not the requirement to be visited. A customer gives a benefit if it is considered as part ofthe proposed solution. The maximization of this benefits is a new objective for this problem. We proposed an algorithmic approach to solving PC-CLRP. First, we introduce a new meta-heuristic algorithm based on the Ant Colony Optimizationalgorithm. Our ant algorithm optimizes the 3 levels of decision: location, clustering and routing. Next, we present new models based on two-index and three-index ow integer linear programmingformulations. Known valid inequalities for CLRP are analyzed and adapted for PC-CLRP. This is complemented with the development of new valid inequalities and optimality cuts andtheir corresponding separation algorithms. Finally, we implement a Branch&Cut algorithm based on one of the proposed models. Computationalresults are reported for both implemented algorithms on a new set of instances speciallydesigned for the new problem. Additionally, we compare it with recent work for CLRP on instancesfrom the literature obtaining competitive results. Keywords: location routing problem, integer linear programming, branch and cut, ant colony,combinatorial optimization, prize-collecting
Citación:
---------- APA ----------
Negrotto, Daniel. (2015). Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n5818_Negrotto
---------- CHICAGO ----------
Negrotto, Daniel. "Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2015.https://hdl.handle.net/20.500.12110/tesis_n5818_Negrotto
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n5818_Negrotto.pdf