optimización de las operaciones en el servicio logístico
TRANSCRIPT
1
Optimización de las Operaciones en el Servicio Logístico de Ambulancias: Localización,
Despacho y Relocalización.
S. Santa*, N. Velascoa, C. Amayab
Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia
* Estudiante de Maestría del Departamento de Ingeniería Industrial, Universidad de los Andes,
Bogotá, Colombia a,b
Profesor Asistente del Departamento de Ingeniería Industrial, Universidad de los Andes,
Bogotá, Colombia
Resumen: La logística del servicio de ambulancias involucra la solución de problemas que van
desde un nivel estratégico como la localización de ambulancias, hasta un nivel operacional
como el despacho de las mismas ante un incidente y la posible relocalización para lograr un
mejor alistamiento en futuros incidentes. Existen medidas de desempeño que permiten
evaluar si las decisiones tomadas en esos procesos estratégicos y operacionales son correctas,
por lo que se define la preparación como un indicador que permite definir qué tan bien está
preparada una ciudad para responder de manera eficiente ante incidentes que se presenten.
En este trabajo se presenta la definición del índice de preparación, un algoritmo genético que
permite localizar las ambulancias en la ciudad teniendo en cuenta dicho índice, un algoritmo
de despacho para definir qué ambulancias deben atender los incidentes y finalmente un
modelo matemático que permite decidir una posible relocalización de ambulancias para
mejorar la preparación que pudo ser afectada luego de realizarse el despacho. La metodología
propuesta es probada en instancias a escala de la ciudad de Bogotá que varían de acuerdo al
número de puntos de demanda.
Palabras claves: Servicios de emergencia médica, ambulancia, localización, relocalización,
modelo dinámico.
Keywords: Emergency Medical Services, Ambulance, Location, Dispatch, Reallocation dynamic
model.
1. INTRODUCCIÓN
La atención médica es un derecho fundamental de cualquier ser humano. En las ciudades, la
red de atención de salud incluye actividades de atención pre-hospitalaria que se encargan de
asistir al paciente en la estabilización de sus signos vitales, definición de la conducta médica
pertinente y traslado a una institución prestadora del servicio de salud de ser necesario [1]. En
el sistema de atención pre-hospitalaria se encuentra el servicio de ambulancia el cual es una
de las principales herramientas del gobierno para apoyar situaciones de urgencias,
emergencias y desastres. El servicio de ambulancias es la atención médica fuera-del-hospital
de una persona incluyendo posible transporte [17].
En el afán de mejorar y fortalecer el servicio de emergencia médica y transporte de pacientes,
el sistema de ambulancias presenta la oportunidad desde el punto de vista logístico [2], de
2
obtener diferentes beneficios tales como reducir el tiempo de respuesta, el costo de operación,
mejorar la utilización de la información, entre otros [21]. El sistema logístico de ambulancias
comprende tópicos neurálgicos que van desde un nivel estratégico hasta un nivel operacional
como se muestra en la Figura 1. La solución de problemas a nivel estratégico permite tomar
decisiones sobre la planeación del servicio y se evalúan temas como el diseño de rutas y la
localización de ambulancias en diferentes puntos de la ciudad. Por el contrario, resolver
problemas operacionales, logra un proceso eficiente en problemas como la asignación de
ambulancias según los incidentes ocurridos y la relocalización de las mismas.
Figura 1. Problemas estratégicos y operacionales de la logística de ambulancias
Las estrategias del Sistema Logístico de Ambulancias trazan parámetros para definir rutas de
acción de manera global y no contempla los cambios que ocurren en diversos factores a lo
largo del día, semana o períodos de tiempo específico. La localización – de tipo estratégico -
contempla encontrar puntos base en los cuales las ambulancias son ubicadas en un momento
del día teniendo en cuenta medidas que evalúan el desempeño de la decisión. Las tácticas
desde el punto de vista operacional se encaminan a encontrar soluciones dinámicas que se
adaptan fácilmente ante modificaciones en las características del entorno. La relocalización,
por ejemplo, permite evaluar si algunas ambulancias que no fueron asignadas a incidentes
deberían realizar un cambio de base con el objetivo de tener tiempos de respuesta menores y
aumentar la cobertura de demanda que pudo haberse visto afectada por la salida de
ambulancias durante el proceso de asignación.
La logística de ambulancias es relevante y sus decisiones son de alto impacto ya que por
ejemplo ciudades como Bogotá, cuentan con Centros Reguladores de Urgencias y Emergencias
(CRUE) para coordinar la atención y resolución de estas situaciones y buscar la promoción,
prevención, investigación, educación y desarrollo del talento humano para optimizar la
prestación del servicio [3]. Actualmente, en la ciudad de Bogotá el CRUE atiende
mensualmente 16.000 casos aproximadamente en los cuales se debe realizar un despacho de
ambulancia al lugar de la emergencia. Según Huertas [4], la asignación y despacho de
ambulancias se realiza evaluando la importancia del incidente y las ambulancias más cercanas
al lugar del incidente por una persona encargada en el momento de registro de la llamada.
El tiempo base de respuesta de una ambulancia es de 15 minutos [5] hasta el lugar del
incidente, pero según el Plan de Desarrollo de Gobierno 2008-2012 de Bogotá, este tiempo
debe reducirse en 5 minutos para así fortalecer el sistema de red de urgencias de la ciudad [5].
3
En el 90% de los casos de despacho de ambulancia, el tiempo de arribo es de 26,65 minutos lo
que sugiere la necesidad de hacer cambios en la utilización y aprovechamiento de los recursos.
La localización ha sido un tema ampliamente estudiado en la literatura. Diferentes autores han
desarrollado modelos definidos para sistemas donde se tienen ambulancias homogéneas
[9,14,22,23,24], así como modelos probabilísticos que pueden estimar la fracción de ocupación
de una ambulancia [25,26,27,28] han permitido encontrar soluciones eficientes –número de
ambulancias necesitadas, puntos de localización- para el sistema logístico de ambulancias y
atención de pacientes. Los modelos encontrados en la literatura tienen una característica en
común: lo estático. Debido a que la respuesta es vital en situaciones de emergencia, se hace
necesario entender que los modelos dinámicos que contemplen la localización continua
pueden ser una salida para asegurar una cobertura adecuada y un tiempo de respuesta rápido
[30]. La relocalización, se convierte entonces, en una estrategia interesante a evaluar para
optimizar la toma de decisiones operacionales a este respecto.
La investigación en relocalización de ambulancias no es muy amplia. Los modelos propuestos
para abordar tal problema se dividen en tres clases [16]. La primera clase, descrita por
Brotcorne et al. [6], son modelos que resuelven el problema de relocalización cada vez que una
ambulancia es ocupada por un incidente. En esta clase se encuentra el modelo de Gendreau et
al. [8] y Céspedes et al. [10]. La función objetivo de este tipo de problemas establece la
cobertura que se espera tener y los costos asociados a la relocalización de ambulancias como
una penalización. La segunda clase incluye realizar una fase preparatoria off-line para
encontrar localidades óptimas dependiendo del número de ambulancias disponibles. En esta
clase se encuentra el trabajo de investigación de Gendreau et al. [7] e Ingolfsson [15]. La
decisión de cuántas ambulancias y en dónde son ubicadas es en últimas del despachador. La
tercera clase son modelos que capturan la aleatoriedad del sistema mediante formulaciones
ya sean exactas o heurísticas. Dentro de los modelos aproximados se encuentra el trabajo de
Maxwell et al. [16], el cual captura la aleatoriedad de manera dinámica pero al ser aproximado
es capaz de aceptar grandes tamaños de problemas. El objetivo de este modelo es disminuir la
cantidad de llamadas perdidas durante el horizonte de tiempo restante. Dentro de las
formulaciones heurísticas encontramos Andersson [2], Andersson et al. [17] y Rajagopalan et
al. [12]. En los modelos propuestos por [2] y [17], se tiene una medición cualitativa que evalúa
el impacto de las decisiones en el futuro del sistema. Esta medición es llamada preparación. La
función objetivo de estos modelos es minimizar el tiempo de viaje de las ambulancias que
deben relocalizarse. El modelo propuesto por Rajagopalan et al. [12] es un modelo
multiperíodo que incorpora un nivel mínimo de confiabilidad requerida y esperada en un
tiempo específico. El objetivo es minimizar el número de ambulancias relocalizadas en el
sistema.
Algunos investigadores han utilizado metaheurísticas como técnicas de solución para resolver
problemas de localización y relocalización. Gendreau et al. [8]-[9] hacen uso de búsqueda tabú
para resolver modelos de localización y relocalización. En Gendreau et al. [8] se muestra que el
utilizar un algoritmo de búsqueda tabú paralela permite encontrar estrategias de
relocalización en el 95% de los casos. Así mismo se obtuvieron respuestas al 2% de la solución
óptima. En Gendreau et al. [9], la metaheurística tabú permite encontrar soluciones en
tiempos computacionales eficientes. En Rajagopalan et al. [11] se utiliza en la primera fase una
4
búsqueda tabú reactiva que maximiza la cobertura global del sistema y en la segunda fase
utilizan un algoritmo greedy para minimizar distancias de respuesta. En Iannoni et al. [29], se
utiliza una extensión del modelo del hipercubo con algoritmos genéticos para optimizar la
configuración y operación de ambulancias en autopistas encontrando soluciones en un nivel
estratégico. En Rajagopalan et al. [13], se hace una comparación entre diferentes
metaheurísticas para un modelo probabilístico de localización donde como resultado se
obtiene que un algoritmo de evolución tiene mejor desempeño en tiempo y solución con
respecto a la búsqueda tabú, recocido simulado y escala de montaña.
Tabla 1. Clasificación de los modelos según su caracterización para la relocalización
Primera clase: Programación
con penalización
Segunda clase: Fase
preparatoria
Tercera clase:
Aleatoriedad
Gendreau et al. [8] Gendreau et al. [7] Andersson [2]
Céspedes et al. [10] Ingolfsson [15] Andersson et al. [17]
Rajagopalan et al. [12]
Maxwell et al. [16]
En este trabajo, se extiende la investigación realizada por Andersson et al. [17] y [18].
Inicialmente se redefine una medida de desempeño denominada preparación para incluir más
variables como el tipo de enfermedad, el tipo de ambulancia y puntos de demanda específicos.
Mediante un algoritmo genético se realizará la localización de ambulancias teniendo en cuenta
que se desea localizar la totalidad de la flota de ambulancias en puntos de localización
previamente definidos para ese fin. El objetivo es maximizar el mínimo índice de preparación
para cada localidad y garantizar un porcentaje de cobertura de la demanda.
Luego que se ha definido en qué lugares deben estar ubicadas las ambulancias, se resuelve el
problema de asignación de ambulancias. Para esto, se generan incidentes aleatorios en los
puntos de demanda y mediante un algoritmo de despacho que tiene en cuenta el tipo de
enfermedad, el tiempo de desplazamiento de las ambulancias hasta el punto de demanda, el
tipo de ambulancia y la preparación de las localidades, se determina qué ambulancia debe ser
asignada al incidente.
Cuando ya se han asignado las ambulancias que deben atender los incidentes, la preparación
de la ciudad pudo ser afectada por la salida del sistema de dichas ambulancias; por lo tanto, se
debe evaluar si se realiza una relocalización de algunas ambulancias con el objetivo de volver a
aumentar la preparación de la ciudad. Para encontrar solución a este problema se propone un
modelo matemático que tiene en cuenta todas las condiciones técnicas del problema y el cual
es resuelto a optimalidad con bajos tiempos computacionales, lo cual es crucial para un
problema en el que la decisión debe ser tomada rápidamente.
Este documento está organizado de la siguiente forma: la sección 2 presenta la descripción del
problema de localización, despacho y relocalización de ambulancias, el índice de desempeño
llamado preparación y se enuncian los supuestos e información importante para el desarrollo
de este estudio. La sección 3 describe el algoritmo genético que resuelve el problema de
localización el cual tiene en cuenta la preparación y la cobertura de la demanda. Además, se
5
presenta el algoritmo de despacho utilizado para asignar las ambulancias a los incidentes y la
formulación matemática que modela el problema de relocalización y el método de solución
propuesto. La sección 4 ilustra computacionalmente la metodología de solución en un
conjunto de instancias a escala de una ciudad. Finalmente, la sección 5 presenta las
conclusiones y las perspectivas del trabajo futuro.
2. DESCRIPCIÓN DEL PROBLEMA
En el sistema de servicio de ambulancias se considera una ciudad que ha sido dividida en N
zonas llamadas localidades. Las localidades a su vez poseen diferentes puntos de
concentración de población llamados puntos de demanda donde pueden ocurrir incidentes.
Los incidentes también se encuentran agrupados según la prioridad de la patología [30].
Considere también una flota de ambulancias disponibles para la ciudad que no son
homogéneas ya que se tienen en cuenta tipos de ambulancias y su adecuación para atender
cierto tipo de prioridades.
Las ambulancias disponibles para atender emergencias pueden ser ubicadas en diferentes
puntos de localización repartidos en la ciudad llamados bases. Cada base posee la capacidad
de albergar un número específico de ambulancias. La ambulancia que ocupe una base tiene la
capacidad para atender un incidente que se encuentre dentro de su alcance. El alcance es el
tiempo de viaje requerido por la ambulancia para llegar desde la base donde se encuentra
ubicada hasta el lugar del incidente.
Antes de definir formalmente el problema de localización, despacho y relocalización es
necesario definir las medidas de desempeño que determinan la solución de dichos problemas:
la preparación y la cobertura.
2.1. Preparación
Los índices de desempeño permiten a los administradores y operadores entender cómo el
sistema logístico de ambulancias se está comportando o se comporta en cierto momento del
día. Las ambulancias al ser un servicio de urgencias y emergencias, que usualmente son
situaciones imprevistas, deben estar disponibles a toda hora del día. La disponibilidad de las
ambulancias se traslada a la capacidad que tenga la ambulancia de atender una situación en
un tiempo de respuesta razonable.
La preparación entra entonces, a hacer parte de este conjunto de índices que permiten evaluar
el desempeño del servicio de ambulancias. La preparación, según Andersson et al. [20], se
refiere a la capacidad de ofrecer atención pre-hospitalaria de ambulancia dentro de un tiempo
razonable, a los habitantes de un área geográfica específica. La preparación se halla por cada
zona, para este estudio localidad, obteniendo un valor que indica qué tan preparada se
encuentra ante cualquier situación de emergencia.
A diferencia del índice de preparación definido por Andersson et al. [20], en este trabajo se
tienen en cuenta para el cálculo de la preparación más variables como el tipo de enfermedad,
el tipo de ambulancia, el número de ambulancias que pueden llegar a los puntos de demanda
de cierta localidad dentro de un tiempo específico y el número esperado de ambulancias en la
localidad.
6
Para calcular el índice de preparación se deben calcular los tiempos de viaje entre las bases y
los puntos de demanda que pertenecen a la localidad, ya que los puntos de demanda que
pertenecen a una localidad son los únicos que contribuyen a su preparación. Además, la
preparación depende de la población concentrada en los puntos de demanda de la localidad, y
estos a su vez podrían variar en un horizonte de tiempo definido. Por ejemplo, en localidades
que concentran puntos de demanda que son centros laborales, la concentración de población
no es la misma a lo largo del día. Para este estudio se supone de forma general que la
población no varía en los puntos de demanda.
Se consideran demandas asociadas al tipo de incidente que se presente. Estas demandas
varían dependiendo de la probabilidad de ocurrencia del incidente (o tipo de enfermedad), los
casos totales que presenta la localidad y la cantidad de población en cada punto de demanda
en la localidad. De igual forma, para ajustar el cálculo de la preparación se considera que no
todas las ambulancias tienen igual alistamiento para atender cualquier tipo de patología.
Pueden existir ambulancias especializadas en cierto tipo de enfermedades por lo tanto la
contribución que tiene una ambulancia frente a un incidente no es la misma para todos los
casos.
De acuerdo a lo descrito con anterioridad es necesario entender algunas consideraciones y
supuestos relacionados con el cálculo de la preparación para cada localidad:
1. Los puntos de demanda que pertenecen a una localidad tienen una característica
especial llamada peso que brinda la importancia necesaria a la localidad dependiendo
de la cantidad de población en el punto de demanda, llamadas y ocurrencia del
incidente o enfermedad. Este peso indica la cantidad de población afectada por un
tipo de enfermedad en un punto de demanda específico.
Se considera el uso de datos históricos que abarcan todos los diferentes tipos de
enfermedades presentados en los incidentes para un punto de demanda k, ������. Así
mismo, se tiene una probabilidad de ocurrencia de la patología o enfermedad e en un
tiempo del día ����.
Por lo tanto el peso para cada punto de demanda dependiendo de la enfermedad se
denomina c y es calculado de la siguiente forma:
�,� � ������ � ���� �1�
2. Las ambulancias pueden ser de diferentes tipos dependiendo de los recursos físicos y
humanos con los que cuenten: Neonatales, medicalizadas, motorizadas, básicas y
psiquiatría. Cada ambulancia � , debido a sus características, tiene una habilidad
cuantificable para atender cierto tipo de patología � llamada factor de contribución:
�,�. Por ejemplo, una ambulancia medicalizada es capaz de atender todos los tipos de
incidentes. En un caso de dificultad respiratoria, su factor de contribución para esta
enfermedad en una escala entre uno (1) y cero (0) siendo (1) lo más preparado para
atender un tipo de enfermedad, será 1. Es decir, la ambulancia está preparada para
este tipo de enfermedad.
7
3. El tiempo de viaje entre el punto de demanda k que se encuentra en la localidad y el
punto de localización j es denominado ��,� y depende de la localización de la
ambulancia. Si hay una ambulancia ubicada en la base j dicho tiempo se tendrá en
cuenta de lo contrario, si no existe ambulancia ubicada en la base j dicho tiempo es
cero.
La expresión (2) presenta entonces, como se realiza el cálculo de la preparación para la
localidad i dependiendo del momento del día t. Donde � es el conjunto de patologías que se
presentan, �� es el conjunto de puntos de demanda que pertenecen a la localidad i, � es el
conjunto de puntos de localización en la ciudad y � es el conjunto de ambulancias disponibles
para atender la localidad.
�� � � � � � �,��,� � ��,�� � � � !� � "# � $ �2�
Luego, se busca maximizar el índice de la localidad con menor preparación. Note entonces que
a mayor contribución de la ambulancia para atender un incidente mayor será la preparación.
Además, el tiempo de viaje entre el punto de localización y el punto de demanda el cual
depende de la localización de la ambulancia, incide de manera inversa en la preparación.
Finalmente, la preparación es una medida de desempeño del comportamiento del sistema y se
calcula para cada localidad en la ciudad indicando su grado de preparación ante cualquier
eventualidad. Este índice tiene en cuenta factores importantes como el tiempo que le toma a
una ambulancia llegar desde la base donde se encuentra ubicada a un punto de demanda, la
cantidad de población afectada por un tipo de enfermedad específico y la habilidad de una
ambulancia para atender cierto tipo de patología.
Es importante aclarar, que la cantidad de casos en cada punto de demanda puede ser
desglosado como la cantidad de casos que ocurren en la localidad donde se encuentra el punto
de demanda, multiplicado por el porcentaje de importancia del punto de demanda
dependiendo de la cantidad de población que se concentra allí; es decir, la población en el
punto de demanda dividido la suma de las poblaciones de todos los puntos de demanda que
pertenecen a la localidad.
Por ejemplo, suponga que queremos hallar la preparación para una localidad denominada
localidad 1. Existen dos ambulancias disponibles ubicadas en la base 1 y 2 respectivamente,
para atender a los dos puntos de demanda pertenecientes a la localidad. En esta zona se
presentaron dos tipos de patologías que afectan a la población en un 60% y 40%
respectivamente. Los datos que se muestran en la tabla 2 son: el tiempo de viaje entre los
puntos de demanda y las bases, la población de cada punto de demanda, el factor de
contribución de la ambulancia a la enfermedad, el peso del punto de demanda dependiendo
de la patología presentada.
8
Tabla 2. Datos ejemplo localidad 1
Tiempo de viaje Base 1 Base 2 Casos
Punto Demanda 1 5 12 15
Punto Demanda 2 10 9 20
Factor de
Contribución Enfermedad 1 Enfermedad 2
Ambulancia 1 1 0,8
Ambulancia 2 0,8 0,5
Primero, se debe hallar el peso de la población en el punto de demanda k debido a la
enfermedad k. Para este caso, tendremos cuatro términos de peso de la población debido a los
dos puntos de demanda y las dos patologías que se presentan en el sistema.
�&,& � 15 � 0.6 � 9 �3�
�&,- � 15 � 0.4 � 6 �4�
�-,& � 20 � 0.6 � 12 �5�
�-,- � 20 � 0.4 � 8 �6�
Ahora bien, podemos hallar el valor de la preparación para la localidad 1:
�& � 0 �&,&�&,& � �&,& 1 �&,&
�&,- � �-,& 1 �-,&�-,& � �&,& 1 �-,&
�-,- � �-,&2 1 0 �&,-
�&,- � �&,- 1 �&,-�&,- � �-,- 1 �-,-
�-,& � �&,- 1 �-,-�-,- � �-,-2 �7�
�& � 4 19 � 5 1 1
6 � 10 1 0.812 � 5 1 0.8
8 � 105 1 4 0.8
9 � 12 1 0.86 � 9 1 0.5
12 � 12 1 0.58 � 95 � 0,095 �8�
En (7), el primer término indica la preparación que aporta la ambulancia uno. Tiene en cuenta
la posibilidad de la ambulancia uno de atender a los dos puntos de demanda y los dos tipos de
patología que se pueden presentar. El segundo término es la preparación aportada por la
ambulancia dos. Luego, se entenderá este término como cuán preparada se encuentra la
localidad 1 en caso que se presenten incidentes.
Para corroborar el término de preparación, se hicieron unas corridas para un mismo momento
de tiempo t variando los términos de tiempo promedio de viaje desde la base hasta los puntos
de demanda y cantidad de casos presentados para una única localidad y así conocer el
comportamiento de este índice de desempeño. Se tienen los siguientes parámetros: 4 tipos de
ambulancias, 8 ambulancias en total, 10 puntos de demanda, 4 tipos de enfermedad y 2
localidades.
9
Figura 2. Diagrama de la preparación vs. El tiempo promedio de viaje
Como se muestra en la figura 2, conforme aumenta el tiempo promedio de viaje entre los
puntos de demanda y las bases, la preparación disminuye paulatinamente. Este tiempo de
viaje se obtiene como la distancia entre las coordenadas de cada punto de demanda y las
bases. Las bases de ubicación de las ambulancias para cada una de las corridas realizadas no
cambian.
Figura 3. Diagrama de preparación vs. Casos presentados en la localidad
En la figura 3, al igual que la anterior, entre más aumenten la cantidad de casos presentados
en la localidad disminuirá el valor de la preparación. En este caso, al realizar las corridas las
bases de ubicación de las ambulancias cambiaban. Esto indica que el índice de desempeño es
más sensible a los cambios en demanda tratando de cubrir la mayor cantidad de población
posible.
El índice de preparación se ha determinado para cada localidad, lo que nos brinda un valor
cuantificable de la habilidad de la localidad para estar preparada ante cualquier incidente. Pero
no se ha establecido una medida de comparación que permita estar alertas ante cambios en
0.000.100.200.300.400.500.600.700.800.90
Pre
par
ació
n
Tiempo promedio de viaje
Preparación
Preparación
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
Pre
par
ació
n
Casos
Preparación
Preparación
10
las condiciones del sistema. Establecer un valor mínimo de preparación para toda la ciudad
que permita al controlador o despachador de ambulancias tomar decisiones correctas a nivel
de planeación, control y operación conseguirá mantener respuestas eficientes en términos de
tiempo y cobertura. En los niveles de planeación y control, es posible obtener el tamaño de
flota de ambulancias y la localización inicial. En operación, permitirá realizar la asignación de
ambulancias a los incidentes y relocalizarlas sin penalizar el índice de desempeño [2].
2.2. Cobertura
La cobertura es otra medida de desempeño importante en la logística de ambulancias
Gendreau et al. [9], inclusive Andersson et al. [19] demuestra que existe una alta relación
entre la preparación y la cobertura. Mientras más alta sea la preparación, mayor cobertura.
6�����7�� � 89�:;�9��� ;� ��:��:;�; 1 <7� �7�;�9 ��� ���9;:;��89�:;�9��� ������� ;� ��:��:;�; 1 �9�
El nivel de cobertura se define en (9). Se desea que la demanda de tipo Prioridad 1 sea cubierta
en unos rangos estipulados así: el 75% de esta demanda debe ser cubierta en un tiempo no
mayor a 10 minutos, es decir, mínimo el 75% de la demanda con tipo de incidentes de
prioridad 1, deben ser atendidos en menos de 10 minutos, el 90% en un tiempo no mayor a 15
minutos y el 95% en un tiempo no mayor a 20 minutos.
2.3 Problema de Localización de Ambulancias
El problema de localización de ambulancias consiste entonces en decidir en qué punto de
localización debe ser ubicada cada ambulancia, con el fin de maximizar el mínimo índice de
preparación de las localidades y garantizar un porcentaje mínimo de cobertura de la demanda.
Un nivel adecuado de preparación se refiere a maximizar el mínimo nivel de preparación en
todas las localidades hallando la cantidad de ambulancias necesarias para cumplir con
restricciones de cobertura. Este valor de preparación se debe hallar en una primera fase del
sistema logístico de ambulancias donde se ubican una cantidad de ambulancias disponibles.
Para esto, se hace uso del modelo NS:
NS: @ABC � D�E� 9��F� � @GHG � I � � � � �,��,� � ��,��J�� � � � !� � "# � $ �10�
Donde, se decide maximizar la mínima preparación en cualquiera de las zonas i en N. Se tiene
un número M de ambulancias. Y(M) es un conjunto de posibles localizaciones de ambulancias
y y es un elemento de este conjunto. El tiempo de viaje de la ambulancia desde la base al
punto de demanda depende del lugar donde se encuentra localizada, es decir de y.
En la localización, se tiene en cuenta la posibilidad de llegar desde la base hasta los puntos de
demanda en un tiempo razonable lo que cuantifica la cobertura de demanda que se tiene para
cada localidad de la ciudad. Es posible también que las ambulancias puedan cubrir puntos de
demanda en común.
11
Es importante aclarar, que la comparación para el valor de preparación se realiza teniendo en
cuenta el valor mínimo obtenido en el uso del modelo NS, el cual es un nivel adecuado de
preparación cumpliendo con restricciones de cobertura. Si alguna localidad tiene una
preparación mayor que este valor, indica que esta localidad se encuentra altamente preparada
antes cualquier eventualidad; y en el caso en que alguna ambulancia sea despachada para
servicio de un incidente, es posible que esta localidad siga por encima del nivel adecuado de
preparación. En caso de estar por debajo de este valor luego de un despacho, indica que la
localidad no se encuentra preparada y en caso de eventualidad, es posible no sea capaz de
responder de manera eficiente al problema.
Considere una ciudad dividida en 4 localidades tal como se muestra en la Figura 4. Cada
localidad tiene puntos de demanda y por toda la ciudad existen posibles bases, cada una con
capacidad de dos ambulancias, además, la flota está conformada por 3 ambulancias del mismo
tipo.
Figura 4. Ejemplo de una ciudad con 4 localidades, y respectivos puntos de demanda y bases
El problema de localización consiste en determinar en cuáles bases deberían ir localizadas las
ambulancias, teniendo en cuenta el índice de preparación y la cobertura. Una posible solución
para el problema sería localizar las ambulancias tal como se presenta en la Figura 5. Note que
ahora es posible calcular el índice de preparación para cada localidad.
12
Figura 5. Ejemplo de solución 1 de localización de tres ambulancias en la ciudad
Al calcular el índice de preparación de cada localidad se obtuvieron los siguientes valores:
�& � 0.0014, �- � 0.0013, �K � 0.00541 y �L � 0.041. Esto indica que el índice mínimo de
preparación es 0.0013. Con esta localización, se alcanza una cobertura para incidentes Nivel 1
en menos de 10 minutos para el 72% de la población, en menos de 15 minutos para el 89% y
en menos de 20 minutos para el 95%.
Sin embargo, otra posible solución para el problema sería la presentada en la Figura 6. Si
realizamos para esta instancia, el cálculo de la preparación para cada localidad obtenemos que:
�& � 0.00251, �- � 0.0015, �K � 0.0431 y �L � 0.031. Por lo tanto, el índice mínimo de
preparación es 0.0015. Con esta configuración se alcanza una cobertura en menos de 10
minutos del 76% de la población, en menos de 15 minutos para el 91% y en menos 20 minutos
para el 96% de la población.
13
Figura 6. Ejemplo de solución 2 de localización de tres ambulancias en la ciudad
Por lo tanto, entre las dos soluciones propuestas, la solución 2 que se ilustra en la Figura 6 es
mejor, ya que cumple con todos los porcentajes de cobertura y presenta un mayor índice de
preparación mínima.
2.4 Problema de Asignación de Ambulancias o Despacho
Luego que se encuentran localizadas las ambulancias en el sistema y se ha producido un
incidente en algún punto de demanda, se debe decidir que ambulancia queda asignada para
atender el incidente. El despacho de ambulancias es un problema operacional y se necesitan
tiempo bajos para encontrar solución.
Suponga que se ha decidido localizar las ambulancias tal como se muestra en la Figura 6, y se
ha producido un incidente. Es ahora cuando aparece el problema del despacho de ambulancias
como el proceso en el que se decide cuáles serán las ambulancias asignadas a los incidentes.
En muchos casos reales, el despacho es un proceso ejecutado de manera subjetiva debido a
que depende del criterio que maneje el operador con las ambulancias disponibles en el
sistema. Por lo tanto, el operador evalúa cuál de las ambulancias del sistema debe asignar.
Para esto, se propone que el índice de preparación sea una medida de desempeño capaz de
realizar una evaluación del comportamiento del sistema y permita ayudar al operador en la
toma de la decisión de la asignación de ambulancias. Luego, se debe asignar la ambulancia que
tendría un menor impacto en la mínima preparación de las localidades, teniendo en cuenta
también factores como el menor tiempo de viaje al incidente y el alistamiento de la
ambulancia para el tipo de incidente que se presente. Suponga entonces que después de
resolver dicho problema el operador decidió asignar una de las ambulancias al incidente tal
como se muestra en la Figura 7.
14
LOCALIDAD 1
LOCALIDAD 2
LOCALIDAD 3
LOCALIDAD 4
Puntos de localizaciónPuntos de demanda
Incidente
Figura 7. Ejemplo de asignación a un incidente
2.5 Problema de Relocalización de Ambulancias
Después que se produce el despacho de ambulancias, es decir, las ambulancias salen de la
base actual para atender un incidente, es posible que la capacidad del sistema para responder
de manera eficiente ante nuevos incidentes en las localidades se haya visto afectada, ya que
las ambulancias asignadas tienen un tiempo de ocupación para volver a estar disponibles y
poder atender nuevos incidentes que se producen. Considerando el ejemplo ilustrativo de la
Figura 7, se presenta cómo la ambulancia que fue asignada al incidente, sale del sistema y deja
de cubrir puntos de demanda, lo que posiblemente puede afectar a la preparación de las
localidades.
El impacto del despacho puede ser medido tanto por el índice de preparación como por la
cobertura –requerimientos del sistema-. Al hacerlo, existe la posibilidad que la cobertura se
disminuya al igual que la preparación. Por tal razón, para conocer si es necesario realizar una
relocalización, se debe como primera fase, evaluar si la cobertura mínima deseada ha
disminuido para entonces, determinar cuáles ambulancias deben cambiar de base para
aumentar la preparación mínima de las localidades respondiendo de manera más eficiente
ante nuevos incidentes, como se muestra en la figura 8.
15
Figura 8. Ejemplo de posibles relocalizaciones de ambulancias
Finalmente, se realizará la relocalización siempre y cuando se maximice el índice mínimo de
preparación. La Figura 9, ilustra una posible solución donde solo se ha decidido relocalizar una
ambulancia.
Figura 9. Ejemplo de relocalización de ambulancia
16
3. METODOLOGÍA DE SOLUCIÓN
En esta sección, se presenta la metodología de solución del problema de localización el cual es
resuelto mediante un algoritmo genético. Posteriormente, se describe el algoritmo de
despacho utilizado para solucionar el problema de asignación de ambulancias y finalmente, se
presenta la formulación matemática que modela el problema de relocalización y la técnica de
solución.
3.1 Algoritmo Genético para resolver el problema de localización.
La elección del algoritmo genético se basa en el trabajo realizado por Rajagopalan et al. [13]
quienes implementaron un algoritmo de evolución para encontrar localizaciones de
ambulancias en un modelo probabilístico obteniendo mejores resultados en comparación con
otras metaheurísticas.
El método de solución es implementar un algoritmo genético híbrido que parte de soluciones
iniciales generadas a partir de una heurística constructiva: un algoritmo que maximiza la
mínima preparación. El algoritmo genético comienza con una población inicial de cromosomas,
el cual representa una solución del problema. A través de una serie de operadores genéticos
de cruzamiento y mutación, la población es modificada en cada iteración de manera aleatoria
agregando diversidad a la población. Al final de cada iteración, se evalúan las nuevas
soluciones encontradas y un subconjunto de éstas (las mejores en la mayoría de los casos)
harán parte de la nueva generación.
A continuación se definirán las definiciones de los componentes del algoritmo genético híbrido
propuesto para resolver el valor de la preparación global.
Genotipo
Para la representación de las soluciones posibles en cuanto a localización de las ambulancias,
se utilizará una matriz binaria que expresa 1 si la ambulancia m (fila m) se localiza en el punto
de localización n (fila m) y 0 de lo contrario. Por ejemplo, en la figura 10, la ambulancia 3
estará ubicada en el punto de localización 1.
1 2 3 4
1 0 1 0 0
2 0 0 0 1
3 1 0 0 0
Figura 10. Representación de la solución
Estructura del Algoritmo
Función de Adaptación
La calidad de la solución se evalúa mediante una función de adaptación que en este caso, será
el máximo de las mínimas preparaciones halladas para cada localidad. Entre mayor sea el valor
de la función de adaptación, mejor será la solución obtenida. Para la ubicación de las
ambulancias se debe tener en cuenta una cobertura mínima para la Prioridad tipo 1, lo que
indica que se debe contabilizar el comportamiento de la atención de esta demanda en un
tiempo de viaje específico.
17
Generación de la Población Inicial
La población inicial se genera de diferentes maneras:
1. Se ordenan las ambulancias de la “mejor a la peor” y se le ubica en el punto de
localización que maximice la mínima preparación global.
2. Se ordenan las ambulancias de la “peor a la mejor”. Se ordenan los puntos de
localización del último al primero en orden de lista y se ubica la ambulancia en el
punto de localización que maximice la mínima preparación global.
3. Se obtiene el menor de tiempo de viaje entre un punto de demanda y una base. Sobre
esta base se ubica una ambulancia que maximice la mínima preparación global.
4. Aleatoriamente se asignan las ambulancias a las bases.
5. Se recorren todas las bases y se localizan la mayor cantidad de ambulancias posibles.
Es decir, se comienza por la primera base y se colocan todas las ambulancias hasta
copar su capacidad. Sigue con la segunda base y se llena su capacidad, así hasta llegar
a la última base. En la siguiente iteración, se comenzará por la segunda base y se
llenará su capacidad con ambulancias. Este procedimiento se realiza tantas veces
como bases hallan disponibles.
Operadores Genéticos
Crossover – Recombinación
Es el principal operador genético y consiste en el intercambio de genes entre dos cromosomas.
La recombinación se utiliza para promover la exploración de una solución dentro del espacio
de solución ya identificado. Al representar nuestra estructura del cromosoma como cadena de
bits se utiliza una recombinación de un punto donde pares de padre crean dos hijos. En este
trabajo se definen dos tipos de cruces:
• Cruce con respecto a las ambulancias: En este cruce, se genera aleatoriamente un
corte horizontal sobre el par de matrices (padres) causando cambios en la localización
de las ambulancias. Se conforman dos hijos los cuales obtienen información de cada
padre.
• Cruce con respecto a las bases: En este cruce, se genera aleatoriamente un corte
vertical sobre el par de matrices causando cambios en las ambulancias que se
encuentran dentro de las localizaciones. Análogo al método anterior, se conforman
dos hijos.
Estos cruces son independientes entre sí y se realiza un solo tipo de cruce en un instante, lo
cual se decide de manera aleatoria.
Mutación
Permite la diversidad genética de la especie para escapar del óptimo local buscando en los
vecinos por una mejor solución realizando un cambio aleatorio de la estructura genética del
cromosoma. Las mutaciones se producen realizando un cambio de 1 o 0 en el cromosoma
generando un cambio en la localización de la ambulancia escogida aleatoriamente. Para este
cambio, se evalúan los posibles vecinos de la base donde se encuentra ubicada la ambulancia.
Los vecinos son estipulados teniendo en cuenta tanto el tiempo de viaje que les toma
trasladarse de una base a la otra, al igual que su capacidad para recibir más ambulancias. Si
18
una base no puede recibir más ambulancias, no es tenido en cuenta para hacer parte del
conjunto de vecinos disponibles.
Reparación
Es un procedimiento que permite ajustar los cromosomas luego que son cruzados o mutados.
Cuando las ambulancias son ubicadas en puntos de localización cuya capacidad ha sido copada,
es necesario ubicar esta ambulancia en alguna otra base que todavía tenga lugar. Así mismo,
se penalizará la infactibilidad en términos de cobertura con un costo alto en la función de
adaptación.
Método de Selección
Existen diferentes técnicas de selección que se utilizan para elegir los cromosomas que
donarán sus genes a las siguientes generaciones. El método de selección por torneo permitirá
escoger al individuo según su función de adaptación sobre dos individuos escogidos de manera
aleatoria. Se seleccionarán a los individuos con mejor desempeño para la nueva población de
un conjunto de población de padres (μ) e hijos (λ), es decir, (μ+ λ) debido a que es posible que
existan padres con buenos desempeños en la función de adaptación y términos de cobertura.
La estructura del algoritmo propuesto es la mostrada en la tabla 3.
Tabla 3. Algoritmo genético de localización
1. Se realiza una heurística constructiva que permite obtener soluciones iniciales con valores
MN, que constituyen la población inicial.
2. Se evalúa la función de adaptación de cada individuo de la población como el máximo de
las mínimas preparaciones en las localidades teniendo en cuenta el valor de cobertura
obtenido para las enfermedades tipo prioridad 1.
3. Mientras (no se alcance la cantidad de generaciones permitida)
Se seleccionan a los mejores individuos de la población, entre padres e hijos, para nueva
generación.
4. Para el tamaño de la población
Recombinación: Se seleccionan los individuos a recombinar según el método por
torneo. Así aleatoriamente se realiza un tipo de cruce: por ambulancia o por base. De
este cruce se obtienen dos hijos.
Mutación: Se escoge un individuo de manera aleatoria. Método de intercambio de
genes según una probabilidad.
Evaluación de la función de adaptación de todos los individuos, padres e hijos.
5. Volver al paso 3
3.2 Algoritmo de Despacho
La asignación de ambulancias depende del tipo de incidente. Las patologías son clasificadas
según un nivel de importancia de atención donde, el Nivel 1 son aquellas enfermedades o
accidentes de tránsito, laborales o comunes urgentes y/o que atentan contra la vida de algún
paciente, Nivel 2 son aquellos incidentes urgentes pero que no amenazan la vida del paciente,
Nivel 3 que constituyen pacientes cuya condición no es urgente. El despacho de ambulancias
para las llamadas que presentan patologías de Nivel 1 es inmediato debido a la urgencia del
19
incidente y se envía la ambulancia más cercana disponible capaz de atender este tipo de
patologías [30]. Para los Niveles 2 y 3 es posible realizar un algoritmo de despacho que evalúa
la posibilidad de enviar una ambulancia que tenga el menor efecto sobre la preparación. La
ambulancia que disminuya en menos cuantía el valor de la preparación mínima será escogida
para atender el incidente pero será tenida en cuenta en caso de presentarse un incidente de
mayor urgencia.
El algoritmo de despacho, como se muestra en la tabla 4, comienza con el ordenamiento de las
ambulancias más cercanas al sitio del incidente según el tiempo de viaje desde la base. Luego,
se verifica cual es el tipo de incidente presentado. Si es una llamada Nivel 1, se despacha la
primera ambulancia capaz de atender este tipo de incidente en la lista. Es decir, no solo
importa su cercanía, sino que además se tiene en cuenta que la ambulancia sea la más
capacitada para atender la patología presentada. Si es una llamada Nivel 2 o 3, se debe
primero verificar cuales ambulancias en la lista pueden llegar al incidente en un tiempo menor
a 15 (R2) y 20 (R3) minutos respectivamente. Si no existe ambulancia alguna capaz de llegar en
este tiempo, la ambulancia más cercana al lugar del incidente se despacha. En caso contrario,
se valora de las ambulancias disponibles en la lista cual debe ser despachada, haciendo que
esta no se encuentre disponible �O�� � 0� en el sistema – esto es hacer que no se encuentre
ubicada en ningún punto base- evaluando la preparación obtenida para las localidades. Se
guarda la menor de las preparaciones �P�Q y se sigue con la siguiente ambulancia en la lista.
Esto se realiza hasta que se acabe la lista de ambulancias que pueden atender la llamada.
Aquella que otorgue la mayor de las preparaciones, será la escogida para servir el hecho.
Tabla 4. Algoritmo de despacho de ambulancias
1. Hacer k el punto de demanda en el cual se identifica el incidente. Se hace una lista m
ordenada de ambulancias según tiempo de viaje. F � 1, … , S�
Sea �P�Q � 0
Sea �F�T � U
2. Si es Nivel(k)=1
Se despacha la primera ambulancia en la lista m que sea tipo de ambulancia medicalizada
(V:���F&� � F�;:���:M�;�). �F�T � F&
3. Si es Nivel(k)=2 o 3
Para F � 1, … , S�
Si ��P W X- ό ��P W XK dependiendo del nivel de prioridad,
Se remueve m de la lista de ambulancias (OP� � 0) y se calcula la preparación
para cada una de las localidades, �� , afectadas por la ocupación de esta
ambulancia.
Si min �� \ �P�Q
�P�Q � min �� , �F�T � F 4. Despachar m.
3.3. Modelo Matemático para la Relocalización de Ambulancias.
Como se ha mencionado anteriormente, relocalizar no es un proceso fácil de realizar debido a
los costos y tiempo que puede acarrear mover las ambulancias. Por esto, se decide primero
20
evaluar la necesidad de efectuar la relocalización mediante el cálculo de los porcentajes de
cobertura del Nivel 1 que se han establecido con anterioridad. El algoritmo de relocalización
funciona de la siguiente manera: Si el porcentaje de cobertura de Nivel 1 en menos de 10
minutos (75%) ha disminuido, se debe realizar la relocalización. Se desea entonces relocalizar
ambulancias de tal forma que se alcance para cada localidad una preparación mayor al �P�Q
calculado en el despacho. Con esto se estaría asegurando un aumento también en la cobertura.
Note en las gráficas anteriores que se comprobó que a mayor �P�Q , mayor será la cobertura
de la población.
Se decide modelar el problema como un programa entero mixto (MIP) que permita determinar
cuáles ambulancias deben ser relocalizadas maximizando la mínima preparación de las
localidades; mientras se satisfacen simultáneamente algunas condiciones técnicas del
problema como: no reubicar más de m ambulancias, garantizar que las bases no superan su
capacidad y no superar el tiempo máximo de relocalización para cada ambulancia
Para el modelo se definen el conjunto de enfermedades ���, de puntos de localización ���, de
ambulancias ���, de localidades �]� y el conjunto ���� que está conformado por los puntos de
demanda que pertenecen a la localidad : � ]. Considere los siguientes parámetros: ^�� es el
tiempo de relocalización de la ambulancia � � � al punto de localización _ � � , el cual
depende también del punto de localización donde se encuentre ubicada la ambulancia
después de la localización; F es la cantidad máxima de ambulancias a relocalizar; � es el
tiempo máximo de relocalización permitido para cualquier ambulancia; `�� es un parámetro
binario que indica la localización de las ambulancias que no fueron asignadas en el despacho;
finalmente, ���� es la capacidad que el punto de localización _ � � tiene para ubicar
ambulancias.
La variable de decisión a�� es una variable binaria que toma el valor de 1 cuando la ambulancia
� � � debe moverse desde o hacia un punto de localización _ � �, 0 de lo contrario. Es decir,
cuando se decide que la ambulancia � � � se mueve desde una base � � � hacia una base
� � � tanto a�,b como a�,c son iguales a uno. O�� es una variable binaria que toma el valor de 1
cuando la ambulancia � � � luego de la relocalización queda ubicada en el punto de
localización _ � �, 0 de lo contrario. Finalmente, M determina la mínima preparación de todas
las localidades.
La formulación matemática resultante es la siguiente:
S�a:F:M�� M �11�
s.a.
� � � � ����d � ���� � � � !� � "# � $ O�� e M f: � ] �12�
� ^��. a����!
W � f� � � �13�
21
� O����!
W 1 f� � � �14�
� � a����!��
W F � 2 �15�
� O����
W ���� f_ � � �16�
ga�� 1 `�� g O�� W 0 f� � �, _ � � �17�
ga�� g `�� 1 O�� W 0 f� � �, _ � � �18�
a�� g `�� g O�� W 0 f� � �, _ � � �19�
a�� 1 `�� 1 O�� W 2 f� � �, _ � � �20�
a�� � h0,1i f� � �, _ � � �21�
O�� � h0,1i f� � �, _ � � �22�
M e 0 �23�
El objetivo (11) es maximizar el mínimo índice de preparación de las localidades, dicho índice
de preparación mínimo se calcula mediante las restricciones (12). La restricción (13) garantiza
que cualquier tiempo de relocalización no supere s unidades de tiempo. Se debe asegurar que
la ambulancia quede localizada máximo en una base (14). La restricción (15) indica que el
número máximo de ambulancias a relocalizar (m) no sea superado. Esta restricción se
encuentra en el lado derecho multiplicado por 2, pues cada ambulancia relocalizada tendrá
dos movimientos (desde y hacia una base) indicado por la variable de decisión a��. Las
restricciones (16) garantizan que no se sobrepase la capacidad de ambulancias de cada base.
Las restricciones (17)-(20) son las encargadas de relacionar las variables a��, O��y el parámetro
`��. Por ejemplo, si el parámetro `-K es igual a 1, indica que la ambulancia 2 después de
realizarse el despacho se encuentra en la base 3, si luego de solucionar el modelo la variable
a-K � 1 indicando que hay un movimiento de la ambulancia 2 desde la base 3, hay que
garantizar que la variable O-K � 0. Finalmente, las restricciones (21)-(23) definen la naturaleza
de las variables de decisión.
4. RESULTADOS COMPUTACIONALES
La metodología propuesta fue probada en instancias a escala de una ciudad. El algoritmo
genético y el algoritmo de despacho se implementaron en Visual Basic para Aplicaciones,
mientras que el modelo matemático se resolvió con el optimizador de Xpress-MP (Versión
1.20.12) en un computador con procesador Intel(R) Xeon(R) CPU X5550 de 2.67 GHz y 4.00 GB
de RAM.
Para ilustrar toda la metodología primero se presenta la solución del problema de localización
utilizando el algoritmo genético. En este caso se genera una ciudad de Bogotá hipotética de
50x50 unidades. Para esto se generan 9 localidades con 94 puntos de demanda aleatorios en
toda la ciudad cuya población varía entre 1.000 y 165.000 personas. La importancia o peso de
cada punto de demanda tiene valores entre 1 y 2500. Los 20 puntos bases también se generan
aleatoriamente sobre esta ciudad obteniendo su capacidad de ambulancias.
22
Para el factor de contribución se tendrán 4 causas de incidentes y cuatro tipos de ambulancias
posibles: medicalizadas, básicas, neonatales y motorizadas. Este valor varía entre 1, 0.8, 0.75,
0.5 y 0.25 de acuerdo a lo adecuada que sea la ambulancia para atender el tipo de incidente.
Cabe aclarar que las causas de incidentes tienen un tipo de prioridad que indica la necesidad
de ser atendidas lo antes posible. Las restricciones de cobertura para la ciudad de Bogotá
significan la atención de una cantidad de población dentro de un tiempo razonable.
Algoritmo genético
Para los parámetros con respecto al algoritmo genético, se utilizaron los siguientes:
• Para la probabilidad de recombinación, se utilizó un valor de 0.8. Para la mutación se
utilizó un valor de 0.1. Estos valores fueron escogidos luego de realizar corridas
manejando valores de probabilidad entre 0.1 y 0.9.
• Se escogió un tamaño de la población de 20 individuos. Se realizaron corridas de 4, 15,
20 y 30 individuos.
• Para la condición de terminación del algoritmo se tuvo en cuenta los cambios en los
resultados después de cierta cantidad de iteraciones. Luego de la iteración 80, los
cambios en los resultados tanto de preparación como cobertura eran muy pequeños
por lo cual se decidió dejar la cantidad de iteraciones en 80. Así mismo, si luego de las
últimas 20 iteraciones no se ha visto cambio alguno en los resultados el algoritmo se
detiene.
Resultados
Para obtener los resultados presentados en la Tabla 4, se hicieron 200 corridas con 80 cantidad
de generaciones hallando valores promedio para el índice de preparación, el tiempo
computacional (Tcomput) y los valores de cobertura (Cob1, Cob2 y Cob3); esto se logra
variando la cantidad de ambulancias disponibles de cada tipo (1, 2, 3, 4). Cuando las
restricciones de cobertura se cumplen: asegurar una cobertura nivel 1 del 75%, nivel 2 del 90%
y nivel 3 del 95%, mientras se maximiza el mínimo índice de preparación, se obtienen la
cantidad de ambulancias necesarias en la ciudad y la preparación mínima a cumplir por las
localidades.
Tabla 4. Resultados Algoritmo Genético para localización de ambulancias
Ambulancias Pmin Cob1 Cob2 Cob3 Tiempo (s) CPU
4 0.00589 27.51% 44.54% 66.07% 15.456
8 0.00966 39.29% 62.17% 87.22% 20.521
10 0.00977 59.52% 72.49% 89.71% 34.551
12 0.00985 75.35% 89.57% 93.53% 45.213
14 0.01132 75.35% 89.57% 95.36% 67.411
16 0.01281 75.82% 89.57% 95.36% 79.312
17 0.01385 76.19% 90.62% 95.36% 89.830
18 0.01655 78.79% 90.62% 95.36% 98.631
Como se puede observar, con 17 ambulancias el sistema es capaz de alcanzar los porcentajes
mínimo de cobertura para los tres niveles y se encontró que el índice mínimo de preparación
23
es igual a 0.01385. Observe también, en la Figura 11, cómo el índice de preparación aumenta
conforme lo hace el número de ambulancias a localizar.
Figura 11. Diagrama de número de ambulancias localizadas vs. Preparación mínima
De igual forma se puede observar como la preparación se encuentra estrechamente
relacionada con la cobertura. A medida que aumenta la preparación mínima también lo hace la
cobertura, sin embargo, se puede observar que la cobertura de los tres niveles se empiezan a
estabilizar en cierto punto, ya que por más que aumente el número de ambulancias en el
sistema y la preparación, con el numero de bases que hay en la ciudad no es posible aumentar
más la cobertura y esta tiende a estabilizarse.
Figura 12. Diagrama de Cobertura Alcanzada vs. Preparación mínima
Note que el problema se puede resolver para cualquier número de ambulancias disponibles y
de acuerdo al desempeño de la preparación y la cobertura, seleccionar la mejor solución
encontrada por el algoritmo para la localización de ambulancias. Sin embargo, utilizando esta
0.00000
0.00200
0.00400
0.00600
0.00800
0.01000
0.01200
0.01400
0.01600
0.01800
0 5 10 15 20
Pm
in
Número de Ambulancias Localizadas
Preparación mínima
Pmin
0.00
0.20
0.40
0.60
0.80
1.00
% d
e C
ob
ertu
ra
Pmin
Preparación
Cob1
Cob2
Cob3
24
metodología se encuentra el número de ambulancias a localizar para cumplir con los tres
niveles de cobertura.
La Tabla 5 presenta la capacidad en términos del número de ambulancia de cada base y las
ambulancias localizadas en ellas.
Tabla 5. Resultados y localización de las ambulancias en las bases
Bases Capacidad Ambulancias localizadas
Bases Capacidad Ambulancias localizadas
1 2 2-3 11 3 -
2 1 4 12 2 -
3 3 5-6-7 13 2 -
4 2 8-9 14 2 -
5 3 10-11-12 15 2 -
6 1 13 16 3 -
7 2 14-15 17 3 -
8 1 16 18 2 -
9 3 17 19 3 -
10 3 - 20 1 1
Luego que se ha resuelto el problema de localización (se conoce en qué bases deben ir
ubicadas las ambulancias), se generan incidentes aleatorios para evaluar el despacho de
ambulancias. Para esto, se ejecuta el algoritmo de despacho que determina cuáles
ambulancias deben atender los incidentes. En este trabajo se supone que cada incidente
generado demanda solo una ambulancia, por lo tanto, mientras que el número de incidentes
sea menor al número de ambulancias disponibles en el sistema, el número de ambulancias
asignadas será igual a la cantidad de incidentes.
La Tabla 6 presenta el número de incidentes presentados, la preparación mínima de las
localidades luego que fueron despachadas las ambulancias y el porcentaje de cobertura 1, 2 y
3.
Tabla 6. Resultados de algoritmo de despacho
No Incidentes Pmin
despacho Cob1 Cob2 Cob3
1 3 0.01165 74.62% 89.57% 95.36%
2 4 0.01105 74.22% 88.32% 95.36%
3 5 0.01048 73.86% 86.07% 95.36%
4 6 0.01002 53.06% 71.00% 89.80%
5 7 0.00961 53.06% 71.00% 89.80%
6 8 0.00821 48.47% 60.91% 79.17%
Como era de esperarse, la preparación mínima calculada luego que las ambulancias salen del
sistema para atender incidentes disminuye a medida que los incidentes aumentan. Sin
embargo, esto puede que no sea así para todas las instancias ya que depende del punto de
demanda donde se presenten los incidentes. Note también que los porcentajes de cobertura
25
de los tres niveles, luego de realizar el despacho, disminuyen a medida que el número de
incidentes se incrementa.
Para efectos ilustrativos, en la tabla 7, se muestran las ambulancias despachadas cuando se
tienen 3 incidentes en un momento del día.
Tabla 7. Resultados de algoritmo de despacho – 3 incidentes-
Zona Incidente Prioridad Ambulancia a
Despachar
4 17 1 4
6 34 2 13
5 23 3 19
La metodología planteada en este estudio para decidir si se realiza relocalización, es revisar el
porcentaje de cobertura Nivel 1 luego de realizar el despacho. Si dicho porcentaje es inferior al
75% debe ejecutarse el modelo de relocalización. Sin embargo, el criterio que define si se
ejecuta o no el modelo puede modificarse a criterio del operador, quien define si es más
importante siempre buscar una preparación mínima para las localidades lo más alto posible o
no relocalizar en un tiempo específico del día.
Las instancias están etiquetadas desde L9A14B20D94-S3 hasta L9A9B20D94-S8 que indican: (L)
la cantidad de localidades, (A) la cantidad de ambulancias disponibles luego de ser
despachadas, (B) la cantidad de bases o puntos de localización, (D) la cantidad de puntos de
demanda y finalmente (S) la cantidad de ambulancias despachadas. En la tabla 8, se reporta
para cada instancia resultante del despacho: el valor de la preparación mínima luego de
reubicar las ambulancias, el tiempo máximo de relocalización, el tiempo computacional en
segundos obtenido, el tamaño del problema en términos del número de variables y
restricciones. El tiempo máximo de relocalización fue fijado en 15 minutos y el número
máximo de ambulancias a relocalizar fue 5 del total de ambulancias disponibles (la diferencia
entre las ambulancias localizadas y las ambulancias asignadas).
Tabla 8. Resultados de la relocalización con diferentes incidentes
Instancias Pmin obtenido en Relocalización
Tiempo máx de relocalización
Tiempo CPU (s)
Variables Restricciones No. Etiqueta
1 L9A14B20D94-S3 0.01402 14.7 0.23 561 1178
2 L9A13B20D94-S4 0.0132 14.7 0.216 521 1096
3 L9A12B20D94-S5 0.01264 14.7 0.195 481 1014
4 L9A11B20D94-S6 0.01144 12.04 0.188 441 932
5 L9A10B20D94-S7 0.01031 12.04 0.252 401 850
6 L9A9B20D94-S8 0.0096 12.04 0.222 361 768
La tabla 9 muestra para la instancia L9A14B20D94-S3, cuáles son las ambulancias que se
relocalizaron, la base donde se encontraban localizadas y la nueva base que van a ocupar.
26
Tabla 9. Resultados de algoritmo de relocalización – 3 incidentes-
Ambulancia Base en despacho Base de relocalización
1 20 4
2 1 3
4 2 4
8 4 9
9 4 5
Figura 13. Diagrama de Preparación mínima en despacho y relocalización
Como se observa en la Figura 13, la preparación mínima de la relocalización mejora para todas
las instancias respecto a la preparación obtenida luego del despacho, en promedio para las seis
instancias la mejora respecto a la preparación después del despacho es del 16,46%. Además
los tiempos computacionales son muy bajos teniendo en cuenta que el modelo es entero
mixto y sin embargo, el algoritmo de ramificación y acotamiento (B&B) se desempeña bastante
bien.
La metodología propuesta para el problema de relocalización se implementó para instancias
de gran tamaño en cuanto a cantidad de ambulancias, posibles puntos de localización y
cantidad de puntos de demanda similares a aquellas propuestas por Céspedes et al. [10]. La
instancia corresponde a una ciudad de 4 localidades con 1000 puntos de demanda generados
aleatoriamente, 50 posibles puntos de localización con diferentes capacidades y 70
ambulancias localizadas. El problema tiene 6,701 variables y 13,589 restricciones. El programa
entero mixto que resuelve el problema de relocalización toma 16.767 segundos en resolver el
problema a optimalidad y mejorando la preparación para todas las localidades, demostrando
que el modelo escala bien en instancias grandes.
0.00000
0.00200
0.00400
0.00600
0.00800
0.01000
0.01200
0.01400
0.01600
0 2 4 6 8 10
Pre
par
acci
ón
Número de Incidentes
Preparación mínima
pmin despacho
pmin relocalización
27
5. CONCLUSIONES Y TRABAJO FUTURO
La solución del problema de localización, despacho y relocalización de ambulancias impacta en
la calidad de vida de una ciudad y los índices de eficiencia del operador encargado de realizar
esta labor.
Fue demostrada la importancia de la preparación como medida de desempeño en la
evaluación del problema. Se agregó además una clasificación por tipo de ambulancia, la cual
no se encontró en la literatura, pero que es significativo ya que de acuerdo al tipo de incidente
que se presente se requerirá de un tipo específico de ambulancia, lo cual es cuantificado por
medio de un factor de contribución de la ambulancia a la enfermedad que se presente en el
incidente. Adicionalmente, se especifica un tipo de enfermedad en el cálculo del índice de
preparación. Para resolver el problema de localización fue programado un algoritmo genético
que teniendo en cuenta la cobertura alcanzada y el índice de preparación logra encontrar una
buena solución para la localización de ambulancias.
Posteriormente, mediante un algoritmo de despacho se define cada vez que se produzcan
incidentes cuáles deben ser las ambulancias que deben salir del sistema a atender el caso. El
algoritmo fue programado con reglas que permiten tomar una buena decisión ya que tienen
en cuenta la cercanía de las ambulancias, el tipo de ambulancia y enfermedad y busca un bajo
impacto en el índice de preparación mínimo.
Finalmente, si luego de despachar las ambulancias la cobertura disminuye por debajo del nivel
estipulado, se debe realizar la relocalización de ambulancias. Para esto, se presenta la
formulación de un programa matemático y se resuelve mediante un MIP propuesto que define
reglas que buscan encontrar soluciones que permitan minimizar el tiempo máximo de
relocalización al tiempo que garantizan subir la preparación mínima en un % de la preparación
mínima de despacho obtenida.
En la práctica, el esfuerzo por determinar con métodos claros la relocalización de ambulancias
es poco, por lo que definir algoritmos rápidos que logren mejorar la preparación de las zonas
mejorará la cobertura y a la vez la calidad de vida de la población.
Como trabajo futuro de la investigación podría tenerse en cuenta la probabilidad que una
ambulancia sea desocupada en el sistema antes que se cumpla el tiempo de relocalización, lo
que permitiría reducir la cantidad de ambulancias a relocalizar o que no se realice
relocalización del todo. Es importante, además, que se tenga en cuenta la demanda variable
durante el día. En la agitada vida de las ciudades, las características del entorno son variables a
lo largo del día. La cantidad de personas en un lugar específico, la congestión en transporte, el
clima, entre otros factores toman diferentes valores dependiendo de la hora y lugar en los
cuales son identificados. En ciudades como Bogotá - Colombia, donde los tiempos de traslado
desde la vivienda al lugar de trabajo son altos, la población se comporta de manera flotante
encontrándose durante el horario de trabajo concentrada en puntos específicos que difieren
de su hogar. Así mismo, en horas pico se aumentan tanto la congestión en transporte y la
28
propagación de enfermedades lo que acarrea que la probabilidad de contagio de
enfermedades sea aún mayor.
REFERENCIAS
[1] Cámara de representantes. Proyecto de Ley 040 de 2009: Por medio del cual se
establecen las condiciones para la prestación del servicio de atención médica de
ambulancia prehospitalaria y extrahospitalaria mediante la modalidad de prepago y se
dictan otras disposiciones. Recuperado el 11 de Mayo de 2010, de:
http://www.congresovisible.org/proyectos-de-ley/por-medio-del-cual-se/1663/#
[2] Andersson, T., Petersson, S., Värbrand, P. Decision Support Tool for Efficient Ambulance
Logistics. Proceedings of the 31st Annual Conference of the European Working Group on
Operational Research Applied to Health Services; 2005 Jul 31 - Ago 5. Southampton, UK,
2005.
[3] Secretaría Distrital de Salud. Centro Regulador de Urgencias y Emergencias: Quiénes
somos. Recuperado el 13 de Mayo de 2010, de:
http://www.saludcapital.gov.co/paginas/quienescrue.aspx
[4] Huertas, J. Evaluación de la asignación y despacho de ambulancias del centro regulador de
urgencias y emergencias de Bogotá (CRUE). Tesis de pregrado no publicada 2009.
Departamento de Ingeniería Industrial. Facultad de Ingeniería. Universidad de los Andes,
Bogotá, Colombia.
[5] Secretaría Distrital de Planeación. Acuerdo 308 de 2008: Plan de Desarrollo Distrital 2008-
2012. Recuperado el 12 de Noviembre de 2010, de: http://www.sdp.gov.co/section-
192823.jsp
[6] Brotcorne, L., Laporte, G., Semet, F. Ambulance location and relocation models. European
Journal of Operational Research 2003; 147(3): 451-463.
[7] Gendreau, M., Laporte, G., Semet, F. The maximal expected coverage relocation problem
for emergency vehicles. Journal of the Operational Research Society 2006; 57(1): 22-28.
[8] Gendreau, M., Laporte, G., Semet, F. A dynamic model and parallel tabu search heuristic
for real time ambulance relocation. Parallel Computing 2001; 27: 1641-1653.
[9] Gendreau, M., Laporte, G., Semet, F. Solving an ambulance location model by tabu search.
Location Science 1997; 5(2): 75-88.
[10] Céspedes, S., Amaya, C., Velasco, N. Localización y relocalización de ambulancias del
centro regulador de urgencias y emergencias de Bogotá. Tesis de maestría no publicada
2009. Departamento de Ingeniería Industrial. Facultad de Ingeniería. Universidad de los
Andes, Bogotá, Colombia.
[11] Rajagopalan, H., Saydam, C. A minimum expected response model: Formulation, heuristic
solution and application. Socio-Economic Planning Sciences 2009; 43: 253-262.
[12] Rajagopalan, H., Saydam, C., Xiao, J. A multiperiod set covering location model for
dynamic redeployment of ambulances. Computers & Operations Research 2008; 35: 814-
826.
[13] Rajagopalan, H., Vergara, F., Saydam, C., Xiao, J. Developing effective meta-heuristics for a
probabilistic location model via experimental design. European Journal of Operational
Research 2007; 177: 83-101.
[14] Goldberg, J. B. Operation Research models for the deployment of emergency services
vehicles. EMS Management Journal 2004; 1(1): 20-39.
29
[15] Ingolfsson, A., Budge, S, Erkut, E. Optimal ambulance location with random delays and
travel times. Health Care Management Science 2008; 11(3): 1515-1526.
[16] Maxwell, M., Henderson, S., Topaloglu, H. Ambulance Redeployment: An approximate
dynamic programming approach. Proceedings of the 2009 Winter Simulation Conference.
2009 Dec 13-16. Austin, Texas, USA.
[17] Andersson, T., Värbrand, P. Decision support tools for ambulance dispatch and relocation.
Journal of the Operational Research Society 2007; 58(2): 195-201.
[18] Andersson, T., Petersson, S., Värbrand, P. Dynamic ambulance relocation for a higher
preparedness. Proceedings of the 35th Annual Meeting of the Decision Sciences Institute
2004; Nov 20-23. Boston, USA.
[19] Andersson, T., Petersson, S., Värbrand, P. Calculating the preparedness for an efficient
ambulance health care. Proceedings of the 7th International IEEE Conference on
Intelligent Transportation Systems 2004; Oct 3-6. Washington D.C., USA. p. 785-790.
[20] Andersson, T., Petersson, S., Värbrand, P. OPAL: Optimized Ambulance Logistics.
Proceedings of the Fifth Triennial Symposium on Transportation Analysis 2004; Jun 13- 18.
Guadeloupe, West Indies.
[21] Haghani, A., Yang, S. Real time emergency response fleet deployment: concepts, systems,
simulation & case studies En: Zeimpekis, V.S., Tarantilis, C.D., Giaglis, G.M., Minis, I.E.
Dynamic Fleet Management: Concepts, Systems, Algorithms & Case Studies. Springer
series in Operations Research Computer Science Interfaces Series 2007; 38: 133-162.
[22] Church, R., ReVelle, C. The maximal covering location problem. Papers of the regional
Science Association 1974; 32: 101-118.
[23] Daskin, M., Stern, E. A hierarchical objective set covering model for emergency medical
service vehicle deployment. Transportation science 1981; 15: 37-152.
[24] Hogan, K., ReVelle C. Concepts and applications of backup coverage. Management science
1986; 34: 1434 – 1444.
[25] Goldberg, J., Dietrich, R., Chen, J., Mitwasi, M. Validating and applying a model for the
locating emergency medical services in Tucson, AZ. European Journal of Operational
research 1990b; 49: 308-324.
[26] Mandell, M. Covering models for two-tiered emergency medical services system. Location
Science 1998; 6: 355- 368.
[27] Marianov, V., ReVelle, C. The queuing probabilistic location set covering problem and
some extensions. Socio Economic Planning Sciences 1994; 28: 167 – 178.
[28] Repede, J., Bernardo, J. Developing and validating a decision support system for locating
emergency medical vehicles in Louisville, Kentucky. European Journal of Operational
Research 1994; 75: 567 – 581.
[29] Iannoni, A., Morabito, R., Saydam, C. An optimization approach for ambulance location
and the districting of the response segments on highways. European Journal of
Operational Research 2009; 195: 528-542.
[30] Dueñas M., Velandia M. Triage Hospitalario. Recuperado el 12 de Noviembre de 2010, de:
http://www.aibarra.org/Apuntes/criticos/Guias/Enfermeria/Triage_hospitalario.pdf