zbMATH — the first resource for mathematics

A multi-product production/distribution system design problem with direct shipments and lateral transshipments. (English) Zbl 07257986
Summary: In this paper, we investigate a multi-product, three-stage production/distribution system design problem (PDSD) with direct shipment and lateral transshipment capabilities. Our overall goal is to find the most efficient network design to minimize the total fixed facility and transportation costs. Specifically, we locate $$p$$ capacitated distribution centers in the second stage from a set of candidate locations. At the same time, our design allows for direct shipments between first (suppliers) and third stages (customers) and lateral transshipments among the distribution centers in the second stage. The PDSD problem is known to be NP-hard, and prior studies have explored several heuristic methods including scatter search, tabu search, and genetic algorithms to solve the problem. In this paper, we propose two solution algorithms based on simulated annealing and GRASP heuristics. We apply both long-term and short-term memory lists to maintain an efficient local search, combined with a custom greedy solver that can effectively evaluate the quality of a solution candidate. We conduct a series of computational experiments to validate the proposed algorithms. Compared with the optimal solution, the simulated annealing algorithm presents an average optimality gap of 0.07% and an average time of 25.56% of optimal solution time, while the GRASP algorithm achieves a solution gap of 0.11% with 17.85% of optimal running time. The experimental results also show that the simulated annealing and GRASP algorithms outperform the best-reported heuristic in the literature based on scatter search regarding both solution quality and duration, especially for large-scale problem instances with tighter capacities.
MSC:
 90 Operations research, mathematical programming 68 Computer science
GRASP
Full Text:
References:
 [1] Ahmadi, S.; Osman, Ih, Greedy random adaptive memory programming search for the capacitated clustering problem, Eur J Oper Res, 162, 1, 30-44 (2005) · Zbl 1132.90363 [2] Arostegui, Ma; Kadipasaoglu, Sn; Khumawala, Bm, An empirical comparison of Tabu search, simulated annealing, and genetic algorithms for facilities location problems, Int J Prod Econ, 103, 2, 742-754 (2006) [3] Brimberg, J.; Drezner, Z., A new heuristic for solving the p-median problem in the plane, Comput Oper Res, 40, 427-437 (2013) · Zbl 1349.90557 [4] Camacho-Vallejo, J-F; Munoz-Sancheza, R.; Gonzalez-Velarde, Jl, A heuristic algorithm for a supply chain’s production-distribution planning, Comput Oper Res, 61, 9, 110-121 (2015) · Zbl 1348.90072 [5] Chen L, Monteiro T, Wang T, Marcon E (2018) Design of shared unit-dose drug distribution network using multi-level particle swarm optimization. Health Care Management Science Appeared Online, 1-14 [6] Chiyoshi, F.; Galvao, Rd, A statistical analysis of simulated annealing applied to the p-median problem, Ann Oper Res, 96, 61-74 (2000) · Zbl 0997.90042 [7] Contreras, Ia; Diaz, Ja, Scatter search for the single source capacitated facility location problem, Ann Oper Res, 157, 73-89 (2008) · Zbl 1153.90481 [8] Diaz, Ja; Fernandez, E., Hybrid scatter search and path relinking for the capacitated p-median problem, Eur J Oper Res, 169, 570-585 (2006) · Zbl 1079.90076 [9] Fahimnia, B.; Luong, L.; Marian, R., Genetic algorithm optimisation of an integrated aggregate production distribution plan in supply chains, Int J Prod Res, 50, 1, 81-96 (2012) [10] Feo, Ta; Resende, Mgc, A probabilistic heuristic for a computationally difficult set covering problem, Oper Res Lett, 8, 2, 67-71 (1989) · Zbl 0675.90073 [11] Feo, Ta; Resende, Mgc, Greedy randomized adaptive search procedures, J Global Optim, 6, 2, 109-133 (1995) · Zbl 0822.90110 [12] Festa, P.; Resende, Mgc, An annotated bibliography of grasp-part ii : applications, Int Trans Oper Res, 16, 131-172 (2009) · Zbl 1168.90582 [13] Firouz, M.; Keskin, Bb; Melouk, Sh, An integrated supplier selection and inventory problem with multi-sourcing and lateral transshipments, Omega, 70, 77-93 (2017) [14] Goetschalckx, M.; Vidal, Cj; Dogan, K., Modeling and design of global logistic systems: a review of integrated strategic and tactical models and design algorithms, Eur J Oper Res, 143, 1-18 (2002) · Zbl 1073.90501 [15] Jawahar, N.; Balaji, A., A genetic algorithm for the two-stage supply chain distribution problem associated with a fixed charge, Eur J Oper Res, 194, 496-537 (2009) · Zbl 1154.90629 [16] Jin, M.; Eksioglu, Sd; Eksioglu, B.; Wang, H., Mode selection for automotive distribution with quantity discounts, Netw Spatial Econ, 10, 1, 1-13 (2010) · Zbl 1183.90058 [17] Kariv, O.; Hakimi, L., An algorithmic approach to network location problems. II: the p-medians, SIAM J Appl Math, 37, 3, 539-560 (1979) · Zbl 0432.90075 [18] Keskin, Bb; Üster, H., Meta-heuristic approaches with memory and evolution for a multi-product production/distribution system design problem, Eur J Oper Res, 182, 2, 663-682 (2007) · Zbl 1121.90022 [19] Keskin, Bb; Üster, H., A scatter search-based heuristic to locate capacitated transshipment points, Comput Oper Res, 34, 10, 3112-3125 (2007) · Zbl 1185.90134 [20] Melo, Mt; Nickel, S.; Saldanha Da Gama, F., Facility location and supply chain management-a review, Eur J Oper Res, 196, 2, 401-412 (2009) · Zbl 1163.90341 [21] Miralinaghi, M.; Keskin, Bb; Lou, Y.; Roshandeh, Am, Capacitated refueling station location problem with traffic deviations over multiple time periods, Netw Spatial Econ, 17, 1, 129-151 (2017) · Zbl 1364.90193 [22] Miranda, Pa; Garrido, Ra, A simultaneous inventory control and facility location model with stochastic capacity constraints, Netw Spatial Econ, 6, 1, 39-53 (2006) · Zbl 1106.90010 [23] Mladenovic, N.; Brimberg, J.; Hansen, P.; Moreno-Perez, Ja, The p-median problem: a survey of metaheuristic approachest, Eur J Oper Res, 179, 927-939 (2007) · Zbl 1163.90610 [24] Olhager, J.; Pashaei, S.; Sternberg, H., Design of global production and distribution networks: a literature review and research agenda, Int J Phys Distrib Logist Manag, 45, 1-2, 138-158 (2015) [25] Paterson, C.; Kiesmüller, G.; Teunter, R.; Glazebrook, K., Inventory models with lateral transshipments: a review, Eur J Oper Res, 210, 2, 125-136 (2011) [26] Pedrola, O.; Ruiz, M.; Velasco, L.; Careglio, D.; Gonzalez De Dios, O.; Comellas, J., A GRASP with path-relinking heuristic for the survivable IP/MPLS-over-WSON multi-layer network optimization problem, Comput Oper Res, 40, 3174-3187 (2013) · Zbl 1348.90160 [27] Pessoa, Ls; Resende, Mgc; Ribeiro, Cc, A hybrid lagrangean heuristic with grasp and path-relinking for set k-covering, Comput Oper Res, 40, 3132-3146 (2013) · Zbl 1348.90643 [28] Resende, Mgc; Werneck, Rf, A hybrid heuristic for the p-median problem, Ann Oper Res, 10, 1, 59-88 (2004) · Zbl 1069.68600 [29] Saez-Aguado, J.; Trandafir, Pc, Some heuristic methods for solving p-median problems with a coverage constraint, Eur J Oper Res, 220, 320-327 (2012) · Zbl 1253.90141 [30] Sahin, G.; Süral, H., A review of hierarchical facility location models, Comput Oper Res, 34, 8, 2310-2331 (2007) · Zbl 1144.90440 [31] Tragantalerngsak, S.; Rönnqvist, Jhm, Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem, Eur J Oper Res, 102, 3, 611-625 (1997) · Zbl 0951.90561 [32] Tragantalerngsak, S.; Holt, J.; Rönnqvist, M., An exact method for the two-echelon, single-source, capacitated facility location problem, Eur J Oper Res, 123, 3, 473-489 (2000) · Zbl 0991.90083 [33] Tsao, Y-C; Linh, Vt, Supply chain network designs developed for deteriorating items under conditions of trade credit and partial backordering, Netw Spatial Econ, 16, 3, 933-956 (2016) · Zbl 1364.90051
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.