Formulaciones de Tamaño Polinomial para el Problema de Recolección y Entrega Punto a Punto

FACTOROVICH, PABLO; MÉNDEZ-DÍAZ, ISABEL; ZABALA, PAULA

Colombia

Congreso; XIV Congreso Latinoiberoamericano de Investigación Operativa; 2008

Asociación Latino-Iberoamericana de Investigación Operativa

En el problema de Recolección y Entrega Punto a Punto (o One-to-One Pickup and Delivery Problem (PDP) por su denominación en inglés), un vehículo debe partir de un depósito de origen, realizar una ruta que satisfaga un conjunto de solicitudes y concluir en un depósito destino. Estas últimas se referirán a actividades de transporte desde un nodo origen a un nodo destino determinados, por lo tanto, las tareas indicarán un orden de precedencia en los nodos a ser visitados. El objetivo del problema es encontrar una ruta que cumpla con las tareas minimizando el combustible utilizado. En este trabajo nos proponemos abordar dicho problema ya que un estudio de estas formulaciones y su efectividad conducirá a nuevas y, posiblemente, exitosas formulaciones para el PDP.