Resumen de Un nuevo heurístico para el problema general de rutas con capacidades

Julio César Angel Gutiérrez, David Soler Fernández , Antonio Hervas Jorge

• Uno de los problemas más complejos de optimización combinatoria sobre rutas de vehículos, es conocido como el Problema General de Rutas con Capacidades sobre grafos mixtos (PGRC-m). Básicamente consiste en buscar un conjunto de rutas sobre un grafo mixto que empiezan y acaban en el mismo vértice, con coste mínimo, que satisfacen demandas localizadas en vértices y enlaces y con una restricción de capacidad sobre la demanda satisfecha por cada ruta. Muchos casos particulares de este problema han sido estudiados con profundidad en la literatura matemática, pero prácticamente nada sobre este problema. En este trabajo se presenta una formulación del mismo (no se conoce ninguna hasta la fecha), así como un algoritmo de resolución aproximada que modifica y mejora uno anterior propuesto por los autores.