The capacitated general routing problem on mixed graphs

The Capacitated General Routing Problem (CGRP) on mixed graphs is one of the more complex combinatorial optimization problems on vehicle routing. It 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. Several particular cases of this problem have deeply been studied in the operational research literature but, in order to solve the general problem, we only have found a heuristic procedure based on route-first-partition-next. We present here a new heuristic that seems to work much better according to our computational results.