Vrppd pickup and delivery
-
Upload
rudo-shinoda-benington -
Category
Engineering
-
view
52 -
download
6
Transcript of Vrppd pickup and delivery
![Page 1: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/1.jpg)
VRPPD problema con entregas y devoluciones(Pickup And Delivery)
BÁEZ MARTÍNEZ JESÚS ALBERTO MATRICULA 13LOT003
HERNÁNDEZ MARTÍNEZ IRAIS MATRICULA 13LOT012
MANZANITA RODRÍGUEZ ANDREA MATRICULA 13LOT023
RAMÍREZ GARCÍA RODOLFO MATRICULA 13LOT034
SÁNCHEZ SÁNCHEZ JONATHAN JAIR MATRICULA13LOT044
![Page 2: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/2.jpg)
1
2
CONTENIDO
Introducción
Antecedentes
Concepto de VRPPD
Casos de aplicación
Formas de solución
Algoritmo de enjambre
Ejemplos
Conclusión
referencias
![Page 3: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/3.jpg)
1
3
INTRODUCCION
El problema de enrutamiento de vehículos (VRP) es un problema de optimización combinatoria de gran importancia en diferentes entornos logísticos, consiste en servir una serie de clientes ubicados geográficamente de manera dispersa, para atenderlos se cuenta con una flota de vehículos que parten desde un deposito central, el problema consiste en asignar a cada vehículo una ruta de clientes, de manera que se minimice el costo de transporte
![Page 4: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/4.jpg)
1
4
ANTECEDENTES
El problema de enrutamiento o ruteo de vehículos (VRP, vehicle routing problem) data del año de 1959 y fue introducido por Dantzig y Ramser, quienes describieron una aplicación real de la entrega de gasolina a las estaciones de servicio y propusieron una formulación matemática.
Cinco años después Clarke and Wright propusieron el primer algoritmo que resulto efectivo para resolverlo.
![Page 5: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/5.jpg)
1
5
Variaciones y derivaciones del Problema de enrutamiento de Vehículos
Haga clic en el icono para agregar una imagen
![Page 6: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/6.jpg)
1
6Concepto “VRPPD (Vehicle Routing Problem with Pick-Up and Delivery)”
VRPPD (Vehicle Routing Problem with Pick-Up and Delivery), en esta variante del problema, además de las entregas realizadas a los clientes, de manera simultanea se realizan recogidas retornando algún tipo de producto.
![Page 7: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/7.jpg)
1
7
Casos de Aplicación
Algunos de los entornos reales para los que el estudio del VRPPD es de gran importancia se encuentran en mensajería, transporte de valores, recolección de basura, transporte de contenedores, transporte de pasajeros, transporte de alimentos y transporte de combustible.
![Page 8: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/8.jpg)
1
8
Formas de soluciónEl VRP es de complejidad NP-co, diferentes métodos se han propuesto para su solución, estos se pueden agrupar en dos grandes grupos:
Exactos (Polinomial) Algoritmo de Branch and Bound (B&B)
Branch and Cut (B&C)
Branch and Price (B&P).
Aproximados. (Heurísticos) Algoritmos de Enjambre
Algoritmos Evolutivos
Sistemas Inmunes Artificiales
Algoritmos de Búsqueda Local
Algoritmos Constructivos
![Page 9: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/9.jpg)
1
9
Algoritmos de Enjambre
Estos algoritmos replican la sinergia que presentan estos sistemas en los que el comportamiento colaborativo de los integrantes del enjambre les permite desarrollar tareas complejas que exceden la capacidad de un solo individuo
El algoritmo inspirado en el comportamiento comunitario de las hormigas, permite aprovechar el éxito que tienen estos esquemas biológicos aplicándolos en la búsqueda de soluciones para problemas complejos de optimización como el VRP.
![Page 10: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/10.jpg)
1
10
Ejemplos
Alshamrani et. al. Tratan un problema de logística reversa inspirado en la situación real de distribución de sangre del American Red Cross, en este problema se debe planear la entrega de los contenedores por los camiones mientras que de manera simultanea se debe estimar la cantidad de contenedores que deben ser recogidos por los camiones en cada parada.
Repoussis et. al, Trata también un problema de logística reversa en la recolección y reciclaje de desperdicios de aceites lubricante
![Page 11: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/11.jpg)
1
11
Conclusión
La combinación de estrategias que permitan la reducción de la complejidad del problema, y el mejoramiento de las soluciones son los enfoques más usados.
![Page 12: Vrppd pickup and delivery](https://reader035.fdocumento.com/reader035/viewer/2022081419/55c7e6dfbb61eb60478b45aa/html5/thumbnails/12.jpg)
1
12
Referencias
Jaque, R. Andrés. (2008). “Métodos Aproximados para la Solución del Problema de Enrutamiento de Vehículo”. Pdf
Linfati, Rodrigo. (2014)“An algorithm based on granular tabu search for the problem of balancing public bikes by using multiple vehicles” Dyna, vol. 81, núm. 186, agosto, 2014, pp. 284-294. Universidad Nacional de Colombia Medellín, Colombia.
P.P. Repoussis, et. al, “A web-based decision support system for waste lube oils collection and recycling” European Journal of Operational Research Vol. 195 (2009) pp. 676–700
H. Zeng, et. al “A hybrid Algorithm for Large-Scale Vehicle Routing Problem in Real Traffic Condition” IEEE International Conference on Automation and Logistics, 2007