A reactive GRASP and path relinking for a combined production-distribution problem. (English) Zbl 1163.90317
Summary: An NP-hard production-distribution problem for one product over a multi-period horizon is investigated. The aim is to minimize total cost taking production setups, inventory levels and distribution into account. An integer linear model is proposed as a compact problem specification but it cannot be solved to optimality for large instances. Instead of using a classical two-phase approach (production planning and then route construction for each day), metaheuristics that simultaneously tackle production and routing decisions are developed: a GRASP (greedy randomized adaptive search procedure) and two improved versions using either a reactive mechanism or a path-relinking process. These algorithms are evaluated on 90 randomly generated instances with 50, 100 and 200 customers and 20 periods. The results confirm the interest of integrating production and distribution decisions, compared to classical two-phase methods. Moreover, reaction and path-relinking give better results than the GRASP alone.
MSC:
| 90B05 | Inventory, storage, reservoirs |
References:
| [1] | Toth, P.; Vigo, D., The vehicle routing problem (2002), SIAM: SIAM Philadelphia · Zbl 0979.00026 |
| [2] | Gendreau, M.; Laporte, G.; Séguin, R., Stochastic vehicle routing, European Journal of Operational Research, 88, 3-12 (1996) · Zbl 0913.90094 |
| [3] | Christiansen, M.; Nygreen, B., A method for solving ship routing problems with inventory constraints, Annals of Operations Research, 81, 357-378 (1998) · Zbl 0906.90055 |
| [4] | Dror, M.; Ball, M., Inventory-routing: reduction from an annual to a short-period problem, Naval Research Logistics, 34, 891-905 (1987) · Zbl 0647.90028 |
| [5] | Golden, B. R.; Wasil, E. A., Computerized vehicle routing in the soft drink industry, Operations Research, 35, 1, 6-17 (1987) |
| [6] | Graves, S. C.; Rinnooy Kan, A. H.G.; Zipkin, P. H., Handbooks in operations research and management science, vol. 4: logistics of production and inventory (1993), Elsevier: Elsevier North-Holland · Zbl 0798.90028 |
| [7] | Nahmias, S., Production and operations analysis (1997), Irwin: Irwin Homewood, IL |
| [8] | Brewer, A. M.; Button, K. J.; Hensher, D. A., Handbook of logistics and supply chain management (2001), Pergamon: Pergamon Oxford |
| [9] | Tayur, S.; Ganeshan, R.; Magazine, M., Quantitative models for supply chain management (1999), Kluwer: Kluwer Massachusetts · Zbl 0932.00033 |
| [10] | De Kok, A. G.; Graves, S. C., Handbooks in operation research and management science , vol. 11: supply chain management: design, coordination and operation (2003), Elsevier: Elsevier North-Holland · Zbl 1101.90311 |
| [11] | Chandra, P.; Fisher, M. L., Coordination of production and distribution planning, European Journal of Operational Research, 72, 3, 503-517 (1994) · Zbl 0805.90051 |
| [12] | Fumero, F.; Vercellis, C., Synchronized development of production, inventory, and distribution schedules, Transportation Science, 33, 3, 330-340 (1999) · Zbl 1002.90001 |
| [13] | Selçuk Erengüc, S.; Simpson, N. C.; Vakharia, A. J., Integrated production/distribution planning in supply chains, An invited review. European Journal of Operational Research, 115, 219-236 (1999) · Zbl 0949.90658 |
| [14] | Blumenfeld, D. E.; Burns, L. D.; Daganzo, C. F., Synchronizing production and transportation schedules, Transportation Research, 25B, 1, 23-37 (1991) |
| [15] | Jayaraman, V.; Pirkul, H., Planning and coordination of production and distribution facilities for multiple commodities, European Journal of Operational Research, 133, 394-408 (2001) · Zbl 1001.90026 |
| [16] | Bard, J. F.; Huang, L.; Jaillet, P.; Dror, M., A decomposition approach to the inventory routing problem with satellite facilities, Transportation Science, 32, 2, 189-203 (1998) · Zbl 0987.90502 |
| [17] | Chandra, P., A dynamic distribution model with warehouse and customer replenishment requirements, Journal of the Operational Research Society, 44, 7, 681-692 (1993) · Zbl 0800.90403 |
| [18] | Ertogral K, Wu SD, Burke LI: Coordination production and transportation scheduling in the supply chain. Technical Report 1998, Lehigh University.; Ertogral K, Wu SD, Burke LI: Coordination production and transportation scheduling in the supply chain. Technical Report 1998, Lehigh University. |
| [19] | Metters, R. D., Interdependent transportation and production activity at the United States postal service, Journal of the Operational Research Society, 47, 27-37 (1996) |
| [20] | Bramel, J.; Goyal, S.; Zipkin, P., Coordination of production-distribution networks with unbalanced leadtimes, Operations Research, 48, 4, 570-577 (2000) |
| [21] | Desrochers, M.; Laporte, G., Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints, Operations Research Letters, 10, 27-36 (1991) · Zbl 0723.90081 |
| [22] | Mingozzi A, Valetta A. A lower bound for the periodic vehicle routing problem. Oral communication. International symposium on combinatorial optimisation (CO 2002), Paris, France.; Mingozzi A, Valetta A. A lower bound for the periodic vehicle routing problem. Oral communication. International symposium on combinatorial optimisation (CO 2002), Paris, France. |
| [23] | Feo TA, Bard j. Flight scheduling and maintenance base planning. Management Science 1989;35(12):1415-1432.; Feo TA, Bard j. Flight scheduling and maintenance base planning. Management Science 1989;35(12):1415-1432. |
| [24] | Feo, T. A.; Resende, M. G.C., Greedy randomized adaptive search procedures, Journal of Global Optimization, 6, 109-133 (1995) · Zbl 0822.90110 |
| [25] | Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581 (1964) |
| [26] | Buffa, E. S.; Sarin, R. K., Modern production-operations management (1987), Wiley: Wiley New York |
| [27] | Prais, M.; Ribeiro, C., Reactive GRASP: an application to a matrix decomposition problem in TDMA traffic assignment, INFORMS Journal on Computing, 12, 3, 164-176 (2000) · Zbl 1040.90504 |
| [28] | Campos, V.; Martí, R.; Laguna, M., Context-independent scatter search and tabu search for permutation problems, INFORMS Journal on Computing, 17, 111-122 (2005) · Zbl 1239.90109 |
| [29] | Resende, M. G.C.; Ribeiro, C. C., GRASP with path-relinking: recent advances and applications, (Ibaraki, T.; Nonobe, K.; Yagiura, M., Metaheuristics: progress as real problem solvers (2005), Springer: Springer Berlin), 29-63 |
| [30] | Borland Software Corporation. Delphi 7, United States of America, 2002.; Borland Software Corporation. Delphi 7, United States of America, 2002. |
| [31] | Boudia M, Louly MAO, Prins C. Combined optimization of production and distribution. CD-ROM proceedings of the international conference on industrial engineering and systems management, IESM’05, Marrakech, Morocco, 16-19 May 2005. Mons, Belgium: I4E2.; Boudia M, Louly MAO, Prins C. Combined optimization of production and distribution. CD-ROM proceedings of the international conference on industrial engineering and systems management, IESM’05, Marrakech, Morocco, 16-19 May 2005. Mons, Belgium: I4E2. |
| [32] | Ribeiro CC. Private communication, August 2005.; Ribeiro CC. Private communication, August 2005. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
