Árboles y Heurísticas en Localización
Árboles y Heurísticas en Localización
Árboles y Heurísticas en Localización
RBOLES Y HEURSTICAS EN
LOCALIZACION.
EL MODELO CENTDIAN MLTIPLE.
1 LOCALIZACIO N EN ARBOLES.
1
1.1 Introduccion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Los arboles en localizacion. . . . . . . . . . . . . . . . . . . 2
1.1.2 Conceptos basicos. . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Convexidad en arboles. . . . . . . . . . . . . . . . . . . . . 4
1.2 Los problemas clasicos en Localizacion. . . . . . . . . . . . . . . . 5
1.2.1 Localizacion en la Recta Real. . . . . . . . . . . . . . . . . 7
1.2.2 CASO HOMOGE NEO. . . . . . . . . . . . . . . . . . . . . 7
1.2.3 CASO NO HOMOGE NEO. . . . . . . . . . . . . . . . . . 10
1.2.4 Localizacion en un A rbol. . . . . . . . . . . . . . . . . . . 13
1.2.5 CASO HOMOGE NEO. . . . . . . . . . . . . . . . . . . . . 13
1.2.6 CASO NO HOMOGE NEO. . . . . . . . . . . . . . . . . . 15
1.3 Modelos Multiobjetivo (Centdian). . . . . . . . . . . . . . . . . . 18
1.3.1 El Centdian. . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.2 Modelos Multiobjetivo en arboles. . . . . . . . . . . . . . . 19
1.4 Modelos de Programacion Matematica. . . . . . . . . . . . . . . . 20
1.5 Modelos con distancias restringidas. . . . . . . . . . . . . . . . . . 22
1.6 Conclusiones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
i
ii CONTENIDO
2 HEURISTICAS Y A RBOLES. 25
2.1 Introduccion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Formulacion y Notacion. . . . . . . . . . . . . . . . . . . . 26
2.1.2 Metodos de solucion. . . . . . . . . . . . . . . . . . . . . . 27
2.2 Heursticas basadas en arboles . . . . . . . . . . . . . . . . . . . . 32
2.3 Estrategias de Busqueda. . . . . . . . . . . . . . . . . . . . . . . . 37
2.3.1 Busquedas al azar. . . . . . . . . . . . . . . . . . . . . . . 38
2.3.2 Busquedas Monotonas. . . . . . . . . . . . . . . . . . . . . 38
2.3.3 Busquedas No Monotonas. . . . . . . . . . . . . . . . . . . 41
2.3.4 El arbol inicial. . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3.5 Heursticas del p-bosque. . . . . . . . . . . . . . . . . . . . 45
2.3.6 Experiencia computacional. . . . . . . . . . . . . . . . . . 47
2.4 La heurstica VNDS. . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.4.1 Introduccion. . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.4.2 La operacion del Intercambio. . . . . . . . . . . . . . . . . 53
2.4.3 La Heurstica VNS para la p-Mediana. . . . . . . . . . . . 58
2.4.4 El Algoritmo VNDS . . . . . . . . . . . . . . . . . . . . . 60
2.4.5 Experiencia computacional. . . . . . . . . . . . . . . . . . 63
2.4.6 Conclusiones. . . . . . . . . . . . . . . . . . . . . . . . . . 67
PRO LOGO.
Los problemas de localizacion han sido objeto de estudio durante siglos, pero
no fue hasta la emergencia de la Investigacion Operativa cuando estos problemas
tomaron mayor interes, siendo actualmente muchas las disciplinas en las que
se estudian estos tipos de problemas. Arquitectos, informaticos, economistas,
ingenieros, matematicos y geografos han descubierto que tienen un interes comun,
en lo que concierne a la teora de la localizacion.
En un problema de localizacion, dado un conjunto de puntos de demanda y un
conjunto de posibles localizaciones, se desea hallar la ubicacion de varios servicios
de forma que, al asignar los puntos de demanda a los servicios, se optimice alguna
funcion de distancia, costo o tiempo del trayecto. Esta funcion suele denominarse
funcion objetivo, y entre las mas estudiadas cabe destacar las funciones Centro
y Mediana.
El problema de la Mediana consiste en minimizar la distancia media entre
el usuario y el servicio a localizar. Este tipo de funcion objetivo mini-sum es
apropiado para localizar servicios que deben satisfacer una demanda continua y
estable, como, por ejemplo, escuelas, centros comerciales, terminales de trans-
porte, etc. Por otro lado, el problema del Centro estriba en localizar un punto
de tal manera que la distancia del usuario mas alejado a el sea mnima. Esta
funcion objetivo mini-max es utilizada con frecuencia en servicios de emergencias
tales como estaciones de ambulancias, de bomberos o de policia.
En muchos problemas reales el objetivo es una mezcla de estos dos mode-
los, muchas veces antagonicos. Por ejemplo, a la hora de ubicar un puesto de
bomberos se puede pretender minimizar el tiempo de viaje al posible punto de
demanda mas alejado, siempre y cuando el puesto este sucientemente cerca de
las areas mas pobladas. El problema consiste en minimizar la funcion Centro con
la restriccion de que la funcion Mediana no supere un determinado nivel. Otro
ejemplo es el de minimizar la distancia media que deben recorrer los ni~nos para
llegar a la escuela sin que a ninguno le quede demasiado lejos. El objetivo aqu es
minimizar la funcion Mediana imponiendo una cota superior a la funcion Centro.
Normalmente, cada usuario lleva asignado un valor positivo, llamado peso
o ponderacion, que a menudo representa el numero de veces que dicho usuario
visita el servicio.
El modelo que sugirio Halpern (1976) consiste en minimizar una combinacion
vi CONTENIDO
convexa de la distancia media ponderada y la distancia maxima no ponderada;
la solucion a este problema recibe el nombre de Centdian. Con ello se consigue
un equilibrio entre la distancia media y la distancia mayor.
El presente trabajo se ha realizado en el marco de la localizacion en grafos,
haciendo hincapie en una clase especial de grafo llamada arbol, y en el modelo
Centdian. Este grafo debe su nombre a la posibilidad de poder ser dibujado
imitando a un arbol genealogico, donde los vertices representan a los miembros
de la familia y las aristas la relacion entre padres e hijos. Los arboles genealogicos
al igual que los grafos arboles no tienen ciclos, pues un ciclo signicara ser padre
e hijo de s mismo. Como ejemplos de arboles tenemos, entre otros, algunas
carreteras y autopistas, la mayora de las vas ferroviarias y casi todos los ros.
Con el objetivo de re
ejar el estado actual de los problemas de localizacion en
arboles, el captulo 1 se dedica al repaso de los modelos clasicos tanto en el arbol
como en su representacion mas simple, la recta real, o lo que es lo mismo, un
arbol en el que cada padre solo puede tener un hijo. Ademas, se recuerdan otros
problemas que tambien tienen gran relevancia en el ambito de la localizacion en
arboles y a los que se hace referencia a lo largo del presente trabajo.
Muchos problemas de localizacion, como los problemas mencionados en su
version multiple del Centro y la Mediana, son NP-Hard, y no se espera que sean
resueltos de forma exacta por ningun algoritmo que tenga complejidad polinomial.
Estos problemas pueden ser analizados desde el punto de vista de la optimizacion
combinatoria llegando a resolverse con tecnicas de enumeracion, sin embargo, es-
tas tecnicas no son practicas en problemas de dimensiones reales, pues no generan
una solucion optima en un tiempo razonable. Es en estos casos en los que deben
utilizarse los metodos heursticos, con el n de encontrar soluciones satisfactorias
que puedan estar en el camino de la solucion optima del problema en cuestion.
Cuando el grafo no es arbol, se puede considerar aproximaciones a este. Una
de tales aproximaciones es el llamado arbol generador o de expansion, el cual es un
subgrafo que contiene todos los vertices del grafo original, pero con solo algunas de
sus aristas. Estas aproximaciones nos permiten utilizar algoritmos para resolver
problemas de localizacion en arboles, cuyas soluciones lo son aproximadamente
del mismo problema en el grafo original.
En esta lnea, se proponen en el captulo 2 varias estrategias heursticas para
resolver problemas de localizacion en grafos, haciendo uso de los algoritmos cons-
truidos para arboles, obteniendose en muy poco tiempo soluciones proximas a la
optima. El codigo de las mismas se halla en el apendice A. Tambien hay que re-
saltar en este captulo, los resultados de la heurstica VNDS, que ha sido dise~nada
para resolver problemas de optimizacion combinatoria en grafos de dimensiones
considerables. Esta ha sido probada con grafos del orden de 6000 vertices, mejo-
CONTENIDO vii
rando apreciablemente los resultados obtenidos con otras heursticas. El codigo
de VNDS se muestra en el apendice B.
En el captulo 3 se estudia la funcion Centdian en un grafo considerando
la funcion Centro ponderada, generalizando as el modelo de Halpern. Se en-
tiende que las ponderaciones de la funcion Centro no tienen que ser iguales a
las ponderaciones de la funcion Mediana. Por simplicidad este nuevo problema
se sigue denotando Centdian. Este captulo comienza analizando el caso de lo-
calizar un solo servicio, extendiendo todas las propiedades del modelo propuesto
por Halpern, para el nuevo modelo que aqu se presenta. A continuacion, se estu-
dia el problema del 2--Centdian, mediante un analisis de la funcion objetivo, y se
propone un algoritmo de complejidad O(m2n4); donde m y n son respectivamente
el numero de aristas y vertices del grafo considerado.
Exceptuando un apartado del artculo de Hooker y otros (1991), en el cual
se propone un conjunto nito dominante para el p--Centdian, no se conoce
literatura que haga mencion al -Centdian multiple. Este conjunto nito domi-
nante propuesto por Hooker, es erroneo, como se muestra en el contraejemplo que
aparece en este captulo 3. Tambien, se presenta un nuevo conjunto nito domi-
nante para el problema p--Centdian en un grafo con una demostracion detallada
del mismo. Finalmente, como consecuencia de este, se propone un algoritmo e-
xacto.
En el cuarto y ultimo captulo, se estudia el problema p--Centdian en un
arbol, y se propone el primer algoritmo polinomial para el problema p--Centdian
(generalizado o no) en arboles. En el caso generalizado, es decir, cuando la funcion
Centro se considera con pesos, la complejidad de este algoritmo es de O(pn6 ), para
p 6, y O(np), si p < 6. En el caso no generalizado, es decir, cuando la funcion
Centro es sin pesos, la complejidad disminuye a O(pn5 ); para p 5, y O(np ), si
p < 5:
Tambien se considera la version discreta del modelo, donde los p puntos deben
seleccionarse entre los vertices. En este caso, la complejidad se reduce a O(pn4),
para p 4, y O(np ), si p < 4. El captulo termina con el estudio de la funcion
Centdian en la recta real.
Con el objetivo de que el lector pueda seguir cualquier captulo sin necesidad
de leer los previos, se han redactado de forma independiente conservando a su
vez la coherencia del trabajo en su conjunto. Esto implica que en algunos casos
se repitan conceptos ya expuestos anteriormente.
Captulo 1
LOCALIZACIO N EN
A RBOLES.
1.1 Introduccion.
Si en la literatura de investigacion operativa se realizara una busqueda con los
localizadores arboles y localizacion, obtendramos una vision de la relevancia
que han tenido y tienen los problemas de localizacion en el ambito de los arboles.
Entre los modelos de localizacion mas tratados aparecen:
Los clasicos problemas del p-Centro y de la p-Mediana, as como los re-
lativamente recientes problemas del p-Anticentro y de la p-Antimediana,
tratados tanto en el arbol como en su representacion mas sencilla, la recta
real.
Los modelos multiobjetivos, apropiados para optimizar simultaneamente
mas de una funcion objetivo.
Los modelos de Programacion Matematica, donde formulaciones alternati-
vas permiten estudiar los tpicos problemas de localizacion como problemas
de Programacion Matematica.
Los modelos con distancias restringidas, aplicables a problemas en los que
existe algun tipo de acotamiento entre la distancia desde el usuario al ser-
vicio.
Con el objetivo de re
ejar el estado actual de la localizacion en arboles, en
este captulo se analizan cada uno de estos modelos, resaltando las aportaciones
mas signicativas de cada uno de ellos acaecidas en la literatura.
1
2 EN ARBOLES.
Captulo 1. LOCALIZACION
vi 2U
vi 2U
pues los pesos wi = 1; para todo vi 2 U:
Contrariamente a lo que ocurre en los problemas de tipo minimizar fc, donde
el modelo sin pesos tiene menor complejidad que el mismo modelo con pesos,
en los problemas minimizar fm el hecho de tener o no peso asignado a cada
vertice, no hace variar la complejidad de sus respectivos algoritmos. Por ello, los
algoritmos empleados son los que se citaron para el problema de la p-Mediana
pesada. El de Blum y otros (1972) [9] para p = 1, y el de Hassin y Tamir (1991)
[80] para un p cualquiera.
El problema de la p-Antimediana.
En este problema tambien conocido como problema p-Maxisum, se pretende
maximizar la siguiente funcion objetivo:
fam(U; X ) = wi d(vi; X ):
X
vi 2U
donde wi; es el peso positivo asociados a vi 2 U . Dado que la funcion objetivo es
convexa [159] la 1-Antimediana es v1 o vn:
Si los elementos de X pueden ser iguales, la solucion de la p-Antimediana es
la misma que la del problema de la 1-Antimediana. Si los elementos de X son
distintos, la solucion optima no tiene por que estar necesariamente ubicada en los
vertices terminales. Por ejemplo, si n = 4; vi = i , 1; i = 1; 2; 3; 4; w1 = w3 = 1;
w2 = 5; w4 = 3; y p = 2; el conjunto optimo es S = fv1;v3g:
El mejor algoritmo que se conoce es el dado por Tamir (1991) [159], que
por medio de un desarrollo en programacion dinamica alcanza una complejidad
O(n p):
vi 2U xj 2X xi 2X xj 2X
donde wij es el peso asociado a vi con respecto el servicio xj y bij es el peso entre
los servicios xi y xj .
Tamir (1993) [161], propone un algoritmo alternativo con la misma compleji-
dad que el algoritmo de Guseld y Martel (1992).
El problema de la p-Antimediana.
En el problema de la p-Antimediana el objetivo es maximizar:
fam(U; X ) = wij d(vi; xj )+ bij d(xi; xj );
X X X X
vi 2U xj 2X xi 2X xj 2X
1.2. Los problemas clasicos en Localizacion. 13
donde wij es el peso asociado a vi con respecto el servicio xj y bij es el peso entre
los servicios xi y xj . O lo que es lo mismo, maximizar la suma de las distancia
pesada entre todos lo pares de puntos. El problema de la p-Antimediana es
NP-Hard, incluso, cuando n = 2, Tamir (1991) [159].
El problema de la p-Antimediana.
Este problema tambien es conocido en la literatura como el problema p-
Maxisum, y consiste en maximizar la funcion objetivo:
fam(U; X ) = wi d(vi; X ):
X
vi 2U
donde wi es el peso positivo asignado al vertice vi 2 U: En un grafo general es
NP-Hard, pero en un arbol Tamir [159], soluciono el problema en tiempo O(n p)
valiendose de la programacion dinamica. Su procedimiento trata de identicar
las utiles propiedades de concavidad, y reformular el modelo como un problema
de
ujo, cuadratico separable y de maxima concavidad.
componente conexa con mas de n=2 vertices. Coincide con el vertice mediana.
16 EN ARBOLES.
Captulo 1. LOCALIZACION
vi 2U xj 2X xi 2X xj 2X
donde wij es el peso asociado a vi con respecto el servicio xj y bij es el peso entre
los servicios xi y xj respectivamente, mejora la complejidad O(n p3 ) de Kolen
(1982) [97] y de Picar y otros (1978) [135]. Para ello, considera una arista [vi; vj ]
1.2. Los problemas clasicos en Localizacion. 17
y la elimina de E; particionando el conjunto de vertices en dos subconjuntos,
V (i; j ) y V (j; i), donde vi 2 V (i; j ) y vj 2 V (j; i): Siguiendo a Picard (1978)
[135] dene el problema local-[i; j ] como:
x f
min wtm d(vi; xm)+ wtm d(vj ; xm)+ bkm d(xk ; xm)g;
P P P
donde x1; :::; xp estan en fvi; vj g: Este problema es la reduccion del problema
original obtenido identicando todos los vertices de V (i; j ) con el vertice vi; y
todos los vertices de V (j; i) con el vertice vj .
Dado que la solucion del problema local-[i; j ] es independiente de la longitud
de la arista [vi; vj ] se concluye, como se muestra en [135], que el problema de la
p-Mediana pesada no homogenea en un arbol es independiente de la longitud de
las aristas, y que solo depende de la topologa del arbol. Este resultado justica el
que Tamir (1993) [161], haya utilizado el metodo de descomposicion del centroide
para resolver el mencionado problema en tiempo O((p3 + n) log n + np):
El hecho de tener peso o no, no afecta a la complejidad de los algoritmos que re-
suelven el problema de la p-Mediana. Ello nos lleva a citar los mismos algoritmos
que en el problema de la p-Mediana pesada.
El problema de la p-Antimediana.
El problema de la p-Antimediana consiste en maximizar la funcion objetivo:
fam(V; X ) = wij d(vi; xj )+ bij d(xi; xj );
X X X X
vi 2U xj 2X xi 2X xj 2X
1.3.1 El Centdian.
El Centdian, es el nombre que Halpern [65] utiliza para el problema de lo-
calizar un servicio bajo dos objetivos: el minimax fc(U; X ) =max
vi 2U
f d(vi ; X )g y el
minisum fm (U; X ) = P
wi d(vi; X ). Los primeros en considerar este problema
vi 2U
en un arbol fueron Halpern [65] y Handler[69].
Halpern desarrollo el problema minimizando:
En un arbol, fm y fc son funciones biyectivas (uno a uno) en los interva-
los [m+; m++]; [c+; c++ ] respectivamente, y son inversas una de la otra. En un
grafo general, la propiedad de la inversa se verica solo para algunos miembros
de [m+; m++ ]; [c+; c++ ] pues en este caso las funciones no son necesariamente
biyectivas.
maxfwij d(vi; xj ) : vi 2 U; xj 2 X g; ;
( )
vi 2U xj 2X xi 2X xj 2X
1.6. Conclusiones. 23
donde wij es el peso asociado a vi con respecto el servicio xj y bij es el peso entre
los servicios xi y xj respectivamente, el problema es comunmente llamado el
problema de la p-Mediana restringida. Por las propiedades de la funcion objetivo
de la p-Mediana, una p-Mediana optima se encuentra en algun conjunto de:
Y = vi[2U Yi(rij ):
j=1::p
donde:
1.6 Conclusiones.
En este captulo se han considerados los problemas clasicos de localizacion en
sus diferentes versiones. Las siguientes tablas recogen las referencias y compleji-
dades de cada uno de ellos, clasicados por su homogeneidad, peso y repulsividad.
El modelo repulsivo es equivalente al modelo Anticentro o Antimediana.
Un campo donde se han aplicado con exito los metodos heursticos son los
problemas en redes. Se consideran redes de interes las de carreteras, la de trans-
porte aereo, las de ros o las de ordenadores. En un problema de localizacion en
red, la red esta representada por un grafo no dirigido, y tanto los nuevos servicios
como los existentes estan usualmente idealizados como puntos. As mismo, los
25
26 Captulo 2. HEURISTICAS Y ARBOLES.
donde los pesos wu y wu0 vienen dados y van asociados a cada vertice usuario
u 2 U . Estos pesos pueden representar la cantidad de demanda que se produce
en cada vertice.
El problema de la p-Mediana.
Los orgenes de este problema se remontan a principios del siglo XVII cuando
Fermat lo propuso de la siguiente forma: dados tres puntos en el plano, encontrar
un cuarto punto tal que minimice la suma de las distancias a los tres puntos dados.
Antes de 1610, Torricelli propuso una solucion geometrica. En el a~no 1750 aparece
el problema de la p-Mediana con pesos. Weber utilizo estos modelos en 1909 para
determinar la localizacion optima de una fabrica que atenda a un solo servicio
y tena dos fuentes de suministro. El problema de la 1-Mediana en el plano es el
denominado el problema de Weber.
Hakimi en 1964 [62] probo que las soluciones al problema de la p-Mediana para
un conjunto de vertices usuario cualquiera puede encontrarse entre los vertices
del grafo. Este resultado permite transformar el problema continuo de la p-
Mediana en un problema discreto donde solo se contempla la localizacion en los
vertices. Por tanto, los principales metodos para resolver el problema de la p-
Mediana operan con la matriz de distancia entre vertices y son los mismos para
los problemas discretos formulados en grafos que en cualquier otro espacio, como
es el caso del problema de la p-Mediana en el plano. El problema de la p-Mediana
es NP-Hard, Kariv y Hakimi (1979) [90]. Los metodos exactos para resolver el
problema de la p-Mediana utilizan principalmente tres tipos de herramientas:
arboles de busqueda, tecnicas de programacion lineal y dualidad.
Algoritmos exactos que usan arboles de busqueda pueden encontrarse en
los trabajos de Jarvinen, Rajala y Sinervo (1972) [87], El-Shaieb (1973) [40] y
Khumawala (1972) [92]. Las herramientas fundamentales utilizadas fueron: pe-
nalizaciones, acotamiento, generacion de soluciones factibles bajo ciertas condi-
ciones, y reglas de ramicacion en una enumeracion implcita. Otras aportaciones
fueron debidas a Christodes y Beasley (1982) [30], y Hanjoul y Peeters (1985)
[73]. Los ejemplos que muestran estos trabajos alcanzan grafos de hasta 400
vertices, excepto Beasley (1985) [7] que utilizando un ordenador vectorial, pudo
trabajar con grafos de hasta 900 vertices. Referencias de trabajos como estos y de
areas relacionadas estan contenidos en Brandeau y Chiu (1989) [12], Mirchandani
y Francis (1990) [124] y Cornuejols, Fisher y Nemhauser (1977) [19].
Entre las primeras contribuciones sobre el uso de tecnicas de programacion
lineal estan las de ReVelle y Swain (1970) [151]. La mas conocida es la relajacion
lineal sobre las variables enteras, con la que generalmente se obtienen soluciones
optimas enteras, o una cota ajustada de las mismas. Debido al gran numero de
variables y restricciones de los problemas reales, el uso del Simplex estandar es
prohibitivo. Para paliar este problema, ReVelle y otros (1976) [152] reducen el
numero de las y columnas del problema original usando un metodo de descom-
posicion que aprovecha la peculiar estructura del problema (Garnkel, Neebe y
2.1. Introduccion. 29
Rao (1974) [53], Swain (1974) [157], Magnanti y Wong (1981) [109], etc.).
En el uso de la dualidad destaca el trabajo de Galvao (1980) [52] quien
aporta una heurstica para el dual del correspondiente problema de Programacion
Lineal; su metodo esta relacionado con el hallazgo de Erlenkotter (1978) [45]
para un problema muy cercano al de la p-Mediana, el problema de localizacion
simple de plantas o problema de Weber. Cornuejols y otros (1977) [19] y Narula,
Ogbu y Samuelson (1977) [132] sugirieron el desarrollo de la dualidad lagrangiana
obtenida al aplicar multiplicadores de Lagrange al conjunto de restricciones. Otra
alternativa de relajar las restricciones se puede ver en Krarup y Pruzan (1983)
[99].
Metodos Heursticos.
Dado que ambos problemas son NP-Hard las heursticas son la mejor alter-
nativa a problemas de dimensiones considerables. Muchas de las heursticas
dise~nadas para cualquiera de estos problemas tienen caractersticas fundamen-
tales que los hacen esencialmente aplicables a cualquier otro problema de lo-
calizacion de p servicios con funcion objetivo monotona en las distancias. Por
ejemplo, aquellas que parten de una particion inicial del conjunto de usuarios
que se va iterativamente transformando. Las heursticas se van a diferenciar en
la forma de manipular la particion para conseguir una secuencia de particiones,
de tal forma que el valor de la funcion objetivo se vaya minimizando.
2.1. Introduccion. 31
El metodo de Adicion o heurstica de Babel (Kuehn y Hamburger (1963)
[100]), empieza localizando un servicio de modo que minimice la funcion objetivo.
A continuacion se van a~nadiendo, uno a uno, los servicios hasta alcanzar los p
deseados. El nuevo servicio se elige de forma que la funcion objetivo en cada paso
disminuya lo mas posible.
La heurstica alternante que combina iterativamente fases de localizacion y
asignacion fue inicialmente propuesta por Maranzana (1964) [110]. En la primera
iteracion, se eligen p puntos de servicio, se le asignan los usuarios mas cercanos
a ellos, y se resuelve el problema de localizacion simple en cada uno de los p
conjuntos que se forman. Entonces el procedimiento es iterado con las nuevas
localizaciones de los servicios, hasta que no ocurran mas cambios en las asigna-
ciones. En la version de arranque multiple de esta heurstica, el procedimiento
se repite un numero determinado de veces partiendo de diferentes conjuntos de p
servicios, manteniendo la que mejor solucion produzca.
La heurstica de eliminacion o sustraccion, tambien denominada metodo
Attila o Stingy, propuesto inicialmente por Feldman, Lehrer y Ray (1966) [46],
supone que inicialmente en todos los puntos de demanda se establece un servicio.
En cada iteracion el servicio que produzca el menor incremento en la funcion
objetivo es eliminado. El proceso se repite hasta que el numero de servicios se
reduce a p.
Teist y Bart (1968) [168], propusieron la llamada heurstica de intercam-
bio, en la que inicialmente se parte de p localizaciones posibles para los servicios.
A continuacion se mueven iterativamente los servicios, uno por uno, reduciendo
lo mas posible el valor de la funcion objetivo. Esta operacion se conoce como
el 1-intercambio, ya que se intercambia un elemento que esta en la solucion por
otro que no lo esta. La heurstica de Montecarlo consiste en generar en
cada iteracion un 1-intercambio y aceptarlo si se produce una mejora. Estas
dos heursticas son comunmente utilizadas como un estandar de referencia en la
comparacion de heursticas y son las utilizadas en la experiencia computacional
descrita al nal de este captulo.
Este tipo de movimiento estandar se ha utilizado en otras heursticas que se
enmarcan dentro de las distintas estrategias metaheursticas, como las busquedas
Tabu, recocido simulado, algoritmos geneticos, metodos de arranque multiple y
la reciente heurstica de entorno variable.
Los metodos heursticos de busqueda Tabu han sido recientemente con-
siderados por Mladenovic, Moreno y Moreno-Vega (1996) [126] para el problema
de la p-Mediana, en los que el movimiento de intercambio ha sido extendido al
llamado movimiento de sustitucion en cadena. Esto permite escapar con mas
facilidad de los mnimos locales. Otro procedimiento Tabu para la p-Mediana es
32 Captulo 2. HEURISTICAS Y ARBOLES.
sugerido por VoB (1996) [172], en el cual se discuten tambien algunas variantes
del metodo de eliminacion inversa.
La busqueda heurstica de arranque multiple ha sido analizada en M.
Moreno (1996) [127]. Estos metodos constan generalmente de dos fases. En la
fase global del procedimiento, se genera una solucion de la region factible. En la
fase local, se aplica una busqueda local desde la solucion encontrada en la fase
global, que acabara en un mnimo local con respecto a la estructura de entorno
considerada. Estos dos pasos se reiteran hasta que se satisfaga algun criterio de
parada. El mnimo local obtenido con menor valor de la funcion objetivo es la
solucion propuesta por el algoritmo. La busqueda con arranque multiple combina
apropiadamente la exploracion del espacio de soluciones con la explotacion en el
entorno de la solucion actual; ah radica en parte su exito. Una de las principales
cuestiones en este tipo de busqueda es cuando parar. Siguiendo los trabajos de
Boender y otros (1987) [10] y Bruno y otros (1987) [13] pueden obtenerse diversas
reglas de parada para la busqueda de arranque multiple.
Las estrategias heursticas del recocido simulado o simulated annealing han
sido aplicadas con exito relativo por Aarts y Laarhoven [3] y Chams, Herts y
Werra [16], y los algoritmos geneticos se han mostrado efectivos al combinarlos
con tecnicas de paralelizacion ver Moreno, Roda y Moreno [131]
La utilizacion de algunas de estas heursticas en problemas de localizacion
puede encontrarse en Perez-Brito (1998) [6]
El procedimiento heurstico mas efectivo ha sido el de la busqueda de en-
torno variable denominado VNS de Mladenovic (1995) [125][77]. Esta heurstica
consiste brevemente en la idea siguiente. Dada la solucion actual, se generan
aleatoriamente un numero especicado de soluciones en el primer entorno denido.
Si se encuentra una solucion mejor en este entorno, se toma esta como la solucion
actual. En otro caso se cambia de entorno aumentando el radio del mismo. El
algoritmo termina si no se ha encontrado ninguna mejora al llegar al ultimo
entorno denido. En la siguiente seccion se ofrecen mas detalles de la misma
incorporando una tecnica de descomposicion que la hace signicativamente mas
eciente para obtener la heurstica denominada VNDS que es la que mejores
resultados computacionales ofrece.
Demostracion:
Sea T (G) el conjunto de todos los subarboles de G. Al considerar el problema
en cada subarbol T 2 T (G) entonces X 2 P (T )p y las distancias estan calculadas
por las longitudes de los caminos mnimos en T denotadas por dT (X; u). Se tiene
que, para cada T 2 T (G) y para cualquier conjunto de localizaciones X 2 P (T )p
es
dG (X; u) dT (X; u); 8u 2 U:
Si por fT (:) se denota la funcion objetivo del problema en T ; es decir:
fT (X ) = g(dT (X; u) : u 2 U ), se sigue que:
fG (X ) fT (X ):
En particular, para la solucion optima X del problema en G se verica:
fG (X ) fT (X ), si X 2 P (T ).
Para cualquier X 2 P (G)p, sea T (X ) el conjunto de todos los subarboles T
que contienen caminos mnimos desde X a todos los puntos de demanda; es decir,
tales que: dG (X; u) = dT (X; u), 8u 2 U . Si se producen empates en las distancias
el conjunto de todos los caminos mnimos desde X no es un arbol, sin embargo se
obtiene un arbol que contiene desde X a todos los vertices usuario si los empates
se resuelve de forma unica aunque arbitraria. Si no hay empates, el unico arbol
de T (X ) es el formado por los caminos mnimos desde X a todos los puntos de
U.
Se tiene que, para cualquier X 2 P (G)p y para cualquier T 2 T (X ) es
fT (X ) = fG(X ). En particular, para la solucion optima X , si T 2 T (X ), se
verica:
fG(X ) = fT (X ):
Luego 8T 2 T (G) y 8X 2 P (T )p se tiene que 8T 2 T (X ):
fT (X ) fT (X ):
Para explorar arboles del entorno pueden usarse cualquier tipo de transfor-
macion que garantice un recorrido eciente del espacio de arboles, en particular
alguna de las dos transformaciones elementales siguientes:
Primera transformacion: Add-Drop
1. Se a~nade una arista del grafo G que no este en el arbol.
2. Se determina el ciclo formado al incorporar esta arista al arbol.
3. Se elimina del arbol una arista de dicho ciclo.
Heurstica AG-Azar.
Paso 0. (Inicializacion):
Sea T0 un arbol inicial de G. Sea k el maximo numero de
iteraciones. Tomar i 0.
Paso 1. (Localizacion):
Sea Xi la localizacion optima de los p servicios en el arbol Ti .
Paso 2. (Transformacion):
Determinar al azar una transformacion elemental Ti+1 del arbol
Ti :
Paso 3. (Terminacion):
Si i k; parar. En otro caso, hacer i i + 1 y volver al paso
1.
Figura 2. Heurstica AG-Azar
Heurstica AG-GP.
Paso 0. (Inicializacion):
Sea T0 un arbol inicial de G, y k el maximo numero de itera-
ciones. Tomar i 0.
Paso 1. (Localizacion):
Sea Xi la localizacion optima de los p servicio en el arbol Ti .
Paso 2. (Transformacion):
Determinar al azar una arista ei que no este en Ti .
Hallar la transformacion optima en Ti; para obtener el arbol
Ti+1 que contenga a ei .
Paso 3. (Terminacion):
Si i k, parar. En otro caso, i i + 1 y volver al paso 1.
Figura 3. Heurstica AG-GP
c) Busqueda Greedy.
La clasica busqueda localmente exhaustiva o heurstica greedy pura se obtiene
seleccionando de manera exhaustiva la mejor transformacion del arbol actual.
Para ello en el paso 2 de la heurstica AG-G (ver gura 4. Heurstica AG-G)
se analizan todas las posibilidades de cambiar una arista del arbol por otra que
no lo sea. La heurstica termina cuando se ha alcanzado el numero maximo de
iteraciones.
Heurstica AG-G.
Paso 0. (Inicializacion):
Sea T0 un arbol inicial de G, y k el maximo numero de itera-
ciones. Tomar j 0.
Paso 1. (Localizacion en un arbol):
Sea Xj la localizacion optima de los p servicio en el arbol Tj .
Paso 2. (Movimiento en el entorno de soluciones):
Determinar la mejor modicacion Tj +1 del arbol Tj .
Paso 3. (Terminacion):
Si j k parar. En en otro caso, j j + 1 y volver al paso 1.
Figura 4. Heurstica AG-G
2.3. Estrategias de Busqueda. 41
2.3.3 Busquedas No Monotonas.
El inconveniente de las busquedas monotonas es que si se aproximan a un
arbol localmente optimo (es decir, un arbol para el que ninguna transformacion
de las contempladas produce una mejora) el procedimiento queda atrapado en
el. Las tres formas principales de escapar de esta situacion consisten en volver
a comenzar la busqueda desde otro arbol inicial, permitir de forma controlada
movimientos que den lugar al empeoramiento del arbol actual, o modicar el
conjunto de transformaciones contempladas.
a) Busquedas de Arranque Multiple.
Los procedimientos de arranque multiple (MultiStart) realizan varias busquedas
monotonas partiendo de diferentes arboles iniciales. Una forma simple de realizar
esto consiste en generar una muestra de arboles de arranque (Rinnooy Kan and
Timmer (1987) [153]), o equivalentemente generar al azar un nuevo arbol de par-
tida cada vez que la busqueda quede estancada. El criterio de parada se convierte
entonces en un criterio para reiniciar la busqueda por lo que hay que incorporar
un nuevo criterio de nalizacion de todo el proceso de busqueda.
Las herramientas para mejorar la generacion totalmente al azar de los arboles
iniciales persiguen que los recorridos de las sucesivas busquedas se distribuyan
lo mas posible en todo el espacio de posibles arboles. Una posibilidad consiste
en seleccionar una muestra representativa de un conjunto mas grande de arboles
iniciales procurando que estos sean lo mas diferentes posible. Tambien se puede
tener en cuenta por que parte del espacio de busqueda han transcurrido los reco-
rridos ya realizados para no insistir en zonas exploradas.
b) Busquedas por Recorrido no monotonos.
Otra de las tecnicas para evitar quedarse atrapados en un arbol optimo lo-
cal, es la de admitir la posibilidad de dar pasos hacia atras. Sin embargo, hay
que controlar de alguna forma estas transformaciones para que, al menos a la
larga, se vayan mejorando los arboles. Esto se realiza principalmente por medio
de dos herramientas: la primera, asignando distintas probabilidades a las trans-
formaciones elementales en funcion de la mejora que produzcan, y la segunda,
utilizando la memoria historica del recorrido para evitar la reincidencia en los
mismos arboles.
La Busqueda Probabilstica se obtiene utilizando una probabilidad no nula
de aceptar el nuevo arbol aun cuando este no mejore al actual. Esta probabil-
idad suele determinarse teniendo en cuenta el valor de la funcion objetivo en
ambos arboles. Los parametros de esta funcion de aceptacion se pueden estable-
cer estaticamente o modicarse dinamicamente para regular la diversicacion e
42 Captulo 2. HEURISTICAS Y ARBOLES.
a) A rbol mnimo.
Algoritmo de Prim
Paso 1. Elegir v1 2 V cualquiera.
Poner Nivel[v ] := 1, 8v 2 V .
VT = fv1 g, ET := ;.
Nivel[v1] := 0, i := 1.
Paso 2. Para cada v 2= VT :
Si [vi; v ] 2 E entonces:
Si Long [vi; v ] < Nivel[v ] entonces:
Enlace[v ] := vi, Nivel[v ] := Long [vi; v].
Paso 3. Hacer i := i + 1.
Sea NivelMin := 1.
Para cada v 2= VT .
Si Nivel[v ] < NivelMin entonces:
vi := v.
NivelMin := Nivel[v].
Paso 4. Hacer VT := VT [ fvig y ET = ET [ f[Enlace[vi]; vi]g.
Si VT 6= V entonces volver al paso 2.
Figura 5. Algoritmo de Prim
b) arbol aleatorio.
Una generacion al azar del arbol de partida se realiza con una adaptacion
del algoritmo de Prim. La modicacion consiste en que el vertice usuario
que se conecta al arbol en cada iteracion se selecciona al azar (ver gura 6.
Algoritmo de Prim-Rand). Sin embargo, se sigue utilizando la forma mas
corta de conectar cada vertice incorporado.
Algoritmo de Prim-Rand
Paso 1. Elegir v1 2 V cualquiera.
Poner Nivel[v ] := 1, 8v 2 V .
VT = fv1 g, ET := ;.
Nivel[v1] := 0, i := 1.
Paso 2. Para cada v 2= VT :
Si [vi; v ] 2 E entonces:
Si Long [vi; v ] < Nivel[v ] entonces:
Enlace[v ] := vi , Nivel[v ] := Long [vi; v]
Paso 3. Hacer i := i + 1.
Sea v 2= VT con Nivel[v ] < 1 elegido al azar
vi := v
Paso 4. Hacer VT := VT [ fvig y ET = ET [ f[Enlace[vi]; vi]g.
Si VT 6= V volver al paso 2.
Figura 6. Algoritmo de Prim-Rand
2.3. Estrategias de Busqueda. 45
c) arbol parametrico.
Con objeto de conseguir un arbol generador al azar que no sea precisamente
el de longitud mnima, pero cuya diferencia de este pueda ser controlada, se
introducen dos parametros y en el algoritmo de Prim. Los parametros
y nos permiten controlar respectivamente, las probabilidades de que se
incorpore al arbol el vertice usuario de menor nivel y de que se enlace al
arbol con el camino de menor longitud (ver gura 7. Algoritmo de Prim;).
El parametro ja la probabilidad con la que se modica el enlace de
un vertice si el enlace al vertice que se conecta mejora el existente. El
parametro establece la probabilidad de que se seleccione el vertice con
mejor enlace. Ver Perez-Brito y otros (1994) [140]
Algoritmo de Prim;
Paso 1. Elegir v1 2 V cualquiera.
Poner Nivel[v ] := 1, 8v 2 V .
VT = fv1 g, ET := ;.
Nivel[v1] := 0, i := 1.
Paso 2. Para cada v 2= VT :
Si [vi; v ] 2 E entonces:
Si Long [vi; v ] < Nivel[v ] entonces:
Si (Random < ) o (Nivel[v ] = 1) entonces:
Enlace[v ] := vi , Nivel[v] := Long[vi; v]
Paso 3. Hacer i := i + 1.
Sea NivelMin := 1
Para cada v 2= VT
Si Nivel[v ] < NivelMin entonces:
Si (Random < ) o (NivelMin = 1) entonces:
vi := v , NivelMin := Nivel[v ]
Paso 4. Hacer VT := VT [ fvig y ET = ET [ f[Enlace[vi]; vi]g.
Si VT 6= V volver al paso 2.
Figura 7. Algoritmo de Prim;
Las dos operaciones elementales para obtener el bosque Fi+1 a partir del
bosque Fi son las siguientes:
Primera transformacion: Add-Drop
1. Se a~nade una arista que no este en el bosque Fi.
2. Pueden ocurrir dos cosas; que los extremos de la arista esten en un mismo
arbol Tij o que conecte dos subarboles Tij y Tik .
(a) Si la arista forma un ciclo en el subarbol Tij entonces se elimina una
arista de dicho ciclo.
(b) Si la arista conecta dos subarboles Tij y Tik entonces se elimina una
arista cualquiera.
Segunda transformacion: Drop-Add
1. Se elimina una arista del bosque Fi.
2. Se determinan las p + 1 componentes conexas que se forman.
3. Se a~nade una arista que conecte dos de dichas componentes.
Heurstica AG-bosque
Paso 0. (Inicializacion):
Sea F0 un bosque inicial de G: Tomar i 0.
Paso 1. (Localizacion):
Sea Xi = fx1i ; :::; xpig la localizacion optima de los p servicios
en Fi , obtenida de resolver el problema de un servicio en cada
arbol Tij , j = 1; :::; p:
Paso 2. (Asignacion):
Sea, para cada j = 1; :::; p, el conjunto Uij con los pun-
tos de demanda asignados a la localizacion xji 2 Xi . Sea
Tij+1 2 T (fxji g; Uij ) y
Fi+1 = Ti1+1 [ [ Tip+1 :
Paso 3. (Terminacion):
Si Fi+1 = Fi parar. En otro caso, hacer i i + 1 y volver al
paso 1.
Figura 8. Heurstica AG-bosque
2.3. Estrategias de Busqueda. 47
2.3.6 Experiencia computacional.
V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje CPU
1221.20 2.75 1560.80 1.76 1354.00 1.43 1664.80 2.64 1418.00 1.48
1221.20 1.59 1560.80 1.98 1354.00 1.65 1664.80 2.58 1418.00 2.25
1221.20 1.98 1560.80 1.42 1354.00 1.59 1664.80 2.30 1418.00 1.65
1221.20 1.42 1560.80 3.41 1354.00 1.15 1664.80 2.09 1418.00 1.37
1221.20 2.75 1560.80 1.48 1354.00 0.66 1664.80 2.69 1418.00 1.32
1221.20 4.06 1560.80 2.04 1354.00 2.20 1664.80 1.59 1418.00 1.27
1221.20 2.42 1560.80 1.48 1354.00 1.37 1664.80 2.03 1418.00 1.48
1221.20 2.42 1560.80 1.87 1354.00 1.43 1664.80 2.25 1418.00 1.59
1221.20 2.19 1560.80 1.15 1354.00 0.93 1664.80 1.27 1418.00 1.70
1221.20 2.53 1560.80 0.93 1354.00 1.48 1664.80 2.58 1418.00 1.93
5 grafos de 25 vertices y 30 aristas.
V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje CPU
1634.40 2.58 1256.00 1.21 1345.60 1.87 1323.40 1.32 1255.40 1.92
1634.40 2.63 1256.00 1.54 1345.60 1.76 1323.40 1.15 1255.40 1.70
1634.40 2.04 1256.00 1.65 1345.60 4.61 1323.40 0.77 1255.40 1.65
1634.40 1.86 1256.00 1.59 1345.60 2.09 1323.40 1.38 1255.40 1.87
1634.40 2.04 1256.00 1.21 1345.60 1.76 1323.40 1.75 1255.40 1.15
1634.40 1.42 1256.00 1.75 1345.60 1.20 1323.40 1.43 1255.40 2.09
1634.40 1.54 1256.00 1.21 1345.60 3.90 1323.40 1.05 1255.40 1.97
1634.40 1.49 1256.00 1.71 1345.60 1.82 1323.40 1.15 1255.40 2.04
1634.40 1.86 1256.00 0.87 1345.60 1.75 1323.40 1.26 1255.40 1.97
1634.40 0.99 1256.00 1.38 1345.60 1.32 1323.40 1.16 1255.40 1.98
5 grafos de 25 vertices y 30 aristas.
50 Captulo 2. HEURISTICAS Y ARBOLES.
V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje CPU
1333.00 18.95 1239.60 49.05 1360.80 5.55 1466.80 8.24 1384.00 3.84
1333.00 4.01 1227.20 18.73 1380.80 14.39 1466.80 21.14 1384.00 20.10
1333.00 13.29 1227.20 35.98 1360.80 15.44 1466.80 5.55 1384.00 4.01
1426.40 24.22 1239.60 4.89 1380.80 5.44 1455.20 25.54 1384.00 6.53
1333.00 6.48 1227.20 4.06 1380.80 4.40 1466.80 5.98 1384.00 4.94
1426.40 5.11 1239.60 14.77 1360.80 5.82 1466.80 4.94 1384.00 24.00
1333.00 19.23 1208.80 33.84 1360.80 6.92 1407.20 17.96 1419.20 5.16
1360.80 4.45 1239.60 11.97 1360.80 4.72 1407.20 5.39 1384.00 10.06
1333.00 11.92 1239.60 6.37 1380.80 5.16 1466.80 23.07 1384.00 4.73
1333.00 7.45 1215.60 42.35 1360.80 4.72 1466.80 5.60 1349.60 9.17
5 grafos de 25 vertices y 40 aristas.
V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje CPU
1042.40 5.11 1042.40 22.58 1014.40 9.45 1590.00 14.17 1060.40 12.85
1042.40 32.68 989.60 13.35 1014.40 7.85 1614.20 5.44 1060.40 14.45
1042.40 16.80 989.60 37.08 1014.40 6.32 1628.00 6.70 1072.40 4.94
989.60 45.47 989.60 6.20 1014.40 7.63 1590.00 5.82 1072.40 33.01
989.60 10.76 989.60 6.32 1014.40 7.63 1614.20 7.25 1072.40 11.98
1042.40 12.41 1042.40 32.24 1014.40 7.86 1628.00 23.13 1072.40 22.19
989.60 32.63 1042.40 3.79 1014.40 7.80 1628.00 5.71 1072.40 6.75
1042.40 5.82 989.60 11.92 1014.40 8.29 1590.00 6.15 1072.40 16.48
989.60 6.97 1042.40 11.48 1014.40 7.80 1628.00 6.26 1072.40 9.94
989.60 8.85 989.60 5.49 1014.40 8.62 1590.00 6.15 1060.40 57.90
5 grafos de 25 vertices y 40 aristas.
V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje CPU
1513.20 34.99 1141.20 17.30 1235.20 65.97 997.60 10.60 1050.80 22.74
1492.80 38.78 1118.40 26.91 1187.60 22.41 1048.40 33.67 1050.80 36.69
1472.40 52.34 1118.40 13.02 1296.40 24.49 1048.40 19.94 1054.00 74.48
1498.80 13.45 1141.20 15.21 1264.00 23.89 1048.40 22.03 1054.00 52.62
1452.00 34.83 1118.40 26.37 1213.20 10.10 1048.40 12.19 1050.80 9.17
1452.00 15.21 1118.40 15.88 1218.00 76.79 1048.40 23.51 1050.80 36.64
1452.00 70.96 1112.40 9.06 1264.00 31.31 1048.40 68.83 1050.80 15.33
1472.40 65.30 1112.40 53.88 1218.00 35.98 1048.40 9.95 1099.20 23.62
1452.00 81.07 1118.40 74.37 1170.40 55.86 1002.40 9.83 1064.40 63.55
1513.20 13.46 1124.80 44.43 1170.40 89.03 1002.40 8.01 1170.00 29.11
5 grafos de 25 vertices y 50 aristas.
2.3. Estrategias de Busqueda. 51
V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje CPU
1255.60 30.10 1093.20 71.18 1221.20 29.00 1047.40 17.30 1264.00 81.18
1196.40 14.55 1106.00 15.77 1218.80 87.33 1047.40 7.19 1213.20 32.69
1196.40 97.93 1093.20 35.70 1218.80 87.33 1047.40 8.34 1170.40 7.63
1304.80 21.31 1093.20 25.43 1209.20 99.74 1047.40 11.21 1213.20 20.65
1293.20 51.25 1093.20 26.80 1232.40 14.94 1096.40 18.01 1213.20 35.26
1231.20 36.31 1089.20 98.32 1230.80 56.69 1099.80 7.75 1213.20 12.68
1300.80 33.67 1106.00 15.93 1209.20 43.94 1110.40 16.64 1264.00 22.47
1300.80 80.35 1093.20 63.00 1218.80 25.15 1078.00 13.51 1164.80 91.56
1255.60 12.47 1089.20 91.83 1239.60 54.65 1047.40 5.99 1170.40 70.75
1255.60 38.83 1093.20 62.34 1218.80 83.27 1087.80 7.75 1213.20 82.50
5 grafos de 25 vertices y 50 aristas.
V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje CPU
2179.20 18.35 2305.60 36.03 2294.40 27.90 2237.60 14.28 2338.80 14.66
2179.20 14.66 2305.60 34.82 2294.40 31.74 2237.60 11.53 2328.00 42.02
2179.20 15.92 2305.60 29.72 2294.40 38.62 2237.60 14.11 2338.80 37.46
2179.20 17.41 2305.60 30.86 2294.40 29.28 2237.60 13.13 2328.00 21.20
2179.20 17.30 2305.60 29.06 2294.40 98.64 2237.60 16.15 2338.80 19.94
2179.20 17.14 2305.60 32.08 2294.40 27.63 2237.60 15.66 2338.80 17.69
2179.20 18.78 2305.60 30.81 2280.80 102.60 2237.60 15.76 2328.00 37.74
2179.20 16.48 2305.60 31.96 2280.80 100.79 2237.60 12.30 2328.00 58.88
2179.20 18.45 2305.60 31.47 2294.40 43.01 2237.60 16.48 2328.00 21.69
2179.20 19.78 2305.60 21.42 2294.40 26.04 2237.60 18.90 2328.00 42.19
5 grafos de 45 vertices y 65 aristas.
V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje CPU
2511.20 24.22 2224.80 18.29 2994.80 28.18 2230.00 84.04 2608.60 43.23
2511.20 17.35 2224.80 101.34 2994.80 24.39 2288.40 38.39 2608.60 54.92
2511.20 11.43 2224.80 82.83 2994.80 35.15 2230.00 28.83 2608.60 51.58
2511.20 7.96 2224.80 25.54 2994.80 97.39 2230.00 39.77 2608.60 50.47
2511.20 22.96 2224.80 14.11 2994.80 117.21 2230.00 52.67 2608.60 45.37
2511.20 14.28 2224.80 23.45 2994.80 45.26 2230.00 54.87 2608.60 48.34
2511.20 20.66 2224.80 14.17 2994.80 61.46 2230.00 92.00 2608.60 48.50
2511.20 20.81 2224.80 20.87 2994.80 37.45 2230.00 85.46 2608.60 62.34
2511.20 15.38 2224.80 18.79 2994.80 78.65 2230.00 52.24 2608.60 48.12
2511.20 17.03 2224.80 14.94 2994.80 71.35 2230.00 72.61 2608.60 64.26
5 grafos de 45 vertices y 65 aristas.
52 Captulo 2. HEURISTICAS Y ARBOLES.
V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje. CPU V.Obje CPU
2396.80 39.33 2195.20 55.64 2413.20 208.44 2159.20 98.70 2099.20 57.51
2396.80 42.41 2195.20 84.53 2462.80 87.39 2436.40 109.08 2208.80 72.34
2219.20 82.56 2195.20 165.38 2304.00 191.75 2180.80 117.81 2099.20 63.11
2216.00 46.96 2195.20 76.78 2375.20 125.83 2269.20 81.95 2099.20 61.13
2396.80 64.16 2195.20 100.24 2413.20 123.04 2180.80 117.48 2208.80 66.02
2216.00 104.53 2206.00 91.06 2465.20 176.86 2368.40 62.23 2099.20 73.60
2216.80 51.13 2195.20 105.90 2465.20 82.82 2135.60 88.05 2099.20 76.62
2216.00 126.66 2195.20 148.08 2413.20 173.02 2180.80 68.71 2099.20 83.11
2470.00 56.51 2195.20 69.10 2413.20 167.30 2175.60 151.70 2099.20 49.71
2216.00 56.19 2195.20 58.99 2304.00 100.30 2175.60 140.83 2208.80 49.05
5 grafos de 50 vertices y 100 aristas.
2.4.1 Introduccion.
Las funciones objetivo de importantes problemas de optimizacion, como son
los modelos clasicos de localizacion en un grafo, no son ni concavas ni convexas
(en el conjunto de sus variables), y en general el numero de optimos locales es e-
levado. Algunas tecnicas de optimizacion global han jugado un papel importante
en la resolucion de estos modelos, Sin embargo, en problemas de tama~no mode-
rado, el tiempo computacional se ve incrementado exponencialmente. Algoritmos
recientes (ver Chen y otros (1992) [20] y Hansen y Mladenovic (1995) [75]) han
obtenidos soluciones exactas para problemas de tama~no mediano. Sin embargo
en problemas reales donde el numero de posibles clientes pueden ser miles, sigue
siendo necesario el uso de procedimentos heursticos.
Mladenovic (1995) [125] sugirio una nueva heurstica para resolver proble-
mas continuos de localizacion-asignacion por medio de estructuras variables de
2.4. La heurstica VNDS. 53
entornos. La idea, brevemente, es la siguiente: un numero especicado de pun-
tos alrededor de la solucion actual es generado aleatoriamente obteniendose as
el primer entorno. Si es posible un movimiento descendente hacia una mejor
solucion desde uno de estos puntos, esta se realiza; en otro caso, se cambia de
entorno ampliando el radio del mismo. El algoritmo termina si no se consige una
mejora en el ultimo entorno denido. Alternativamente, se permiten movimien-
tos ascendente como en una busqueda tabu. La motivacion de la estructura de
entorno variable, es aportar un mecanismo que metodologicamente extienda el es-
pacio de busqueda de las soluciones, para evitar quedar atrapado en un mnimo
local. La heurstica es denotada VNS (Variable Neighbourhood Search), y se
describe en las proximas secciones.
En este apartado se muestra que una idea similar a la de VNS, puede ser
aplicada con exito en la resolucion de problemas de grandes dimensiones, me-
diante la descomposicion de los mismos. Para ello se ha desarrollado una nueva
heurstica denominada VNDS (Variable Neighbourhood Decomposition Search)
y se ha implementado para el problema de la p-Mediana (ver apendice B). El
correspondiente algoritmo heurstico VNDS ha sido probado en la resolucion de
problemas de la p-Mediana para grafos de 1400, 3038 y 5934 vertices. Estos grafos
han sido elegidos de la librera del problema del viajante de comercio TSPLIB
[150].
Nk (x) = X;
[ X
k=0 k=0 k k p
El procedimiento Decompose.
Decompose(f; x; m; s; d; n; p; f 0; x0; m0; s0; d0; n0; p0; k)
Colocar a true k indices del vector Merged(:) entre 1 y p
p0 k
f0 0
j 0
do i = 1; n
If Merged(m(xi)) then
j j+1
x0j xi
m0 (xi) m(xi )
f 0 f 0 + d(xi; m(xi))
endif
enddo
n0 j
FindSecond(x0; m0; s0; d; p0; n0)
tabla 1.
Para valores de p menores de 50, la heurstica VNDS alcanza, en menos
tiempo, los valores obtenidos por Hansen y Mladenovic (1996) [77], pero,
para p mayor que 50, VNDS mejora el mejor valor de la funcion objetivo
conocido, y por ello para p 50 se han actualizado los valores objetivos
de [77] con los valores objetivos obtenidos de VNDS. Se concluye que la
heurstica VNDS es un 11% mejor que la heurstica de Hansen y Mladenovic
68 Captulo 2. HEURISTICAS Y ARBOLES.
(1996) [77], en el tiempo que esta ultima gasta en realizar una sola busqueda
local descendente.
tabla 2.
En la tabla 2, se puede observar que para cada valor de p 500, la heurstica
VNDS mejora siempre el mejor valor objetivo conocido citados en Hansen
y Mladenovic (1996) [77]. Por ello los mejores valores objetivos conocidos
para el problema, son precisamente, los obtenidos por medio de VNDS.
Cuando p > 500, no se conoce referencia alguna, para el problema de la
p-Mediana en un grafo de 3038 vertices. Por ello se compara VNDS con
las heursticas de intercambio y Montecarlo. Es claro que los resultados
que se obtienen de VNDS son los mejores. Esta heurstica en media para
p 500 es un 28% mejor que la heurstica de Hansen y Mladenovic (1996)
[77], en el tiempo que esta ultima gasta en realizar una sola busqueda local
descendente.
tabla 3.
Al igual que en la tabla 2, los mejores valores objetivos conocidos para el
problema de la p-Mediana en un grafo de 5934 vertices, son los obtenidos
por medio de VNDS. Una vez mas, la comparacion se ha realizado con
respecto a las heursticas de intercambio y Montecarlo, dado que no se
conoce referencia alguna.
Captulo 3
EL PROBLEMA DEL
CENTDIAN EN GRAFOS.
3.1 Introduccion.
Los problemas de localizacion del Centro y de la Mediana de un grafo han
sido objeto de profundos estudios desde que fueron formulados por Hakimi (1964)
[62], lo cual ha dado lugar a diversos algoritmos para su resolucion as como a
numerosas aplicaciones de estos conceptos. Antes de acometer el estudio del
problema del Centdian, conviene recordar brevemente el concepto de cada uno
de ellos.
El problema de la Mediana consiste en minimizar la distancia media entre
el usuario y el servicio a localizar. Este tipo de funcion objetivo mini-sum es
apropiado para localizar servicios que deben satisfacer una demanda continua y
estable, como, por ejemplo, escuelas, centros comerciales, terminales de trans-
porte, etc. En la literatura es comunmente conocido tambien como el problema
de Fermat-Weber (Wendell and Hurter (1973) [173]). Por otro lado, el problema
del Centro estriba en localizar un punto en el grafo de tal manera que la distan-
cia del vertice mas alejado a el sea mnima. Esta funcion objetivo mini-max es
frecuentemente usada en servicios de emergencias tales como estaciones de am-
bulancias, de bomberos o de policia. Este problema tambien es conocido como el
problema de Rawl [15]. En este contexto, el modelo incorpora una medida de la
aversion por la desigualdad. Sin embargo, este modelo fracasa si hay variaciones
de las distancias dentro de la poblacion de los usuarios.
En muchos problemas reales el objetivo es una mezcla de estos dos mode-
los, muchas veces antagonicos. Por ejemplo, a la hora de ubicar un puesto de
69
70 Captulo 3. EL PROBLEMA DEL CENTDIAN EN GRAFOS.
bomberos se puede pretender minimizar el tiempo de viaje al posible punto de
demanda mas alejado, siempre y cuando el puesto este sucientemente cerca de
las areas mas pobladas. El problema consiste en minimizar la funcion Centro
con la restriccion de que la funcion Mediana no supere un determinado nivel.
Otro ejemplo es minimizar la distancia media que deben recorrer los ni~nos para
llegar a la escuela sin que a ninguno le quede demasiado lejos. El objetivo aqu es
minimizar la funcion Mediana imponiendo una cota superior a la funcion Centro.
El modelo que sugirio Halpern (1976) [65] consiste en minimizar una com-
binacion convexa de la distancia media ponderada y la distancia maxima no
ponderada; la solucion a este problema recibe el nombre de Centdian. Con ello
se consigue un equilibrio entre las distancias media y la distancia mas alejada.
En Carrizosa y otros, [15] se encuentra un desarrollo axiomatico en el que se
justica el uso del criterio Centdian.
En este captulo se considera la funcion Centro ponderada generalizando as
el modelo de Halpern. Se entiende que las ponderaciones de la funcion Centro
son distintas que las ponderaciones de la funcion Mediana. Por simplicidad este
nuevo problema se sigue denotando Centdian.
Se comienza analizando el caso de localizar un solo servicio, extendiendo todas
las propiedades del modelo de Halpern, para el nuevo modelo aqu presentado.
A continuacion, se estudia el problema del 2--Centdian. Realizando un
analisis de la funcion objetivo, y proponiendo un algoritmo cuya complejidad
es de O(m2n4):
Exceptuando un apartado del artculo de Hooker y otros (1991) [82], en el
cual se propone un conjunto nito dominante para el p--Centdian, no se conoce
literatura que haga mencion al -Centdian multiple. Este conjunto nito do-
minante propuesto por Hooker, es erroneo, como se muestra en el contraejemplo
presentado en este captulo.
Finalmente se propone un nuevo conjunto nito dominante para el problema p-
-Centdian en un grafo. Y como consecuencia del mismo se propone un algoritmo
exacto.
vi 2U
Esto implica que hay que abrir p servicios y asignar cada usuario a uno de
ellos, optimizando las correspondientes funciones objetivos.
Dado un numero p de servicios a ser localizados y un valor ; 0 1;
el problema p--Centdian consiste en encontrar p puntos servicios X en G que
minimizen la funcion objetivo:
f(U ; X ) = fc (U ; X ) + (1 , ) fm (U ; X ):
Denotamos con p--CD el conjunto de todos los p--Centdian del grafo para
un dado.
El valor de representa el peso atribudo a la funcion Centro con respecto
al peso de la funcion Mediana. Generalmente es difcil para el decisor determi-
nar exactamente el peso que debe ser asociado a cada uno de los dos criterios.
Por tanto, es importante encontrar una expresion sencilla de la ubicacion del -
Centdian para todos los pesos relativos. En particular, si = 0 los -Centdian
son las Medianas, y si = 1 el -Centdian es un Centro. Cuando el 0 < < 1;
el -Centdian es la solucion optima para un problema de localizacion en el que
los dos criterios de eciencia y equidad son importantes.
Una solucion X 2 P (G) es eciente, respecto al problema bicriterio min ffc; fm g
si no existe ninguna solucion Y 2 P (G) tal que fc (Y ) fc (X ) y fm (Y ) fm (X )
siempre que, al menos, una de las dos desigualdades sea estricta. En Perez-Brito
y Moreno Perez (1997) [146] se encuentra un procedimiento geometrico que car-
acteriza los puntos ecientes de este problema bicriterio. Sea EF el conjunto de
72 Captulo 3. EL PROBLEMA DEL CENTDIAN EN GRAFOS.
todos las soluciones ecientes del grafo. El conjunto de los puntos -Centdian
del grafo para todo 2 [0; 1] es un subconjunto del conjunto de puntos ecientes
del min ffc; fm g, es decir,
[ fp--CD : 0 1g EF:
Existe a lo sumo un centro local y dos puntos pendientes con respecto a cada
pareja de vertices en cada arista, por tanto, el numero de los diferentes radios de
los centros locales y de los puntos pendientes es nito. El conjunto de distancias
ponderadas entre vertices y vertices usuarios junto con el de rangos de centro
locales y rangos de los puntos pendientes viene determinado por:
LC =r[2R LC (r)
PP =r[2R PP (r)
EP =r[2R EP (r):
74 Captulo 3. EL PROBLEMA DEL CENTDIAN EN GRAFOS.
3.3 El 1--Centdian.
El objetivo del 1--Centdian es encontrar un punto x 2 P (G) tal que:
Demostracion: Para todo 2 [0; 1] los puntos fxi : i = 1; :::; rg que apare-
cen en la propiedad 3.3.4 son algunos puntos -Centdian y ademas verican
que fc(U; xi) fc(U; xi+1) y fm(U; xi) fm(U; xi+1), i = 1; :::; r , 1. Como
x(0) = xm = x1 y x(1) = xc = xr , es facil comprobar lo que se establece en esta
propiedad 3.3.6. 2
Para resolver el problema del 1--Centdian en grafos generales se han prop-
uesto dos metodos con identica complejidad O(mn log mn): el de Halpern (1976)
[65] y el de Hansen y otros (1991) [74]. En ambos casos los algoritmos propuestos
dan como solucion un conjunto de puntos -Centdian, para todos los 2 [0; 1] :
El metodo de Halpern se basa en la construccion de cotas superiores para el
valor mnimo de f; mientras que Hansen y otros, abordan el problema desde el
punto de vista geometrico, resultando este ultimo conceptualmente mas sencillo.
3.4 El 2--Centdian.
El objetivo del 2--Centdian es encontrar dos puntos x1; x2 2 P (G) de tal
forma que:
r
v1
4
x1 2
v2 v4
r
v5 5
x2 5
v6
6 2 100 10
2
v3
v1 r
5 x1 1
v2 v4
v5r 5 x2 5
v6
6 2 100 10
2
v3
i=1 i=5
v1r
4 x1 2 v2 v4
r
v5 5 x2 5
v6
6
2
v3
2 100 10
v1 r
5 x1 1
v2 v4
r
v5 5 x2 5
v6
6 2 100 10
2
v3
80 Captulo 3. EL PROBLEMA DEL CENTDIAN EN GRAFOS.
Vamos a mostrar con un ejemplo (ver gura.-Caso1) como desplazando el
punto x1 sobre la arista podemos conseguir que la funcion f(U ; X ) disminuye
hasta que x1 alcance un vertice o un r2-extremo. (ver gura.- Caso 1) Como se
observa fx1g 2 Bc(4; v1; v3) y fx2g 2 Bc(5; v5; v6): Puesto que los radios r1 =
4 < r2 = 5, x1 se puede mover hacia v2 hasta que r1 = r2 = 5, lo cual hace que
la funcion Centro no se vea afectada, y siga valiendo maxfr1; r2g = 5; pero, al
mismo tiempo, este movimiento favorece a la funcion Mediana en dos unidades
pues incrementa una unidad respecto a v1 y disminuye una unidad respecto a
cada uno de los vertices v2; v3 y v4. El resultado global de este movimiento hace
disminuir la funcion objetivo en 0:4 unidades, pasando de 8:8 a 8:4. La solucion
optima para = 0:8 consiste en fx1; x2g. El punto x2 es un centro local con
rango 5 y el punto x1 es un r2 -extremo.
Caso 2. Sea r2 < r1 = r.
v1 r
5.5
x1 2.5
v2 v4
r
v5 4
x2 4
v6
8
2
v3
2 100 8
v1 r
5 x1 3 v2 v4
r
v5 4 x2 4
v6
8 2 100 8
2
v3
v1 r
6
x1 1
v2 v4
r
v5 6 x2 4
v6
7
2
v3
2 100 10
v1r
5 x1 2 v2 v4
r
v5 5 x2 5
v6
7 2 100 10
2
v3
Vamos a mostrar con un tercer ejemplo (ver gura.- Caso3), como partiendo
de dos puntos fx1; x2g donde ninguno es vertice, o centro local, al desplazarlo
simultaneamente sobre sus respectivas aristas podemos conseguir que la funcion
f(U; X ) no aumente hasta que uno de los dos puntos, fx1; x2g sea un centro
local o un vertice, en este ejemplo, es el punto x2 el que alcanza un centro local
respecto a v5 y v6: Como se observa, los respectivos radios pasan de 6 a valer
r1 = r2 = 5; y por tanto la funcion objetivo del 0:8-Centdian pasa de valer 9:4, a
valer 9:0. La unica solucion optima para = 0:8 consiste en fx1; x2g. El punto
x2 es un centro local con rango 5 y el punto x1 es un punto r2-extremo.
Proposicion 3.4.2 Sea (x1; x2) una solucion optima del 2--Centdian en G y
r = fc(U ; X ). Entonces:
1. x1 2 LC (r ) [ PP (r ) [ (V \ EP (r )) y x2 2 V [ EP (r ), o
2. x2 2 LC (r ) [ PP (r ) [ (V \ EP (r )) y x1 2 V [ EP (r ).
Algoritmo.- 2-CD-G.
Paso 0. Sea f = 1.
Paso 1. Calcular el conjunto P1 de pares (x; r); donde x 2 LC (r)[PP (r). Calcular
el conjunto P2 de pares (vi ; r); donde vi 2 V y r = wj0 d(vi ; vj ) para algun
vj 2 U . Sea L1 la lista de los pares de P1 [ P2 .
Paso 2. Tomar un par (x1; r1) de la lista L1; y calcular el conjunto EP (r1). Sea
L2 la lista de los puntos de EP (r1) [ V .
Paso 3. Tomar un punto x2 de la lista L2; y calcular f = f(U ; x1; x2). Si f < f
hacer f = f , x1 = x1 y x2 = x2 , y eliminar el punto x2 de la lista L2.
Paso 4. Si L2 no esta vaco, ir al paso 3.
Paso 5. Eliminar (x1; r1) de la lista L1. Si la lista L1 no esta vaca, ir al paso 2.
En otro caso, parar.
3.5 El p--Centdian.
El objetivo del p--Centdian es encontrar p puntos X = (x1; x2; :::; xp) 2
P (G)p tal que:
Supongamos que xk 2= D para algun k 2 f1; :::; pg. Se probara que el conjunto
X puede ser modicado sin incrementar la funcion f(U ; X ) hasta que xk 2 D
para todo k. En la demostracion se consideraran dos casos: caso 1.) rk (X ) <
r(X ) y caso 2.) rk (X ) = r(X ):
Pasamos a ver detalladamente cada uno de estos casos.
Caso 1.) Sea rk (X ) < r(X ).
Como xk 2= D, este debe ser un punto interior en la arista [i; j ]. Se pro-
bara como se puede mover este punto xk en su arista sin incrementar la funcion
f(U ; X ) hasta que un vertice sea alcanzado o rk (X ) sea igual a r(X ). Para ello
se necesita analizar la pendiente de f(U ; X ) en terminos de la distancia desde
xk al extremo i:
Para cualquier punto x 2 [i; j ], el conjunto de vertices usuarios que son
optimamente cubiertos por x a traves de i se representa por U i (x); es decir,
U i(x) = fvi 2 U : wi0 d(x; vi) = wi0 (l(x; i) + d(i; vi)) wi0 (l(x; j ) + d(j; vi ))g:
Analogamente, a traves de j ,
U j (x) = fvi 2 U : wi0 d(x; vi) = wi0 (l(x; j ) + d(j; vi)) wi0 (l(x; i) + d(i; vi))g:
Uk< (X ) = Uk (X ) , Uk= (X ) =
= fvi 2 U : wi0 d(xk ; vi) =min w0 d(x; vi) < wi0 d(xm; vi); 8m 6= kg:
x2X i
86 Captulo 3. EL PROBLEMA DEL CENTDIAN EN GRAFOS.
Los vertices de Uk= (X ) son asignables a xk y a otro servicio de X , pero si xk se
mueve una peque~na cantidad hacia j o hacia i; encontramos que algunos de estos
vertices pueden permanecer asignados a xk y mientras que otros pueden cambiar
de asignacion, e incluso vertices que estaban en equilibrio con respecto a mas de
un servicio pueden dejar de estarlo. El nuevo punto xk () denota a xk cuando
este se ha movido una peque~na cantidad hacia j ; es decir, si xk = p([i; j ]; t)
entonces xk () = p([i; j ]; t + ). Luego, aquellos vertices usuarios de
Uk= (X ) \ U j (xk )
son asignados solo a xk () y aquellos de
Uk= (X ) , U j (xk )
no son asignados a xk ().
Si X () denota la nueva solucion (x1; x2; :::; xk(); :::; xp); entonces una nueva
particion optima para X () es dada por:
a) Uk< (X ) , U j (xk ) gana un vertice. Las unicas posibilidades para que esto
ocurra son:
a1) Un vertice deja U j (xk ()), pero esto no es posible porque el movimiento
de xk se esta produciendo hacia j .
a2) Un vertice que no pertenece a U j (xk ()) se le asigna a Uk< (X ), pero
esto tampoco es posible, pues para este vertice, la distancia a xk ()
aumenta mientras que la distancia a xm, para m 6= k, permanece
inalterable.
b) [Uk<(X ) [ Uk= (X )] \ U j (xk ) pierde un vertice. Esto es imposible porque la
distancia desde xk () a los vertices de U j (xk ) decrece, dado que xk () se
esta acercando a j , por lo tanto, ningun vertice de U j (xk ) puede salir de
Uk< (X ) [ Uk= (X ).
Por lo tanto la pendiente de fc (U; X ()) puede ser wi0 o ,wi0, (y la de fc(U; X (,))
es ,wi0 o wi0 respectivamente) y la pendiente de f se puede expresar de una de
las formas siguientes:
a) D() = Dj () = , wi0 + (1 , ) Dmj () y
D(,) = Di () = + wi0 + (1 , ) Dmi ().
b) D () = Dj () = + wi0 + (1 , ) Dmj () y
D(,) = Di () = , wi0 + (1 , ) Dmi ().
En ambos casos, como se puede deducir del analisis del caso 1, la suma de las
pendientes tanto cuando xk se mueve hacia j; como cuando se mueve hacia i es:
Di () + Dj () =(1 , )(Dmi () + Dmj ()) 0:
| {z } | {z }
0 0
k 2K
k2K
90 Captulo 3. EL PROBLEMA DEL CENTDIAN EN GRAFOS.
Se concluye que una de estas dos pendiente debe ser no positiva, porque la
suma de ellas es:
(1 , ) 1=wk0 [Dkik () + Dkjk ()] 0:
X
k2K | {z
0
}
Proposicion 3.5.1 Existe una solucion optima X para el problema del p--
Centdian tal que, si r = fc (U ; X ) es el maximo radio de la solucion, entonces
cada x 2 X es un centro local, un punto pendiente, un vertice, o un punto
extremo con rango r . Esto es, X V [ LC [ PP [ EP (r ).
Algoritmo.- p-CD-G
Paso 1. Obtener la lista L de pares (x; r); consistente en centros locales y puntos
pendientes x y sus respectivos radios r. A~nadir a L todos los pares (vi ; r);
donde vi es un vertice y r = wj0 d(vi; vj ) para algun vj 2 U .
Paso 2. Calcular el p-Centro Xc y la p-Mediana Xm. Sea rc = r(Xc) y rm =
r(Xm) sus correspondientes radios maximos.
Paso 3. Para cada (x; r) 2 L; con rc r rm hacer lo siquiente:
i) obtener el conjunto EP (r) de puntos extremos con rango r, y
ii) para cada seleccion Y de p , 1 puntos de U \ EP (r);calcular f (U ; fxg\ Y ).
Paso 4. Mantener el mejor conjunto de p puntos de los evaluados en el Paso 3.
3.6 Conclusiones.
El hecho de introducir pesos a la funcion Centro en el modelo propuesto por
Halpern, pesos que no necesariamente tienen que ser iguales a los existentes para
la funcion Mediana, hace que se pierda simplicidad y se gane generalidad.
Ademas de generalizar el modelo, se ha estudiado por primera vez el caso
multiple, en el que el objetivo es encontrar p nuevos servicios que minimicen la
funcion -Centdian.
Un contraejemplo sobre el conjunto nito dominante existente en la literatura,
demuestra por un lado que el estudio del modelo multiple no es facil, y por el
otro, el interes que este modelo suscita.
El estudio de la funcion objetivo Centdian multiple, nos lleva a presentar,
un conjunto nito verdaderamente dominante para el p--Centdian en un
grafo, y como consecuencia del mismo un algoritmo exacto.
Captulo 4
EL PROBLEMA DEL
CENTDIAN EN EL A RBOL.
4.1 Introduccion.
En este captulo se resuelve el problema Centdian en un grafo, pero a diferencia
del captulo 3, en este se estudia el problema en un grafo especial conocido en
la literatura como arbol, y del cual ya se ha hablado anteriormente. Dada la
importancia que tienen estos tipos de grafos especiales, se ha dedicado un capitulo
al estudio del problema Centdian en el mismo. Proponiendo el primer algoritmo
polinomial para el problema p-Centdian (generalizado o no) en arboles. Este es
fruto del trabajo en colaboracion con A.Tamir. Para el caso generalizado, es decir,
cuando la funcion Centro se considera con pesos, la complejidad de este algoritmo
es de O(pn6 ), para p 6, y O(np ), para p < 6. Para el caso no generalizado, es
decir, para el modelo con la funcion Centro sin pesos, la complejidad disminuye
a O(pn5 ); para p 5, y O(np), para p < 5:
Tambien se considera la version discreta del modelo, donde los p puntos deben
seleccionarse entre los vertices, en este caso la complejidad se reduce a O(pn4),
para p 4, y O(np ), para p < 4.
fc(U; X ) =max
vi 2U
f wi0 d(X; vi )g:
Recordemos que dado e = [vi; vj ] 2 E; Qe representa el conjunto de puntos
mnimos locales de fc (U; x) sobre e ademas de vi y vj :
Recuerdese tambien los siguientes conjuntos de puntos especiales:
i) El conjunto de todos los centros locales de rango r 0 viene determinado
por:
ii) El conjunto de todos los puntos pendiente con rango r 0 viene determi-
nado por:
PP (r) =v ;v[2U Bp(r; vk ; vl)
k l
4.2. Formulacion del problema. 95
donde un punto x 2 Bp(r; vk ; vl), si x es un punto interior de una arista [i; j ]
tal que :
1. wk0 (l(x; i) + d(i; vk )) = wl0 (l(x; i) + d(i; vl)) con wk0 6= wl0 y / o
2. wk0 (l(x; j ) + d(j; vk )) = wl0 (l(x; j ) + d(j; vl)) con wk0 6= wl0.
Ademas,
LC =r[2R LC (r)
PP =r[2R PP (r)
siendo R como sigue:
R = fr : LC (r) 6= ;g [ fr : PP (r) 6= ;g [ fr : r = wi0 d(vi; vj ); vi 2 U; vj 2 V g:
4.3 El 1--Centdian.
Es bien conocido que la 1-Mediana de un grafo tiene la propiedad de ser
localizada en al menos un vertice del grafo. El 1-Centro sin embargo, tiene
que estar localizado en un vertice o en un centro local, y por tanto puede estar
localizado a lo largo de la arista de un grafo. El Centdian posee una propiedad
similar a la del Centro, esta queda recogida en el teorema 4.3.2.
Recordemos que el objetivo del 1--Centdian reside en encontrar un punto
x 2 P (T ) tal que:
f(x) =x2min
P (T )
f fc (U; x) + (1 , ) fm (U; x)g:
j =0 j =t+1
t kS
+1
siendo Tt el subarbol generado por S
Uj y Tt0+1 el generado por Uj .
j =0 j =t+1
2
Con este resultado es sencillo determinar la localizacion de los 1--Centdian
como una funcion de y de wj:
Esta proposicion nos permite dar un algoritmo para localizar los 1--Centdian
de un arbol para un dado que denominamos Algoritmo de Halpern generalizado,
(ver gura.-Algoritmo de Halpern generalizado) y esta basado en el algoritmo de
Halpern (1976) [65].
100
Captulo 4. EL PROBLEMA DEL CENTDIAN EN EL ARBOL.
Algoritmo de Halpern generalizado.
Paso 1. Usar el algoritmo el algoritmo de Megiddo [112], para hallar el Centro
pesado xc de T .
Paso 2. Usar el algoritmo de Goldman [58] para hallar las Medianas de T .
Sea xm la mediana mas cercana a xc .
Paso 3. Calcular los puntos de ruptura qi ; i = 1::r de la funcion fc en el
camino P (xm ; xc ).
Paso 4. Realizar una busqueda dicotomica en dichos puntos de ruptura a lo
largo del camino P (xm ; xc ); hasta encontrar el punto donde la pendiente
de la funcion f cambie de signo. Dicho punto representa el 1--Centdian
del arbol T:
Figura 17. Algoritmo de Halpern generalizado
Para cada r no negativo sea g(r) = r + m(r): Lo cual nos permite reformular
el problema del p-Centdian como:
g0(r) es una funcion lineal, y sus puntos de ruptura coinciden con los puntos de
ruptura de las funciones mj (r); j = 1; :::; p. Por lo tanto, el punto que minimiza
a g0(r) es uno de estos puntos de ruptura. Esto concluye la demostracion del
teorema. 2
Notese que la casustica de este teorema para el caso no pesado, es decir,
4.5. La p-Mediana r-restringida. 105
cuando wi0 = wi = 1, para todo i = 1; :::; n, puede ser obtenida de los resultados
de Perez-Brito y otros. [143, 144]. Adviertase que en el modelo no generalizado,
es decir, cuando wi0 = 1, para todo i = 1; :::; n, el valor optimo r se encuentra en
el conjunto R = R1 [ R2:
Demostracion: Dado que EP (r) contiene todos los puntos extremos a distancia
wi0 -pesado de r de un vertice de U , y dado que una solucion se encuentra en el
conjunto de vertices usuarios, Hakimi (1964) [62] se sigue que Y (r) es un conjunto
nito dominante para el problema de la p-Mediana r-restringida. 2
Demostracion: Por cada arista, hay a lo sumo un punto extremo de radio r con
respecto a cada vertices, por lo tanto la cardinalidad de Y (r) es de O(n2 ). 2
106
Captulo 4. EL PROBLEMA DEL CENTDIAN EN EL ARBOL.
En Kim y otros, [94], se muestra como calcular el conjunto Y (r), y aumentar
con sus puntos el conjunto de vertices de T , todo ello en un tiempo O(n2 ).
Representamos por T (r) el arbol al que se le ha insertado como nuevos vertices
el conjunto de puntos EP (r).
Como T (r) tiene O(n2 ) vertices, el algoritmo de Tamir (1996) [163], resuelve
el problema de la p-Mediana sin restringir, en un tiempo O(pn4 ).
Sabiendo que para resolver el problema del p-Centdian en T se requiere la
solucion de la p-Mediana r-restringida, para los O(n3) valores de r, la complejidad
total es O(pn7 ). En la siguiente seccion se muestra de que manera se puede
reducir esta complejidad a O(pn6 ), mejorando la complejidad de la p-Mediana
r-restringida a O(pn3 ).
Para el modelo no generalizado la complejidad sera de O(pn5 ): Ya que los
posibles valores de r (r 2 R1 [ R2) pasan a ser del orden O(n2):
Denicion 4.5.4 Una hoja del arbol, es un vertice que no tiene hijos.
4.5. La p-Mediana r-restringida. 107
Fase 1. Transformacion en un arbol binario
Como muestra Tamir [163], es conveniente transformar el arbol dirigido T
en un arbol binario equivalente Tbin , en el que cada vertice no hoja vj tenga
exactamente dos hijos, vj(1); vj(2). Al primero se le denominara hijo izquierdo,
y al segundo hijo derecho.
1. Se considera cada vertice no hoja vj del arbol original con un solo hijo,
digamos vj(1); se introduce un nuevo vertice uj(1) con peso cero; y se conecta
a vj con una nueva arista de longitud cero. Por lo que, uj(1) ademas de ser
el segundo hijo de vj ; sera una hoja del nuevo arbol.
2. Se considera cada vertice vj del arbol original con al menos tres hijos,
digamos vj(1); :::; vj(t); t 3; se a~naden t-2 nuevos vertices, uj(2); :::; uj(t,1)
todos ellos con peso cero, para cada z = 2; :::; t-1; se reemplaza la arista
[vj ; vj(z)] por la arista [uj(z); vj(z)]; tambien, se reemplaza la arista [vj ; vj(t)]
por esta otra arista [uj(t,1); vj(t)]. La longitud de cada una de estas nuevas
aristas es la longitud de la arista que sustituye.
La gura 24 (A rbol binario) muestra un ejemplo donde un vertice con cinco
hijos t = 5 que al a~nadirle t , 2 = 3 nuevos vertices con peso cero, uj(2); uj(3); uj(4),
del modo descrito anteriormente, se transforma en un arbol binario.
108
Captulo 4. EL PROBLEMA DEL CENTDIAN EN EL ARBOL.
lvj lvj
%Le T
% Le T
% L e
% L e 3 T
T
0
3 l7 l 2 l6 l5
%% L ee
l
L
l
TT
l u2
v1 v2 v3 v4 v5 v1 J
J
7 0
J
l l u3
J
J
v2
J
J
2
J 0
J
l
J
l u4
v3 % J
% J
6 % J 5
v4 l
%
% JJ
v5 l
Figura 18. Arbol binario
Despues de realizar este proceso para cada vertice vj del arbol original T , el
nuevo arbol tendra a lo mas 2n , 3 vertices.
Esta union tiene por complejidad el tama~no de las respectivas listas L,k 2 y
L,k(2) no jY j = O(n2 ); se tiene L,k 2 = L,k(2)
2 : Al ser las listas de tama~ 2 = O(n2 ):
lv1
%\
2%
% \
\
3
% \
lv2
%% \\
lv3
A A
A A
1 A 4 5 A 2
A A
l
AA
l l AA
l
v4 v5 v6 v7
6 = f5g; L7 = f2g;
L++ ++
112
Captulo 4. EL PROBLEMA DEL CENTDIAN EN EL ARBOL.
L+2 = f0; 1; 4g; L+3 = f0; 2; 5g;
2 = f2; 3; 6g; L3 = f3; 5; 8g;
L++ ++
G(vj ; 0; r) = 1:
4.5. La p-Mediana r-restringida. 113
Denicion 4.5.10 F (vj ; q; r) es el valor optimo del subproblema denido en el
subarbol Tj , bajo las condiciones siguientes:
Es decir:
La funcion recursiva F (vj ; q; r) sera calculada solo para q jVj j, y r = rji , donde
rji se corresponde con un semi-vertice yji 2 Y , Yj .
El motivo de esta ultima denicion, viene dado porque si todos los elemen-
tos de Lj son distintos, entonces G(vj ; q; rji ) es el valor optimo del subproblema
denido en Tj , dado que al menos 1 y a los mas q semi-vertices son seleccionados
en Tj , y el mas cercano de ellos a vj esta a una distancia de al menos rji desde vj .
La condicion de Lj , requirida anteriormente, asegura que la misma interpretacion
de G(vj ; q; rji ) puede ser hecha para distintos elementos de Lj , es decir, elementos
rji , satisfaciendo rji < rji+1 .
El algoritmo dene las funciones G y F en todas las hojas de T , y recursiva-
mente procede desde las hojas a la raz calculando los valores relevantes de estas
dos funciones recursivas en todos los vertices de T . El valor optimo del problema
vendra dado por G(v1; p; r1m ), donde v1 es la raz del arbol. (Ver gura.-Algoritmo
de las hojas a la raz)
114
Captulo 4. EL PROBLEMA DEL CENTDIAN EN EL ARBOL.
Algoritmo De las hojas a la raz.
Paso 0. Inicializaci
on Si vj es una hoja de Tbin . Entonces: 8i = 1; :::; m tal que
yji 2 Y , Yj
G(vj ; 1; rji ) = 0; i = 1; :::; m :
F(vj ; 0; rji ) = wj0 d(vj ; yji ) = wj0 rji ; y
F(vj ; 1; rji ) = minfF(vj ; 0; rji ); G(vj ; 1; rji )g:
Paso 1. Paso arriba Si vj es un vertice no hoja de Tbin
(1.a) calcular el valor de G en vj para cada rji de interes correspondiente a Yji.
Caso 1.- Si yji = vj , entonces calcular:
G(vj ; q; rj1) = min fF(vj (1); q1; rjk(1)) + F (vj (2); q2; rjt (2))g :
q1+q2 =q,1
q1 jVj(1) j
q2 jVj(2) j
Esto signica que un servicio puede establecerse en vj (la raz del subarbol Tj )
y para evaluar la funcion objetivo en el, hay que evaluar todas las posibilidades
en sus respectivos hijos. Con tal n se utilizan las funciones F (vj(1); q1; rjk(1)) y
F (vj(2); q2; rjt(2)), ya que vj esta fuera de los subarboles Tj(1) y Tj(2):
En los casos venideros, consideramos rji ; para i = 2; :::; m:
Caso 2.- Si rji es el radio correspondiente al semi-vertice yji 2 Y ,Yj , entonces:
G(vj ; q; rji ) = G(vj ; q; rji,1) :
En este caso no es necesario realizar nuevos calculos, pues la funcion vale lo mismo
que cuando esta fue evaluada con el radio que le precede.
Caso 3.- Si rji es el radio correspondiente al semi-vertice yji 2 Yj(1), entonces,
yji tambien le corresponde a un elemento, digamos rjk(1) de Lj(1), y a un elemento,
digamos rjt(2) de Lj(2); entonces:
G(vj ; q; rji ) = min fG(vj ; q; rji,1);
wj rji + q
min
+q q=
fG(vj (1); q1; rjk(1)) + F (vj (2); q2; rjt (2))gg:
q11 j2Vj(1) j
1
q2jVj(2) j
116
Captulo 4. EL PROBLEMA DEL CENTDIAN EN EL ARBOL.
Es decir, hay dos posibilidades, la primera de ellas, es no establecer un servicio
en yji ; esta posibilidad es evaluada con la funcion G(vj ; q; rji,1). La segunda de las
posibilidades, es establecer un servicio en yji ; con un coste de wj rji ; y establecer los
q-1 restantes entre las dos ramas de vj : La rama correspondiente a vj(1) se evalua
con G(vj(1); q1; rjk(1)); 1 q1 jVj(1)j, pues ya se ha establecido un servicio en
el subarbol Tj(1). La rama correspondiente a vj(2) se evalua con F (vj(2); q2; rjt(2));
q2 jVj(2)j ya que no se ha establecido un servicio en el subarbol Tj(2).
Caso 4.- Si rji es el radio correspondiente al semi-vertice yji 2 (vj ; vj(1)), e
yji 6= vj(1), entonces:
G(vj ; q; rji ) = minf G(vj ; q; rji,1);
wj rji + min
q1 +q2 =q,1
fF (vj (1); q1; rjk(1)) + F(vj (2); q2; rjt (2))gg:
q1jVj(1) j
q2jVj(2) j
Proposicion 4.5.5 La complejidad del Algoritmo de las hojas a la raz es O(p2 n3).
Hj Hj(1) + Hj(2);
y si vj es pobre,
Hj Hj(1) + Hj(2) + c n2 minf Vj(1) ; p=2g minf Vj(2) ; p=2g;
i=1
fvk 2U j g
El problema del p-Centdian en un bosque reside en encontrar p reales, x1; :::; xp,
que minimicen la funcion:
n
max f j (x )+ fmj (xj ):
X
fj =1;:::;pg c j
(4.1)
j =1
Una reformulacion del problema puede ser obtenida asociando una variable
real fk a cada vertice vk de T . El problema estriba n
en encontrar las variables
reales, x1; :::; xp, f1; :::; fn y r, minimizando fr+ fig; cuando este este sujeto
P
i=1
a las restricciones,
r wk0 (jxj , ai(k)j + bk );
fk wk (jxj , ai(k)j + bk );
para todo vk 2 U , j = 1; :::; p,
j
i=1
v2Ti v2Ti
Demostracion: Sea (z1; z2) el 2--Centdian del 2-bosque B = (T1; T2). Entonces
f(B; (z1; z2)) = fc (B; (z1; z2)) + (1 , )fm (B; (z1; z2)) =
= maxffc(T1; z1); fc (T2; z2)g + (1 , )fm (B; (z1; z2)) =
= fc (T1; z1) + (1 , )fm (B; (z1; z2)) =
= fc (T1; z1) + (1 , )[fm(T1; z1) + fm(T2; z2))] =
= f(T1; z1) + (1 , )fm (T2; z2)
f(T1; z1) + (1 , )fm (T2; y2):
Por tanto, (z1; y2) es el 2--Centdian del 2-bosque B = (T1; T2). 2
4.7. Un algoritmo eciente para el 2--Centdian. 123
Proposicion 4.7.4 Si fc(T1; z1) fc (T2; y2) entonces (z1; y2) es el 2--Centdian
de B = (T1; T2).
Demostracion: Sea (z1; z2) el 2--Centdian del 2-bosque B = (T1; T2) y sean
r = fc(B; (z1; z2)) r1 = fc(T1; z1) y r2 = fc(T2; z2).
Si r1 < r2 tomando z10 2 C1 tal que fc(T1; z10 ) = r2, se tiene:
f(B; (z1; z2)) = fc (B; (z1; z2)) + (1 , )fm (B; (z1; z2)) =
= maxffc(T1; z1); fc (T2; z2)g + (1 , )fm (B; (z1; z2)) =
= fc (T2; z2) + (1 , )fm (B; (z1; z2)) =
= fc (T2; z2) + (1 , )[fm(T1; z1) + fm(T2; z2))] >
> fc (T2; z2) + (1 , )[fm(T1; z10 ) + fm (T2; z2))] = f(B; (z10 ; z2))
pues fm(T1; z10 ) < fm (T1; z1). Ademas, dado que fc(T1; z10 ) = fc(T2; z2) = r2, se
tiene:
f(B; (z10 ; z2)) = f(T1; z10 ) + (1 , )fm (T2; z2)
f(T1; z1) + (1 , )fm (T2; z2) = f(B; (z1; z2))
pues f(T1; z1) f(T1; z10 ). Finalmente, dado que fc(T1; z1) fc(T2; y2), se
tiene:
f(B; (z1; z2)) = f(T1; z1) + (1 , )fm (T2; z2)
f(T1; z1) + (1 , )fm (T2; y2) = f(B; (z1; y2))
pues fm (T2; y2) fm (T2; z2).
En otro caso, si r1 r2 se tiene analogamente f(B; (z1; z2)) f(B; (z1; z2))
pues f(T1; z1) f(T1; z1). Finalmente tambien f(B; (z1; y2)) f(B; (z1; z2))
pues fm (T2; y2) fm (T2; z2).
Por tanto en ambos casos f(B; (z1; y2)) f(B; (z1; z2)). 2
Sea rz = maxffc(T1; z1); fc(T2; z2)g y rm = minffc(T1; y1); fc(T2; y2)g.
2. Si fc(B; (z1; z2)) < rz entonces tomando z10 = z1(rz ) y z20 = z2(rz ) se tiene
f(B; (z10 ; z20 )) < f(B; (z1; z2)):
Por tanto, rz r1 = r = r2 rm . 2
Ademas, siguiendo los resultados obtenidos al determinar el conjunto nito
dominante para el p-Centdian, z1 o z2 es un punto de ruptura de la funcion
fc en su arbol respectivo. Si Qi denota al conjunto de puntos de ruptura de
la funcion fc en el camino Ci entonces, los pares de puntos candidatos (z1; z2)
estan formados por un elemento de z1 2 Q1 y z2 = z2(r1(z1)) o por z2 2 Q2 y
z1 = z1(r2(z2)) donde ri(zi) = fc(Ti; zi) y zi(r) es el unico punto zi del camino Ci
tal que fc(Ti; zi) = r.
Luego, el procedimiento para resolver el 2-Centdian en el bosque B = (T1; T2)
propuesto consiste en determinar las Medianas y Centdianes de ambos arboles
y calcular rz y rm. Si rm < rz la solucion es la formada por el Centdian de un
arbol y la Mediana del otro. En otro caso basta recorrer los pares de puntos
(z1; z2(r1(z1))), para z1 2 Q1 y (z1(r2(z2)); z2), para z2 2 Q2 desde z1 = z1 o
z2 = z2 hasta que la pendiente de f(z1(r); z2(r)) cambie de signo.
Dado que las Medianas y Centdianes se obtienen en tiempo O(n) y los tama~nos
de los conjuntos Q1 y Q2 son O(n), la complejidad de todo el procedimiento es
O(n).
Algoritmo de Handler
Paso 1. Sea v un vertice cualquiera.
Paso 2. Sea u el vertice mas alejado a v .
Paso 3. Sea w el vertice mas alejado a u.
Paso 4. El centro x de T es el punto medio del camino de u a w.
Figura 20. Algoritmo de Handler
Algoritmo CDT
Paso 1. Calcular el Centro x del arbol T por medio del algoritmo de Handler.
Paso 2. Calcular la Mediana y del arbol T por medio del algoritmo de Gold-
man.
Paso 3. Calcular la pendiente de la funcion Mediana Dm.
Paso 4. Recorrer los vertices del camino de x a y hasta que:
D = , (1 , )Dm(x) 0;
Figura 22. Algoritmo CDT
4.7. Un algoritmo eciente para el 2--Centdian. 127
Algoritmo 2CDB (caso no ponderado).
Paso 1. (i) Aplicar el algoritmo CDT al arbol T1, para obtener el Centro x1,
la Mediana y1 y el -Centdian z1 de dicho arbol.
(ii) Aplicar el algoritmo CDT al arbol T2, para obtener el Centro x2 , la
Mediana y2 y el -Centdian z2 de dicho arbol.
Paso 2. (i) Si fc(U1; z1) fc (U2; y2) entonces z1 = z1 y z2 = y2.
(ii) Si fc (U2; z2) fc (U1 ; y1) entonces z2 = z2 y z1 = y1.
En otro caso ir al paso 3.
Paso 3. Para cada arbol Ti sea Ci el camino desde zi a yi dado por Ci =
[vi ; vi ; vi ; :::; vi ] donde zi 2 (vi0; vi1] y vini = yi . El algoritmo CDT
0 1 2 n i
proporciona, junto con este camino, las pendientes Dij de fm (Ti ; zi(t))
en la arista [vij ; vij +1], las distancias d(vij ; ui ) donde ui es el vertice de Ti
mas lejano a yi; j = 1; 2; :::; ni y
(i) Inicializacion.
Sea j1 0 y j2 0. Tomar s sj11 + sj22
(ii) Iteraciones.
Mientras s =(1 , ) ejecutar los pasos:
(a) Si d(v1j1 ; u1) d(v2j2 ; u2) entonces: j1 j1 + 1, en otro caso
j2 j2 + 1.
(b) Hacer s sj11 + sj22
(iii) Finalizacion.
Si d(v1j1 ; u1) d(v2j2 ; u2) entonces:
(a) Si j1 = 0 entonces z1 = z1 , en otro caso (j1 > 0) z1 v1j1 .
(b) Sea z2 2 [v2j2 ; v2j2 +1 ] tal que d(z1 ; u1) = d(z2; u2).
En otro caso, (d(v1j1 ; u1) > d(v2j2 ; u2)),
(a) Si j2 = 0 entonces z2 = z2 ; en otro caso (j2 > 0) z2 v2j2 .
(b) Sea z1 2 [v1j1 ; v1j1 +1 ] tal que d(z1 ; u1) = d(z2; u2).
Figura 23. Algortimo 2CDB (caso no ponderado)
i=1 i=1
Por lo tanto, se puede reformular w(j; k) y w0(j; k) como se muestra a conti-
nuacion:
w+ (j; k) = AV (k) , AV (j , 1) , (A(k) , A(j , 1))vj ; (1:1a)
w, (j; k) = ,AV (k) + AV (j , 1) + (A(k) , A(j , 1))vk : (1:1b)
Se sigue de (1.1) que despues de unos pasos previos para calcular A y AV
que consumen un tiempo O(n), tanto w+ (j; k) como w, (j; k) pueden obtenerse
en tiempo constante para un par jado j k: Para resolver el problema del
p-Centdian se utilizan dos funciones recursivas denominadas F (j ) y G(j ) con
j = 1; ::; n: Donde F (j ) es el valor objetivo optimo del subproblema reducido al
conjunto de vertices N j = fvj ; :::; vng y G(j ) es el valor respectivo del mismo
subproblema, siempre que un servicio este en vj :
G(j ) =j<kmin
n+1
f,AV (j , 1) + A(j , 1)vj , A(k , 1)vj + AV (k , 1) + F (k)g:
F (j ) =j<k
minn
fAV (j , 1) , A(j , 1)vk + A(k)vk , AV (k) + G(k)g:
Se dene para j = 1; :::; n;
F 0(j ) = F (j ) + AV (j , 1);
G0(j ) = G(j ) , AV (j ) + A(j )vj :
Entonces las funciones se pueden reescribir como se muestra a continuacion:
G(j ) =j<kmin
n+1
f,A(k , 1)vj + F 0(k)g: (2:2a)
4.9. Conclusiones. 131
F (j ) =j<k
minn
f,A(j , 1)vk + G0(k)g: (2:2b)
Para resolver este sistema de ecuaciones recursivas, considerese la ecuacion
G(j ); donde cada k > j representa un punto en el plano con coordenadas
(A(k , 1); F 0(k)): Un punto k = k(j ) que minimiza la ecuacion G(j ) se corre-
sponde con un punto extremo de la envoltura convexa del conjunto planar de
puntos (A(k , 1); F 0(k)); j < k n + 1: Por esta razon solo es necesario man-
tener estos puntos extremos. Este mnimo de todos ellos es determinado por
el coeciente ,vj : Este coeciente es monotono en j y, por lo tanto, se asume
que la secuencia de puntos mnimos es monotona. Es decir, k(j ) k(j + 1): El
razonamiento es similar para la ecuacion F (j ); pero con los puntos del plano,
(vk ; G0(k)); j k n: La monotona de estos puntos mnimos permite usar pro-
cedimientos estandares de geometra computacional, para construir y mantener
ecientemente la envoltura convexa, cuando j vara de n a 1:
Todos los valores de G(j ) y F (j ), para j = 1; :::; n, son generados en tiempo
lineal. La union entre las dos envolturas convexas es gobernada por las ecuaciones
(2.2a) y (2.2b). Especcamente se comienza con G(n) = F (n), y recursivamente
para j = n , 1; :::; 1 se calcula primero G(j ) y despues F (j ): De esta manera se
concluye que el tiempo total empleado es de O(pn). 2
4.9 Conclusiones.
En este captulo se introduce el problema del Centdian generalizado, adaptando
las propiedades del 1--Centdian al problema del 1--Centdian generalizado, as
como el algoritmo de Halpern.
Respecto al p-Centdian, primero hay que hacer notar que el modelo discreto
en el que el conjunto p-Centdian esta restringido al conjunto de vertices U , puede
solucionarse en un tiempo O(pn4 ). Esto se deduce directamente del hecho de que
en este caso, el conjunto R1, del teorema p-CD-arbol debe incluir el valor optimo
r, y el problema de la p-Mediana r-restringido discreto se puede solucionar en
un tiempo O(pn2); si se utiliza el algoritmo de Tamir (1996) [163]. Tambien se
ha a~nadido un algoritmo alternativo que resuelve el modelo discreto en tiempo
O(np ) para p < 4.
El modelo (continuo) con wi0 = 1; i = 1; :::; n, es solucionable en un tiempo
O(pn5 ). Lo cual se inere del hecho de que el conjunto R1 [ R2 del teorema
p-CD-arbol, incluye el valor optimo r, para este caso R = R1 [ R2.
En el caso especial de la recta real, la complejidad del problema p-Centdian
(continuo y discreto) se reducira a O(pn3 ). Para obtener esta complejidad notese
132
Captulo 4. EL PROBLEMA DEL CENTDIAN EN EL ARBOL.
que el vertice vk , de la denicion del conjunto R3 del teorema p-CD-arbol, debe
coincidir con vi o vj . Por lo tanto, en este caso jR3j = O(n2 ). Ademas, el
problema de la p-Mediana r-restringido puede solucionarse en un tiempo O(pn):
En vista de la relativa alta complejidad O(pn6 ), se plantea la relevante cuestion
de si podra evitarse el explcito calculo de la funcion g(r), para todos lo valores
de r 2 R, denida en el teorema p-CD-arbol. Esto podra ser posible si la funcion
g(r) fuera convexa. Desafortunadamente, no es el caso, como se ilustra con el
siguiente ejemplo.
M+2 e
M+3/2 e
e
5 e
1/2 1 2
133
134
Apendice A. CODIGO DEL 2-CENTDIAN EN UN GRAFO.
USES Dos ;
VertPter = ^Vert;
Vert = Record
Vertice : Vertices;
Next : VertPter;
End;
NodoPter = ^Nodo;
Nodo = Record
Vertice : Vertices;
Long : Real;
Next : NodoPter;
End;
ListaAdy = array[Vertices] of NodoPter;
Punto = Record
vi, vj : Integer;
ti, tj : real;
End;
Solucion = Record
punto1,punto2 : punto;
Radio, suma : real;
Funcion : real
End;
Arista = Record
e1,e2: Vertices ;
Long12 : Real ;
End ;
AristVector = array[Vertices] of Arista ;
Sol,MejorSol : Solucion ;
MejorObj : Real ;
Tiempo,MejorTiempo : Real;
Fuera : AristVector ;
k,Entra : Integer ;
Mejora : Boolean ;
BEGIN
GetTime(h,m,s,c);
cputime := h*3600.0 + m*60. + s + 0.01*c ;
END ;
BEGIN
With Sol
do Begin
writeln (' SOLUCION :');
writeln (' Radio: ', Radio:6:2);
writeln (' Suma : ', Suma:6:2);
writeln (' Funcion lambda-cent-dian: ',funcion:6:2);
With Punto1
do writeln (' Punto 1: p([',vi,',',vj,'],',ti:4:2,').');
With Punto2
do writeln (' Punto 2: p([',vi,',',vj,'],',ti:4:2,').');
end;
Readln;
END ;
136
Apendice A. CODIGO DEL 2-CENTDIAN EN UN GRAFO.
BEGIN
Readln (Datos, nNodos, naristas);
For i := 1 to nNodos
do Adyac[i] := nil; { Inicializa las listas }
For k := 1 to naristas
do Begin
Readln(Datos, i, j, long);
New(Nuevo); {Listas de adyacencia}
Nuevo^.Vertice := j;
Nuevo^.Long := long;
Nuevo^.Next := Adyac[i];
Adyac[i] := Nuevo ;
New(Nuevo); { Listas de adyacencia }
Nuevo^.Vertice := i;
Nuevo^.Long := long;
Nuevo^.Next := Adyac[j];
Adyac[j] := Nuevo ;
End;
END;
BEGIN { DFS }
Visitado[s] := True;
v := Arbol[s];
While v <> nil
do Begin
Grado[s] := Grado[s] + 1;
If Visitado[v^.Vertice] = False Then
Begin
Padre[v^.Vertice] := s;
Dist[v^.Vertice] := Dist[s] + v^.Long;
DFS(v^.Vertice, Arbol, Dist, Padre, Visitado, Grado);
End;
v := v^.Next;
End;
138
Apendice A. CODIGO DEL 2-CENTDIAN EN UN GRAFO.
END; { DFS }
VAR i : Vertices;
BEGIN { DistArbol }
For i := 1 to nNodos
Do Begin { Inicializacion de visitado y grado }
Visitado[i] := False;
Grado[i] := 0 ;
End ;
Padre[s] := s;
Dist[s] := 0 ; { DFS desde el nodo raiz }
DFS(s,Arbol,Dist,Padre,Visitado,Grado) ;
END ; { DistArbol }
BEGIN
DistArbol(s, Arbol, Dist, Padre, Visitado, Grado);
Distmax := 0;
Vertmax := s;
For i := 1 to nNodos
do If visitado[i] then
If (dist[i] > dist[vertmax]) then
Vertmax := i;
Distmax := dist[vertmax];
END;
BEGIN
MasLejos(s, Arbol, t, Dist, Padre, Visitado, Grado, Distmax);
{ Halla el vertice t mas alejado de s.}
MasLejos(t, Arbol, s, Dist, Padre, Visitado, Grado, Distmax);
{ Halla el vertice s mas alejado de t }
{ y la distancia ente s y t. }
Radio := Distmax / 2;
i := s; { Busca el punto medio del camino que une s y t.}
While Dist[Padre[i]] > Radio
do i := Padre[i] ;
With Centro
do Begin
ti := Dist[i] - Radio;
vi := i;
vj := Padre[i];
tj := Radio - Dist[Padre[i]] ;
End ;
END;
BEGIN { MedianaArbol }
DistArbol(Raiz,Arbol,Dist,Padre,Activo,grado) ;
{ Calcula los grados y activos }
nNodosArbol := 0 ;
{ nNodosArbol es el numero de nodos del rbol }
For i := 1 to nNodos
do If Activo[i] Then
nNodosArbol:= nNodosArbol + 1 ;
For i := 1 to nNodos
do If Activo[i] Then { Para la version con pesos no se inicializa }
Pesos[i] := 1 ;
If nNodosArbol = 1 { Hay que tener en cuenta aparte este caso }
Then Begin
Mediana := Raiz ;
Padre[Mediana] := Mediana ;
Pendiente[Mediana] := 0 ;
Exit ;
End ;
Encontrado := False ;
Repeat { Toma una hoja del arbol }
Hoja := Hojas^.Vertice ;
If (Encontrado = False) Then
If ((Pesos[hoja] + Pesos[hoja]) >= nNodosArbol) Then
Begin { La hoja es mediana }
Encontrado := True ;
Mediana := Hoja ;
141
End ;
If Hoja = Raiz Then
Begin { en este caso solo elimina la hoja }
HojaPter := Hojas ;
Hojas := Hojas^.Next ;
Dispose(HojaPter) ;
End
Else
Begin
Pesos[Padre[hoja]] := pesos[padre[hoja]] + pesos[hoja];
Grado[Padre[hoja]] := grado[padre[hoja]] - 1;
If Grado[Padre[hoja]] = 1 Then
Hojas^.vertice := Padre[hoja]{ el padre de la hoja pasa }
Else { a ser una nueva hoja }
Begin
HojaPter := Hojas ; { desaparece la hoja y no }
Hojas := Hojas^.Next ; { aparece ninguna nueva }
Dispose(HojaPter) ;
End ;
End ;
Until Hojas = Nil ;
{ Se le da la vuelta al camino de la mediana a la raiz }
{ determinando el nuevo vector Padre[.] para que quede }
{ la mediana como raiz del arbol }
j1 := Mediana ;
j2 := Padre[j1] ;
j3 := Padre[j2] ;
While j1 <> Raiz { Reasignacion de enlaces }
do Begin { <--- j3 <--- j2 <--- j1 }
Padre[j2] := j1 ; { <--- j3 j2 ---> j1 }
j1 := j2 ;
j2 := j3 ; { j3 j2 j1 }
j3 := Padre[j2] ; { j3 j2 j1 }
End ;
Padre[Mediana] := Mediana ;
BEGIN { CentDianArbol }
x := lambda/(1-lambda) ;
With Centro
do If DistMediana[vi] < DistMediana[vj]
{ v es un extremo de la arista }
Then v := vj { que contiene al centro, el }
Else v := vi ; { mas alejado a la mediana }
END; { CentDianArbol }
BEGIN
Suma := 0.0 ; { Calcula las distancias desde p }
With p { a los vertices del arbol de p }
do Begin
DistArbol(vi,Arbol,Dist1,Padre,Visitado,Grado) ;
144
Apendice A. CODIGO DEL 2-CENTDIAN EN UN GRAFO.
DistArbol(vj,Arbol,Dist2,Padre,Visitado,Grado) ;
For i := 1 to nNodos
do If visitado[i] Then
If ti+ Dist1[i] < tj + Dist2[i] Then
Suma := Suma + ti + Dist1[i]
Else
Suma := Suma + tj + Dist2[i] ;
End ;
SumaMediana := Suma ;
END ;
VAR
Lejos1,Lejos2 : Vertices ;
CentDian1,CentDian2,
Centro1,Centro2,p : punto ;
Mediana1,Mediana2 : Vertices ;
Pendiente1,Pendiente2 : IVector ;
RadioCentro1,RadioCentro2 : real ;
RadioMediana1,RadioMediana2 : real ;
RadioCentDian1 : Real ;
RadioCentDian2 : real ;
v10,v20,v1,v2,i : Vertices;
Dist1,Dist2 : RVector ;
Visitado1,Visitado2 : BVector ;
Padre1,Padre2 : IVector ;
x : Real ;
BEGIN { DosCDBosque }
CentDianArbol(s1, Bosque,
CentDian1, RadioCentDian1,
Centro1, RadioCentro1,
145
Mediana1, RadioMediana1,
Pendiente1, Dist1, Padre1, Lejos1) ;
CentDianArbol(s2, Bosque,
CentDian2, RadioCentDian2,
Centro2, RadioCentro2,
Mediana2, RadioMediana2,
Pendiente2, Dist2, Padre2, Lejos2) ;
v1 := v10 ;
v2 := v20 ;
x := lambda/(1-lambda) ;
{ Se van moviendo los dos vertices v1 y v2 }
{ hacia sus medianas m1 y m2 hasta que }
{ la pendiente cambia de signo }
{ En cada caso se mueve el de menor radio }
While Pendiente1[v1] + Pendiente2[v2] > x
do If RadioMediana1-Dist1[Padre1[v1]] <
RadioMediana2-Dist2[Padre2[v2]]
Then v1 := Padre1[v1]
Else v2 := Padre2[v2] ;
Punto2.ti := (RadioMediana1-Dist1[v1])
- (RadioMediana2-Dist2[v2]) ;
148
Apendice A. CODIGO DEL 2-CENTDIAN EN UN GRAFO.
Punto2.tj := (RadioMediana2-Dist2[Padre2[v2]])
- (RadioMediana1-Dist1[v1]);
Radio := RadioMediana1-Dist1[v1] ;
Suma := SumaMediana(Punto1,Arbol)
+ SumaMediana(Punto2,Arbol) ;
Punto1.ti := (RadioMediana2-Dist2[v2])
- (RadioMediana1-Dist1[v1]) ;
Punto1.tj := (RadioMediana1-Dist1[Padre1[v1]])
- (RadioMediana2-Dist2[v2]) ;
Radio := RadioMediana2-Dist2[v2] ;
Suma := SumaMediana(Punto1,Arbol)
+ SumaMediana(Punto2,Arbol) ;
Funcion := lambda * Radio + (1 - lambda) * Suma ;
End ;
END; { DosCDBosque }
BEGIN
p := Arbol[e1];
If p^.vertice = e2 Then{ es el primero en la lista de adyacencia }
Begin
Arbol[e1]:= p^.next ;
149
Dispose(p);
End
Else Begin { NO es el primero en la lista de adyacencia }
while p^.vertice <> e2
do Begin
q := p ;
p := p^.next ;
End ;
long := p^.long ;
q^.next := p^.next;
dispose(p);
End ;
p := Arbol[e2];
If p^.vertice = e1 Then{ es el primero en la lista de adyacencia }
Begin
Arbol[e2]:= p^.next ;
Dispose(p);
End
Else Begin { NO es el primero en la lista de adyacencia }
while p^.vertice <> e1
do Begin
q := p ;
p := p^.next ;
End ;
long := p^.long ;
q^.next := p^.next;
dispose(p);
End ;
END ; { QuitaArista }
BEGIN
new(nuevo);
nuevo^.vertice := e2;
nuevo^.long := long;
nuevo^.next := Arbol[e1] ;
Arbol[e1] := Nuevo ;
150
Apendice A. CODIGO DEL 2-CENTDIAN EN UN GRAFO.
new(nuevo);
nuevo^.vertice := e1;
nuevo^.long := long;
nuevo^.next := Arbol[e2] ;
Arbol[e2] := Nuevo ;
END ;
PROCEDURE DosCDArbol (
Var Arbol : ListaAdy ;
Pesos : IVector;
Var MejorSol : Solucion );
v1,v2 : Vertices ;
vList,v2Item,v2Lista,
item,item1 : VertPter ;
e : NodoPter;
Long : Real ;
Centro1,CentDian1 : Punto ;
RadioCentDian1, RadioCentro1, RadioMediana1 : Real ;
Pendiente1 : IVector ;
Padre1 : IVector ;
Mediana1,Lejos1: Vertices ;
Dist1 : RVector ;
BEGIN { DosCDArbol }
MejorSol.funcion := Infin ;
151
MedianaArbol(1, Arbol, pesos, PadreMed, Mediana) ;
v2Item := v2Lista ;
Repeat
v2 := v2Item^.vertice ;
QuitaArista(v1,v2,Arbol,long) ;
Radio1 := RadioCentDian1 ;
suma1 := SumaMediana(CentDian1 , Arbol) ;
152
Apendice A. CODIGO DEL 2-CENTDIAN EN UN GRAFO.
Funcion1 := lambda * radio1 + (1 - lambda) * suma1;
PoneArista(v1,v2, Arbol,long) ;
item := vList ;
153
vList := vList^.next ;
Dispose(item) ; { Se elimina elemento de la lista vList }
END ; { DosCDArbol }
PROCEDURE Mueve(
Var Arbol : ListaAdy;
Var Fuera : AristVector ;
Var MejorSol : Solucion );
{ HEURISTICA ANSIOSA-GREEDY }
{ Usa el Movimiento ADD-DROP }
{ Selecciona la arista entrante }
{ con la regla el primero mejor }
{ y despues la arista saliente }
{ con la regla el mejor primero }
BEGIN
MejorObj := MejorSol.Funcion ;
InicObj := InicSol.Funcion ;
If (Entra < 1) or (Entra > nAristas-nNodos+1) Then
Entra := 1 ;
InicEntra := Entra ;
Repeat
v1 := Fuera[Entra].e1 ;
v2 := Fuera[Entra].e2 ;
Lv12 := Fuera[Entra].Long12 ;
QuitaArista(v1,v2, Arbol,Lv12 ) ;
Entra := Entra + 1 ;
If (entra > nAristas-nNodos+1) Then
entra := 1 ;
Until Entra = InicEntra ;
END ;
BEGIN (* SEMI-PRIM *)
For i := 1 to nNodos { Inicializaciones }
do Begin
Level[i] := MaxInt;
Dentro[i] := False ;
NumEnlaces[i] := 0 ;
End ;
s := 1 ; { La raiz es 1 }
Level[s] := 0;
Padre[s] := s ;
New(ListaEntra) ; { Lista de vertices a entrar }
With ListaEntra^
do Begin
Vertice := s ;
Next := Nil ;
End ;
UltimoEntra := ListaEntra ;
For k := 1 to nNodos
do Begin (* ITERATION *)
156
Apendice A. CODIGO DEL 2-CENTDIAN EN UN GRAFO.
i := ListaEntra^.Vertice ; { Entra el primer vertice de la lista }
Dentro[i] := True ;
Edge := Grafo [i];
While Edge <> Nil
do Begin
j := Edge^.Vertice ; { Con los adyacentes al vertice entrante }
If Dentro[j] = False Then { que no hayan entrado }
Begin { IF-1 }
If Level[j] = MaxInt Then
Begin { Si no hay ningun enlace se conecta a i }
Level[j] := Edge^.Long ;
Padre[j] := i ;
NumEnlaces[j] := 1 ;
New(ItemEntra) ;
With ItemEntra^
do Begin
Vertice := j ;
Next := Nil ;
End ;
UltimoEntra^.Next := ItemEntra ;
UltimoEntra := ItemEntra ;
End
Else
Begin
NumEnlaces[j] := NumEnlaces[j] + 1 ;
If Random < 1.0/NumEnlaces[j]
{ Si hay ya hay enlaces }
Then Beginm { con esta probabilidad el enlace es i }}
Level[j] := Edge^.Long ;
Padre[j] := i ;
End ;
End ;
End ; { IF-1 }
Edge := Edge^.Next;
End; { ENDWHILE }
ItemEntra := ListaEntra ;
ListaEntra := ListaEntra^.Next ;
Dispose(ItemEntra) ;
End { Iteracion };
{ Creacion de las listas de adyacencia del arbol }
For i := 1 to nNodos
do Arbol[i] := nil; { Inicializa las listas }
157
For i := 1 to nNodos
do For j := 1 to nNodos
do If (i <> j) Then
If Padre[j] = i Then
Begin
New(Nuevo); {Listas de adyacencia}
Nuevo^.Vertice := j;
Nuevo^.Long := Level[j];
Nuevo^.Next := Arbol[i];
Arbol[i] := Nuevo ;
END ; { SEMI-PRIM }
BEGIN
Writeln('Grafo:');
For i := 1 to nNodos
do Begin
Write(i:3,': ');
e := Grafo[i] ;
Repeat
Write(e^.Vertice:3);
e := e^.Next ;
Until e = Nil ;
Writeln;
End ;
END ;
LeerDatos( Grafo,Pesos) ;
Lambda := 0.8 ;
For k := 1 to nNodos do
pesos[k] := 1;
randomize ;
Tiempo := cputime;
TotalMejorSol.Funcion := MaxLongInt ;
MejorSol.Funcion := MaxLongInt ;
Repeat
159
SemiPrim (Grafo, Arbol, Fuera ) ;
DOSCDARBOL ( Arbol, Pesos , MejorSol );
Sol := MejorSol ;
Repeat
Mueve(Arbol,Fuera,Sol) ;
If Sol.Funcion < MejorSol.Funcion Then
Begin
Mejora := True ;
MejorSol := Sol ;
Mejortiempo := cputime - tiempo ;
Writeln ('MEJOR SOLUCION :');
EscribeSolucion(Sol) ;
Writeln(' Mejor Tiempo: ',Mejortiempo:8:2,' segundos');
Writeln('Pulsa Return'); Readln ;
End
Else Mejora := False ;
Until Not Mejora ;
If Sol.Funcion < TotalMejorSol.Funcion Then
Begin
TotalMejorSol := Sol ;
Mejortiempo := cputime - tiempo ;
Writeln ('MEJOR SOLUCION :');
EscribeSolucion(Sol) ;
Writeln(' Mejor Tiempo: ',Mejortiempo:8:2,' segundos');
Writeln('Pulsa Return'); Readln ;
End ;
Writeln(Salida,MejorSol.funcion:6:2,Mejortiempo:6:2);
Writeln(MejorSol.funcion:6:2,Mejortiempo:6:2);
Close (Datos);
Close (Salida) ;
END.
Apendice B
CO DIGO DE LA HEURISTICA
VNDS.
* Variable Neighbourhood Decomposition Search (VNDS)
* for p-median problem of the vertex set of a graph.
* ---------------------------------------------------------------------
* Authors: Pierre Hansen, Nenad Mladenovic and Dionisio Perez Brito
* ---------------------------------------------------------------------
*
* Data:
* -----
* n - number of vertices
* p - number of medians
* d - distance matrix
*
* Variables:
* ----------
* m(j) - median where vertex j is assigned (solution)
* f - solution value obtained by this heuristic
*
* Auxiliary Variables:
* ----------------------
* x(j) - solution
* m(j) - median
* s(j) - second median
*
161
162
Apendice B. CODIGO DE LA HEURISTICA VNDS.
* ----------------------------------------------------------------
integer n,p
real d(6000,6000)
real*8 seed
* ----------------------------------------------------------------
*
write(*,*)'Enter: "1" for solving SINGLE problem'
write(*,*)' "2" for ORLIB test problems'
read(*,*)input
if(input.eq.1)then
read(*,*) n,p,d
else
write(*,*)' Enter file '
read(*,*) n,p,d
endif
*
* CONSTANTS:
* ------------------------------------ seed for pseudo-random numbers
seed=21.d+00
big=1.e20
*
* Stop parameters:
* ----------------
MaxNoImpIt = 1000
* -------------------------- Max. Number of No Improvement Iterations
MaxItInt = 10000
* ----------------------------- Max. Number of Interchange Iterations
maxitVNS = 1000000
* ------------------------------------- Max. Number of VNS Iterations
maxitVNDS = 100000
* ------------------------------------ Max. Number of VNDS Iterations
kmaxVNS = p
* ------------------------------------------- Max. value of k for VNS
kmaxVNDS = p
* ------------------------------------------ Max. value of k for VNDS
kmaxMC-VNS = 2
* ---------------------------------------- Max. value of k for MC-VNS
*
call VNDS(f,x,m,s,d,n,p,MaxTimeVNDS,MaxTimeVNS,TotalVNDS)
stop
end
*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
163
subroutine InitSol(f,x,m,s,d,n,p)
* --------------------------------------------------- Random Solution
real d(6000,6000)
integer m(6000),s(6000),x(6000),p,n
* --------------------------------------
do j=1,n
x(j)=j
enddo
do j=1,p
i=j+(n-j)*GGUBFS(seed)
xj=x(j)
x(j)=x(i)
x(i)=xj
enddo
call FindMedian(x,m,d,n,p)
* --------------------------------------- Compute the objective value
f=0.
do i=1,n
f=f+d(x(i),m(x(i)))
enddo
call FindSecond(x,m,s,d,n,p)
return
end
*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subroutine FindMedian(x,m,d,n,p)
integer m(6000),x(6000),p,n
real d(6000,6000)
* ----------------------------------------- Find the median for users
do i=1,n
xi=x(i)
dmin=1.e20
do j=1,p
xj=x(j)
if(d(xi,xj).lt.dmin)then
dmin=d(xi,xj)
m(xi)=xj
endif
enddo
enddo
return
end
*
164
Apendice B. CODIGO DE LA HEURISTICA VNDS.
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subroutine FindSecond(x,m,s,d,n,p)
integer m(6000),s(6000),x(6000),p,n
real d(6000,6000)
* ------------------------------------- Find second medians of users
do i=1,n
xi=x(i)
dmin=1.e20
do j=1,p
xj=x(j)
if(xj.ne.m(xi))then
if(d(xi,xj).lt.dmin)then
dmin=d(xi,xj)
s(xi)=xj
endif
endif
enddo
enddo
return
end
*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subroutine MedianOut(dif,x,m,s,d,n,p,xin,jout)
integer m(6000),s(6000),x(6000),p,n
real d(6000,6000),v(6000)
* ------------------------------------ Find the best going-out median
dif=0.
do j=1,p
v(x(j))=0.
* -------------------------------- v(x) the difference if x goes out
enddo
do i=1,n
xi=x(i)
if(d(xi,xin).lt.d(xi,m(xi)))then
dif=dif+d(xi,xin)-d(xi,m(xi))
else
mxi=m(xi)
if(d(xi,xin).lt.d(xi,s(xi))then
v(mxi)=v(mxi)+d(xi,xin)-d(xi,mxi)
else
v(mxi)=v(mxi)+d(xi,s(xi))-d(xi,mxi)
endif
endif
165
enddo
difmin=1.e20
do j=1,p
xj=x(j)
if(v(xj).lt.difmin)then
difmin=v(xj)
jout=j
endif
enddo
dif=dif+difmin
return
end
*
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subroutine Update(x,m,s,d,n,p,xin,jout)
real d(6000,6000)
integer m(6000),s(6000),x(6000),p,n
* ----------------------------------- Update medians and second medians
xout=x(jout)
do i=1,n
xi=x(i)
if(m(xi).eq.xout)then
* --------------------------------------- x(i) loses its median
if(d(xi,xin).lt.d(xi,s(xi)))then
* ------------------------------- x_in will be the its median
m(xi)=xin
else
* ---------------------- the second median will be its median
m(xi)=s(xi)
* --------------------------------- find the second median
s(xi)=xin
dmin=d(x(i),xin)
do j=1,p
xj=x(j)
if(xj.ne.m(xi))then
if(xj.ne.xout)then
if(d(xj,xi).lt.dmin)then
dmin=d(xj,xi)
s(xi)=xj
endif
endif
endif
enddo
166
Apendice B. CODIGO DE LA HEURISTICA VNDS.
endif
else
* -------------------------------- x(i) does NOT lose its median
if(d(xi,xin).lt.d(xi,m(xi)))then
* ----------------------------------- x_in will be the median
s(xi)=m(xi)
m(xi)=xin
else
if(d(xi,xin).lt.d(xi,s(xi)))then
* ------------------------- x_in will be the second median
s(xi)=xin
else
* --------------------------- x(i) loses its second median
if(s(xi).eq.xout)then
s(xi)=xin
dmin=d(x(i),xin)
do j=1,p
xj=x(j)
if(xj.ne.m(xi))then
if(xj.ne.xout)then
if(d(xj,xi).lt.dmin)then
dmin=d(xj,xi)
s(xi)=xj
endif
endif
endif
enddo
endif
endif
endif
endif
enddo
return
end
*
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subroutine Shake(f,x,m,s,d,n,p,k)
real d(6000,6000)
integer m(6000),s(6000),x(6000),p,n
* ---------------------------------------
fold=f
do k=1,k
goin=p+1+(n-p)*GGUBFS(seed)
167
* ------------------------------------- a random vertex goes in
xin=x(goin)
call MedianOut(dif,x,m,s,d,n,p,xin,jout)
* ------------------------------------ the best median goes out
call Update(x,m,s,d,n,p,xin,jout)
x(goin)=x(jout)
x(jout)=xin
f=f+dif
if(f.lt.fold)then
return
enddo
return
end
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subroutine InterCh(f,x,m,s,d,n,p)
real d(6000,6000)
integer m(6000),s(6000),xcur(6000),p,n
* ------------------------- Initialization with the input solution
fcur=fopt
ItInter=0
bestiter=1
* ----------------------------------------------------- Iterations
do while(ItInter.le.maxitInt)
ItInter=ItInter+1
* ------------------- Get the best solution in the 1-neighbourhood
difmin=1.e20
do i=p+1,n
xin=x(i)
call MedianOut(dif,x,m,s,xin,jout,d,n,p)
if(dif.lt.difmin)then
difmin=dif
goin=i
goout=jout
endif
enddo
* ----------------------------------- If no improvement, return
if(Dif.ge.0)then
bestiter=IterInter
return
endif
* ----------------------------------------- If improved, update
f=f+fdif
168
Apendice B. CODIGO DE LA HEURISTICA VNDS.
xin=x(goin)
call Update(x,m,s,xin,goout,d,n,p)
x(goin)=x(goout)
x(goout)=xin
enddo
bestiter=iterInter
return
end
*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Variable Neighbourhood Search (VNS)
* ------------------------------------
subroutine VNS(fopt,xopt,mopt,sopt,d,n,p,time,MaxTimeVNS,se)
real d(6000,6000)
integer xopt(6000),xcur(6000),p,n
* ------------------------------------- Initialization of counters
iterVNS=0
kfirst=1
kstep=1
bestiterVNS=1
time=0.
* ---------------------------------- Start with the input solution
fcur=fopt
do i=1,n
xi=xopt(i)
mcur(xi)=mopt(xi)
scur(xi)=sopt(xi)
xcur(i)=xopt(i)
enddo
* ----------------------------------------------------- Main step
do while(iterVNS.le.maxitVNS)
kinter=kfirst
do while(kinter.le.kmaxVNS)
iterVNS=iterVNS+1
* ----------------------------- Shake in the k-th neighbourhood
call Shake(fcur,xcur,mcur,scur,d,n,p,kinter)
call InterCh(fcur,xcur,mcur,scur,d,n,p)
if(fcur.lt.fopt)then
* ------------------ If improved start with first neighbourhood
bestiterVNS=iterVNS
fopt=fcur
do i=1,n
xi=xcur(i)
169
mopt(xi)=mcur(xi)
sopt(xi)=scur(xi)
xopt(i)=xcur(i)
enddo
kinter=kfirst
else
* ------------------- If no improved increase the neighbourhood
fcur=fopt
do i=1,n
xi=xopt(i)
mcur(xi)=mopt(xi)
scur(xi)=sopt(xi)
xcur(i)=xopt(i)
enddo
kinter=kinter+kstep
endif
* -------------------------------------------------- Stopping Criteria
if(iterVNS-bestiterVNS.gt.MaxNoImpItVNS)return
if(time-InitTimeVNS.gt.MaxTimeVNS)return
enddo
enddo
return
end
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subroutine Decompose(fd,xd,md,sd,d,nd,pd,merged
* f, x, m, s, n, p)
real d(6000,6000)
integer x(6000),xd(6000),m(6000),md(6000),s(6000),sd(6000)
integer p,pd,n,nd,merged(6000)
logical*1 merged(6000)
* ---------------------------- select "pd" indeces between 1 and p
do i=1,p
merged(i)=i
enddo
do i=1,pd
j=i+(p-i)*GGUBFS(seed)
xx=merged(i)
merged(i)=merged(j)
merged(j)=xx
enddo
do i=1,p
merging(i)=.false.
170
Apendice B. CODIGO DE LA HEURISTICA VNDS.
enddo
do i=1,pd
merging(merged(i))=.true.
enddo
* ---------------------- merging the "pd" clusters with true value
k=0
fd=0.
do i=1,n
xi=x(i)
if(merging(m(xi))) then
k=k+1
fd=fd+d(m(xi),xi)
xd(k)=xi
md(xi)=m(xi)
sd(xi)=s(xi)
endif
enddo
nd=k
call FindSecond(xd,md,sd,d,nd,pd)
return
end
*
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subroutine VNDS(f,x,m,s,d,n,p,se,MaxTimeVNDS,MaxTimeVNS,TotalTime)
* -------------------------------------------------------------------
integer m(6000),s(6000),x(6000),pos(6000),p,n
real d(6000,6000)
* ----------------------- Initial solution obtained by INTERCHANGE
* (only to find total CPU time 'MaxTimeVNS')
call INSOL(f,x,m,s,d,n,p)
t0=time
call InterCh(f,x,m,s,d,n,p)
t0=time-t0
MaxTimeVNDS=t0
t0=t0/1.5
MaxTimeVNS=t0
* --------------------- Initial solution obtained by Monte-Carlo VNS
call INSOL(f,x,m,s,d,n,p)
call VNS(f,x,m,s,d,n,p,MaxTimeVNS)
* ------------------------------------------ Save initial solution
fcur=f
fopt=f
do i=1,n
171
xi=x(i)
mopt(xi)=m(xi)
sopt(xi)=s(xi)
xopt(i)=x(i)
enddo
* --------------------------------------- Constants and paremeters
iterVNDS = 0
kstep = 1
kfirst = 1
* ----------------------------------------------------- Main loop
do while(iterVNDS.le.maxitVNDS)
kdec=kfirst
* ---------------------------- Merging and solving subproblems
do while(kdec.lt.kmaxVNDS)
iterVNDS=iterVNDS+1
TimeInitVNDS=time
pd=kdec
call Decompose(fd,xd,md,sd,d,pd,nd,merged,x,m,s,f,n,p)
fold=fd
do i=1,n
pos(x(i))=i
enddo
call VNS(fd,xd,md,sd,d,nd,kdec,t0)
fcur=fopt+fd-fold
do j=1,pd
call Update(x,m,s,xd(j),merged(j),d,n,p)
x(pos(xd(j))=x(merged(j))
x(merged(j))=xd(j)
enddo
if(fd.lt.fold)then
kdec=kfirst
fopt=f
do i=1,n
xi=x(i)
mopt(xi)=m(xi)
sopt(xi)=s(xi)
xopt(i)=x(i)
enddo
else
kdec=kdec+kstep
f=fopt
do i=1,n
xi=x(i)
172
Apendice B. CODIGO DE LA HEURISTICA VNDS.
m(xi)=mopt(xi)
s(xi)=sopt(xi)
x(i)=xopt(i)
enddo
endif
if(time.gt.,MaxTimeVNDS)then
fopt=0.
do j=p+1,n
fopt=fopt+d(x(j),m(x(j)))
enddo
return
endif
enddo
enddo
f=fopt
return
end
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* IMSL random number generator
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
real function GGUBFS(dseed)
real*8 dseed,d2p31m,d2p31
data d2p31m/2147483647.d0/,d2p31/2147483648.d0/
dseed=dmod(16807.d0*dseed,d2p31m)
ggubfs=dseed/d2p31
return
end
*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Input disimilarities
*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Apendice C
LISTA DE SIMBOLOS.
A continuacion se encuentra una lista de los principales smbolos que aparecen
en el texto. En la primera de las columnas se muestra el smbolo y en la segunda
una peque~na descripcion del mismo.