Registro:
| Documento: | Tesis Doctoral |
| Título: | Problemas de recolección y entrega punto a punto |
| Título alternativo: | One-to-one pickup and delivery problems |
| Autor: | Factorovich, Pablo Matías |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la Web: | 2022-03-29 |
| Fecha de defensa: | 2019-07-01 |
| Fecha en portada: | 2019 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
| Director: | Méndez-Díaz, Isabel; Zabala, Paula Lorena |
| Jurado: | Cancela Bosi, Héctor; Marenco, Javier Leonardo; Figueira, Santiago |
| Idioma: | Español |
| Palabras clave: | PROBLEMA DE RECOLECCION Y ENTREGA; GRAFO DE INCOMPATIBILIDADES; PROBLEMA DE RUTEO; PROGRAMACION LINEAR ENTERA; BRANCH AND CUT; COLOREO DE GRAFOS; BIN PACKING PROBLEM; TEORIA POLIEDRAL; NP-HARDPICKUP AND DELIVERY PROBLEMS; INCOMPATIBILITIES GRAPH; ROUTING PROBLEMS; LINEAR INTEGER PROGRAMMING; BRANCH AND CUT; GRAPH COLORING; BIN PACKING PROBLEM; POLYHEDRAL THEORY; NP-HARD |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n6915_Factorovich |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n6915_Factorovich.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n6915_Factorovich |
| Ubicación: | Dep.COM 006915 |
| 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. Factorovich, Pablo Matías. (2019). Problemas de recolección y entrega punto a punto. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n6915_Factorovich |
Resumen:
En este trabajo se estudian dos problemas de ruteo de vehículos: el Problema de Recolección y Entrega Punto a Punto con Distancias Asimétricas (APDP, por sus siglas en inglés) y el Problema de Recolección y Entrega Punto a Punto con Distancias Asimétricas e Incompatibilidades (PDPwI), una variante del primero a ́un no descripta en la bibliografía. Se presenta un estudio sobre la efectividad computacional de distintas formulaciones para resolver el APDP. Uno de los modelos evaluados es original, mientras que los restantes fueron tomadas de la bibliografía. De estos, algunos fueron pensados inicialmente para este problema y la amplia mayoría fueron ideados para el Problema del Viajante de Comercio con Restricciones de Precedencia y Distancias Asimétricas que, aunque lo generaliza, sus formulaciones no habían sido aún usadas para resolver al APDP. En cuanto al PDPwI, se lo define formalmente y se muestra que además de generalizar al APDP, generaliza el problema de coloreo de vértices, el Bin Packing Problem y el Bin Packing Problem with Conflicts. Se formulan tres diferentes modelos para el PDPwI basados en formulaciones que resultaron eficientes para el APDP. Se construye también un conjunto de instancias de prueba para el PDPwI y se lo utiliza para evaluar las tres formulaciones creadas mediante algoritmos Branch And Cut. En base a estas pruebas y otras consideraciones, se selecciona uno de estos modelos para el cual se realiza un estudio poliedral del politopo asociado, hallándose 36 familias de desigualdades y 5 de igualdades válidas. Asimismo se caracteriza la dimensión del mismo y se demuestra que una de las familias de desigualdades halladas define una faceta. En base a los análisis ya mencionados se desarrolla un algoritmo Branch And Cut, para el cuál también se crean algoritmos de planos de corte, una heurística primal y una estrategia de branching. Finalmente se muestra la efectividad de las componentes propuestas para el algoritmo mediante pruebas computacionales con el conjunto de instancias creadas.
Abstract:
In this work we study two routing problems: the asymmetric one-to-one pickup and delivery problem(APDP) and the asymmetric one-to-one pickup and delivery problem with incompatibilities(PDPwI), a variant of the former not yet introduced in the routing literature. We present a study on the computational effectiveness of some formulations to solve the APDP. One of these models is original, while the remaining were taking from the literature. From these, some were thought specifically for this problem and almost all of them for the precedence constrained asymmetric travel salesperson problem (PCATSP). Though PCATSP generalizes APDP, their formulations have never been used to solve the APDP. We also define formally the PDPwI and show that it generalizes the APDP, the vertex coloring problem, the bin packing problem and the bin packing problem with conflicts. We formulate three different models for the PDPwI which rest on three respective efficient formulations for APDP. We also generate a set of instances for PDPwI. We use it to evaluate the three formulations created through Branch And Cut algorithms. Based on these tests and other considerations, we pick one of the models. We perform a polyhedral study of the associated polytope and find several families of valid lineal restrictions: 36 inequalities and 5 equalities. Besides, we characterize the polyhedron dimension and we show that one of the inequalities families found is facet defining. Following the mentioned analysis we develop a Branch And Cut algorithm and we improve it by developing a cutting plane algorithm, a primal heuristic and a branching strategy. Finally, we show the effectiveness of those components testing them on the instance set built
Citación:
---------- APA ----------
Factorovich, Pablo Matías. (2019). Problemas de recolección y entrega punto a punto. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n6915_Factorovich
---------- CHICAGO ----------
Factorovich, Pablo Matías. "Problemas de recolección y entrega punto a punto". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2019.https://hdl.handle.net/20.500.12110/tesis_n6915_Factorovich
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n6915_Factorovich.pdf
