A new heuristic for the linear placement problem

The linear placement problem (LPP) arises when allocating facilities to sites on a line where adjacent sites are a unit distance apart. Every two facilities have a given amount of traffic between them. The LPP seeks to minimize the total distance traveled. The problem arises in a wide variety of settings and is NP-complete; hence, the need for an efficient heuristic arises. In this paper, a new heuristic algorithm called ‘linear placement with multidimensional scaling’ (LPMDS) is developed and compared with existing exchange algorithms. The comparison is conducted on problems ranging in size from 10 to 40 facilities and LPMDS performs well in terms of solution quality and execution time.