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

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
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id tesis:tesis_n5818_Negrotto
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (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 para satisfacer 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 nuevo problema. 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.
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
work_keys_str_mv AT negrottodaniel algoritmosparaelproblemadelocalizacionyruteodevehiculosconcapacidadesypremios
AT negrottodaniel algorithmsfortheprizecollectingcapacitedlocationroutingproblem
_version_ 1831981734485295104
spelling tesis:tesis_n5818_Negrotto2025-03-31T21:38:42Z 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 Negrotto, Daniel Loiseau, Irene 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 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 para satisfacer 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 nuevo problema. 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. 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. Fil: Negrotto, Daniel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2015-09-24 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion application/pdf spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n5818_Negrotto

Ejemplares similares