Resumen de Una nueva formulación para el problema general de rutas es un grafo mixto
Hermilson Velásquez Ceballos
En esta Tesis se estudia, desde el punto de vista poliédrico, un problema de rutas de vehículos clásico, el Problema General de Rutas sobre un grafo mixto MGRP, Consiste en, dado un grafo mixto encontrar un tour de longitud mínima que pase al menos uanv ez, por un subconjunto dado de aristas "requeridas", por un subconjunto dado de aracos "requeridos" y por un subconjunto dado de vértices "requeridos". Así, el MGRP incluye, como casos particulares, a una gran parte de los problemas de rutas clásicos y puede considerarse como el problema de rutas con un solo vehículo más general. En esta Tesis proponemos una formulación que permite que los resultados obtenidos sean aplicables a todos los problemas de rutas que generaliza.
Así, la mayor aportación de este trabajo es el establecimiento de un marco común para el estudio poliedrico de la mayor parte de los problemas de rutas clásicos con un solo vehículo. También es la base teórica para el futuro desarrollo de un algoritmo exacto de resolución para el MGRP basado en los planos de corte definidos por las desigualdades aquí encontradas que inducen faceta de poliedro.
