UNIVERSIDAD AUTNOMA DE NUEVO LEN Facultad de Ingeniera Mecnica y Elctrica
Maestro: Iris Abril Martinez Salazar Materia: Temas Selectos de Optimizacion
Tema:
DEMOSTRACION DEL METODOLOGIA GRASP EN VEHICLE ROUTING PROBLEM
HORA:M5
Alumnos: Israel Garca Martnez MAURICIO ORTIZ RIVERA SALVADOR ADRIAN REYES SILVA DANIEL IVAN CRUZ REYES
Matriculas: 1448574 1494718 1570296 1447043
DESCRIPCION DE PROYECTO
El proyecto trata de una demostracin de GRASP en un problema de Vehicle Routing, en el cual dando datos como el nmero de clientes, viajes, la capacidad del vehculo, demanda, tiempo y coordenadas , podremos sacar el tour ptimo del problema. Se realizo el proyecto en Java con funciones de acceso al archivo de texto.
REVISION DE LITERATURA
La Bsqueda Local es una tcnica utilizada para mejorar una solucin inicial para un problema de optimizacin. Es un proceso iterativo que consiste en lo siguiente. En cada iteracin se busca una solucin vecina de la solucin actual que mejore el valor de la funcin objetivo. Para cada solucin xX se define una estructura de vecindad. Algoritmo voraz es un procedimiento iterativo que, empezando con una solucin vaca, en cada iteracin se aade un elemento a la solucin, y el procedimiento termina cuando se obtiene una solucin factible. Para la seleccin de los candidatos se utiliza una funcin voraz que mide el beneficio de aadir el elemento a la solucin. El mtodo GRASP es un procedimiento iterativo que consiste en: una fase de construccin y una fase de bsqueda local. Se obtiene una solucin factible durante la fase de construccin aplicando un procedimiento voraz. En cada iteracin del procedimiento voraz se agrega un nuevo elemento a la solucin de acuerdo al valor de una funcin voraz. En lugar de escoger siempre el mejor elemento candidato, se construye una lista con los mejores candidatos, de donde se selecciona uno aleatoriamente. Una vez que se construye una solucin utilizando un procedimiento voraz, se realiza un procedimiento de bsqueda local. VRP: Vehicle Routing Problem. Es un problema clsico de optimizacin combinatoria con mltiples aplicaciones, en el que consiste de un deposito central, en donde una flotilla de vehculos disponibles con tanta capacidad de transportacin, para entregar a clientes que requieren productos con cierta demanda. Se desea minimizar los costos de transportacin (distancia total recorrida, nmero de vehculos, tiempo total de transportacin), disear las rutas de los vehculos que salen y regresan al depsito para satisfacer las demandas de los clientes, con ciertas restricciones operacionales.
METODO DE SOLUCION PROPUESTO
Para empezar creando los tours usando el algoritmo del vecino ms cercano con una metodologa un poco diferente de la tradicional. Al crear los tour lo que hicimos es crearlos de manera simultnea, para ver la posibilidad de disminuir latencia al momento de querer ingresar un cliente a un tour, teniendo como condicin al incluir el cliente al tour la capacidad del vehculo si tena capacidad se anexa este, de lo contrario se pasa al siguiente vehculo. Ya teniendo los tour hicimos un intercambio de cada uno de los nodos de un tour contra otros de un diferente tours para ver si podamos reducir la latencia de los tours
EXPERIMENTACION COMPUTACIONAL
CONCLUSION
El problema del ruteo de vehculos (VRP), como se menciona en lo anterior, se mostro los vehculos solicitados y las entregas hechas, que se encontr la solucin optima. El mtodo GRASP se procedi a iterar el algoritmo para ordenar, realizar las visitas y buscar disponibles. El proyecto presentado tuvo algunas consideraciones para demostrar la metodologa GRASP en el problema de Vehicle Routing, por lo que con la ayuda de compaeros y de lo aprendido en la clase, se obtuvo buenos resultados y mejoras al avance y su terminacin.
BIBLIOGRAFIA
An effective memetric algorithm for the cumulative capacitated Sandra Ulrich Nigueveu, Christian Prins, Roberto Wolfler Calvo An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routinfg problem Glaydston Mattos Ribeiro, Gilbert Laporte Capitulo 3. GRASP (Greedy Randomized Adaptive Search Procedures). Diseo de un algoritmo heurstico para el problema de localizacin p-mediana de Carlos Martn
Hernndez Ramrez
[Link]
El problema de ruteo de vehiculos Irma Delia Garcia Calvillo
[Link]
GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES (GRASP) [Link] [Link]
