Caso particular del problema del transporte: vrpb
Páginas: 38 (9436 palabras)
Publicado: 7 de enero de 2011
Métodos Cuantitativos III
Caso particular del problema del Transporte:
VRPB
Grupo: 6
Sergi Cercós Carbó
Miloud El Bakouri El Haddaji
David Modroño Preixens
Silvia Poyato Hernández
Pedro A. Ramírez Cobo
Mònica Viso Balduz
23/05/08
Índice
1.- Introducción: 3
2.- Definición del problema VRP: 4
2.1.- Instancia del problema VRP: 5
3.- Variantes del problema VRP: 84.- Caso concreto de estudio: VRPB 10
5.- Algoritmos de solución y aplicaciones: 12
5.1.- Algoritmo de Gillett y Miller 12
5.1.- Algoritmo de Fisher y Jaikumar 18
5.3.- Algoritmo de Clarke & Wright modificado 25
5.3.- Conclusiones 32
6.- Software de ejemplo: 33
6.- Opciones: 37
9.- Bibliografía: 43
El Problema del Transporte
El problema del transporte o VRP (VehicleRouting Problem) consiste en determinar un conjunto de rutas minimizando el coste total de transportar paquetes de un origen a un destino. Se ha tratado de disminuir ese coste por medio de la utilización de métodos de computación para calcular las rutas óptimas o cercanas a las óptimas. Implementar el problema VRP en casos reales es difícil por el gran número de restricciones que se deben considerar.1.- Introducción:
El problema del transporte (Vehicle Routing Problem o VRP), consiste en determinar un conjunto de rutas para una flota de vehículos que parten de uno, o más depósitos o almacenes, para satisfacer la demanda de varios clientes dispersos geográficamente en un territorio problema.
El objetivo es entregar la demanda de dichos clientes minimizando el coste total involucrado enlas rutas. El problema VRP es un problema muy conocido que se clasifica como un problema NP completo. Por este motivo, se recurre al empleo de métodos aproximados de manera que se pueda encontrar soluciones suficientemente buenas en un tiempo de computación razonable. El problema VRP aparece de forma natural en las áreas de transporte, distribución y logística, el transporte implica un gran costeasociado a los productos que se distribuyen pero realizando una buena planeación de distribución puede resultar un valor añadido.
La utilización de métodos de computación para calcular las rutas óptimas o cercanas a las óptimas puede suponer ahorros de costos importantes (del orden de 5% al 20%).
El presente trabajo, ilustrará la aplicación de técnicas metaheurísticas en la solución de unproblema de ruteo de vehículos en un caso ficticio de una empresa del sector logístico. En dicha empresa, disponemos de un almacén central, donde se tiene que servir a clientes en la periferia del mismo, una cierta cantidad de producto y con la posibilidad de que se devuelva algo de cantidad.
2.- Definición del problema VRP:
El problema VRP tiene sus orígenes en el año de 1959 propuesto porDantzing y Ramser quienes originalmente le dieron el nombre de “Trucking Dispatching Problem”. El problema maneja conceptos de ruteo como lo hace el problema del agente viajero (“Traveling Salesman Problem”) y conceptos de almacenamiento de paquetes en contenedores (“Bin Packing”).
El problema VRP se define como: “la determinación de la ruta óptima para una flota de vehículos que parten de uno o másdepósitos (almacenes) para satisfacer la demanda de varios clientes dispersados geográficamente”]. Las variables o parámetros involucrados en el problema son: visitas, depósitos, localizaciones geográficas, vehículos, capacidades y pesos. Las visitas son entregas o recolección de paquetes. El depósito es donde comienzan todas las rutas y donde terminan. Las localizaciones geográficas involucran:tiempo, distancia, origen y destino.
Los vehículos son los que realizan los viajes (flota homogénea, dónde todos los vehículos son iguales; o heterogénea, dónde todos los vehículos son diferentes). Las capacidades que se observan en el vehiculo son: carga total, volumen total y número de las plataformas. Los pesos especifican el costo de recorrido entre las localizaciones geográficas.
Dentro...
Caso particular del problema del Transporte:
VRPB
Grupo: 6
Sergi Cercós Carbó
Miloud El Bakouri El Haddaji
David Modroño Preixens
Silvia Poyato Hernández
Pedro A. Ramírez Cobo
Mònica Viso Balduz
23/05/08
Índice
1.- Introducción: 3
2.- Definición del problema VRP: 4
2.1.- Instancia del problema VRP: 5
3.- Variantes del problema VRP: 84.- Caso concreto de estudio: VRPB 10
5.- Algoritmos de solución y aplicaciones: 12
5.1.- Algoritmo de Gillett y Miller 12
5.1.- Algoritmo de Fisher y Jaikumar 18
5.3.- Algoritmo de Clarke & Wright modificado 25
5.3.- Conclusiones 32
6.- Software de ejemplo: 33
6.- Opciones: 37
9.- Bibliografía: 43
El Problema del Transporte
El problema del transporte o VRP (VehicleRouting Problem) consiste en determinar un conjunto de rutas minimizando el coste total de transportar paquetes de un origen a un destino. Se ha tratado de disminuir ese coste por medio de la utilización de métodos de computación para calcular las rutas óptimas o cercanas a las óptimas. Implementar el problema VRP en casos reales es difícil por el gran número de restricciones que se deben considerar.1.- Introducción:
El problema del transporte (Vehicle Routing Problem o VRP), consiste en determinar un conjunto de rutas para una flota de vehículos que parten de uno, o más depósitos o almacenes, para satisfacer la demanda de varios clientes dispersos geográficamente en un territorio problema.
El objetivo es entregar la demanda de dichos clientes minimizando el coste total involucrado enlas rutas. El problema VRP es un problema muy conocido que se clasifica como un problema NP completo. Por este motivo, se recurre al empleo de métodos aproximados de manera que se pueda encontrar soluciones suficientemente buenas en un tiempo de computación razonable. El problema VRP aparece de forma natural en las áreas de transporte, distribución y logística, el transporte implica un gran costeasociado a los productos que se distribuyen pero realizando una buena planeación de distribución puede resultar un valor añadido.
La utilización de métodos de computación para calcular las rutas óptimas o cercanas a las óptimas puede suponer ahorros de costos importantes (del orden de 5% al 20%).
El presente trabajo, ilustrará la aplicación de técnicas metaheurísticas en la solución de unproblema de ruteo de vehículos en un caso ficticio de una empresa del sector logístico. En dicha empresa, disponemos de un almacén central, donde se tiene que servir a clientes en la periferia del mismo, una cierta cantidad de producto y con la posibilidad de que se devuelva algo de cantidad.
2.- Definición del problema VRP:
El problema VRP tiene sus orígenes en el año de 1959 propuesto porDantzing y Ramser quienes originalmente le dieron el nombre de “Trucking Dispatching Problem”. El problema maneja conceptos de ruteo como lo hace el problema del agente viajero (“Traveling Salesman Problem”) y conceptos de almacenamiento de paquetes en contenedores (“Bin Packing”).
El problema VRP se define como: “la determinación de la ruta óptima para una flota de vehículos que parten de uno o másdepósitos (almacenes) para satisfacer la demanda de varios clientes dispersados geográficamente”]. Las variables o parámetros involucrados en el problema son: visitas, depósitos, localizaciones geográficas, vehículos, capacidades y pesos. Las visitas son entregas o recolección de paquetes. El depósito es donde comienzan todas las rutas y donde terminan. Las localizaciones geográficas involucran:tiempo, distancia, origen y destino.
Los vehículos son los que realizan los viajes (flota homogénea, dónde todos los vehículos son iguales; o heterogénea, dónde todos los vehículos son diferentes). Las capacidades que se observan en el vehiculo son: carga total, volumen total y número de las plataformas. Los pesos especifican el costo de recorrido entre las localizaciones geográficas.
Dentro...
Leer documento completo
Regístrate para leer el documento completo.