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*pLa 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.