The corridor allocation problem

摘要

The corridor allocation problem (CAP) seeks an arrangement of facilities along a central corridor defined by two horizontal lines parallel to the x-axis of a Cartesian coordinate system. The objective is to minimize the total communication cost among facilities, while respecting two main conditions: (i) no space is allowed between two adjacent facilities; (ii) the left-most point of the arrangement on either line should have zero abscissa. The conditions (i) and (ii) are required in many applications such as the arrangement of rooms at office buildings or hospitals. The CAP is a NP-Hard problem. In this paper, a mixed-integer programming formulation of the CAP is proposed, which allows us to compute optimal layouts in reasonable time for problem instances of moderate sizes. Moreover, heuristic procedures are presented that can handle larger instances.