The facility layout instances of the generalised travelling salesman problem

In this paper, we provide new insight into the problem of designing loop flow-patterns and input-output (I/O) stations in a facility layout to minimise the summation of loaded and empty trip distances. The loop covering at least one contourline of each workcenter in a manufacturing facility layout is an instance of the generalised travelling salesman problem (GTSP). The shortest length solution to this GTSP provides a promising heuristic scheme to minimise the total loaded and empty flow in vehicle-based material handling. The sequence of the I/O stations alongside the loop also plays a significant role in determining the volume of the loaded and empty flow. The larger the set of candidate locations for I/O stations, the higher the flexibility in sequencing the stations. On this foundation, we define a new objective function of maximal-node-covering for our instance of the GTSP. By combining the characteristics of the shortest and the maximal-node-covering loops, a set of complementary heuristics are developed to design a loop and locate the I/O stations to minimise the total loaded and empty flow.