Trabajo de grado - Pregrado
Estudio del problema Inventory Routing Problem (IRP)
Registro en:
Universidad Tecnológica de Pereira
Repositorio Institucional Universidad Tecnológica de Pereira
Autor
Hincapié Londoño, Frank Alejandro
García Guevara, Jhonatan Stiven
Institución
Resumen
El problema integrado de gestión de inventarios y de enrutamiento Inventory Routing Problem (IRP), combina las actividades logísticas de diseño de redes y manejo de inventarios. Es un problema NP-duro que tiene como objetivo atender al menor costo las necesidades de un conjunto de clientes, utilizando una flota de vehículos, que a partir de un almacén central, recorren rutas de distribución para abastecer a los clientes en un horizonte de tiempo establecido.
En un inicio se analizan de manera separada los modelos de gestión de inventarios y enrutamiento, así como sus variantes con el fin de tener un mayor conocimiento del funcionamiento individual de los modelos, para posteriormente abordar el problema conjunto del IRP. The Inventory Routing Problem (IRP) combines the logistics activities of network design and inventory management. It is a NP-hard problem that aims to meet the needs of a group of customers at the lowest cost, using a fleet of vehicles that, starting from a central warehouse, travel distribution routes to supply customers in a set time horizon.
At the beginning, the inventory management and routing models, as well as their variants, are analyzed separately to have a better understanding of the individual operation of the models, to later address the joint problem of the IRP.
From the understanding of the proposed models of the IRP, the model Inventory Routing Problem (IRP) will be replicated, using the algebraic programming software A Mathematical Programming Language (AMPL), validating it with the instances in liretaure, addressing two inventory supply policies, one of them maximum level (at the customer's request) and the other the Order up to level policy (fill the maximum storage capacities of the clients), there are also three ways to eliminate subtours (MTZ, Flows, general), since this is the part where the greatest computational complexity is found. Similarly, a new proposal is put forward to the multi-vehicle IRP problem, adapted from the IRP model, reaching a competitive model in affordable computational times.
Finally, it is verified that the responses generated are of very good quality, highlighting the elimination of subtours by medium of the flow model since it is the most efficient model of the three proposed. Pregrado Ingeniero(a) Industrial Indice
1. Introduccion 10 ´
2. Justificacion 12 ´
3. Objetivos 13
3.1. Objetivo general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2. Objetivos espec´ıficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4. Marco referencial 14
4.1. Antecedentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2. Enrutamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2.1. Vehicle routing problem (VRP) . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2.1.1. Capacitated Vehicle routing problem (CVRP) . . . . . . . . . . 17
4.2.1.2. Modelo matematico . . . . . . . . . . . . . . . . . . . . . . . . ´ 18
4.3. Gestion de inventarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 23
4.3.1. Modelo Single Sourcing . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3.1.1. Modelo matematico . . . . . . . . . . . . . . . . . . . . . . . . ´ 24
4.3.2. Modelo Multiple Sourcing . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3.2.1. Modelo matematico . . . . . . . . . . . . . . . . . . . . . . . . ´ 29
4.3.3. Modelo multiple sourcing considerando demanda estocastica . . . . . . . . ´ 32
4.3.3.1. Modelo matematico . . . . . . . . . . . . . . . . . . . . . . . . ´ 33
4.4. Inventory routing problem (IRP) . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.5. Tecnicas de soluci ´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 37
4.6. Variantes Inventory routing problem (IRP) . . . . . . . . . . . . . . . . . . . . . . 39
4.7. Aplicaciones del IRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5. Modelos matematicos 44 ´
3
5.1. IRP bajo pol´ıtica de abastecimiento Maximum level (ML) . . . . . . . . . . . . . 45
5.2. IRP bajo pol´ıtica de abastecimiento Order up to level (OU) . . . . . . . . . . . . . 48
5.3. IRP con multiples veh ´ ´ıculos (multi vehicle IRP) . . . . . . . . . . . . . . . . . . . 52
5.4. Variaciones generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4.1. Considerando stock de seguridad . . . . . . . . . . . . . . . . . . . . . . . 57
5.4.2. Considerando flota heterogenea . . . . . . . . . . . . . . . . . . . . . . . ´ 58
5.4.3. Particion del horizonte temporal . . . . . . . . . . . . . . . . . . . . . . . ´ 58
5.4.4. Eliminacion de subtours . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 59
5.4.4.1. Eliminacion de subtours por Miller-Tucker-Zemlin (MTZ) . . . . ´ 59
5.4.4.2. Eliminacion de subtours por flujos . . . . . . . . . . . . . . . . ´ 60
6. Resultados computacionales 61
6.1. Instancias de prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.2. Conteo de variables y restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.3. Resultados IRP bajo pol´ıtica ML . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.4. Resultados IRP bajo pol´ıtica OU . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.5. Resultados multi vehicle IRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.6. Interpretacion de resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 87
7. Conclusiones y trabajos futuros 93
7.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.2. Trabajos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95