DESCRIPCION DE PUESTO

Conceptos Básicos

1

CAPÍTULO 1.
CONCEPTOS BÁSICOS

El problema de la ruta más corta es uno de los problemas más importantes de
optimización combinatoria con muchas aplicaciones, tanto directas como
subrutinas en otros algoritmos de optimización combinatoria. Los algoritmos
para este tipo de problemas han sido estudiados desde la década de los 50’s y
continúan siendo un área activa deinvestigación. De hecho, ha sido el objetivo
de una investigación extensiva durante muchos años y ha dado como resultado
la publicación de un gran número de documentos científicos.
Encontrar la ruta más corta entre dos nodos de una red, en la cual cada arco
tiene un costo (o longitud) no negativo es un problema que a menudo se
presenta en cierto tipo de actividades. El objetivo es minimizarel costo (tiempo
o longitud) total.
El ejemplo más sencillo para explicar el problema de la ruta más corta es tomar
el viaje de una persona que quisiera ir de la Ciudad de México a la ciudad de
Monterrey, Nuevo León, podría tener varias alternativas dependiendo de sus
intereses, es decir, si deseara llegar más rápido (minimizando el tiempo o la
distancia) o de una forma más económica(minimizando el costo), toda vez que
cada carretera tiene una longitud específica (kms.) y un precio por el derecho
de transitar en ella (costo). Entonces, el problema consiste en encontrar la ruta
más eficiente (la ruta mínima) con base en la longitud o el costo. Este problema
se representa por una red, donde las ciudades son identificadas por nodos y las
carreteras por arcos.

Conceptos Básicos2

Monterrey
Saltillo
Linares

San Roberto
Matehuala

Cd. Victoria

San Luis Potosí

Río Verde
Jalpan

Querétaro
San Juan del Río

Tampico
Tuxpan
Poza Rica

Pachuca
Cd. de México

Figura 1.1. Ejemplo

1.1.

IMPORTANCIA DEL PROBLEMA

El problema de la Ruta más Corta es fundamental en muchas áreas, como son:
investigación de operaciones, ciencia de la computacióne ingeniería. Algunas
de las razones son:
i. La amplia variedad de aplicaciones prácticas como es el envío de algún
material entre dos puntos específicos de la forma más eficiente,
económica o rápida.
ii. Existen métodos de solución eficientes, los cuales al ser aplicados a una
red con características específicas (acíclica y con costos no negativos),
proveen una solución exacta a un tiempoy costo razonables.
iii. Se puede utilizar como inicio en el estudio de modelos complejos de
redes, esto es, cuando no se conoce la estructura de la red se pueden
aplicar algoritmos para conocer algunas características de la red
(presencia de ciclos negativos).

Conceptos Básicos

3

iv. Se utiliza frecuentemente como subproblemas (subrutinas) en la solución
de problemas combinatoriosy redes, así en el caso de problemas para
los cuales no existe un algoritmo de solución exacto (p. e. problemas NPcompletos), la aplicación de algoritmos de ruta más corta, resultan
auxiliares para encontrar una buena solución.

1.2.

APLICACIONES

El problema de ruta más corta tiene muchas aplicaciones prácticas, algunas
son: encontrar la ruta más corta o más rápida entre dos puntos enun mapa,
redes eléctricas, telecomunicaciones, transporte, planeación de tráfico urbano,
trasbordo, diseño

de rutas de vehículos, planeación de inventarios,

administración de proyectos, planeación de producción, horarios de operadores
telefónicos, diseño de movimiento en robótica, redes de colaboración entre
científicos, reemplazo de equipo, etc.
Además, como se mencionó anteriormentelos algoritmos de solución pueden
adaptarse en la búsqueda inicial de una solución aproximada de problemas
complejos, esto significa que la aplicación consiste precisamente en proveer
estructura para varios problemas de optimización combinatoria como: el
problema de la mochila, secuencia de alineación en biología molecular
(secuenciación del ADN), el problema del agente viajero, etc.

1.3....