Problemas de recolección y entrega punto a punto

Mostrar todas las versiones(3)

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 d...

Descripción completa

Detalles Bibliográficos
Autor principal: Factorovich, Pablo Matías
Formato: Tesis Doctoral
Lenguaje:Español
Publicado: 2019
Materias:
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-HARD
PICKUP AND DELIVERY PROBLEMS
INCOMPATIBILITIES GRAPH
ROUTING PROBLEMS
LINEAR INTEGER PROGRAMMING
GRAPH COLORING
POLYHEDRAL THEORY
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n6915_Factorovich
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:tesis_n6915_Factorovich
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 Español
topic 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-HARD
PICKUP AND DELIVERY PROBLEMS
INCOMPATIBILITIES GRAPH
ROUTING PROBLEMS
LINEAR INTEGER PROGRAMMING
BRANCH AND CUT
GRAPH COLORING
BIN PACKING PROBLEM
POLYHEDRAL THEORY
NP-HARD
spellingShingle 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-HARD
PICKUP AND DELIVERY PROBLEMS
INCOMPATIBILITIES GRAPH
ROUTING PROBLEMS
LINEAR INTEGER PROGRAMMING
BRANCH AND CUT
GRAPH COLORING
BIN PACKING PROBLEM
POLYHEDRAL THEORY
NP-HARD
Factorovich, Pablo Matías
Problemas de recolección y entrega punto a punto
topic_facet 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-HARD
PICKUP AND DELIVERY PROBLEMS
INCOMPATIBILITIES GRAPH
ROUTING PROBLEMS
LINEAR INTEGER PROGRAMMING
BRANCH AND CUT
GRAPH COLORING
BIN PACKING PROBLEM
POLYHEDRAL THEORY
NP-HARD
description 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.
format Tesis Doctoral
author Factorovich, Pablo Matías
author_facet Factorovich, Pablo Matías
author_sort Factorovich, Pablo Matías
title Problemas de recolección y entrega punto a punto
title_short Problemas de recolección y entrega punto a punto
title_full Problemas de recolección y entrega punto a punto
title_fullStr Problemas de recolección y entrega punto a punto
title_full_unstemmed Problemas de recolección y entrega punto a punto
title_sort problemas de recolección y entrega punto a punto
publishDate 2019
url https://hdl.handle.net/20.500.12110/tesis_n6915_Factorovich
work_keys_str_mv AT factorovichpablomatias problemasderecoleccionyentregapuntoapunto
AT factorovichpablomatias onetoonepickupanddeliveryproblems
_version_ 1807315372681986048
spelling todo:tesis_n6915_Factorovich2023-10-03T13:14:13Z Problemas de recolección y entrega punto a punto One-to-one pickup and delivery problems Factorovich, Pablo Matías 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-HARD PICKUP AND DELIVERY PROBLEMS INCOMPATIBILITIES GRAPH ROUTING PROBLEMS LINEAR INTEGER PROGRAMMING BRANCH AND CUT GRAPH COLORING BIN PACKING PROBLEM POLYHEDRAL THEORY NP-HARD 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. 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 Fil: Factorovich, Pablo Matías. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2019 Tesis Doctoral PDF Español info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n6915_Factorovich

Ejemplares similares