American Institute of Mathematical Sciences

Advanced
  • 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

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

O. Berman and Z. Drezner, Location of congested capacitated facilities with distance-sensitive demand,, IIE Transactions, 38 (2006), 213.  doi: 10.1080/07408170500288190.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

M. S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications,, John Wiley & Sons, (2011).  doi: 10.1002/9781118032343.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[17]

V. Marianov and D. Serra, Probabilistic, maximal covering location-allocation models for congested systems,, Journal of Regional Science, 38 (1998), 401.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

O. Berman and Z. Drezner, Location of congested capacitated facilities with distance-sensitive demand,, IIE Transactions, 38 (2006), 213.  doi: 10.1080/07408170500288190.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

M. S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications,, John Wiley & Sons, (2011).  doi: 10.1002/9781118032343.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[17]

V. Marianov and D. Serra, Probabilistic, maximal covering location-allocation models for congested systems,, Journal of Regional Science, 38 (1998), 401.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Yuri Chekanov, Felix Schlenk. Notes on monotone Lagrangian twist tori. Electronic Research Announcements, 2010, 17: 104-121. doi: 10.3934/era.2010.17.104
[2]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[3]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[4]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[5]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225
[6]

Johannes Kellendonk, Lorenzo Sadun. Conjugacies of model sets. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 3805-3830. doi: 10.3934/dcds.2017161
[7]

Didier Bresch, Thierry Colin, Emmanuel Grenier, Benjamin Ribba, Olivier Saut. A viscoelastic model for avascular tumor growth. Conference Publications, 2009, 2009 (Special) : 101-108. doi: 10.3934/proc.2009.2009.101
[8]

Ondrej Budáč, Michael Herrmann, Barbara Niethammer, Andrej Spielmann. On a model for mass aggregation with maximal size. Kinetic & Related Models, 2011, 4 (2) : 427-439. doi: 10.3934/krm.2011.4.427
[9]

Martin Bohner, Sabrina Streipert. Optimal harvesting policy for the Beverton--Holt model. Mathematical Biosciences & Engineering, 2016, 13 (4) : 673-695. doi: 10.3934/mbe.2016014
[10]

Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53
[11]

Chin-Chin Wu. Existence of traveling wavefront for discrete bistable competition model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 973-984. doi: 10.3934/dcdsb.2011.16.973
[12]

Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089
[13]

Alba Málaga Sabogal, Serge Troubetzkoy. Minimality of the Ehrenfest wind-tree model. Journal of Modern Dynamics, 2016, 10: 209-228. doi: 10.3934/jmd.2016.10.209
[14]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183
[15]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1
[16]

Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623
[17]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[18]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021035
[19]

Guirong Jiang, Qishao Lu. The dynamics of a Prey-Predator model with impulsive state feedback control. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1301-1320. doi: 10.3934/dcdsb.2006.6.1301
[20]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (30)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences