Estudio poliédrico del Problema del Viajante Múltiple con Varios Depósitos
- Benavent López, Enric
- Martínez Sykora, Antonio
Editorial: Universidad de Murcia. Departamento de Estadística e Investigación Operativa
ISBN: 978-84-691-8159-1
Año de publicación: 2009
Congreso: Congreso Nacional de Estadística e Investigación Operativa (31. 2009. Murcia)
Tipo: Aportación congreso
Resumen
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.