Registro:
| Documento: | Tesis de Grado |
| Título: | Ruteo de vehículos y asignación de conductores : un enfoque combinado |
| Autor: | Bakarcic, Damián; Di Piazza, Gabriela |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2012 |
| Fecha en portada: | Septiembre 2012 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Méndez Díaz, Isabel |
| Director Asistente: | Zabala, Paula Lorena |
| Jurado: | Feuerstein, Esteban Zindel; Marenco, Javier Leonardo |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000727_BakarcicDiPiazza |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000727_BakarcicDiPiazza.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000727_BakarcicDiPiazza |
| Ubicación: | Dep.COM 000727 |
| 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. Bakarcic, Damián; Di Piazza, Gabriela. (2012). Ruteo de vehículos y asignación de conductores : un enfoque combinado. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000727_BakarcicDiPiazza |
Resumen:
El problema de planificar rutas para vehículos y sus correspondientes conductores se presenta en la práctica en áreas de logística como transporte de pasajeros y distribución de mercadería. En la actualidad, dada la complejidad y variedad de los sistemas de transporte y distribución, se hace imperativo el uso de herramientas de optimización para resolver esta clase de problemas. En este trabajo se aborda un problema surgido de la práctica que consiste en planificar el retiro y entrega de un conjunto de pedidos de mercadería, cumpliendo con ciertas restricciones horarias, en función de un conjunto de vehículos disponibles. Asimismo, se debe planificar la asignación de los conductores a los vehículos que realizarán cada tarea. El problema conjuga características de tres problemas estudiados en la literatura como son: el Vehicle Routing Problem, el Crew Scheduling Problem y el Pick-up and Delivery Problem with Time Windows. Para resolver este problema proponemos un modelo de programación lineal entera binaria que contempla en forma integrada la planificación de rutas de vehículos y la asignación de los correspondientes conductores. Debido a que el modelo resultante cuenta con una gran cantidad de variables, utilizamos la técnica de generación de columnas para generar los posibles recorridos a realizar por los vehículos. El esquema de resolución propuesto particiona al problema en dos: el problema maestro y el subproblema de generación de columnas. Para el primero utilizamos un algoritmo Branch and Cut. Para el último desarrollamos un algoritmo basado en programación dinámica que busca el camino óptimo sobre una red con recursos y restricciones. Los caminos sobre dicha red representan las posibles rutas que pueden transitar los vehículos. Además de la implementación original propuesta para el algoritmo de generación de columnas, desarrollamos optimizaciones sobre el mismo y realizamos pruebas para verificar los resultados de dichas optimizaciones. Finalmente, presentamos un conjunto de pruebas que evalúa el comportamiento del esquema de resolución general implementado.
Abstract:
The problem of vehicle routing planning combined with crew scheduling arise in areas of logistics such as passenger transport and merchandise distribution. At present, given the complexity and variety of transport and distribution systems, it is imperative to use optimization tools to solve such problems. This work addresses a real life problem involving the planning of the pick-up and delivery of a set of orders, according to certain time restrictions, based on a set of available vehicles. In addition, the allocation of crews to the vehicles which perform each task must also be scheduled. This problem combines features present in three well studied problems: the Vehicle Routing Problem, the Crew Scheduling Problem and the Pick-up and Delivery Problem with Time Windows. To solve this problem we propose a binary integer linear programming model that provides integrated planning of vehicle routing and crew scheduling. Due to the large number of variables of the resulting model, we use column generation in order to generate the possible routes to be taken by the vehicles. The proposed resolution framework gives rise to two problems: the master problem and the subproblem of column generation. To solve the first we use a Branch and Cut algorithm. For the latter we develop a dynamic programming algorithm that seeks the optimal path over a resource constrained network. The paths on this network represent the possible routes that can be taken by the vehicles. In addition to the original implementation, we develop optimizations over the column generation algorithm and perform tests to verify the results of these optimizations. Finally, we present a set of tests to analyze the performance of the implemented algorithms.
Citación:
---------- APA ----------
Bakarcic, Damián; Di Piazza, Gabriela. (2012). Ruteo de vehículos y asignación de conductores : un enfoque combinado. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000727_BakarcicDiPiazza
---------- CHICAGO ----------
Bakarcic, Damián; Di Piazza, Gabriela. "Ruteo de vehículos y asignación de conductores : un enfoque combinado". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2012.https://hdl.handle.net/20.500.12110/seminario_nCOM000727_BakarcicDiPiazza
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000727_BakarcicDiPiazza.pdf
Distrubución geográfica
