Título: Problemas de recolecci ón y entrega punto a punto.
Directoras: Isabel Méndez-Díaz y Paula Zabala.
Jurados: Héctor Cancela, Santiago Figueira y Javier Marenco.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 ún no descripta en la bibliografía.

Se presenta un estudio sobre la efectividad computacional de distintas formulaciones para resolver el 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. Considerando los análisis realizados se desarrolla un algoritmo Branch And Cut. Finalmente se muestra la efectividad de las componentes propuestas para el algoritmo mediante pruebas computacionales sobre el conjunto de instancias creadas.