Sistema RutaSoft
Informe de Experimentación Numérica
Versión 1.0
-
Integrante
|
Código
|
Carlos Velez Correa
|
20047227
|
Jonathan Pumapillo Gutarra
|
20052159
|
Jaime Díaz Riofrío
|
20060390
|
Tania Gonzales Villa
|
20060578
|
Miguel Benites Regalado
|
20064934
|
Historia de Revisión
Fecha
|
Versión
|
Descripción
|
Autor
|
30/09/10
|
1.0
|
Versión inicial
|
Miguel Benites
Carlos Velez
Jonathan Pumapillo
Jaime Diaz
Tania Gonzales
|
Tabla de Contenidos
Introducción 4
Definición del problema 4
Presentación de Algoritmos 4
Algoritmo Genético 4
Algoritmo Grasp 5
Variables de respuesta 5
Planeación del experimento 5
Planeamiento de Hipótesis 5
Factores Experimentales 5
Selección del Diseño Experimental 6
Planeación del trabajo experimental 6
Ejecución y análisis 7
Interpretación 9
Conclusiones 9
Informe de Avance
Introducción
El presente documento describe la experimentación numérica realizada con dos algoritmos de resolución de problemas de ruteo de vehículos.
En el documento se describirá el problema planteado, se presentarán los algoritmos a utilizar, la planificación del experimento, la ejecución de experimento, resultados y conclusiones.
Mediante la experimentación numérica se pretende saber que algoritmo es el más adecuado de acuerdo al problema planteado, las hipótesis planteadas, los factores de evaluaciones y pruebas estadísticas.
Definición del problema
El problema planteado (el cual se quiere resolver mediante la experimentación numérica) consiste en determinar la mejor ruta de asignación de clientes sobre una ciudad en particular dado una flota de vehículos cisterna.
Este problema se presenta en una empresa encargada de comercializar y distribuir gas licuado de petróleo a toda una ciudad. La solución que se intenta conseguir es encontrar la ruta óptima de viajes priorizando el menor consumo de combustible para llegar a un cliente.
Presentación de Algoritmos
Los algoritmos seleccionados para la experimentación numérica son el Algoritmos Genético y el Algoritmo Grasp.
Algoritmo Genético
Algoritmo inspirado en la evolución biológica. Consiste en un método de búsqueda dirigida basada en probabilidad. Se empieza con una población de individuos a los cuales se les hace evolucionar al someterlos a acciones aleatorias como mutación y cruzamiento. También existe el proceso de selección que de acuerdo a un criterio se decide cuáles son los individuos más óptimos que sobrevivirán y cuáles son los menos óptimos que serán descartados.
El algoritmo bajo condiciones probabilísticas débiles mantiene un cierto elitismo, es decir siempre guarda las mejores soluciones sin hacerles ningún cambio.
Consideraciones del algoritmo:
Si la función a optimizar tiene muchos máximos/mínimos locales se requerirán más iteraciones del algoritmo para "asegurar" el máximo/mínimo global.
Si la función a optimizar contiene varios puntos muy cercanos en valor al óptimo, solamente podemos "asegurar" que encontraremos uno de ellos (no necesariamente el óptimo).
Algoritmo Grasp
Algoritmos que utiliza métodos de construcción y mejora. Es decir se encuentra una solución factible inicial y se mejora mediante un procedimiento de búsqueda local.
Para las soluciones factibles iniciales se usa la lista de candidatos restringidos (RCL) en la que se incluyen a los mejores aspirantes para ser parte de la solución. Una constante de relajación es necesaria para establecer el tamaño de esta lista. Esta constante varia de 0 a 1.
La estructura del algoritmo es la siguiente:
Mientras no se satisfaga el criterio de parada
Construir una solución greedy aleatoria
Aplicar una técnica de búsqueda local a la solución greedy aleatoria obtenida en el paso anterior (para mejorarla)
Actualizar la mejor solución encontrada
Este algoritmo se basa en un criterio del algoritmo voraz, sin embargo es mas eficiente ya que agrega a la solución final los mejores elementos de cada iteración. Dichos elementos se obtienen de forma aleatoria. Las consideraciones y variables que presenta este algoritmo son las siguientes:
Parámetros
|
Consideraciones
|
Alfa=0.5
|
Hallada de manera empirica.
|
Número de Iteraciones por vehículo=1000
|
Hallada de manera empirica.
|
Variables de respuesta
Las variables de respuesta que se usarán para la comparación de los algoritmos son las siguientes:
Variable 1: Cantidad de combustible consumido.
Variable 2: Tiempo de ejecución.
Planeación del experimento
Planeamiento de Hipótesis
La hipótesis con la que se trabajará en la experimentación es la siguiente:
El Algoritmo Genético genera una mejor solución en comparación con la solución del algoritmo Grasp.
Factores Experimentales
Los factores experimentales que se aplicaran según el planteamiento de hipótesis son:
La distancia de cada cliente a la planta central.
La cantidad de pedidos realizados.
El tiempo requerido para obtener la solución.
La cantidad mínima de combustible empleado para llegar a un punto dado.
Selección del Diseño Experimental
El experimento planteado se basa en la aceptación o rechazo de pruebas de hipótesis estadísticas. Las conclusiones sobre las hipótesis estarán basadas en la muestra aleatoria de la población.
Se escoge emplear el estadístico T-Student debido a que se analiza muestras de una población normal y se requiere analizar medias utilizando una desviación estándar conocida.
El valor del nivel de riesgo será = 5%. Esto nos indica que se tendrá un 5 % de probabilidad de rechazar la Ho (Hipotesis nula) siendo esta cierta..
Distribución del estadístico t para dos muestras:
Sean:
Si: Varianza muestral del algoritmo i
Ni: Tamaño de las muestras
Planeación del trabajo experimental
Para la ejecución de la experimentación de los algoritmos se contará con el siguiente tipo de información:
Un archivo xml con la información relativa a los pedidos de los clientes que maneja la empresa.
Un método que crea los diferentes tipos de vehículos cisterna con los que cuenta la empresa.
La empresa brindó la siguiente información:
Vehículos: flota de 4 tipos de vehículos cuyo volumen de gas varia entre 8 y 30 toneladas de glp.
Clientes: cartera de 40 clientes con una cantidad promedio de 40 toneladas de glp.
Para cada algoritmo se aplican dichos tipos de datos en sus distintas iteraciones.
Los resultados obtenidos de cada algoritmo son el tiempo de ejecución y uso de combustible diesel total necesario para cada planificación de rutas. A partir de estos datos obtenidos se calcularán el promedio gasto de combustible diesel y del tiempo de ejecución. Luego se calcularán los estadísticos necesarios para aprobar o rechazar las hipótesis planteadas en cada uno de los experimentos.
Ejecución y análisis
Se define la ejecución de la experimentación.
Experimentos
Se describen las variables y las hipótesis utilizadas en el experimento.
Experimento 1
Este experimento permite comprobar cuál de los dos algoritmos, Genetico o Grasp, nos da un menor consumo de combustible en el planeamiento de rutas.
Definición de variables
Se definen las variables aleatorias que definen el gasto de combustible diesel necesario para realizar un plan de rutas.
X1= gasto de combustible del Algoritmo Genético.
X2= gasto de combustible del Algoritmo Grasp.
Las medias de estas variables.
μ1= gasto promedio de combustible del Algoritmo Genético.
μ2= gasto promedio de combustible del Algoritmo Grasp.
Las muestras tomadas de ambas poblaciones de de igual característica y número debido a que se trabaja sobre los mismos datos de entrada.
Planteamiento de hipótesis
Las hipótesis nula y alternativa planteadas para este experimento se describen a continuación.
H0: Mediante el algoritmo Genético se obtiene igual gasto de combustible promedio que con el algoritmo Grasp.
H0: μ1 = μ2
H1: Mediante el algoritmo Grasp se obtiene mayor gasto de combustible que con el algoritmo Genético.
H0: μ2 > μ1
Criterios de decisión
Considerando un nivel de significación =0.05, y seleccionada el estadístico T-Stundet para realizar la prueba de hipótesis se puede definir la siguiente región crítica.
R.C. = { T > t1-α,n1 +n2-2} prueba unilateral de cola derecha
Si se obtiene un estadístico a partir de los datos obtenidos de la muestra, que está dentro de la región crítica, entonces se rechaza H0 y se acepta H1. Caso contrario, se rechaza H1 y se acepta H0.
5.2 Interpretación de resultados
A continuación se describirán los resultados obtenidos.
Experimento 1
Se obtiene el siguiente cuadro con los cálculos más importantes de esta prueba.
Muestra:
Grasp
|
|
Genético
|
118.6855
|
|
124.6353
|
136.298
|
|
129.6056
|
170.274
|
|
186.3743
|
144.7964
|
|
136.2349
|
131.2571
|
|
126.1219
|
151.9261
|
|
128.8951
|
110.2853
|
|
112.0712
|
125.4893
|
|
124.6459
|
107.2508
|
|
119.8287
|
129.5583
|
|
149.7476
|
127.7226
|
|
108.4187
|
128.02
|
|
86.0088
|
124.8651
|
|
163.6597
|
140.1212
|
|
148.3029
|
153.8178
|
|
114.1722
|
164.4529
|
|
91.44022
|
139.131
|
|
171.8301
|
145.3523
|
|
118.3443
|
119.2865
|
|
121.7459
|
142.9583
|
|
145.1455
|
Resultado para una muestra de n=20:
Media
|
135.5774
|
|
130.3614
|
Desviación
|
16.68516
|
|
25.01842
|
t = 0.77595
Se rechaza Ho Si t > 1.9845
El valor 1.9845 se halla en la tabla t-Student con los grado de libertad n1+n2 -2 una probabilidad de 0.975 de acuerdo al definido= 5 % que es la probabilidad de rechazar Ho siendo esta cierta.
Entonces existe un 95 % de grado de confianza aceptar Ho siendo esto válido.
"Como t = 0.77595< 1.9845 se acepta Ho"
Interpretación
Conclusiones
El algoritmo Genético es más rápido que el algoritmo Grasp.
El algoritmo Grasp en promedio y conforme aumenta la muestra brinda mejores soluciones en promedio que el genético.
Las muestras utilizadas para el ejemplo tienen distribución normal
El algoritmo genético no es tan preciso conforme aumenta la cantidad de información de entrada, es decir mayor número de pedidos.
Para el Sistema se busca un algoritmo que de resultados estables a medida aumenten los pedidos de glp. Estos resultados deben ser eficientes en su uso de combustible diesel para los vehículos cisterna, además la generación de dicho plan de rutas debe ser en el menor tiempo posible. Entonces decidimos que pese a que el Algoritmo GRASP tiene un mayor tiempo de repuesta, es el que se implementara en la solución.
|
