El doble problema del viajante con múltiples pilas

• Autores: Gregorio Tirado Domínguez
• Directores de la Tesis: Angel Felipe Ortega (dir. tes.) , María Teresa Ortuño Sánchez (dir. tes.)
• Lectura: En la Universidad Complutense de Madrid ( España ) en 2009
• Idioma: inglés
• Tribunal Calificador de la Tesis: Francisco José Cano Sevilla (presid.) , Begoña Vitoriano Villanueva (secret.) , Giovanni Righini (voc.) , Laureano Fernando Escudero Bueno (voc.) , Joaquín A. Pacheco Bonrostro (voc.)
• MSC2000 :
  • Ciencias de la computación
    • Inteligencia artificial
      • Resolución de problemas (heurística, estrategias de búsqueda, etc.)
  • Investigación de operaciones, programación matemática
    • Programación matemática
      • Métodos de aproximación y heurística
• Enlaces
  • Tesis en acceso abierto en: Docta Complutense
• Resumen

  • Los constantes cambios a los que se han visto sometidas las industrias del transporte y la logística durante los últimos años, junto con los nuevos requerimientos relacionados con el aumento de complejidad de las estrategias de planificación, han pro piciado la aparición de nuevos problemas de rutas de vehículos, muchos de los cuales incluyen restricciones complejas como pueden ser restricciones de precedencia y carga y aúnan elementos que antes pertenecían a campos perfectamente diferenciados, U no de estos problemas que han aparecido recientemente es el Doble Problema del Viajante con Múltiples Pilas (DTSPMS, del inglés Double Traveling Salesman Problem with Multiple Stacks), que es un problema de rutas de vehículos con restricciones de pre cedencia introducido recientemente a raíz de un proyecto de colaboración de la Universidad Técnica de Dinamarca con una empresa de software informático. Los problemas de rutas de vehículos han sido objeto de un amplio estudio en la literatura especia lizada durante las últimas décadas, considerándose una gran variedad de versiones con características muy distintas, pero el DTSPMS introduce algunos elementos novedosos que no han sido tratados todavía con detalle de forma conjunta.

    Se trata de un problema que consiste en encontrar la forma óptima de atender una serie de encargos consistentes en recoger cierta mercancía en determinadas localizaciones de una región y entregarla en las correspondientes localizaciones de otra región alejada geogr áficamente de la primera. La carga a transportar está formada habitualmente por euro-palés de tamaño estándar, que aunque pueden contener mercancías de muy diverso tipo, tienen unas dimensiones fijas que facilitan el uso de distintos medios de transp orte y permiten su almacenaje en varias filas en el contenedor del vehículo. Los vehículos son de carga trasera y los conductores, por razones de seguridad, no están autorizados a manipular la carga transportada en ningún caso, por lo que no es posib le ningún tipo de reorganización durante todo el proceso y los primeros encargos recogidos deben ser los últimos en entregarse.

    El DTSPMS es una generalización del Problema del Viajante (TSP, del inglés Traveling Salesman Problem) y por tanto es un problema NP-duro. En realidad es un problema notablamente más difícil de resolver que el TSP debido a las restricciones de precedencia y de carga que se añaden al problema, las cuales le permiten adaptarse mejor a diversas situaciones prácticas, y no