A cutting plane algorithm for the site layout planning problem with travel barriers. (English) Zbl 1391.90381
Summary: Site layout planning is an imperative procedure that may significantly impact the productivity and the efficiency of logistical operations undertaken on a construction site. This paper considers the site layout planning problem (SLPP) which entails the allocation of temporary facilities on a construction site in the presence of travel barriers such that the total transportation cost between facilities is minimised. In order to account for travel barriers, the SLPP is typically solved under the assumption that the available region for facility layout can be discretised. In this paper, we propose a general mixed integer programming (MIP) model to represent the SLPP, accounting for the presence of barriers, and we show how space-discretised formulations can be derived from this model. In particular, we propose a novel MIP model, which permits facilities to cover multiple locations. This is then benchmarked against a commonly adopted MIP model in the literature. We also highlight a systematic procedure to convert the continuous feasible space in SLPP to a set of discretised locations based on the concept of \(d\)-visibility, enabling us to approximate the barrier distance function embedded in the objective function. In particular, we focus on presenting a simple space discretisation approach for converting the continuous SLP into a discrete problem for which the discrete SLP models would be applicable. Space-discretised MIP formulations are highly combinatorial, and we introduce a cutting plane algorithm to improve their tractability. Specifically, we propose a novel exact location-decomposition algorithm which works from a relaxed MIP formulation and iteratively generates feasibility cuts to converge to an optimal solution. Both space-discretised MIP models and the decomposition algorithm are tested on a large group of instances to analyse their effectiveness in solving the SLPP. Computational results indicate that the proposed location-decomposition algorithm improves on the pure MIP approach and provides a competitive framework to solve realistic SLPP instances.
MSC:
| 90B80 | Discrete location and assignment |
| 90C11 | Mixed integer programming |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
site layout planning; mixed integer programming; cutting plane algorithms; decomposition methods; global optimisation; \(d\)-visibilitySoftware:
Algorithm 97References:
| [1] | Abdel, R., Electimize a new evolutionary algorithm for optimization with applications in construction engineering, (2011) |
| [2] | Anumba, C.; Bishop, G., Importance of safety considerations in site layout and organization, Can J Civ Eng Can Genie Civ, 24, 229-236, (1997) |
| [3] | Bischoff, M.; Fleischmann, T.; Klamroth, K., The multi-facility location-allocation problem with polyhedral barriers, Comput Oper Res, 36, 1376-1392, (2009), Selected papers presented at the Tenth International Symposium on Locational Decisions (ISOLDE X) · Zbl 1177.90322 |
| [4] | Butt, S. E.; Cavalier, T. M., An efficient algorithm for facility location in the presence of forbidden regions, Eur J Oper Res, 90, 56-70, (1996) · Zbl 0916.90177 |
| [5] | Cakı r, O.; Wesolowsky, G. O., Planar expropriation problem with non-rigid rectangular facilities, Comput Oper. Res, 38, 75-89, (2011), Project Management and Scheduling · Zbl 1231.90273 |
| [6] | Canbolat, M. S.; Wesolowsky, G. O., The rectilinear distance Weber problem in the presence of a probabilistic line barrier, Eur J Oper Res, 202, 114-121, (2010) · Zbl 1173.90447 |
| [7] | Chen, Y.; Jiang, Y.; Wahab, M. I.M.; Long, X., The facility layout problem in non-rectangular logistics parks with split lines, Expert Syst Appl, 42, 7768-7780, (2015) |
| [8] | Dearing, P. M.; Klamroth, K.; Jr, R. S., Planar location problems with block distance and barriers, Ann Oper Res, 136, 117-143, (2005) · Zbl 1114.90056 |
| [9] | Drezner, Z.; Klamroth, K.; Schöbel, A.; Wesolowsky, G. O., The Weber problem, Facility location: applications and theory, (2002), Springer Science & Business Media · Zbl 1041.90023 |
| [10] | Drira, A.; Pierreval, H.; Hajri-Gabouj, S., Facility layout problems: a survey, Annu Rev Control, 31, 255-267, (2007) |
| [11] | Easa, S.; Hossain, K., New mathematical optimization model for construction site layout, J Constr Eng Manag, 134, 653-662, (2008) |
| [12] | El-Rayes, K.; Khalafallah, A., Trade-off between safety and cost in planning construction site layouts, J Constr Eng Manag, 131, 1186-1195, (2005) |
| [13] | Floyd, R. W., Algorithm 97: shortest path, Commun ACM, 5, (1962), 345-. |
| [14] | Fourer, R.; Gay, D.; Kernighan, B., Ampl, (1993), Boyd & fraser |
| [15] | Hammad, A.; Akbarnezhad, A.; Rey, D.; Waller, S., A computational method for estimating travel frequencies in site layout planning, J Constr Eng Manag, 4015102, (2015) |
| [16] | Hammad, A. W.A.; Akbarnezhad, A.; Rey, D., A multi-objective mixed integer nonlinear programming model for construction site layout planning to minimise noise pollution and transport costs, Autom Constr, 61, 73-85, (2016) |
| [17] | Hassan, M. M.; Hogg, G. L., On constructing a block layout by graph theory, Int J Prod Res, 29, 1263-1278, (1991) |
| [18] | Holt, A. S.J., Principles of construction safety, (2008), John Wiley & Sons |
| [19] | Jr, A. R.M.; Liu, W.-H., New tabu search heuristics for the dynamic facility layout problem, Int J Prod Res, 50, 867-878, (2012) |
| [20] | Khalafallah, A.; Abdel-Raheem, M., Electimize: new evolutionary algorithm for optimization with application in construction engineering, J Comput Civ Eng., 25, 192-201, (2011) |
| [21] | Khalafallah, A.; El-Rayes, K., Automated multi-objective optimization system for airport site layouts, Autom Constr, 20, 313-320, (2011) |
| [22] | Klamroth, K., A reduction result for location problems with polyhedral barriers, Eur J Oper Res, 130, 486-497, (2001) · Zbl 0981.90042 |
| [23] | Kusiak, A.; Heragu, S. S., The facility layout problem, Eur J Oper Res, 29, 229-251, (1987) · Zbl 0612.90035 |
| [24] | Lam, K. C.; Tang, C. M.; Lee, W. C., Application of the entropy technique and genetic algorithms to construction site layout planning of medium‐size projects, Constr Manag Econ, 23, 127-145, (2005) |
| [25] | Larson, R. C.; Sadiq, G., Facility locations with the Manhattan metric in the presence of barriers to travel, Oper Res, 31, 652-669, (1983) · Zbl 0521.90045 |
| [26] | Li, H.; Love, P. E., Genetic search for solving construction site-level unequal-area facility layout problems, Autom Constr, 9, 217-226, (2000) |
| [27] | McGarvey, R. G.; Cavalier, T. M., A global optimal approach to facility location in the presence of forbidden regions, Comput Ind Eng, 45, 1-15, (2003) |
| [28] | McKendall, A. R.; Hakobyan, A., Heuristics for the dynamic facility layout problem with unequal-area departments, Eur J Oper Res, 201, 171-182, (2010) · Zbl 1177.90259 |
| [29] | McKendall, A. R.; Shang, J.; Kuppusamy, S., Simulated annealing heuristics for the dynamic facility layout problem, Comput Oper Res, 33, 2431-2444, (2006) · Zbl 1086.90037 |
| [30] | Miyagawa, M., Rectilinear distance to a facility in the presence of a square barrier, Ann Oper Res, 196, 443-458, (2012) · Zbl 1251.90258 |
| [31] | Moore, J. M., Facilities design with graph theory and strings, (1976), Omega 4 |
| [32] | Ning, X.; Lam, K. C., Cost-safety trade-off in unequal-area construction site layout planning, Autom Constr, 32, 96-103, (2013) |
| [33] | Ning, X.; Lam, K.-C.; Lam, M. C.-K., Dynamic construction site layout planning using MAX-MIN ant system, Autom Constr, 19, 55-65, (2010) |
| [34] | Osman, H. M.; Georgy, M. E.; Ibrahim, M. E., A hybrid CAD-based construction site layout planning system using genetic algorithms, Autom Constr, 12, 749-764, (2003) |
| [35] | Rossin, D. F.; Springer, M. C.; Klein, B. D., New complexity measures for the facility layout problem: an empirical study using traditional and neural network analysis, Comput Ind Eng, 36, 585-602, (1999) |
| [36] | Sadeghpour, F.; Andayesh, M., The constructs of site layout modeling: an overview, Can J Civ Eng, 42, 199-212, (2015) |
| [37] | Ş ahin, R.; Ertoğ ral, K.; Türkbey, O., A simulated annealing heuristic for the dynamic layout problem with budget constraint, Comput Ind Eng, 59, 308-313, (2010) |
| [38] | Savaş, S.; Batta, R.; Nagi, R., Finite-size facility placement in the presence of barriers to rectilinear travel, Oper Res, 50, 1018-1031, (2002) · Zbl 1163.90623 |
| [39] | Scholz, D.; Jaehn, F.; Junker, A., Extensions to stats for practical applications of the facility layout problem, Eur J Oper Res, 204, 463-472, (2010) · Zbl 1181.90172 |
| [40] | Singh, S. P.; Sharma, R. R.K., A review of different approaches to the facility layout problems, Int J Adv Manuf Technol, 30, 425-433, (2006) |
| [41] | Sirinaovakul, B., An analysis of computer-aided facility layout techniques, Int J Comput Integr Manuf, 9, 260-264, (1996) |
| [42] | Smith-Miles, K.; Lopes, L., Measuring instance difficulty for combinatorial optimization problems, Comput Oper Res, 39, 875-889, (2012) · Zbl 1251.90339 |
| [43] | Tam, C. M.; Tong, T. K.; Leung, A. W.; Chiu, G. W., Site layout planning using nonstructural fuzzy decision support system, J Constr Eng Manag, 128, 220-231, (2002) |
| [44] | Tompkins, J. A.; White, J. A.; Bozer, Y. A.; Tanchoco, J. M.A., Facilities planning, (2010), John Wiley & Sons |
| [45] | Warshall, S., A theorem on Boolean matrices, J ACM, 9, 11-12, (1962) · Zbl 0118.33104 |
| [46] | Wong, C.; Fung, I.; Tam, C., Comparison of using mixed-integer programming and genetic algorithms for construction site facility layout planning, J Constr Eng Manag, 136, 1116-1128, (2010) |
| [47] | Xu, J.; Song, X., Multi-objective dynamic layout problem for temporary construction facilities with unequal-area departments under fuzzy random environment, Knowl Based Syst, 81, 30-45, (2015) |
| [48] | Yahya, M.; Saka, M. P., Construction site layout planning using multi-objective artificial bee colony algorithm with levy flights, Autom Constr, 38, 14-29, (2014) |
| [49] | Zhang, H.; Wang, J. Y., Particle swarm optimization for construction site unequal-area layout, J Constr Eng Manag, 134, 739-748, (2008) |
| [50] | Li, Z.; Anson, M; Li, G., A procedure for quantitatively evaluating site layout alternatives, Constr Manag. Econ, 19, 459-467, (2001) |
| [51] | Zouein, P.; Harmanani, H.; Hajar, A., Genetic algorithm for solving site layout problem with unequal-size and constrained facilities, J Comput Civ Eng, 16, 143-151, (2002) |
| [52] | Zouein, P.; Tommelein, I., Dynamic layout planning using a hybrid incremental solution method, J Constr Eng Manag, 125, 400-408, (1999) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
