Algoritmo hibrido

A Hybrid Algorithm for Multi-depot Vehicle Routing Problem
María Alejandra Valencia Jhonny Alexander Ocampo Lina Marcela Rojas Hernán Darío Zuluaga

introducción


Con el desarrollo de la economía y los negocios comerciales, la distribución es una de las partes más importantes de la logística moderna. El problema de ruteo de vehículos (VRP), es un problema bien conocido de optimizacióncombinatoria.



introducción


El problema de ruteo de vehículo multideposito (MDVRP) es un problema NPcomplejo  “simultáneamente determina las vías de varios vehículos de más de un depósito a un conjunto de clientes, y luego vuelve al mismo almacén, sin exceder las limitaciones de capacidad de cada vehículo, minimizando el costo total de las rutas combinadas para una flota de vehículosy reduciendo al mínimo la distancia total recorrida ”

Key words
•

NP-hard problem:

en teoría de la complejidad computacional np-complejo es el

conjunto de los problemas de decisión que contiene un problema X con un problema Y
lo que hace es transformar el problema y polinomialmente, es encontrar un algoritmo A uno de lso problemas en X en un tiempo polinomico, reduciendo el problemaX ejecutando el algoritmo A.

•

Algoritmo Genetico: binarios al azar basado en funciones de desempeño Aplicados según probabilidad: cruzamiento (1 o 2 puntos, uniforme, etc.), mutación (negación de bit, al azar) .

•

Simulated annealing: Simulated annealing (SA) o recocido simulado es un algoritmo de búsqueda meta-heuristica para de problemas de optimización global, encontrar unabuena aproximación al óptimo global de una función en un espa.cio de búsqueda
grande.

Key words


Elitist selection: Característica de los MÉTODOS de Selección, Que garantiza la Supervivencia del Mejor individuo(S). Heuristica: procedimientos simples que realizan una exploracion limitada del espacio de búsqueda y dan soluciones de calidad



aceptable en tiempos moderados.
Heurísticas para encontrar el camino más corto: Para problemas de búsqueda del camino más corto el término tiene un significado

más específico. En este caso una heurística es una funcion matematica,
h(n) definida en los nodos de un arbol de busqueda, que sirve como una estimación del coste del camino más económico de un nodo dado hasta el nodo objetivo.

Estado del arte
http://catarina.udlap.mx/u_dl_a/tales/ documentos/lat/velazquez_d_e/capitul o2.pdf

Estado del arte


GONZALEZ VARGAS, Guillermo and GONZALEZ ARISTIZABAL, Felipe. Metaheuristics applied to vehicle routing. A case study: Parte 1: formulating the problem. Ing. Investig., Sep./Dec. 2006, vol.26, no.3, p.149-156. ISSN 0120-5609.
RESUMEN En este artículo se presentan la formulación matemática del problema de ruteode vehículos (VRP) y una serie de metodologías utilizadas por diferentes autores para resolver sus variaciones. Se presenta con el propósito de introducir al lector a una serie de artículos referentes a la decisión de localización de una empresa manufacturera tomando como criterio de selección la distancia total a recorrer para distribuir su producto.

Estado del arte
http://andresjaquep.files.wordpress.com /2008/12/estado-del-arte-vrp1.pdf Métodos Aproximados para la Solución del Problema de Enrutamiento de Vehículos (Dic 2008)
R. Andrés Jaque Pirabán*

Estado del arte


http://www.utp.edu.co/revistaciencia/32/2/articulo/algoritmohibrido-cumulo-de-particulas-y-busqueda-en-vecindario-variableusado-en-la-solucion-del-problema-de-la-mochila-bidimensional

Hybrid algorithmparticle swarm optimization and variable neighborhood search for the two-dimensional guillotineable single knapsack problem Resumen Articulo En este documento se presenta un algoritmo de optimización hibrido cúmulo de partículas y vecindario variable el cual utiliza una propuesta de codificación basada en árbol binario de cortes para resolver el problema de la mochila bidimensional guillotinada....