Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Presentación Sustentación

Presentación Sustentación
by

hugo martinez

on 19 August 2010

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Presentación Sustentación

Un problema combinatorio consiste en encontrar un objeto entre un conjunto finito de objetos. Este conjunto finito se define como la delimitación del problema de optimización. " MÉTODOS HEURÍSTICOS PARA LA SOLUCIÓN DE PROBLEMAS DE RUTEO DE VEHÍCULOS CON CAPACIDAD (CVRP)" Tesis de grado para optar al título de Ingeniera industrial CLAUDIA MARCELA CONTRERAS PINTO
MARÍA FERNANDA DÍAZ DELGADO Director del proyecto:
Ph. D Henry Lamos Díaz CONTENIDO 1. Objetivos
2. Antecedentes del CVRP
3. Problemas Combinatorios
4. Problema de Ruteo de Vehículos
5. Instancia
6. Formulación matemática del CVRP
7. Métodos heurísticos para el CVRP
8. Comparación de Resultados
9. Software H-CVRP
10. Conclusiones y Recomendaciones OBJETIVO GENERAL Desarrollar algunas técnicas heurísticas para la solución del problema de ruteo de vehículos con capacidad (CVRP) en Matlab.
OBJETIVOS ESPECÍFICOS ANTECEDENTES El problema del CVRP (Capacitated Vehicle Routing Problem ó Problema de Ruteo de Vehículos con Capacidad) definido hace más de 40 años, ha sido uno de los más desafiantes que presentan los problemas de optimización combinatoria.
Surge a partir del TSP (Travelling Salesman Problem ó Problema del Agente Viajero), despertando un interés por su práctica utilidad, así como por su considerable dificultad.

Desde entonces se sigue investigando acerca de él ya que es considerado uno de los mayores sucesos en la investigación de operaciones. Estudiar los métodos de solución de problemas de ruteo de vehículos con capacidad CVRP.

Seleccionar y comparar los métodos Heurísticos que se usan para la solución del problema CVRP. Desarrollar el Toolbox en MATLAB correspondiente a los métodos heurísticos elegidos para la solución de problemas de ruteo de vehículos con capacidad CVRP.
Elaborar el manual de usuario del Toolbox desarrollado.
ANTECEDENTES PROBLEMAS
COMBINATORIOS MODELO DECISION Un conjunto de variables de decisión (Variables independientes).
Una función objetivo (F.O.) que mide la efectividad de cada sistema de decisiones.
Un conjunto de restricciones que representan las limitaciones bien sea de capital, recursos etc.
VRP El problema consiste en encontrar la ruta con el menor costo, usando la cantidad mínima de vehículos para visitar a un conjunto de clientes distribuidos geográficamente. VARIANTES DEL VRP
INSTANCIA Las instancias son aquellas características o datos del problema, que se usan en un planteamiento concreto y generalmente están asociadas a los vehículos y a los clientes.
Formulación matemática del CVRP Éste conjunto de restricciones se denomina restricciones de corte-capacidad (CCCs) donde r(S) es el número mínimo de vehículos que se requieren para atender el conjunto de clientes (S).
RAZONES PARA USAR UN MÉTODO HEURÍSTICO Las Heurísticas de Inserción son métodos con los cuales se pueden hallar las soluciones parciales de las rutas. En cada iteración, hay una solución parcial donde las rutas visitan solo a un subconjunto de los clientes. Se elige a uno de los clientes que aún no haya sido visitado y se inserta en la solución.
Algoritmo 3 - OPT El algoritmo 3-opt, es un método de muestreo utilizado para generar poblaciones de soluciones localmente óptimas.
La ruta inicial puede ser calculada aleatoriamente o ser el resultado de la aplicación de alguna heurística.
PASOS ALGORITMO 3 - OPT 1. Se define el criterio de parada.

2. Se intercambian 3 arcos al azar en la ruta inicial (r-opt) creando una nueva ruta denominada (r-new).

3. Se comparan las longitudes de (r-new) y (r-opt).
Si (r-new) < (r-opt), (r-opt) = (r-new).
Si (r-new) > (r-opt), se repite este paso hasta que se cumpla el criterio de parada.
Este algoritmo opera en dos fases.

Fase 1: Determinación de cantidad de rutas y nodos iniciales.

Fase 2: Asignación de clientes a las rutas.
Este algoritmo es una extensión del algoritmo de barrido el cual agrega los clientes a una ruta trazando una línea recta desde el depósito e incorpora los clientes “barridos” sin que se violen las restricciones de capacidad.
De este conjunto formado de rutas R, se debe escoger un sub-conjunto de R que visite exactamente una vez a cada cliente, el cual se formula por medio del Set Partitioning Problem (SPP):
Paso 1. Calcular una ruta que solucione el VRP.

Paso 2. Construir un grafo que represente los nodos, permitiendo rutas que respeten las restricciones de capacidad.

Paso 3. Solucionar el SPP encontrando el camino mas corto. (Dijkstra).
ALGORITMO DE AHORROS El algoritmo supone la posibilidad de unir dos rutas diferentes (0,…i, 0) y (0, j,…,0) para formar una nueva ruta (0,…, i, j,…,0) con un ahorro en los costos. MÉTODOS
HEURÍSTICOS
PARA LA SOLUCIÓN
DEL CVRP
MÉTODOS
CONSTRUCTIVOS MÉTODO
DE
BÚSQUEDA
LOCAL HEURÍSTICAS
DE
INSERCIÓN


INSERCIÓN EN PARALELO
DE CHRISTOFIDES
MINGONZZI Y TOTH

INSERCIÓN SECUENCIAL
DE MOLE AND JAMESON


RUTEAR PRIMERO ASIGNAR DESPUES

PÉTALOS
ALGORITMO DE AHORROS
CLARKE AND WRIGHT

MEJORA CW

VECINO MAS CERCANO

No se conoce ningún método exacto que le brinde solución.

Se conoce un método exacto que le brinde solución pero el tiempo computacional que requiere es demasiado largo.

El método heurístico es más flexible que el método exacto, es decir, permite incorporar condiciones que son difíciles de modelar.
Los métodos heurísticos para el CVRP son aquellos que dan una solución factible al problema, sin asegurar que esa solución obtenida sea la óptima. La heurística de Mole & Jameson usa dos criterios para la elección de clientes a insertar.

Primer criterio: Examinar los clientes que aún no han sido visitados y calcular la mejor posición para insertarlos en la ruta actual.

Segundo criterio: Medida de urgencia.
HEURÍSTICA DE INSERCIÓN DE MOLE AND JAMESON Paso 1 (Creación de una ruta): Si todos los clientes pertenecen a alguna ruta, terminar. Si no, seleccionar un cliente no visitado w y crear la ruta r = (0, w, 0).

Paso 2 (Inserción): Sea r = donde
Para cada cliente no visitado w, calcular si no hay inserciones factibles, ir al paso 1. Calcular Insertar w* luego de en r.

Paso 3 (Optimización): Aplicar el algoritmo 3-opt sobre r. Ir al paso 2.
Este algoritmo opera en dos fases.

Fase 1: Determinación de cantidad de rutas y nodos iniciales.
Fase 2: Asignación de clientes a las rutas.
FASE 1
Paso 1 (Nueva ruta). Hacer k = 1
Paso 2 (Cliente inicial). Seleccionar un cliente no visitado
para insertar en la ruta. Para cada cliente no visitado w, calcular
Paso 3 (Inserciones). Calcular sobre los clientes no visitados w. Insertar w en la ruta y aplicar el algoritmo 3-opt. Si quedan clientes no visitados que puedan insertarse en la ruta, ir a 3.
Paso 4 (Siguiente ruta). Si todos los clientes pertenecen a alguna ruta, terminar. Si no, hacer k = k + 1 e ir a 2
FASE 2

Paso 5 (Inicialización): Crear k rutas para t = 1,. . ., k, siendo k la cantidad de rutas obtenidas en la fase 1. Sea
conjunto de rutas a asignar.
Paso 6 (Asociación): Para cada cliente w que no haya sido visitado calcular
Paso 7 (Urgencias): Seleccionar del conjunto J y hacer .
Para cada cliente w tal que , calcular y y
Paso 8 (Inserción): Calcular Insertar en la ruta y aplicar el algoritmo 3-opt. Si quedan clientes asociados a que pueden ser insertados, ir a 8.
Paso 9 (Finalización): Si , ir a 6. Si todos los clientes han sido visitados, terminar.


PROBLEMA DE OPTIMIZACIÓN COMBINATORIA
PARA EL CVRP El conjunto de decisiones: Es el conjunto de rutas posibles que satisfacen las restricciones.
La función objetivo: Costo de una solución.
Las restricciones sujetas a este problema son:

1. Cada cliente es atendido una vez por exactamente un vehículo.
2. La demanda total de cada ruta no debe exceder la capacidad del vehículo.
3. Cada ruta empieza y termina en el depósito
FASE 1 FASE 2 INSERCION EN PARALELO DE CHRISTOFIDES, MINGOZZI Y TOTH RUTEAR PRIMERO
ASIGNAR DESPUES Paso 1 Calcular una ruta que solucione el VRP.
Paso 2 Construir un grafo que represente los nodos, permitiendo rutas que respeten las restricciones de capacidad.
Paso 3 Solucionar el SPP encontrando el camino mas corto. (Dijkstra).
ALGORITMO DE PETALOS ALGORITMO DE AHORROS
CLARKE AND WRIGHT El algoritmo supone la posibilidad de unir dos rutas diferentes (0,…i, 0) y (0, j,…,0) para formar una nueva ruta (0,…, i, j,…,0) con un ahorro en los costos.
El ahorro de unir las rutas (0, i, 0) y (0, j, 0) es:





Donde Cij es el costo de ir del nodo i al nodo j.
El costo total asociado a cada solución es:






El número total de ahorros es igual a:

Condiciones de factibilidad para la unión de 2 rutas:

El nodo j debe ser visitado enseguida del nodo i.

La fusión se realiza siempre y cuando no se borre una conexión directa establecida previamente entre los dos clientes.

Cumplir con las restricciones de capacidad.
Una empresa cuyo depósito está ubicado en Bucaramanga (0) debe distribuir sus productos a sus 6 clientes localizados en las ciudades de Barranquilla (1), Bogotá (2), Medellín (3), Leticia (4), Cali (5) e Inírida (6). La capacidad del vehiculo es de 160 unidades.
RUTAS INICIALES Costo Inicial El número total de ahorros es de:
PRIMERA ITERACION SEGUNDA ITERACION Costo Total:

(0,3) + (3,2) + (2, 1) + (1, 5) + (5, 0) + (0, 4) + (4, 6) + (6, 0)

Es decir,

8 + 6 + 12 + 4 + 6 + 7 + 8 + 3 = 54 respectivamente.

Ahorro:

94 – 54 = 40 unidades monetarias.
MEJORA DEL ALGORITMO DE AHORROS DE CW Se introduce en la formula original, el parámetro λ llamado forma de la ruta (λ) que evita la formación de rutas circulares.

Calculo de los ahorros mejora CW:
HEURISTICA DEL VECINO MAS CERCANO PASOS

1. Ubicarse en un nodo inicial (Depósito).

2. Tomar la distancia desde el nodo agregado hacia todos y cada uno de los nodos restantes.

3. Escoger el nodo que tenga menor distancia en relación con el último nodo agregado, siempre y cuando no haya sido considerado.
4. Repetir el paso 2 hasta incluir todos los nodos. De esta forma se construye la trayectoria.

5. El algoritmo termina cuando se han unido todos los nodos según su cercanía.

6. Después de haber construido toda la trayectoria, unir el último nodo encontrado con el depósito, para indicar que la ruta regresa al depósito de donde partió inicialmente.
NODOS INICIALES

ELECCION NODO SALIDA RUTA LUEGO DE LA PRIMERA BUSQUEDA ELIMINACION DE NODOS ELIMINACION DE NODOS ELECCION SEGUNDO NODO RUTA SEGUNDA ITERACION ELECCION TERCER NODO RUTA TERCERA ITERACION ELIMINACION DE NODOS RUTA CUARTA ITERACION ELECCION CUARTO NODO Ck es el costo de cada petalo ELIMINACION DE NODOS ELECCION QUINTO NODO RUTA QUINTA ITERACION ELIMINACION DE NODOS ELECCION NODO FINAL RUTA FINAL COSTO TOTAL

3 + 2 + 8 + 8 + 6 + 15 + 6 + 5 + 7 = 60
unidades monetarias.
CALCULO DEL GAP PARA
ALGUNAS INSTANCIAS GAP
ALGORITMO DE AHORROS GAP
VECINO MAS CERCANO CONCLUSIONES
Y OBSERVACIONES Los resultados obtenidos en este trabajo de investigación son la solución al problema de ruteo de vehículos con capacidad a través de una herramienta de software llamada H-CVRP que utiliza dos métodos heurísticos para hallar las rutas a asignar a la flota de vehículos.
El primer método implementado en el programa fue el vecino más cercano con el cual se corrieron todas las instancias planteadas por Christofides. Los errores obtenidos al comparar el valor optimo del problema versus la solución arrojada por H-CVRP, oscilan entre el 14.61% y el 47.2%.
El segundo método implementado en el programa de computadora fue el algoritmo de ahorros de Clarke And Wright con la mejora, la cual fue propuesta por Gaskell y Yellow y que consiste en adicionar a la fórmula del cálculo de los ahorros, un parámetro lambda llamado parámetro de forma de la ruta que evita la formación de rutas circulares. Los resultados a las diferentes instancias que se obtuvieron mejoraron en la mayoría de los casos cuando lambda toma valores de 0.4 y 0.8, sin embargo en algunos casos, el mejor resultado se obtiene al ingresar un lambda igual a 1 que equivale a ejecutar el programa con el algoritmo de Clarke and Wright sin la mejora.
Teniendo en cuenta que la forma de búsqueda del vecino más cercano consiste en inspeccionar en la vecindad de cada nodo y que las heurísticas constructivas buscan en cada iteración una mejor solución, puede ocurrir que las soluciones encontradas sean solo óptimos locales. Por esta razón los errores encontrados al realizar comparaciones con los valores óptimos de las instancias son significativos. Sin embargo, se debe aclarar que las heurísticas debido a que son procedimientos con un alto grado de confianza, en algunas ocasiones encuentran el valor óptimo de la función objetivo, aunque este no pueda llegar a corroborarse. 
Comparando los resultados obtenidos por los dos algoritmos para las mismas instancias se puede concluir que en la mayoría de los casos el algoritmo de ahorros llega a mejores soluciones que el algoritmo del vecino más cercano.
Los errores que se obtuvieron de la comparación de los valores óptimos de las instancias de Christofides versus los valores arrojados por H-CVRP para el algoritmo de ahorros oscilan entre el 11.37% y 55.94%.

Estas heurísticas pueden ser usadas para calcular las soluciones iniciales de métodos metaheurísticos.
SOFTWARE
HCVRP MUCHAS GRACIAS!!! Capacidad del Vehiculo = 80 unidades
Demanda nodo 6 = 35 unidades Capacidad disponible 80 - 35 = 45 unidades Demanda cliente 1 = 32 unidades
Capacidad disponible 45 - 32 = 13 unidades Capacidad vehiculo = 80 unidades Demanda cliente 5 = 40 unidades
Capacidad disponible = 80 - 40 = 40 unidades Demanda cliente 4 = 39 unidades
Capacidad actual = 40 - 39 = 1 unidad Capacidad vehiculo = 80 unidades
Demanda cliente 3 = 31 unidades Capacidad actual = 80 - 31 = 49 unidades Demanda cliente 2 = 48 unidades
Capacidad actual 49 unidades
Capacidad disponible 49 - 48 = 1 unidad Seguir desarrollando investigaciones en esta área
para tener mas herramientas de investigacion de operaciones y diseño de experimentos y poder verificar los problemas combinatorios. En la Escuela de Estudios Industriales y Empresariales de la UIS deberian existir cursos permanentes de Matlab, para permitir a los estudiantes ser desarrolladores de problemas. ARCHIVOS H-CVRP cvrp.m --> Código Fuente
cvrp.fig --> Cuadro diálogo
algoaho.m --> Código ahorros
vecino.m --> Código vecino mas cercano RECOMENDACIONES CUARTA ITERACIÓN TERCERA ITERACION
CUARTA ITERACION Para el estudio realizado se considera una flota homogénea de vehículos.
Full transcript