Problemas de ruteo de vehículos
El Problema del Repartidor, PR, consiste en encontrar un camino que recorra un conjunto de clientes, comenzando en un punto dado, minimizando la suma de los tiempos de espera de estos clientes. Este es un problema de optimización simple y natural, que puede ser encontrado en diversas situaciones de...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Tesis doctoral publishedVersion |
| Lenguaje: | Español |
| Publicado: |
Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
2006
|
| Acceso en línea: | https://hdl.handle.net/20.500.12110/tesis_n3987_Zabala |
| Aporte de: |
| Sumario: | El Problema del Repartidor, PR, consiste en encontrar un camino que recorra un conjunto de clientes, comenzando en un punto dado, minimizando la suma de los tiempos de espera de estos clientes. Este es un problema de optimización simple y natural, que puede ser encontrado en diversas situaciones de la vida real, dentro de la industria y en el sector de servicios. La gran cantidad de aplicaciones hacen que este problema no sóolo tenga interés teórico, sino también, una gran importancia práctica. PR pertenece a la clase de problemas NP-Difícil. Para estos problemas no se conoce un algoritmo que encuentre la solución en tiempo polinomial. La mayor parte de la literatura sobre el PR está dedicada al desarrollo de algoritmos aproximados y heurísticas y son pocos los algoritmos exactos propuestos. Como muchos de los problemas de Optimización Combinatoria, PR puede ser modelado mediante formulaciones de programación lineal entera o entera mixta. Los algoritmos Branch-and-Cut son la herramienta más efectiva que se conoce para resolver un modelo de programación lineal entera. Especialmente las implementaciones basadas en combinatoria poliedral han permitido incrementar el tamaño de las instancias resueltas. El objetivo de esta tesis es abordar la resolución del Problema del Repartidor utilizando modelos de programación lineal entera binaria. Con este fin, proponemos una nueva formulación para modelar este problema. Realizamos un estudio poliedral de la cápsula convexa de las soluciones factibles, encontrando varias familias de desigualdades válidas que, bajo ciertas condiciones, demostramos que definen facetas del poliedro. Es la primera vez que se realiza un estudio poliedral asociado al Problema del Repartidor. En base a estas familias de desigualdades válidas, desarrollamos e implementamos un algoritmo Branch-and-Cut. |
|---|