A Multi-Period 1-Center Location Problem in the Presence of a Probabilistic Line Barrier

Document Type : Research Article

Authors

Abstract

This paper investigates a multi-period rectilinear distance 1-center location problem considering a line-shaped barrier, in which the starting point of the barrier follows the uniform distribution function. In addition, the existing points are sensitive to demands and locations. The purpose of the presented model is to minimize the maximum barrier distance from the new facility to the existing facilities during the finite planning horizon. Additionally, a lower bound problem is generated. The presented model is mixed-integer nonlinear programming (MINLP); however, an optimum solution is reached.

Keywords


[1]     Y. P. Aneja and M. Parlar, “Algorithms for Weber facility location in the presence of forbidden regions and/or barriers to travel,” Transportation Science, vol. 28, pp. 70–76, 1994.
[2]     A. Antunes and D. Peeters, “On solving complex multi-period location models using simulated annealing,” European Journal of Operational Research, vol. 130, pp. 190–201, 2001.
[3]     L. Aupperle and J. M. Keil, “Polynomial algorithms for restricted Euclidean p-centre problems,” Discrete Applied Mathematics, vol. 23, pp. 25–31, 1989.
[4]     R. Batta, A. Ghose and U. Palekar, "Locating facilities on the Manhattan metric with arbitrarily shaped barriers and convex forbidden regions," Transportation Science, vol. 23, pp. 26–36, 1989.
[5]     M. Bischoff, T. Fleischmann and K. Klamroth, “The multi-facility location–allocation problem with polyhedral barriers,” Computers and Operations Research, vol. 36, pp. 1376 –1392, 2009.
[6]     M. Bischoff and K. Klamroth, “An efficient solution method for Weber problems with barriers based on genetic algorithms,” European Journal of Operational Research, vol. 177, pp. 22–41, 2007.
[7]     S. E. Butt and T. M. Cavalier, “An efficient algorithm for facility location in the presence of forbidden regions,” European Journal of Operational Research, vol. 9011, pp. 56–70, 1996.
 
[8]     M. S. Canbolat and G. O. Wesolowsky, “The rectilinear distance Weber problem in the presence of a probabilistic line barrier,” European Journal of Operational Research, vol. 2021, pp. 114–121, 2010.
[9]     C. Canel, B. M. Khumawala, J. Law and A. Loh, “An algorithm for the capacitated, multi-commodity multi-period facility location problem,” Computers and Operations Research, vol. 28, pp. 411–427, 2001.
[10]   N. R. Chakrabarty and P. K. Chaudhuri, “Geometric solution of a constrained rectilinear distance minimax location problem,” Asia-Pacific Journal of Operations Research, vol. 7, pp. 163-171, 1990.
[11]   N. R. Chakrabarty and P. K. Chaudhuri, “Geometrical solution to some planar constrained minimax problems involving the weighted rectilinear metric,” Asia-Pacific Journal of Operations Research, vol. 9, pp. 135-144, 1992.
[12]   J. Current, S. Ratick, and C. ReVelle, “Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach,” European Journal of Operational Research, vol. 110, pp.  597–609, 1997.
[13]   P. M. Dearing and Jr., R. Segars, “An equivalence result for single facility planar location problems with rectilinear distance and barriers,” Annals of Operations Research, vol. 111, pp. 89-110, 2002.
[14]   P. M. Dearing and Jr., R. Segars, “Solving rectilinear planar location problems with barriers by a polynomial partitioning,” Annals of Operations Research, vol. 111, pp. 111-133, 2002.
[15]   P. M. Dearing, H. W. Hamacher and K. Klamroth, “Dominating sets for rectilinear center location problems with polyhedral barriers,” Naval Research Logistics, vol. 49, pp. 647–665, 2002.
[16]   P. M. Dearing, K. Klamroth, and Jr., R. Segars, “Planar location problems with block distance and barriers,” Annals of Operations Research, vol. 136, pp. 117–143, 2005.
[17]   J. Dias, M. E. Captivo and J. Clímaco, “Efficient primal-dual heuristic for a dynamic location problem,” Computers and Operations Research vol. 34, pp. 1800–1823, 2007.
[18]   J. Dias, M. E. Captivo, and J. Clímaco, “A memetic algorithm for multi-objective dynamic location problems,” Journal of Global Optimization, vol. 42, pp. 221–253, 2009.  
[19]   Z. Drezner and G. P. Wesolowsky, “Facility location when demand is time dependent,” Naval Research Logistics, vol. 38, pp. 763–777, 1991.
[20]   D. Erlenkotter, “A comparative study of approaches to dynamic location problems,” European Journal of Operational Research, vol. 6, pp. 133–143, 1981.
[21]   R. Z. Farahani, Z. Drezner, and N. Asgari, “Single facility location and relocation problem with time dependent weights and discrete planning horizon,” Annals of Operations Research, vol. 167, pp. 353–368, 2009.
[22]   M. Frantzeskakis and C. D. T. Watson-Gandy, “The use of state space relaxation for the dynamic facility location problem,” Annals of Operations Research, vol. 18, 1989.
[23]   L. Frieß, K. Klamroth and M. Sprau, “A wavefront approach to center location problems with barriers,” Annals of Operations Research, vol. 136, pp. 35–48, 2005.
[24]   R. D. Galvão, E. Santibañez-Gonzalez, and R. Del, “A Lagrangean heuristic for the P-median dynamic location problem,” EuropeanJournal of Operational Research, vol. 58, pp. 250–62, 1992.
[25]   R. D. Galvão, E. Santibañez-Gonzalez, and R. Del, “The pk-median dynamic location problem: formulation and a heuristic solution method, Investigación Operativa, vol. 1, pp. 295–308, 1990.
[26]   H. W. Hamacher, and K.  Klamroth, “Planar Weber location problems with barriers and block norms,” Annals of Operations Research, vol. 96, pp. 191–208, 2000.
[27]   H. W. Hamacher, and S. Nickel, “Multicriteria planar location problems,” European Journal of Operational Research, vol. 94, pp. 66–86, 1996.
[28]   H. W. Hamacher, and S. Nickel, “Classification of location problems,” Location Science, vol. 6, pp. 229–242, 1998.
[29]   P. Hansen, D. Peeters and J. Thisse, “On the location of an obnoxious facility,” Sistemi Urbani, vol. 3, pp. 299–317, 1981.
[30]   Y. Hinojosa, J. Puerto, and F. R. Fernández, “A multiperiod two-echelon multicommodity capacitated plant location problem,” European Journal of Operational Research, vol. 123, pp. 271–291, 2000.
[31]   A. M. Hormozi and B. M. Khumawala, “An improved algorithm for solving a multi-period facility location problem,” IIE Transactions, vol. 28, pp. 105–114, 1996.
[32]   I. N. Katz and L. Cooper, “Formulation and the case of Euclidean distance with one forbidden circle,” European Journal of Operational Research, vol. 6, pp. 166–173, 1981.
[33]   H. Kelachankuttu, R. Batta, and R. Nagi, “Contour line construction for a new rectangular facility in an existing layout with rectangular departments,” European Journal of Operational Research, vol. 180, pp. 149–162, 2007.
[34]   D. L. Kelly and A. S. Marucheck, “Planning horizon results for the dynamic warehouse location problem,” Journal of Operations Management, vol. 4, pp. 279–294, 1984. 
[35]   Klamroth, K. “A reduction result for location problems with polyhedral barriers,” European Journal of Operational Research, vol. 130, pp. 486–497, 2001.
[36]   K. Klamroth, “Planar Weber location problems with line barriers,” Optimization, vol. 49, pp. 517–527, 2001.
[37]   K. Klamroth, “Algebraic properties of location problems with one circular barrier,” European Journal of Operational Research, vol. 154, pp. 20–35, 2004.
[38]   K. Klamroth and M. M. Wiecek, “A bi-objective median location problem with a line barrier,” Operations Research, vol. 50(4), pp. 670–679, 2002.
[39]   R. C. Larson and G. Sadiq, “Facility location with the Manhattan metric in the presence of barriers to travel,” Operations Research, vol. 31, pp. 652–669, 1983.
[40]   R.G. McGarvey and T.M. Cavalier, “A global optimal approach to facility location in the presence of forbidden regions,” Computers and Industrial Engineering, vol. 45, pp. 1–15, 2003.
[41]   E. Melachrinoudis, H. Min, and A. Messac, “The Relocation of a Manufacturing/Distribution Facility from Supply Chain Perspectives: A Physical programming Approach,” Multi-Criteria Applications, vol. 10, pp. 15–39, 2000.
[42]   H. Min, “The dynamic expansion and relocation of capacitated public facilities: A multi-objective approach,” Computers and Operations Research, vol. 15, pp. 243–252, 1988.
[43]   P. Nandikonda, R. Batta and R. Nagi, “Locating a 1-center on a Manhattan plane with ‘arbitrarily’ shaped barriers,” Annals of Operations Research, vol. 123, pp. 157–172, 2003.
[44]   S. Nickel, “Restricted center problems under polyhedral gauges,” European Journal of Operational Research, vol. 104, pp. 343–357, 1998.
[45]   J. Puerto and A. M. Rodríguez-Chía, “New models for locating a moving service facility,” Mathematical Methods of Operations Research, vol. 63, pp. 31–51, 2006.
[46]   A. Sarkar, R. Batta and R. Nagi, “Placing a finite size facility with a center objective on a rectangular plane with barriers,” European Journal of Operational Research, vol. 179, pp. 1160–1176, 2007.
[47]   S. Savaş, R. Batta and R. Nagi, “Finite-size facility placement in the presence of barriers to rectilinear travel. Operations Research, vol. 50(6), pp. 1018–1031, 2002.
[48]   A. Shulman, “An Algorithm for Solving Dynamic Capacitated Plant Location Problems with Discrete Expansion Sizes,” Operations research, vol. 39(3), pp. 423–436, 1991.
[49]   J. J. Sylvester, “A question in the geometry of situation,” Quarterly Journal of Pure and Applied Mathematics, vol. 1, pp. 79–80, 1857.
[50]   B. C. Tansel, R. L. Francis, and T. J. Lowe, “Location on networks: A survey. Part I: The p-center and p-median problems,” Management Science, vol. 29, pp. 482–497, 1983.
[51]   T. Van Roy, D. Erlenkotter, “A dual-based procedure for dynamic facility location,” Management Science, vol. 28, pp. 1091–1105, 1982.
[52]   S. J. Wang, J. Bhadury, R. Nagi, “Supply facility and input/output point locations in the presence of barriers,” Computers and Operations Research, vol. 29, pp. 685–699, 2002.
[53]   G. O. Wesolowsky, “Dynamic facility location,” Management Science, vol. 19, pp. 1241–1248, 1973.
 
Books:
 
[54]   R. Z. Farahani and M. Hekmatfar, Facility location: Concepts, models, algorithms and case studies, Berlin: Physica-Verlag, 2009, p. 347.
[55]   K. Klamroth, Single-facility location problems with barriers, Springer Series in Operations Research, 2002, p. 17.
 
Papers from Conference Proceedings (Published):
 
[56]   S. Shiripour, I .Mahdavi, M. Amiri-Aref, M. Mohammadnia-Otaghsara, “A Nonlinear Programming Model for a Multi-Facility Location Problem with a Probabilistic Line Barrier” in Proc. International Conference on Industrial Engineering and Engineering Management (IEEM) 2010 IEEE, pp. 630-634.