Problema de localización y ruteo con pickup y delivery

Abstract

El objetivo de esta tesis es formular un modelo que integre el Pickup and Delivery Problem (PDP) y la localización óptima de los depots de distribución, el cual llamaremos Problema de Localización y Ruteo con Pickup and Delivery (PLRPDP). Este problema se plantea y tiene una gran variedad de aplicaciones en la industria, como por ejemplo en el courier, en el transporte de pasajeros, o en el transporte de alimentos perecibles, y por lo tanto es de suma importancia cuando existe un sistema de alta demanda con diferentes opciones en relación a la ubicación de los depots. Para modelar este problema se propone un esquema de generación de columnas, donde el problema maestro resultante es similar al del modelo propuesto por Berger et al. (2007), pero en este caso, el subproblema es un PDP. Para resolver este subproblema y poder generar columnas factibles para el problema maestro, se propone un algoritmo de label-setting, que resuelve el problema de camino más corto, con restricciones de Pickup and Delivery y ventanas de tiempo. Además se propone un conjunto de heurísticas para acelerar este proceso. Para validar el modelo, se hace una implementación del esquema de generación de columnas, el cual se prueba en diferentes instancias, algunas ya existentes en la literatura actual, como también desarrolladas en este trabajo. Destacando dentro de estas últimas, las instancias clusterizadas y las de tipo corredor, las cuales por su geometría especial hacen que la localización de los depots sea de suma importancia. También se hace un análisis detallado de como los costos de apertura de los depots inciden en la solución óptima. Finalmente se presentan resultados del rendimiento de nuestra implementación para cada una de las instancias.