Location and capacity design of congested intermediate facilities in networks

Previous Article
$p$th Moment absolute exponential stability of stochastic control system with Markovian switching
JIMO Home
This Issue
Next Article
A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse

April 2016, 12(2): 449-470. doi: 10.3934/jimo.2016.12.449

Location and capacity design of congested intermediate facilities in networks

Dandan Hu ^1, and Zhi-Wei Liu ^2,

1.	School of Management, South-Central University for Nationalities, Wuhan, 430074, China
2.	Department of Automation, School of Power and Mechanical Engineering, Wuhan University, Wuhan, 430072, China

Received August 2014 Revised February 2015 Published June 2015

Abstract
Related Papers

This article deals with the problem of making simultaneous decisions on the location, capacity and demand flow assignment for intermediate facilities in a network. Two nonlinear mixed-integer program (NMIP) models for continuous and discrete capacity decisions are proposed, respectively. The objective is to minimize the total costs, including fixed location cost, transportation cost, congestion cost and capacity cost. Congestion at intermediate facilities is modeled as the ratio of total flow to surplus capacity by viewing each facility as an M/M/1 queuing system. To solve NMIP with continuous capacity decision, we apply the Lagrangean algorithm that has been proposed to solve the classic inventory-location model. For the NMIP with discrete capacity decision, we propose another Lagrangean algorithm where the problem is decomposed into $|K|$ subproblems that can be solved to optimality. The measures of allocation heuristic, capacity increase and capacity adjustment are taken to construct feasible solutions. Computational results indicate that the heuristics for the two models are both efficient and effective.

Keywords: capacity, optimization model., Location, congestion, Lagrangian heuristics.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.

Citation: Dandan Hu, Zhi-Wei Liu. Location and capacity design of congested intermediate facilities in networks. Journal of Industrial and Management Optimization, 2016, 12 (2) : 449-470. doi: 10.3934/jimo.2016.12.449

References:

[1]	R. Aboolian, O. Berman and D. Krass, Profit maximizing distributed service system design with congestion and elastic demand, Transportation Science, 46 (2012), 247-261. doi: 10.1287/trsc.1110.0392.
[2]	S.R. Agnihothri, S. Narasimhan and H. Pirkul, An assignment problem with queueing time cost, Naval Research Logistics, 37 (1990), 231-244. doi: 10.1002/1520-6750(199004)37:2<231::AID-NAV3220370204>3.0.CO;2-N.
[3]	M. Armony, E. Plambeck and S. Seshadri, Sensitivity of optimal capacity to customer impatience in an unobservable m/m/s queue (why you shouldn't shout at the dmv), Manufacturing & Service Operations Management, 11 (2009), 19-32. doi: 10.1287/msom.1070.0194.
[4]	O. Berman and Z. Drezner, Location of congested capacitated facilities with distance-sensitive demand, IIE Transactions, 38 (2006), 213-221. doi: 10.1080/07408170500288190.
[5]	O. Berman and Z. Drezner, The multiple server location problem, Journal of the Operational Research Society, 58 (2006), 91-99. doi: 10.1057/palgrave.jors.2602126.
[6]	M. L. Brandeau and S. S. Chiu, A center location problem with congestion, Annals of operations research, 40 (1992), 17-32. doi: 10.1007/BF02060468.
[7]	M. L. F. Cheong, R. Bhatnagar and S. C. Graves, Logistics network design with supplier consolidation hubs and multiple shipment options, Journal of Industrial and Management Optimization, 3 (2007), 51-69. doi: 10.3934/jimo.2007.3.51.
[8]	S. M. Choi, X. Huang and W. K. Ching, Minimizing equilibrium expected sojourn time via performance-based mixed threshold demand allocation in a multiple-server queueing environment, Journal of Industrial and Management Optimization, 8 (2012), 299-323. doi: 10.3934/jimo.2012.8.299.
[9]	M. S. Daskin, C. R. Coullard and Z.-J. M. Shen, A maximum expected covering location model: formulation, properties and heuristic solution, Transportation Science, 17 (1983), 48-70. doi: 10.1287/trsc.17.1.48.
[10]	M. S. Daskin, C. R. Coullard and Z.-J. M. Shen, An inventory-location model: Formulation, solution algorithm and computational results, Annals of Operations Research, 110 (2002), 83-106. doi: 10.1023/A:1020763400324.
[11]	M. S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications, John Wiley & Sons, 2011. doi: 10.1002/9781118032343.
[12]	S. Elhedhli and H. Wu, A lagrangean heuristic for hub-and-spoke system design with capacity selection and congestion, INFORMS Journal on Computing, 22 (2010), 282-296. doi: 10.1287/ijoc.1090.0335.
[13]	A. F. Gabor and J. Van Ommeren, An approximation algorithm for a facility location problem with stochastic demands and inventories, Operations research letters, 34 (2006), 257-263. doi: 10.1016/j.orl.2005.04.009.
[14]	R. Hassin and M. Haviv, To Queue or not to Queue: Equilibrium Behavior in Queueing Systems, Kluwer Academic Publishers, 2002. doi: 10.1007/978-1-4615-0359-0.
[15]	D. Hu, C. Yang and J. Yang, Budget constrained flow interception location model for congested systems, Journal of Systems Engineering and Electronics, 20 (2009), 1255-1262.
[16]	S. Huang, R. Batta and R. Nagi, Distribution network design: Selection and sizing of congested connections, Naval Research Logistics, 52 (2005), 701-712. doi: 10.1002/nav.20106.
[17]	V. Marianov and D. Serra, Probabilistic, maximal covering location-allocation models for congested systems, Journal of Regional Science, 38 (1998), 401-424.
[18]	S. H. R. Pasandideh, S. T. A. Niaki and V. Hajipour, A multi-objective facility location model with batch arrivals: two parameter-tuned meta-heuristic algorithms, Journal of Intelligent Manufacturing, 24 (2013), 331-348.
[19]	S. H. A. Rahmati, A. Ahmadi, M. Sharifi and A. Chambari, A multi-objective model for Facility Location-allocation Problem with immobile servers within queuing framework, Computers and Industrial Engineering, 74 (2014), 1-10. doi: 10.1016/j.cie.2014.04.018.
[20]	H. Shavandi and H. Mahlooji, A fuzzy queuing location model with a genetic algorithm for congested systems, Applied mathematics and computation, 181 (2006), 440-456. doi: 10.1016/j.amc.2005.12.058.
[21]	Q. Wang, R. Batta and C. M. Rump, Algorithms for a facility location problem with stochastic customer demand and immobile servers, Annals of Operations Research, 111 (2002), 17-34. doi: 10.1023/A:1020961732667.
[22]	Q. Wang, R. Batta and C. M. Rump, Facility location models for immobile servers with stochastic demand, Naval Research Logistics, 51 (2004), 137-152. doi: 10.1002/nav.10110.
[23]	L. Zhang and G. Rushton, Optimizing the size and locations of facilities in competitive multi-site service systems, Computers & Operations Research, 35 (2008), 327-338. doi: 10.1016/j.cor.2006.03.002.

show all references

References:

[1]	R. Aboolian, O. Berman and D. Krass, Profit maximizing distributed service system design with congestion and elastic demand, Transportation Science, 46 (2012), 247-261. doi: 10.1287/trsc.1110.0392.
[2]	S.R. Agnihothri, S. Narasimhan and H. Pirkul, An assignment problem with queueing time cost, Naval Research Logistics, 37 (1990), 231-244. doi: 10.1002/1520-6750(199004)37:2<231::AID-NAV3220370204>3.0.CO;2-N.
[3]	M. Armony, E. Plambeck and S. Seshadri, Sensitivity of optimal capacity to customer impatience in an unobservable m/m/s queue (why you shouldn't shout at the dmv), Manufacturing & Service Operations Management, 11 (2009), 19-32. doi: 10.1287/msom.1070.0194.
[4]	O. Berman and Z. Drezner, Location of congested capacitated facilities with distance-sensitive demand, IIE Transactions, 38 (2006), 213-221. doi: 10.1080/07408170500288190.
[5]	O. Berman and Z. Drezner, The multiple server location problem, Journal of the Operational Research Society, 58 (2006), 91-99. doi: 10.1057/palgrave.jors.2602126.
[6]	M. L. Brandeau and S. S. Chiu, A center location problem with congestion, Annals of operations research, 40 (1992), 17-32. doi: 10.1007/BF02060468.
[7]	M. L. F. Cheong, R. Bhatnagar and S. C. Graves, Logistics network design with supplier consolidation hubs and multiple shipment options, Journal of Industrial and Management Optimization, 3 (2007), 51-69. doi: 10.3934/jimo.2007.3.51.
[8]	S. M. Choi, X. Huang and W. K. Ching, Minimizing equilibrium expected sojourn time via performance-based mixed threshold demand allocation in a multiple-server queueing environment, Journal of Industrial and Management Optimization, 8 (2012), 299-323. doi: 10.3934/jimo.2012.8.299.
[9]	M. S. Daskin, C. R. Coullard and Z.-J. M. Shen, A maximum expected covering location model: formulation, properties and heuristic solution, Transportation Science, 17 (1983), 48-70. doi: 10.1287/trsc.17.1.48.
[10]	M. S. Daskin, C. R. Coullard and Z.-J. M. Shen, An inventory-location model: Formulation, solution algorithm and computational results, Annals of Operations Research, 110 (2002), 83-106. doi: 10.1023/A:1020763400324.
[11]	M. S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications, John Wiley & Sons, 2011. doi: 10.1002/9781118032343.
[12]	S. Elhedhli and H. Wu, A lagrangean heuristic for hub-and-spoke system design with capacity selection and congestion, INFORMS Journal on Computing, 22 (2010), 282-296. doi: 10.1287/ijoc.1090.0335.
[13]	A. F. Gabor and J. Van Ommeren, An approximation algorithm for a facility location problem with stochastic demands and inventories, Operations research letters, 34 (2006), 257-263. doi: 10.1016/j.orl.2005.04.009.
[14]	R. Hassin and M. Haviv, To Queue or not to Queue: Equilibrium Behavior in Queueing Systems, Kluwer Academic Publishers, 2002. doi: 10.1007/978-1-4615-0359-0.
[15]	D. Hu, C. Yang and J. Yang, Budget constrained flow interception location model for congested systems, Journal of Systems Engineering and Electronics, 20 (2009), 1255-1262.
[16]	S. Huang, R. Batta and R. Nagi, Distribution network design: Selection and sizing of congested connections, Naval Research Logistics, 52 (2005), 701-712. doi: 10.1002/nav.20106.
[17]	V. Marianov and D. Serra, Probabilistic, maximal covering location-allocation models for congested systems, Journal of Regional Science, 38 (1998), 401-424.
[18]	S. H. R. Pasandideh, S. T. A. Niaki and V. Hajipour, A multi-objective facility location model with batch arrivals: two parameter-tuned meta-heuristic algorithms, Journal of Intelligent Manufacturing, 24 (2013), 331-348.
[19]	S. H. A. Rahmati, A. Ahmadi, M. Sharifi and A. Chambari, A multi-objective model for Facility Location-allocation Problem with immobile servers within queuing framework, Computers and Industrial Engineering, 74 (2014), 1-10. doi: 10.1016/j.cie.2014.04.018.
[20]	H. Shavandi and H. Mahlooji, A fuzzy queuing location model with a genetic algorithm for congested systems, Applied mathematics and computation, 181 (2006), 440-456. doi: 10.1016/j.amc.2005.12.058.
[21]	Q. Wang, R. Batta and C. M. Rump, Algorithms for a facility location problem with stochastic customer demand and immobile servers, Annals of Operations Research, 111 (2002), 17-34. doi: 10.1023/A:1020961732667.
[22]	Q. Wang, R. Batta and C. M. Rump, Facility location models for immobile servers with stochastic demand, Naval Research Logistics, 51 (2004), 137-152. doi: 10.1002/nav.10110.
[23]	L. Zhang and G. Rushton, Optimizing the size and locations of facilities in competitive multi-site service systems, Computers & Operations Research, 35 (2008), 327-338. doi: 10.1016/j.cor.2006.03.002.

[1]	Hongzhi Lin, Min Xu, Chi Xie. Location and capacity planning for preventive healthcare facilities with congestion effects. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022076
[2]	Julien Dambrine, Nicolas Meunier, Bertrand Maury, Aude Roudneff-Chupin. A congestion model for cell migration. Communications on Pure and Applied Analysis, 2012, 11 (1) : 243-260. doi: 10.3934/cpaa.2012.11.243
[3]	Sebastián Ferrer, Francisco Crespo. Parametric quartic Hamiltonian model. A unified treatment of classic integrable systems. Journal of Geometric Mechanics, 2014, 6 (4) : 479-502. doi: 10.3934/jgm.2014.6.479
[4]	Ghendrih Philippe, Hauray Maxime, Anne Nouri. Derivation of a gyrokinetic model. Existence and uniqueness of specific stationary solution. Kinetic and Related Models, 2009, 2 (4) : 707-725. doi: 10.3934/krm.2009.2.707
[5]	Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1145-1160. doi: 10.3934/jimo.2021013
[6]	Zhimin Liu, Shaojian Qu, Hassan Raza, Zhong Wu, Deqiang Qu, Jianhui Du. Two-stage mean-risk stochastic mixed integer optimization model for location-allocation problems under uncertain environment. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2783-2804. doi: 10.3934/jimo.2020094
[7]	Faker Ben Belgacem. Uniqueness for an ill-posed reaction-dispersion model. Application to organic pollution in stream-waters. Inverse Problems and Imaging, 2012, 6 (2) : 163-181. doi: 10.3934/ipi.2012.6.163
[8]	Shu Zhang, Jian Xu. Time-varying delayed feedback control for an internet congestion control model. Discrete and Continuous Dynamical Systems - B, 2011, 16 (2) : 653-668. doi: 10.3934/dcdsb.2011.16.653
[9]	Shu Zhang, Yuan Yuan. The Filippov equilibrium and sliding motion in an internet congestion control model. Discrete and Continuous Dynamical Systems - B, 2017, 22 (3) : 1189-1206. doi: 10.3934/dcdsb.2017058
[10]	Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial and Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157
[11]	Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial and Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629
[12]	Adriano Festa, Simone Göttlich, Marion Pfirsching. A model for a network of conveyor belts with discontinuous speed and capacity. Networks and Heterogeneous Media, 2019, 14 (2) : 389-410. doi: 10.3934/nhm.2019016
[13]	Qing Yang, Shiji Song, Cheng Wu. Inventory policies for a partially observed supply capacity model. Journal of Industrial and Management Optimization, 2013, 9 (1) : 13-30. doi: 10.3934/jimo.2013.9.13
[14]	Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215
[15]	Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495
[16]	Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial and Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136
[17]	Michele Gianfelice, Marco Isopi. On the location of the 1-particle branch of the spectrum of the disordered stochastic Ising model. Networks and Heterogeneous Media, 2011, 6 (1) : 127-144. doi: 10.3934/nhm.2011.6.127
[18]	Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial and Management Optimization, 2021, 17 (2) : 669-686. doi: 10.3934/jimo.2019128
[19]	Shoufeng Ji, Jinhuan Tang, Minghe Sun, Rongjuan Luo. Multi-objective optimization for a combined location-routing-inventory system considering carbon-capped differences. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1949-1977. doi: 10.3934/jimo.2021051
[20]	Katarzyna Grabowska. Lagrangian and Hamiltonian formalism in Field Theory: A simple model. Journal of Geometric Mechanics, 2010, 2 (4) : 375-395. doi: 10.3934/jgm.2010.2.375

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Dandan Hu Zhi-Wei Liu
on Google Scholar
Dandan Hu Zhi-Wei Liu

[Back to Top]