THE CAPACITATED GENERAL ROUTING PROBLEM ON MIXED GRAPHS.

Resumen

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

Key words: Capacitated vehicle routing, mixed graphs, heuristic.

RESUMEN
El Problema General de Rutas con Capacidades (CGRP) sobre grafos mixtos es uno de los más complejos problemas de optimización combinatoria sobre rutas de vehículos. Básicamente consiste en
buscar un conjunto de rutas sobre un grafo mixto, que empiezan y terminan en el mismo vértice (depósito), con coste total 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. Varios casos particulares de este problema han sido estudiados con profundidad en investigación operativa pero, de cara a resolver el problema general, sólo hemos encontrado un algoritmo heurístico basado en ruta-primero-particióndespués. Presentamos aquí un nuevo heurístico que funciona bastante bien de acuerdo con nuestros resultados computacionales.

Palabras clave: Rutas de vehículos con capacidades, grafos mixtos, heurístico.