摘要：El Problema General de Rutas con Capacidades sobre Grafos Mixtos (PCRC-m) consiste básicamente en encontrar un conjunto de rutas en un grafo mixto, comenzando y acabando en el mismo vértice (depósito), con coste total mínimo, satisfaciendo demandas localizadas en enlaces y vértices y con restricciones de capacidad en las demandas satisfechas por cada ruta. Este problema generaliza muchos problemas de rutas que han sido extensamente estudiados en la literatura de Investigación Operativa debido a sus importantes aplicaciones en problemas reales. Sin embargo, este problema general ha sido poco estudiado y sólo de cara a encontrar soluciones heurísticas. Con el objetivo de resolver tanto óptima como heurísticamente el PGRC-m, presentamos en este artículo una transformación polinomial del PGRC-m, en el Problema de Rutas de Vehículos con Capacidades sobre Grafos Dirigidos para el que existen implementados tanto algoritmos exactos como heurísticos.
其他摘要：The Capacitated General Routing Problem on Mixed Graphs (CGRP-m) consists basically of finding a set of routes on a mixed graph, beginning and ending at the same vertex (depot), with minimum total cost, satisfying demands located at links and vertices and with a capacity restriction on the demand satisfied by each route. This problem generalizes many routing problems that have been largely studied in the operational research literature due to their important applications in real-world problems. However, this general problem has been hardly studied and only in order to find heuristic solutions.We present in this paper a polynomial transformation of the CGRP-m into the Capacitated Vehicle Routing Problem on Directed Graphs, that allows us to solve it both optimally and heuristically with existing algorithms for this last problem..
关键词：Problemas de rutas con capacidades;Grafos Mixtos;Resolución Exacta;Capacitated routing problems;Mixed graphs;Exact resolution
