An efficient transformation of General Problem of Routes with Capacity on Mixed Graphs

Abstract

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..