Un procedimiento optimal para resolver el median shortest path problem
Páginas: 118 (29405 palabras)
Publicado: 14 de marzo de 2011
UNIVERSIDAD DEL BÍO-BÍO FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL
PROFESOR GUÍA: SR. CARLOS OBREQUE NIÑEZ
UN PROCEDIMIENTO OPTIMAL PARA RESOLVER EL MEDIAN SHORTEST PATH PROBLEM
TRABAJO DE TITULACIÓN PRESENTADO EN CONFORMIDAD A LOS REQUISITOS PARA OBTENER EL TÍTULO DE INGENIERO CIVIL INDUSTRIAL
Concepción, 10 de Abril de 2008
GERMÁN ENRIQUE PAREDES BELMAR DEDICATORIA Dedico este trabajo a mis padres, Enrique y Elvira, que con su esfuerzo, su incondicional apoyo y amor, hicieron posible el cumplimiento de esta meta; a mi abuelo Luis (Q.E.P.D.) que siempre me apoyó y aconsejó; y a Dios, que siempre me guía y acompaña en este hermoso camino.
AGRADECIMIENTOS Quiero darle las gracias al Profesor Carlos Obreque, por su confianza, entrega,paciencia y sus valiosos consejos que me entregó durante todo el desarrollo del presente Proyecto de Título.
También agradezco a todas las personas (amigos, familiares, compañeros, profesores) que me entregaron ánimo y apoyo durante la realización de este trabajo, y a lo largo de todos estos años de estudio.
RESUMEN
Sea G = (N, A) un grafo conexo, donde N es el conjunto de nodos y A elconjunto de arcos. Se consideran conocidos dos nodos de N: el nodo origen y nodo destino. Cada arco de A tiene un costo de construcción y se conoce la distancia más corta entre cada par de nodos de la red. El Median Shortest Path Problem (MSPP) consiste en localizar un path (camino) entre el nodo origen y el nodo destino, llamado path principal, de tal manera que todos los otros nodos de la red,que no están sobre este path, sean asignados a partir del nodo más cercano que se encuentre sobre el mismo path principal.
El MSPP es un problema multiobjetivo con trade-off entre el costo total del path principal y la accesibilidad a este path. El objetivo del costo consiste en la suma de todos los costos (o longitudes) de los arcos que conforman el path principal, entre el nodo origen yel nodo destino, y el objetivo de accesibilidad es medido en términos del tiempo (o distancia) hacia el path principal, definida como la suma de todas las distancias desde el path principal a todos los nodos que no pertenecen a este path. Estos dos objetivos están en conflicto porque mientras más grande es el costo del path principal más pequeño es el tiempo de viaje desde el path a losdemás nodos de la red y viceversa.
En este trabajo se propone un procedimiento para detectar arcos que no forman parte de ninguna solución no inferior. Se propone un modelo de programación lineal entera binaria para determinar soluciones no inferiores del MSPP en forma óptima. Además, se resolvió el MSPP con una formulación basada en flujo multicommodity, con el objetivo de comparar resultados.Se presenta una red de 30 nodos y 108 arcos dirigidos para mostrar el procedimiento que se propone en este trabajo. Se exponen también los resultados de las experiencias computacionales realizadas.
Índice de Contenidos Capítulo 1: GENERALIDADES.................................................................................... 1 1.1 Introducción....................................................................................................... 1 1.2 Origen del Tema. ............................................................................................... 1 1.3 Justificación del Tema. ...................................................................................... 1 1.4Objetivos............................................................................................................ 4 1.4.1 Objetivo General ......................................................................................... 4 1.4.2 Objetivos Específicos .................................................................................. 4 1.5 Alcances y Ámbito de Estudio. .......................................................................... 4 1.6 Metodología...
PROFESOR GUÍA: SR. CARLOS OBREQUE NIÑEZ
UN PROCEDIMIENTO OPTIMAL PARA RESOLVER EL MEDIAN SHORTEST PATH PROBLEM
TRABAJO DE TITULACIÓN PRESENTADO EN CONFORMIDAD A LOS REQUISITOS PARA OBTENER EL TÍTULO DE INGENIERO CIVIL INDUSTRIAL
Concepción, 10 de Abril de 2008
GERMÁN ENRIQUE PAREDES BELMAR DEDICATORIA Dedico este trabajo a mis padres, Enrique y Elvira, que con su esfuerzo, su incondicional apoyo y amor, hicieron posible el cumplimiento de esta meta; a mi abuelo Luis (Q.E.P.D.) que siempre me apoyó y aconsejó; y a Dios, que siempre me guía y acompaña en este hermoso camino.
AGRADECIMIENTOS Quiero darle las gracias al Profesor Carlos Obreque, por su confianza, entrega,paciencia y sus valiosos consejos que me entregó durante todo el desarrollo del presente Proyecto de Título.
También agradezco a todas las personas (amigos, familiares, compañeros, profesores) que me entregaron ánimo y apoyo durante la realización de este trabajo, y a lo largo de todos estos años de estudio.
RESUMEN
Sea G = (N, A) un grafo conexo, donde N es el conjunto de nodos y A elconjunto de arcos. Se consideran conocidos dos nodos de N: el nodo origen y nodo destino. Cada arco de A tiene un costo de construcción y se conoce la distancia más corta entre cada par de nodos de la red. El Median Shortest Path Problem (MSPP) consiste en localizar un path (camino) entre el nodo origen y el nodo destino, llamado path principal, de tal manera que todos los otros nodos de la red,que no están sobre este path, sean asignados a partir del nodo más cercano que se encuentre sobre el mismo path principal.
El MSPP es un problema multiobjetivo con trade-off entre el costo total del path principal y la accesibilidad a este path. El objetivo del costo consiste en la suma de todos los costos (o longitudes) de los arcos que conforman el path principal, entre el nodo origen yel nodo destino, y el objetivo de accesibilidad es medido en términos del tiempo (o distancia) hacia el path principal, definida como la suma de todas las distancias desde el path principal a todos los nodos que no pertenecen a este path. Estos dos objetivos están en conflicto porque mientras más grande es el costo del path principal más pequeño es el tiempo de viaje desde el path a losdemás nodos de la red y viceversa.
En este trabajo se propone un procedimiento para detectar arcos que no forman parte de ninguna solución no inferior. Se propone un modelo de programación lineal entera binaria para determinar soluciones no inferiores del MSPP en forma óptima. Además, se resolvió el MSPP con una formulación basada en flujo multicommodity, con el objetivo de comparar resultados.Se presenta una red de 30 nodos y 108 arcos dirigidos para mostrar el procedimiento que se propone en este trabajo. Se exponen también los resultados de las experiencias computacionales realizadas.
Índice de Contenidos Capítulo 1: GENERALIDADES.................................................................................... 1 1.1 Introducción....................................................................................................... 1 1.2 Origen del Tema. ............................................................................................... 1 1.3 Justificación del Tema. ...................................................................................... 1 1.4Objetivos............................................................................................................ 4 1.4.1 Objetivo General ......................................................................................... 4 1.4.2 Objetivos Específicos .................................................................................. 4 1.5 Alcances y Ámbito de Estudio. .......................................................................... 4 1.6 Metodología...
Leer documento completo
Regístrate para leer el documento completo.