| El
Problema de Enrutamiento en Grafos |
El estudio matemático de diversos tipos
de problemas de rutas ha sido abordado desde el siglo XVIII. Tradicionalmente,
este tipo de problemas ha sido planteado en términos de problemas
en grafos en los que se desea identificar algún tipo de recorrido
que satisfaga ciertas condiciones.
El problema básico de enrutamiento es
facil de formular: construir un conjunto de rutas factibles de menor
costo que permita, a un vendedor o vehículo, flota de vendedores
o vehículos, servir a un conjunto de nodos y o arcos.
En los problemas básicos no hay restricciones
sobre cuando o el orden en la cual estas entidades deben ser servidas.
Estos problemas pueden clasificarse en dos grandes
familias según se establezcan las condiciones sobre los nodos
o arcos. En el primer tipo de problemas son todos aquellos en los
que los vehículos deben prestar servicio sobre los nodos
del grafo, como por ejemplo la recolección y reparto de mercancias
o bienes de servicio. En el segundo tipo de problemas los vehículos
deben prestar servicio sobre los arcos del grafo, como en el caso
de limpieza de carreteras, diseño de una red de tendido eléctrico,
telefónico, etc.
Una primera clasificación podría
ser la mostrada en el siguiente árbol:
|
