Tratamiento Multicriterio de Problemas de Ruta solucionados a través de Técnicas de Simulación Monte Carlo

Tratamiento Multicriterio de Problemas de
Ruta solucionados a través de
Técnicas de Simulación
Monte Carlo

1.
Introducción
2. Desarrollo
3. Orígenes y aspectos
teóricos de la Toma de Decisiones
Multicriterio
4. Primeros pasos en la solución
del Problema Práctico
5. Método STEM
6. Método VIA
7.
Conclusiones

1. Introducción.

La aplicación de las Técnicas de
Simulación Monte Carlo en la solución de Problemas
de Ruta ofrecen resultados computacionales satisfactorios
considerando el problema monocriterio: encontrar un tour de coste
o longitud total mínima.
Al plantear resolver un Problema de Ruta donde no sólo se
desee minimizar distancia y se consideren otros criterios, para
la determinación de la ruta "deseada", las técnicas
a utilizar deben ser otras y es necesario introducir en el
análisis herramientas
teóricas adicionales, es decir, debemos analizar el
problema con varios criterios de decisión dentro de una
nueva estructura
teórica: Toma de Decisión Multicriterio objetivo
fundamental de este trabajo.

2. Desarrollo.

Planteamiento del Problema.
Distinguimos entre "viaje" y "vehículo". Un "viaje" es una
ruta con base en el depósito que sirve a unos
vértices con una demanda total
no mayor que Q. Un "vehículo" estará definido por
un conjunto de tales "viajes", de
modo que la suma de los tiempos totales empleados no sea superior
a T horas. El tiempo empleado
por un vehículo en recorrer la arista (i,j),
tij, es estimado. La longitud de la arista
cij y el tiempo de descarga en cada nodo,
ti, son también conocidos, así como el
tiempo t0 necesario para cargar el vehículo en
el depósito. Se trata de minimizar, primero, el
número de vehículos y después, la distancia
total recorrida por los vehículos de modo que todos los
nodos sean servidos dentro de su horario.

Un ejemplo práctico de ello pudiera ser la
repartición de combustible a varias brigadas ubicadas
dentro de una red
caminera forestal. El camión cisterna debe salir de un
depósito con una capacidad y se irá moviendo
aleatoriamente dentro de la red hacia un nodo adyacente
(brigada). Si la demanda de esa brigada no esta cubierta y la
capacidad de que dispone el camión es mayor a la demanda
se abastece y se marca como tal,
se pasa entonces a otro nodo adyacente realizando la misma
pregunta, en caso de no ser cubierta la demanda con la carga del
camión en ninguna brigada o de que todas las brigadas
fueron abastecidas se vuelve al origen (depósito), de
quedar brigadas por abastecer y alcanzar la ventana de tiempo
establecida se comienza otro viaje. Solo se acude a otro
vehículo si las ventanas de tiempo preestablecidas para
cumplir con el abastecimiento no se cumplen con él o los
vehículos en trabajo.

Si observamos el algoritmo
descrito, ya se incluyen dos criterios a tener en cuenta, por un
lado minimizar el número de vehículos y por el otro
la distancia a recorrer cumpliendo con ventanas de tiempo, pero,
no necesariamente la distancia es proporcional al tiempo, sobre
todo si consideramos que los caminos más cortos pueden
resultar los más peligrosos y por consiguiente no los de
menor tiempo. Estos y otros criterios pueden presentar
contradicción con el criterio distancia, por tanto, es
necesaria una metodología que permita desarrollar el
problema como un Problema de Ruta Multicriterio, clasificado como
Problema de Ruta sobre vértices, donde la demanda de
servicio tiene
lugar en los vértices o nodos del grafo
(brigadas).

3. Orígenes y
aspectos teóricos de la Toma de
Decisiones Multicriterio.

La modelización multicriterio de las decisiones o
la preconizada por B. Roy y adoptada por Vincke (1989) citado por
(Barba-Romero, S. y col., 1997): Ayuda Multicriterio a la
Decisión, son expresiones beneficiosas para los que
comienzan aplicando este nuevo proceso de
tomar una decisión donde intervienen de manera natural
más de un objetivo.
El análisis de problemas decisionales con criterios
múltiples constituye quizás el área de
desarrollo más activo en los últimos años en
el campo de las ciencias de la
decisión (Investigación Operativa, Gestión
de Recursos, etc.)
según plantea (Romero,
C., 1993).
En el Congreso de las Asociaciones Europeas de
Investigación Operativa en 1975, el 3.5% de los trabajos
presentados estaban dedicados a temas multicriterios. Este
porcentaje en 1985 alcanzó el 14% mostrando un aumento
considerable.

Esta revolución
científica comenzó en el campo de las ciencias de
la decisión con los trabajos de Koopmans (1951), Jun y
Tucker (1951), Charnes, Cooper y Ferguson (1955) y Charnes y
Cooper (1961), citado por (Romero, C., 1993). Sus ideas pioneras
fueron desarrolladas por otros investigadores, culminando estos
esfuerzos en la primera Conferencia
Mundial sobre Toma de Decisiones Multicriterio (Multiple
Criterial Decision Making), que se celebró en Estados Unidos en
Octubre de 1972 en la Universidad de
Carolina del Norte. Tal acontecimiento puede considerarse el
nacimiento del paradigma
multicriterio, así como el comienzo de un nuevo
período de ciencia normal
en el campo de la ciencia de
las decisiones.

El proceso de tomar una decisión se puede
describir de la siguiente forma (Caballero, R. 1997):
"Planteado un problema se establece el conjunto de puntos
factibles o admisibles, en nuestro caso el correspondiente
conjunto que nos determina las restricciones del problema.
Después se le asocia a cada alternativa, criterio u
objetivo un grado de deseabilidad. Posteriormente se busca,
mediante cualquier técnica, una solución o un
conjunto de posibles soluciones
alternativas. Dichas soluciones posibles son aquellas que
satisfacen las restricciones y los deseos de preferencias, las
cuales se efectúan sobre los objetivos
planteados."

La parte de la Programación Matemática
que trata de buscar soluciones a los problemas multiobjetivos, se
encuadra dentro de un campo más general denominado
M.C.D.M. (Toma de Decisiones Multicriterio),
distinguiéndose el caso discreto que se denomina M.C.D.A.
(Toma de Decisión Multiatributo), y el continuo M.P.O.
Programación Multiobjetivo. (Caballero, R.
1997)

Aspectos básicos de la Programación
Multiobjetivo.
Un Problema de Programación Multiobjetivo responde a la
siguiente formulación:
Opt( f1(x), f2 (x), …,
fp(x))
s.a xÎ
X
donde:

• x=(x1,…,xn) son las
  variables de
  decisión,
• X es el conjunto de oportunidades,
• fi son cada uno de los
  objetivos,
• f=(f1, …,fp) es la
  función vectorial objetivo,
• Y=f(x) es el espacio de objetivos o espacio
  imagen.

Si se supone que en el problema original todos los
objetivos son de máximo, dicha consideración no
plantea ninguna limitación, dado que si alguno de ellos
fuera de mínimo tomaríamos la función
opuesta del problema, así:
Max(f1(x), f2(x),…,
fp(x))
s.a xÎ
X
se generan "p" problemas que serian:
(Pi) Max fi(x)
s.a xÎ
X

Tras la solución obtendremos p puntos
correspondientes a los máximos individuales de cada uno de
ellos, denotándolos por: x*1,
x*2,…,x*p
La
evaluación de los puntos óptimos en
sus correspondientes objetivos nos determinará un punto
que se denomina punto ideal:

(f1(x*1),
f2(x*2),…,
fp(x*p))
Es evidente que si existiera un punto en el cual todas las
funciones
alcanzan su máximo, el problema estaría resuelto,
pero esto es algo utópico, por tanto, tendremos que
proceder a intentar buscar una solución para nuestro
problema. Lo primero que se hace es construir la denominada
Matriz de
Pagos, en el cual evaluamos todas las funciones objetivo en los
óptimos individuales obtenidos en cada uno de ellos. La
diagonal principal de esta matriz de tamaño
pxp, corresponde al punto ideal, y las
correspondientes columnas nos indican el campo de
variación de los objetivos en los puntos obtenidos. Estos
intervalos se construyen tomando el valor
máximo y mínimo de la correspondiente columna,
así para cada objetivo determinamos:

[fimin,
fimax]
Obtenida la matriz de pagos asociada a nuestro problema, nos
planteamos de manera natural, con qué punto quedarnos;
ahora bien cómo comparamos si los resultados que tenemos
son vectores. De este
hecho surge la necesidad de establecer un orden, es decir, una
relación que nos establezca cuándo un vector es
preferido a otro.

Dentro del espacio vectorial Rp y dado
nuestro problema general de Programación
Multiobjetivo:
Max((f1(x), f2(x), …,
fp(x))
s.a xÎ
X
vamos a definir dos tipos de órdenes (la relación
la vamos a establecer atendiendo al valor que tomen los objetivos
en dichos puntos) (Caballero, R. 1997):

1. Orden de Pareto; Diremos que un punto x es preferido
   a x’ si se verifica que:
   fi(x) ³
   fi(x’) " i=1,…, p con al menos un j
   tal que fj(x) >
   fj(x’)
2. Orden débil de Pareto: Diremos que un punto x
   es preferido a x’ si se verifica que:
   fi(x) > fi(x’)
   " i=1,…,
   p

El orden de Pareto y el orden débil de Pareto son
ordenes parciales y nos establecen que una combinación
será preferida a otra siempre que en el primer caso mejore
a todos los objetivos, mejorando a uno de ellos de forma
estricta, y en el segundo, denominado débil, siempre que
mejore todos los objetivos estrictamente.

Como hemos comentado anteriormente, en general, no
existirá una combinación que sea a la vez
solución de todos los objetivos. De esta forma el primer
concepto que
perdemos es el de óptimo tal y como se entiende en la
programación monoobjetivo tradicional, y lo que buscaremos
para solucionar nuestro problema serán las denominadas
soluciones eficientes.
En general, en cualquier problema existirá más de
una solución eficiente y evidentemente estas no
serán comparables. Por tanto, el problema continúa,
y nos planteamos dos cuestiones importantes: por un lado,
¿cómo resolver estos problemas? y, por otro, una
vez resueltos ¿cómo realizar la elección
entre soluciones no comparables?
En muchas situaciones de la vida real surge la necesidad de
plasmar en un modelo, la
información disponible sobre un problema
real, con el fin de facilitar una comunicación fluida de las ideas aportadas
por las personas implicadas en la resolución del mismo. En
esta labor se destacan por su importancia dos figuras
específicas del dúo problema-modelo: el decisor y
analista. (Caballero, R. 1997)

• El analista o modelizador, que será la
  persona
  encargada de aplicar la técnica o técnicas
  adecuadas y posteriormente resolver el problema. No tiene
  poder para
  manipular el problema y sólo actúa con los
  datos del
  problema una vez planteado. Cuando lo resuelve será la
  persona encargada de proporcionar la información
  obtenida al centro decisor.
• El decisor o centro decisor, que será la
  persona o las personas encargadas de tomar la elección
  final una vez que conozcan la información dada por el
  modelizador de las posibles combinaciones factibles para el
  problema.

En la resolución del problema debe haber un
continuo intercambio de información crítica entre
el decisor y analista, sobre los diferentes aspectos del modelo
que haya que tener en consideración, hasta que se produzca
un total acuerdo entre ambas partes, sobre todo desde el punto de
vista del decisor. Una vez hechas las consideraciones oportunas,
el analista calculará una o varias soluciones que
presentará al decisor. El conjunto de acciones u
opciones en el que se ha de obtener la solución al
problema recibe el nombre de alternativas. El conjunto de todas
las alternativas posibles constituyen un conjunto que recibe el
nombre de espacio de decisión o también, conjunto
de oportunidades.

A partir de esto, tenemos una situación en la que
un decisor (a veces varios) trata de encontrar la alternativa que
más le satisfaga, dentro de las posibles, en base a unos
determinados criterios u objetivos. Dada una alternativa posible,
conocida como alternativa eficiente, los valores
correspondientes para cada uno de los criterios u objetivos con
dicha alternativa, constituyen un vector, llamado vector
criterio. El conjunto de todos los vectores criterio que se
obtienen a partir de todas las alternativas eficientes, recibe el
nombre de espacio criterio.
La misión de
la Toma de Decisiones Multicriterio es de encontrar la
alternativa que más desea o prefiere el decisor (en el
caso de que el decisor prefiera varias alternativas,
bastaría con conseguir una de ellas, ya que al decisor le
sería indiferente entre todas ellas). Lo ideal
sería tener una alternativa que fuese más preferida
o indiferente en cada uno de los criterios que cualquier otra
alternativa posible, ya que en ese caso, la buscada sería
esta. El problema va a estar en que los criterios están en
conflicto, lo
cual implica que cuando estamos mejorando uno de los criterios,
al menos vamos a estar empeorando otro (u otros), haciendo
imposible que exista dicha alternativa.

Parece lógico que la alternativa que más
satisface al decisor va a estar entre las alternativas
eficientes. Este hecho básico en el análisis de la
Toma de Decisiones Multicriterio, responde a la
representación de las preferencias de un decisor por un
orden parcial de tipo paretiano, de ahí, que a las
alternativas eficientes también se les conozca como
óptimos de Pareto. Este concepto constituye un aspecto
básico en todo el campo de la Toma de Decisiones
Multicriterio.
La idea de dirigir sistemáticamente al decisor hacia el
conjunto de alternativas eficientes, puede parecer en
determinadas ocasiones una mala idea, ya que puede dirigir
rápidamente al decisor a razonar en términos de
compensación: qué debo perder en un criterio para
esperar ganar en otro; quizás es preferido que el decisor
incremente progresivamente su satisfacción
encontrándose con una sucesión de alternativas
eventualmente no eficientes, hasta la última o
últimas que son eficientes.
La mayoría de las técnicas de resolución de
problemas de Toma de Decisiones Multicriterio tratan de, en
algunos casos, encontrar una buena representación del
conjunto de soluciones eficientes, y en otros, a partir de unos
niveles de aspiración conseguir, en el caso que le sea
posible, una alternativa eficiente que satisfaga dichos niveles
(solución satisfactoria), y en el caso que no le sea
posible, una alternativa eficiente que más ‘se
acerque’ en alguna medida a dichos niveles (solución
no satisfactoria).

4. Primeros pasos en la
solución del Problema Práctico.

El Algoritmo Monte Carlo ofrece una solución
monocriterio, este considera dos criterios implícitamente,
primeramente escoge aquellas rutas que generen menor
número de vehículos y dentro de ellas selecciona
aquella en la que se obtenga una menor distancia. La dificultad
estriba cuando se consideran otros criterios
adicionales.

Consideremos el caso más sencillo donde se
minimiza tiempo y distancia (ya está implícito el
número mínimo de vehículos). La
solución quedará representada gráficamente
en la frontera de un conjunto convexo que bien pudiera ser el
segmento entre los puntos A y B:

Donde:
A: Punto óptimo (minimizar criterio tiempo)
A´: Solución a través de técnicas de
simulación (minimizar criterio tiempo)
B: Punto óptimo (minimizar criterio distancia)
B´: Solución a través de técnicas de
simulación (minimizar criterio distancia).
Entre A´ y B´ existen infinitas soluciones factibles
imposibles de analizar en su totalidad.
Consideremos
=
1, entonces:
´i,
j), 1) +
´i,
j), 2) +…+
´i,
j), K)] = E(i,j)

Donde:
i, j), k sería el criterio k en
el arco (i,j), k: 1, 2,…, K
La solución por el algoritmo de ruta planteado y
considerando como criterio a tener en cuenta minimizar los
valores de
E(i,j), permitiría moverse en la frontera entre
los puntos extremos y entregaría tantas particiones como
combinaciones de  formemos. Un mayor
número de particiones permitiría al analista y al
decisor analizar una mayor cantidad de posibles soluciones en
cada iteración.

Para el ejemplo gráfico planteado se
buscaría entonces:

donde:

t(i,j): Criterio tiempo en el
arco(i,j).

d(i,j): Criterio distancia en el arco
(i,j)

Si consideramos

y  y
aplicamos el algoritmo de rutas planteado minimizando
E(i,j) obtendremos 5 posibles soluciones que se
encuentran entre A´ y B´ , observemos que
y
 hacen
corresponder las soluciones para los extremos (puntos ideales),
donde se minimiza tiempo y distancia respectivamente.

Quedará entonces la tarea de escoger, entre las
rutas generadas, aquella preferida por el decisor. Para el
ejemplo gráfico descrito puede resultar bastante sencillo
pues solamente quedan 5 alternativas para seleccionar entre
ellas, pero tengamos en cuenta que solamente se consideran dos
criterios y cinco valores de
 incrementar el
número de criterios, el número de particiones o
ambos representaría un incremento considerable de las
posibles rutas a analizar.

Primeramente debemos realizar un filtrado de las rutas
obtenidas. Este filtrado se basará en la
eliminación de aquellas rutas que resulten dominadas por
otras rutas según los criterios expuestos y posteriormente
con las rutas resultantes pasaríamos a aplicar Métodos
Interactivos para, con la participación activa del
decisor, escoger la ruta "más preferida".

Los métodos interactivos en la toma de decisiones
multicriterio, tanto en problemas continuos como discretos,
constituyen metodologías que conducen a un decisor a
obtener la solución o alternativa que más prefiera
dentro de las alternativas posibles entre las que puede elegir.
Este esfuerzo por reflejar las preferencias del decisor, hace que
la aplicabilidad y utilidad
práctica sean algo esencial en estos
métodos.

En cualquier otro método de
resolución en la Toma de Decisiones Multicriterio, las
preferencias del decisor sólo pueden manifestarse al
principio y/o al final del proceso de resolución, pero
nunca dentro del propio proceso. Este es el aspecto fundamental
en la Toma de Decisiones Interactiva: se trata de que a lo largo
del proceso de resolución, el decisor vaya manifestando
sus preferencias a través de determinadas preguntas, de
forma que dichas preferencias sean incorporadas en el problema,
para así conducirlo hasta su solución más
preferida.

El objetivo final de un proceso multicriterio
interactivo es encontrar una alternativa que sea la más
preferida del decisor dentro de las posibles (factibles), es
decir , aquella que se corresponda con el sistema de
preferencias del decisor, que en la mayoría de los casos
no se encuentra explicitado. En los métodos interactivos,
existe un flujo continuo de información entre el decisor y
el analista, del primero al segundo y viceversa, así pues,
el decisor, a lo largo del proceso, "diseña" de una u otra
forma dicha solución, al ir incorporando
información acerca de sus preferencias. En general el
esquema del método es proporcionar una solución que
el decisor acepta o rechaza. Si la rechaza, debe además
proporcionar al algoritmo información acerca de la misma
como por ejemplo, por qué no le gusta, qué le
gustaría más, por qué otra la
cambiaría… Este intercambio periódico
de información entre uno y otro agente del proceso
decisional constituye, además de la base operativa de los
métodos, la esencia de los mismos. El enorme interés de
dichos métodos, provocado por la sucesiva
incorporación de información en el proceso de
obtención de resultados, ha motivado a muchos autores a
trabajar en esta línea, lo cual se ha traducido en una
gran variedad de trabajos publicados.

Todos los métodos interactivos multicriterio se
pueden clasificar de acuerdo con las características del sistema de
comunicación que se establece entre el centro decidor y el
modelo a través del analista, según lo consultado
en la literatura
científica. Existen varias clasificaciones pero quisimos
compartir el criterio de Luque, M. (2000), quien los clasifica en
base a dos puntos de vistas distintos:

1. Información solicitada al decisor.
2. Análisis interno en la
   resolución.

Este tipo de clasificación posee
características y utilidades distintas, en el primero los
métodos se estructuran en consonancia a las preguntas
realizadas, mientras que el segundo afecta especialmente desde el
punto de vista del modelizador.
En lo que sigue desarrollaremos algunas ideas de estas
clasificaciones, debido a que en la solución de nuestro
problema práctico utilizaremos dos técnicas de este
grupo.

Clasificación en base a la información
solicitada al decisor.
La interacción con el decisor tiene por objeto que
éste manifieste sus preferencias sobre distintas
soluciones que le son mostradas en cada iteración, con el
fin de incorporar dichas preferencias en el proceso de
decisión y buscar una dirección dentro del conjunto de soluciones
factibles hacia una región más adecuada a dichas
preferencias. Según la información proporcionada
por el decisor en cada iteración, podemos distinguir entre
métodos en los que el decisor debe: (Caballero, R.
2002).

• Proporcionar en cada iteración los tradeoff o
  tasas de intercambio entre objetivos de forma local, es decir,
  a partir de la solución actual. Estos son conocidos como
  métodos interactivos de tradeoff.

Entre los métodos más importantes basados
en los tradeoff, desarrollados en Luque, M. (2000), cabe
resaltar: G-D-F (1972), IGP (1972), SPOT (1982) e ISWT
(1978).

• Elegir, en cada iteración, entre un conjunto
  de soluciones, generalmente eficientes. Los denominaremos
  métodos interactivos de generación de
  soluciones.

Entre los métodos más importantes de
generación de soluciones, desarrollados en Luque, M.
(2000), cabe resaltar: Zionts-Wallenius (1976) y Tchebychev
(1977).

• Expresar en cada iteración niveles de
  referencia para todos los objetivos o un subconjunto de ellos,
  que llamaremos métodos interactivos de
  programación por metas o niveles de
  referencia.

Entre los métodos más importantes de
programación por metas o niveles de referencia cabe
resaltar el Método Stem (1971) y el Método VIA
(Caballero, R., 2002), a los que dedicaremos especial atención por ser los utilizados para dar
solución al problema práctico planteado.

Clasificación en base al análisis interno
en la resolución.
La clasificación en base al análisis interno de
resolución, es menos importante desde el punto de vista
del decisor, puesto que el aspecto fundamental a tener en cuenta
por cualquier decisor, debe ser la información que se le
va a solicitar. A pesar de esto, no hay que olvidarse que la
manera de operar internamente influye directamente en la
solución o soluciones generadas en cada
iteración.
En esta clasificación una vez que el decisor proporciona
la información, se basa en el análisis de
cómo es procesada ésta, para obtener la ó
las nuevas soluciones. Cabría señalar en esta
clasificación el hecho de que puede haber métodos
que podrían estar en más de un grupo.
La clasificación realizada con respecto al análisis
interno de resolución es:

1. Método de reducción de la región
   factible. Principales métodos citados por Luque, M.
   (2000): STEM (1971), Vector Aspiration (1977), Tradeoff Cut
   (1980),…, etc.
3. Métodos de búsqueda en línea.
   Principales métodos citados por Luque, M. (2000): G-D-F
   (1972), IGP (1972), TSCP (1973),…, etc.
4. Métodos de reducción del espacio de
   pesos. Principales métodos citados por Luque, M. (2000):
   Z-W (1976), Tchebychev (1983), MOIP (1980),…,
   etc.
5. Métodos basados en multiplicadores.
   Principales métodos citados por Luque, M. (2000): ISWT
   (1978) y SPOT (1982)
6. Métodos de punto de referencia o
   función escalarizada de logro.

5. Método
STEM.

Este método pertenece a los métodos de
programación por metas o niveles de referencia
según la información solicitada al decisor, y a los
de reducción de la región factible según el
análisis interno en la resolución. El STEM (STEp
Method) es el método interactivo pionero y fue publicado
en 1971 por los autores R. Benayoun, J. De Montgolfier, J. Tergny
y O. Laritchev. En cada iteración, el método
restringe el conjunto de oportunidades en función de las
preferencias manifiestas por el decisor. Cada solución se
obtiene mediante la minimización de la distancia de
Tchebychev respecto al vector ideal sobre el conjunto de
oportunidades restringido. Las preferencias del decisor se
reflejan mediante la relajación de algún objetivo
satisfactorio, que permitirá mejorar algún otro
objetivo aún no satisfactorio.
Descripción detallada de forma
secuencial.
Los pasos a seguir de forma secuencial para el problema en el
método de Stem son los siguientes:
Paso 1: obtención de la matriz de pagos.

Paso 2: obtención de los valores de los
parámetros p
i (pesos normalizadores):

Denotamos por conjunto índices de las funciones a relajar en la
iteración h. e inicialicemos X0 = X,
J0 = Æ y h = 0.
Paso 3: cálculo de
los pesos de la distancia de la métrica de
Tchebychev:

Paso 4: se obtiene la solución que minimiza la
distancia desde el ideal al espacio objetivo restringido
. Para ello, se
resuelve el problema:

Dicha solución es denotada por y su correspondiente vector
criterio corresponde a .
Paso 5: el decisor manifiesta las preferencias sobre la
solución:

• Si está satisfecho, terminar con como solución
  final. STOP.
• En caso contrario, continuar.

Paso 6: sea h = h+1. El decisor especifica:

• Funciones a mejorar ().
• Funciones a relajar (), con las cantidades máximas a relajar
  ().

De esta manera se tiene la región factible de la
siguiente iteración:

Volver a paso 3 (obsérvese que ).

6. Método
VIA.

Este método pertenece a los métodos de
programación por metas o niveles de referencia
según la información solicitada al decisor, y a los
de punto de referencia según el análisis interno en
la resolución.
La característica fundamental es la utilización de
la función escalarizada de logro. En cada
iteración, se obtienen una o varias soluciones,
minimizando la función escalarizada de logro para el punto
de referencia proporcionado por el decisor, y puntos de
referencia cercanos al anterior, en el caso de obtener varias
soluciones. La información proporcionada por el decisor,
en cada iteración, corresponde al punto de referencia,
además de elegir entre varias soluciones.

Este método posee buena aceptación
práctica, motivado sobre todo por el carácter
intuitivo en la información requerida al decisor.
Además, también tiene la posibilidad de volver
hacia atrás ante errores cometidos en las preferencias del
decisor. Por otra parte, la solución obtenida en cada
iteración es débilmente eficiente, pero no tiene
porque ser eficiente, por tanto la solución final tampoco
tiene porque serlo (aunque en muchos casos la eficiencia de una
solución no es complicada de comprobar). Hay que
señalar también que el método no posee
convergencia matemática probada.

Descripción detallada de forma secuencial.
Los pasos que se deben llevar a cabo de forma secuencial, son los
siguientes:
Paso 1: sea h = 0. Consideración de los pesos para la función
escalarizada de logro. Obtención de una solución
inicial factible, que puede ser obtenida mediante la
resolución del problema:

Paso 2: se le pregunta al decisor si está
satisfecho con la solución obtenida:

• Si la respuesta es afirmativa Þ Solución final:
  .
  STOP.
• Si la respuesta es negativa, sea h = h +1 y
  continuar.

Paso 3: se le pide al decisor que especifique unos
nuevos niveles de referencia o punto de referencia , en base a los niveles
obtenidos en las funciones objetivo.

Paso 4: para distintos valores de l en el intervalo [0,1],
incluido l = 0,
resolvemos el problema:

obteniendo los vectores criterio solución que
denotaremos por .

Paso 5: de entre todos estos vectores criterio el decisor elige el
más preferido, denotándolo por y a su correspondiente
vector en el espacio de decisión por . Volver a paso
2.

Solución del Problema Práctico.
En nuestro ejemplo concreto se
consideraron 25 brigadas (nodos) interconectados entre si (325
aristas) por caminos forestales, las cuales deberían ser
abastecidas de combustible en un tiempo determinado.
Cada camino presenta una distancia, un tiempo estimado para su
recorrido, una puntuación de impacto ambiental
y una de peligrosidad entre 0 y 10, estos dos últimos
criterios con el objetivo de ser minimizados. Por tanto estamos
en presencia de un problema de ruteo con 4 criterios de
decisión. La expresión general a minimizar
quedará de la siguiente manera:

Donde:
t(i,j): Criterio tiempo en el arco (i,j).
d(i,j): Criterio distancia en el arco (i,j)
I(i,j): Criterio Impacto Ambiental en el arco
(i,j)
P(i,j): Criterio Peligrosidad en el arco
(i,j)

Se conformaron las rutas que entrelazan cada nodo
(aristas) y se generaron los ficheros para cada
combinación de valores de
Los valores a
minimizar estarán dados por la siguiente
expresión:

El algoritmo, como ya se dijo, implícitamente
minimiza el número de camiones a utilizar, lo cual podemos
considerarlo como un quinto criterio al cual se le da un
tratamiento lexicográfico, tomando como base una ventana
de tiempo que para nuestro ejemplo fue de 120 minutos, o sea, es
necesario atender la demanda de todas las brigadas en menos de 2
horas, se buscará entonces mejorar los restantes criterios
a partir de aquellas soluciones que generen un mínimo uso
del parque automotriz. Este tratamiento crea particularidades
específicas para el algoritmo que lo diferencia de otros
creados al efecto.
Se consideró además un tiempo de carga en el
depósito de 30 minutos, un tiempo de descarga de 15
minutos, capacidad de cada camión 900 litros y demanda en
cada brigada de 300 litros.
A partir de esta información se generaron los ficheros a
solucionar, ponderando cada uno de los criterios con 4
particiones (saltos de 0.25 unidades). Este salto puede variar en
dependencia de la precisión que se persiga, valores
más pequeños barrerían con una mayor
precisión la frontera del conjunto solución. Para
nuestro ejemplo se generaron 56 posibles combinaciones las cuales
fueron solucionadas y analizadas.
Del total de combinaciones analizadas 9 se consideran eficientes,
quedando el resto dominadas por estas. Los resultados de los
indicadores se
plasman a continuación:

A partir del conjunto de soluciones
obtenidas, aplicaremos dos técnicas interactivas muy
utilizadas en el campo continuo y extendidas al caso discreto. En
concreto, aplicaremos el método de punto de referencia VIA
(1986) y el método STEM (1971).

En nuestro ejemplo, el número de soluciones
obtenidas por cada una de las vías es pequeño, por
lo que la aplicación de las técnicas interactivas
podría sustituirse por una elección directa por
parte del decisor de la solución más preferida. Sin
embargo, hemos considerado oportuno aplicarlas, con el objetivo
de plasmar el funcionamiento de las técnicas y que puedan
ser aplicadas a otros problemas con un mayor número de
soluciones.

Partamos de una solución inicial, que podemos
tomar por ejemplo la primera:

que denotaremos por .

A partir de los valores conseguidos en cada uno de los
objetivos, el decisor, en base a sus preferencias, debe
proporcionar unos niveles de referencia en los objetivos. En
concreto, el decisor proporciona un tiempo de 1315 minutos, una
distancia de 545000 metros, un impacto ambiental de 160 unidades
y una peligrosidad de 165 unidades:

Con estos valores y tomando como puntos de referencia,
puntos en el segmento que une con ,
se obtienen varias soluciones obtenidas mediante la
minimización de la función escalarizada de logro de
las cuales, el decisor elige la solución 7:

Con esta solución, nos cambiamos al método
STEM, puesto que el decisor nos manifiesta que quiere mejorar los
objetivos Tiempo y Distancia, a cambio de
relajar los objetivos Impacto Ambiental y Peligrosidad en
cantidades 7 y 3 unidades respectivamente. Con estas
preferencias, la solución obtenida es la solución
5:

la cual satisface al decisor.

7.
Conclusiones.

1. La solución de los Problemas de Ruta requieren
   del uso de métodos heurísticos para su
   solución al constituir problemas NP-duros (No
   Polinómicos).
2. La constitución de una función
   ponderada que incluya varios criterios a tener en cuenta en los
   Problemas de Ruta y la consideración de la misma como
   función a minimizar, permite extender las
   Técnicas de Simulación Monte Carlo a Problemas de
   Ruta Multicriterios.
3. La generación de puntos pertenecientes a la
   frontera eficiente del Problema de Ruta Multicriterio nos
   garantiza valores eficientes a tener en cuenta por el decisor y
   el analista para escoger la estrategia
   más deseada.
4. Los Métodos Interactivos, en especial los
   Métodos Stem y VIA, constituyen herramientas muy
   eficientes que auxilian al decisor en la toma de decisiones
   definitiva.
5. La aplicación de la metodología
   propuesta en una red de caminos forestales con 25 brigadas a
   las que era necesario abastecer de combustible con una ventana
   de tiempo de 2 horas, garantizó trazados de rutas
   eficientes considerando cinco criterios, número de
   vehículos (ya incorporado en el algoritmo de
   solución Monte Carlo), distancia, tiempo, peligrosidad e
   impacto ambiental.

Se obtuvieron nueve soluciones eficientes después
de filtrada la información a las cuales se les
aplicó, de manera demostrativa, los métodos
interactivos VIA y Stem. Estos métodos nos permitieron
valorar los posibles deseos del decisor para escoger la "mejor"
solución.

8. Bibliografía.

• Barba-Romero, S. y Romerol, J. Ch., Decisiones
  Multicriterio. Fundamentos Teóricos y Utilización
  Práctica. Colección de Economía.
  Universidad de Alcalá. 1997.
• Caballero, R., Gómez, T., González, M.,
  Muñoz, M. M., Rey, L., Ruiz, L., Programación
  Matemática para Economistas. Universidad de
  Málaga.1997.
• Caballero, R., Luque, M., Molina, J., y Ruiz, F.,
  Programación Multiobjetivo Interactiva. Series
  Monográficas. Toma de decisiones con criterios
  múltiples. Revista
  Electrónica de Comunicaciones y Trabajos de ASEPUMA Rect@.
  Valencia. 2002.
• Luque Gallego, M., Toma de Decisiones multicriterio
  con Métodos interactivos. Implementación
  Computacional y Aplicación a la Economía de la
  salud.
  Málaga. 2000
• Romero, C., Teoría de la decisión
  multicriterio: Conceptos, técnicas y aplicaciones.
  Alianza editorial, S.A. Madrid. 1997.

Resumen.
La determinación de rutas cada vez más eficientes
para la repartición de recursos en los bosques constituye
una problemática difícil de resolver en el
aprovechamiento forestal, sobre todo si se conjugan criterios que
pueden contraponerse entre sí (distancia, medios
de transporte, tiempo, peligrosidad, entre otros).
En este trabajo se desarrollan una metodología para la
solución de esta problemática, basada en
Técnicas de Simulación Monte Carlo para la
obtención del Conjunto Eficiente de un problema de
Programación Multiobjetivo. Sobre la aproximación
del conjunto eficiente obtenida se aplica un método
interactivo de toma de decisiones multicriterio para la
búsqueda de las mejores alternativas.

Autor:

MsC. Caridad Beatriz Saavedra Castillo. (*)

Dr. Osvaldo Fosado Téllez. (*)

Dr. Pedro Fernández de Córdoba Castellá.
(**)

(*) Universidad de Pinar del Río. Cuba.
(**) Universidad Politécnica de Valencia. España.