×

A branch-and-price algorithm for an integrated production and inventory routing problem. (English) Zbl 1231.90010

Summary: With globalization, the need to better integrate production and distribution decisions has become ever more pressing for manufacturers trying to streamline their supply chain. This paper investigates a previously developed mixed-integer programming (MIP) model aimed at minimizing production, inventory, and delivery costs across the various stages of the system. The problem being modeled includes a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of homogeneous vehicles. Demand can be satisfied from either inventory held at a customer site or from daily product distribution. Whether a customer is visited on a particular day is determined by an implicit tradeoff between inventory and distribution costs. Once the decision is made, a vehicle routing problem must be solved for those customers who are scheduled for a delivery.
A hybrid methodology that combines exact and heuristic procedures within a branch-and-price framework is developed to solve the underlying MIP. The approach takes advantage of the efficiency of heuristics and the precision of branch and price. Implementation required devising a new branching strategy to accommodate the unique degeneracy characteristics of the master problem, and a new procedure for handling symmetry. A novel column generation heuristic and a rounding heuristic were also implemented to improve algorithmic efficiency. Computational testing on standard data sets showed that the hybrid scheme can solve instances with up to 50 customers and 8 time periods within 1 h. This level of performance could not be matched by either CPLEX or standard branch and price alone.

MSC:

90B05 Inventory, storage, reservoirs
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lei, L.; Liu, S.; Ruszczynski, A.; Park, S., On the integrated production, inventory, and distribution routing problem, IIE Transactions on Scheduling & Logistics, 38, 11, 955-970 (2006)
[2] Boudia M, Louly MAO, Prins C. A memetic algorithm with population management for a production-distribution problem. In: Doglui A, Morel, G, Pereira, CE, editors, 12th IFAC symposium on information control problems in manufacturing. Saint-Etienne, France; vol. 3. 2006. May 17-19, p. 541-46.; Boudia M, Louly MAO, Prins C. A memetic algorithm with population management for a production-distribution problem. In: Doglui A, Morel, G, Pereira, CE, editors, 12th IFAC symposium on information control problems in manufacturing. Saint-Etienne, France; vol. 3. 2006. May 17-19, p. 541-46.
[3] Boudia, M.; Louly, M. A.O.; Prins, C., A reactive GRASP and path relinking for a combined production-distribution problem, Computers & Operations Research, 34, 11, 3402-3419 (2007) · Zbl 1163.90317
[4] 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 New York), 29-63
[5] Bard, J. F.; Nananukul, N., The integrated production-inventory-distribution—routing problem for a single commodity, Journal of Scheduling, 12, 3, 257-280 (2009) · Zbl 1185.90005
[6] Cheung, K. L.; Zhang, S. H., Balanced and synchronized ordering in supply chains, IIE Transactions on Scheduling & Logistics, 40, 1, 1-11 (2008)
[7] Baudin, M., Lean logistics: the nuts and bolts of delivering materials and goods (2004), Productivity Press: Productivity Press New York
[8] Cetinkaya, S.; Mutlu, F.; Lee, C.-Y., A comparison of outbound dispatch policies for integrated inventory and transportation decisions, European Journal of Operational Research, 171, 3, 1094-1112 (2006) · Zbl 1116.90005
[9] Zhao, Q.-H.; Wang, S.-Y.; Lai, K. K., A partition approach to the inventory/routing problem, European Journal of Operational Research, 177, 2, 786-802 (2007) · Zbl 1102.90005
[10] Fumero, F.; Vercellis, C., Synchronized development of production, inventory, and distribution schedules, Transportation Science, 33, 3, 330-340 (1999) · Zbl 1002.90001
[11] O’Brien C, Tang O, editors. Integrated enterprise and supply chain management. International Journal of Production Economics, vol. 101. 2006 [special issue].; O’Brien C, Tang O, editors. Integrated enterprise and supply chain management. International Journal of Production Economics, vol. 101. 2006 [special issue].
[12] Boudia, M.; Prins, C., A memetic algorithm with dynamic population management for an integrated production-distribution problem, European Journal of Operational Research, 195, 3, 703-715 (2009) · Zbl 1156.90344
[13] Abdelmaguid, T. F.; Dessouky, M. M., A genetic algorithm approach to the integrated inventory-distribution problem, International Journal of Production Research, 44, 21, 4445-4464 (2006) · Zbl 1114.90302
[14] Archetti, C.; Bertazzi, L.; Laporte, G.; Speranza, M., A branch-and-cut algorithm for a vendor-managed inventory-routing problem, Transportation Science, 41, 3, 382-391 (2007)
[15] 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
[16] Golden, B.; Assad, A.; Dahl, R., Analysis of a large scale vehicle routing problem with an inventory component, Large Scale Systems, 7, 2-3, 181-190 (1984) · Zbl 0551.90018
[17] Dror, M.; Ball, M., Inventory/routing: reduction from an annual to a short period problem, Naval Research Logistics Quarterly, 34, 4, 891-905 (1987) · Zbl 0647.90028
[18] Cordeau, J.; Gendreau, M.; Laporte, G., A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks, 30, 105-119 (1997) · Zbl 0885.90037
[19] Gaudioso, M.; Paletta, G., A heuristic for the periodic vehicle routing problem, Transportation Science, 26, 2, 86-92 (1992) · Zbl 0759.90025
[20] Mourgaya, M.; Vanderbeck, F., Column generation based heuristic for tactical planning in multi-period vehicle routing, European Journal of Operational Research, 183, 3, 1028-1041 (2007) · Zbl 1278.90048
[21] Parthanadee, P.; Logendran, R., Periodic product distribution from multi-depots under limited supplies, IIE Transactions on Scheduling & Logistics, 38, 11, 1009-1026 (2006)
[22] Gutiérrez, J.; Sedeño-Noda, A.; Colebrook, M.; Sicilia, J., A polynomial algorithm for the production/ordering planning problem with limited storage, Computers & Operations Research, 34, 4, 934-937 (2007) · Zbl 1102.90001
[23] Chandra, P.; Fisher, M. L., Coordination of production and distribution planning, European Journal of Operational Research, 72, 3, 503-517 (1994) · Zbl 0805.90051
[24] Savelsbergh, M.; Song, J.-H., An optimization algorithm for the inventory routing problem with continuous moves, Computers & Operations Research, 35, 2266-2282 (2008) · Zbl 1179.90021
[25] Christiansen, M., Decomposition of a combined inventory and time constrained ship routing problem, Transportation Science, 33, 1, 3-16 (1999) · Zbl 1002.90509
[26] Chand, S.; Hsu, V. N.; Sethi, S.; Deshpande, V., A dynamic lot sizing problem with multiple customers: customer-specific shipping and backlogging costs, IIE Transactions on Scheduling & Logistics, 39, 11, 1059-1069 (2007)
[27] Herer, Y. T.; Tzur, M.; Yucesan, E., The multilocation transshipment problem, IIE Transactions on Scheduling & Logistics, 38, 3, 185-200 (2006)
[28] Villegas, F. A.; Smith, N. R., Supply chain dynamics: analysis of inventory vs. order oscillations trade-off, International Journal of Production Research, 44, 6, 1037-1054 (2006) · Zbl 1095.90010
[29] Vanderbeck, F., On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm, Operations Research, 48, 1, 111-128 (2000) · Zbl 1106.90360
[30] Wolsey, L. A., Integer Programming (1998), Wiley: Wiley New York · Zbl 0299.90012
[31] Carlton B. A tabu search approach to the general vehicle routing problem. PhD dissertation, Graduate Program in Operations Research and Industrial Engineering, The University of Texas, Austin; 1995.; Carlton B. A tabu search approach to the general vehicle routing problem. PhD dissertation, Graduate Program in Operations Research and Industrial Engineering, The University of Texas, Austin; 1995.
[32] Ryan, D. M.; Foster, B. A., An integer programming approach to scheduling, (Wren, A., Computer scheduling of public transport urban passenger vehicle and crew scheduling (1981), North Holland: North Holland Amsterdam), 269-280 · Zbl 0327.90030
[33] Bard, J. F.; Nananukul, N., Heuristics for a multiperiod inventory routing problem with production decisions, Computers & Industrial Engineering, 57, 3, 713-723 (2009)
[34] Choi, E.; Tcha, D.-W., A column generation approach to the heterogeneous fleet vehicle routing problem, Computers & Operations Research, 34, 7, 2080-2095 (2007) · Zbl 1187.90094
[35] Irnich S, Desaulniers G. Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon M, editors. column generation. New York: Springer; 2005. p. 33-65, [Chapter 2].; Irnich S, Desaulniers G. Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon M, editors. column generation. New York: Springer; 2005. p. 33-65, [Chapter 2]. · Zbl 1130.90315
[36] Nananukul N. Lot-sizing and inventory routing for production, inventory and distribution Systems. PhD dissertation, Graduate Program in Operations Research and Industrial Engineering, The University of Texas, Austin; 2008.; Nananukul N. Lot-sizing and inventory routing for production, inventory and distribution Systems. PhD dissertation, Graduate Program in Operations Research and Industrial Engineering, The University of Texas, Austin; 2008.
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.