Location and capacity design of congested intermediate facilities in networks

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

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

Location and capacity design of congested intermediate facilities in networks

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 & 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. 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. 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. 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. doi: 10.1080/07408170500288190.
[5]	O. Berman and Z. Drezner, The multiple server location problem,, Journal of the Operational Research Society, 58 (2006), 91. 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. 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. 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. 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. 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. 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. 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. 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.
[16]	S. Huang, R. Batta and R. Nagi, Distribution network design: Selection and sizing of congested connections,, Naval Research Logistics, 52 (2005), 701. 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.
[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.
[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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1080/07408170500288190.
[5]	O. Berman and Z. Drezner, The multiple server location problem,, Journal of the Operational Research Society, 58 (2006), 91. 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. 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. 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. 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. 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. 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. 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. 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.
[16]	S. Huang, R. Batta and R. Nagi, Distribution network design: Selection and sizing of congested connections,, Naval Research Logistics, 52 (2005), 701. 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.
[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.
[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. 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. 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. 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. 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. doi: 10.1016/j.cor.2006.03.002.

[1]	Julien Dambrine, Nicolas Meunier, Bertrand Maury, Aude Roudneff-Chupin. A congestion model for cell migration. Communications on Pure & Applied Analysis, 2012, 11 (1) : 243-260. doi: 10.3934/cpaa.2012.11.243
[2]	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
[3]	Ghendrih Philippe, Hauray Maxime, Anne Nouri. Derivation of a gyrokinetic model. Existence and uniqueness of specific stationary solution. Kinetic & Related Models, 2009, 2 (4) : 707-725. doi: 10.3934/krm.2009.2.707
[4]	Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial & Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629
[5]	Shu Zhang, Jian Xu. Time-varying delayed feedback control for an internet congestion control model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (2) : 653-668. doi: 10.3934/dcdsb.2011.16.653
[6]	Shu Zhang, Yuan Yuan. The Filippov equilibrium and sliding motion in an internet congestion control model. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 1189-1206. doi: 10.3934/dcdsb.2017058
[7]	Faker Ben Belgacem. Uniqueness for an ill-posed reaction-dispersion model. Application to organic pollution in stream-waters. Inverse Problems & Imaging, 2012, 6 (2) : 163-181. doi: 10.3934/ipi.2012.6.163
[8]	Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157
[9]	Qing Yang, Shiji Song, Cheng Wu. Inventory policies for a partially observed supply capacity model. Journal of Industrial & Management Optimization, 2013, 9 (1) : 13-30. doi: 10.3934/jimo.2013.9.13
[10]	Adriano Festa, Simone Göttlich, Marion Pfirsching. A model for a network of conveyor belts with discontinuous speed and capacity. Networks & Heterogeneous Media, 2019, 14 (2) : 389-410. doi: 10.3934/nhm.2019016
[11]	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 & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215
[12]	Michele Gianfelice, Marco Isopi. On the location of the 1-particle branch of the spectrum of the disordered stochastic Ising model. Networks & Heterogeneous Media, 2011, 6 (1) : 127-144. doi: 10.3934/nhm.2011.6.127
[13]	Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495
[14]	Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-9. doi: 10.3934/jimo.2018136
[15]	Oliver Kolb, Simone Göttlich, Paola Goatin. Capacity drop and traffic control for a second order traffic model. Networks & Heterogeneous Media, 2017, 12 (4) : 663-681. doi: 10.3934/nhm.2017027
[16]	Hanwu Liu, Lin Wang, Fengqin Zhang, Qiuying Li, Huakun Zhou. Dynamics of a predator-prey model with state-dependent carrying capacity. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-15. doi: 10.3934/dcdsb.2019028
[17]	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
[18]	Min Sha. Heuristics of the Cocks-Pinch method. Advances in Mathematics of Communications, 2014, 8 (1) : 103-118. doi: 10.3934/amc.2014.8.103
[19]	Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743
[20]	Julius Fergy T. Rabago, Jerico B. Bacani. Shape optimization approach for solving the Bernoulli problem by tracking the Neumann data: A Lagrangian formulation. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2683-2702. doi: 10.3934/cpaa.2018127

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences