segurida industrial

Optimizaci´n de rutas de evacuaci´n
o
o
Manuel Abellanas

†

Gregorio Hern´ndez
a

∗

‡

Resumen
En este trabajo se resuelven varios problemas de optimizaci´n geom´trica relacionados con el
o
e
dise˜o de rutas que se desea que est´n pr´ximas a un conjunto de puntos del plano. Se resuelve el
n
e
o
problema b´sico de encontrar una ruta de desviaci´n m´
a
o
ınima y variosproblemas de optimizaci´n
o
multicriterio, en los que adem´s de buscar rutas de desviaci´n m´
a
o
ınima, se busca satisfacer otros
requisitos: longitud m´
ınima, desviaci´n m´
o
ınima en cada punto, unimodalidad de la desviaci´n o
o
giro total m´
ınimo.

1

Introducci´n
o

En el traslado en ambulancia de una localidad a otra de un enfermo que requiere atenci´n especial,
o
esconveniente elegir una ruta en la que haya cerca un hospital en todo momento 1 . Una ruta que
cumpla este requisito diremos que es una ruta segura. En este trabajo presentamos varios problemas de
optimizaci´n geom´trica relacionados con el dise˜o de rutas seguras. Supongamos que existen n puntos
o
e
n
en el plano que calificaremos de seguros. Si tenemos que desplazarnos de un punto seguro A aotro B,
estamos interesados en que el camino por el que nos desplazamos se aleje lo menos posible del conjunto
de puntos seguros S. Definiremos la desviaci´n de un camino respecto a un conjunto de puntos S y
o
la desviaci´n m´
o
ınima asociada a un par de puntos A y B de S. Veremos que existen muchos caminos
de desviaci´n m´
o
ınima y c´mo encontrar alguno. Entre los caminos de desviaci´n m´o
o
ınima, tiene inter´s
e
buscar aquellos que optimicen alguna otra condici´n. En la secci´n 3 consideramos varios casos. Entre
o
o
ellos, el camino de desviaci´n m´
o
ınima de m´
ınima longitud, que es el camino m´s corto que no se desv´
a
ıa
m´s de lo necesario de S, o el camino de m´
a
ınima desviaci´n en cada punto, que es el m´s seguro en todo
o
a
momento. Estos problemasson, por tanto, de optimizaci´n multicriterio. En general estos problemas
o
son d´
ıficiles, pues incluso con s´lo dos criterios a optimizar ya hay muchos NP-completos. Por ejemplo,
o
Arkin et al. demuestran en [1] que encontrar un camino de longitud m´
ınima en un entorno poligonal
respecto de dos m´tricas distintas Lp y Lq es NP-duro. En [8] se pueden encontrar m´s problemas
e
ageom´tricos multicriterio.
e
La planificaci´n de rutas es uno de los problemas m´s estudiados en el ´rea de Localizaci´n de
o
a
a
o
servicios (Facility location). Usualmente se plantean casos discretos en los que el espacio de trabajo
se reduce a un grafo finito, pero tambi´n hay resultados en el caso continuo. Por ejemplo, las rutas
e
de minimizaci´n de riesgo para el transporte de mercanc´peligrosas, (D´ et al. [2] y Erkurt y
o
ıas
ıaz
Verter [3]), en las que se desea maximizar la m´
ınima distancia de los puntos del camino a los puntos
de un conjunto S (lugares habitados o puntos de demanda). Otro problema estudiado es el Maximum
Concealment Path (Gewali et al. [7]) en el que se buscan rutas en un entorno poligonal del plano que
minimicen la longitud de los tramos del caminoque son visibles desde los puntos de un conjunto S de
”enemigos”.
Dado un conjunto de puntos S en el plano, los lugares ”seguros”, y un par de puntos A y B de S,
queremos obtener un camino entre A y B que no se aleje demasiado de los puntos de S. Precisamos a
continuaci´n esta noci´n de cercan´
o
o
ıa.
∗ Parcialmente

subvencionado por CAM P-DPI-000235-0505 (Gatarvisa).
de Inform´tica,Universidad Polit´cnica de Madrid, mabellanas@fi.upm.es
a
e
‡ Facultad de Inform´tica, Universidad Polit´cnica de Madrid, gregorio@fi.upm.es
a
e
1 Se dan casos. Dedicado a Bel´n Palop y Manuel Aguilar
e
† Facultad

Definici´n 1.1. Llamamos desviaci´n de un punto z del plano con relaci´n a S a la m´
o
o
o
ınima distancia
de z a los puntos de S.
dev(z, S) = min{dist(z, x)/x ∈ S}...