Resumen de Estudio poliédrico del Problema del Viajante Múltiple con Varios Depósitos

Enric Benavent López , Antonio Martínez Sykora

• En este trabajo se estudia el poliedro asociado a una generalizacion del Problema del Viajante de Comercio (TSP) que denotamos por MDMTSP por sus siglas en ingles:

  Multiple Depot, Multiple Traveling Salesman Problem. Dados un conjunto de clientes, J, y un conjunto de depositos, I, el MDMTSP consiste en encontrar un conjunto de rutas de coste total mnimo tales que, conjuntamente pasen por todos los clientes exactamente una vez y cada ruta empiece y acabe en el mismo deposito. Se propone una formulacion lineal entera del problema y se estudia la dimension y diversas facetas del poliedro asociado.

  Se presentan tambien algunos resultados computacionales preliminares obtenidos con un algoritmo de Rami cacion y Corte (Branch & Cut) basado en esta formulacion.