The facility layout instances of the generalised travelling salesman problem

Abstract

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.

Keywords:

• Loop-based facility planning
• loop-based material handling
• generalised travelling salesman problem
• GTSP
• AGVS

Acknowledgments

Thanks are due to Mohammad Modarress and Kourosh Eshghi professors of Industrial Engineering at Sharif University for their life-long academic contributions.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was partially supported by Research, Scholarship, and Creative Activity Award, California State University, Northridge.

Notes on contributors

Ardavan Asef-Vaziri

Ardavan Asef-Vaziri is a Professor of Systems and Operations Management in the David Nazarian College of Business and Economics, California State University, Northridge. He completed his BSc, MSc, and Ph.D. all in Industrial Engineering. His research revolves around applications of optimisation and simulation in process flows analysis. The main theme of his teaching and research is how to create a streamlined and smooth flow in manufacturing, distribution, service, and educational systems. He was among the first wave adopting the flipped classroom course delivery format more than a decade ago. Dr. Asef-Vaziri's publications have appeared in EJOR, IISE-Transactions, Computers & Operations Research, Journal of the Operational Research Society, International Journal of Production Economics, among others.

Morteza Kazemi

Morteza Kazemi is an Assistant Professor of Industrial Engineering at the Shiraz University of Technology, Shiraz, Iran. He is teaching Statistical and queuing theory courses at undergraduate and graduate levels. He completed his BSc, MSc, and Ph.D. all in Industrial Engineering with a focus in Design and Operations of Production Systems. His research interest includes applications of optimisation, simulation, and queuing theory in automated manufacturing systems. Dr. Kazemi's publications have appeared in EJOR, Computer & Industrial Engineering, ORIJ, among others.

Maryam Radman

Maryam Radman is a lecturer teaching advanced courses in Operations Research at the Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran. Her research interests include mathematical programming, combinatorial optimisation, decomposition algorithms, stochastic processes, and queuing theory. Dr. Radman obtained her BSc, MSc, and Ph.D. all in Industrial Engineering in 2013, 2015, and 2021, respectively. Her publications have appeared in Computers & Industrial Engineering, OR Spectrum, International Journal of Mathematics in Operational Research, among others.