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

Mostrar todas las versiones(3)

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Negrotto, Daniel
Otros Autores: Loiseau, Irene
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2015
Materias:
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
ANT COLONY
COMBINATORIAL OPTIMIZATION
PRIZE-COLLECTING
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n5818_Negrotto
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n5818_Negrotto_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n5818_Negrotto_oai
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Español
orig_language_str_mv spa
topic 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
spellingShingle 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
Negrotto, Daniel
Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios
topic_facet 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
description 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.
author2 Loiseau, Irene
author_facet Loiseau, Irene
Negrotto, Daniel
format Tesis doctoral
Tesis doctoral
publishedVersion
author Negrotto, Daniel
author_sort Negrotto, Daniel
title Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios
title_short Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios
title_full Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios
title_fullStr Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios
title_full_unstemmed Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios
title_sort algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2015
url https://hdl.handle.net/20.500.12110/tesis_n5818_Negrotto
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n5818_Negrotto_oai
work_keys_str_mv AT negrottodaniel algoritmosparaelproblemadelocalizacionyruteodevehiculosconcapacidadesypremios
AT negrottodaniel algorithmsfortheprizecollectingcapacitedlocationroutingproblem
_version_ 1766015862366535680
spelling I28-R145-tesis_n5818_Negrotto_oai2023-04-26 Loiseau, Irene Negrotto, Daniel 2015-09-24 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. 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 Fil: Negrotto, Daniel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n5818_Negrotto spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar 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 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 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n5818_Negrotto_oai

Ejemplares similares