Loading...
Please wait, while we are loading the content...
Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios
| Content Provider | Semantic Scholar |
|---|---|
| Author | Negrotto, Daniel |
| Copyright Year | 2015 |
| Abstract | El problema de Localizacion y Ruteo de Vehiculos con Capacidades (CLRP) es la combinacion de dos problemas muy estudiados del area de la Investigacion Operativa: el problema de localizacion de depositos con capacidades (CFLP) y el problema de ruteo de vehiculos con multiples depositos (MDVRP). Dado un conjunto de posibles localizaciones se busca determinar cuales 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 depositos, de utilizacion de vehiculos y de ruteo satisfaciendo restricciones de capacidad tanto en los vehiculos como en los depositos. En este trabajo se presenta una nueva version del problema denominada Localizacion y Ruteo de Vehiculos 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 maximizacion 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 metaheuristico para resolverlo basado en el metodo de optimizacion por Colonia de Hormigas. Se implementa una metaheuristica de 3 colonias de hormigas que colaboran construyendo las distintas etapas de una solucion PC-CLRP: localizacion, clusterizado y ruteo. Posteriormente, se presentan modelos de programacion lineal entera basadas en modelos de flujo de 2 indices y 3 indices. Se analizan distintas familias de desigualdades validas utilizadas para CLRP y se proponen nuevas versiones de las mismas para el problema PC-CLRP. Ademas, se definen nuevas desigualdades validas y cortes de optimalidad junto a sus correspondientes algoritmos de separacion. Por ultimo, se implementa un algoritmo Branch&Cut utilizando uno de los modelos de programacion 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 ademas los resultados frente a los reportados en otros trabajos sobre el problema CLRP obteniendo resultados competitivos. Palabras claves: problema de localizacion y ruteo de vehiculos, programacion lineal entera, branch and cut, colonia de hormigas, optimizacion combinatoria, recoleccion de premios. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://digital.bl.fcen.uba.ar/Download/Tesis/Tesis_5818_Negrotto.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
