A cutting plane algorithm for the site layout planning problem with travel barriers. (June 2017)

• Record Type: Journal Article
• Authors: Hammad, Ahmed W.A.; Rey, David; Akbarnezhad, Ali
• Is Part Of: Computers & operations research. Volume 82(2017)
• Page Start: 36
• Page End: 51
• Publication Date: 2017-06
• Subjects: Site layout planning -- Mixed integer programming -- Cutting plane algorithms -- Decomposition methods -- Global optimisation -- d-visibility; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.01.005
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A novel discrete Construction Site layout planning model (SLP) is proposed, where multiple coverage of locations by facilities is permitted. We contrast the proposed model with the approach commonly adopted in the literature to solve the SLP problem to exact optimality. We quantify the impact of space discretisation on discrete SLP models. We propose a novel cutting plane algorithm to solve large instances of the discrete SLP problem. We provide a comprehensive analysis on the computational effectiveness of the proposed models. Abstract: 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.