Methods for the one-dimensional space allocation problem

Although special cases of the one-dimensional space allocation problem (ODSAP) have been efficiently solved, like the so-called linear ordering problem with independent destinations, or the all prominent matrix case, the general problem appears redoubtable. So far, the use of known exact algorithms has been limited to small size problems, and for bigger problems very few heuristics have been devised. The best known solution methods for the ODSAP are contrasted here with several heuristics that incorporate the novel concept of simulated annealing. Various combinations of elementary interchange and insertion procedures are also studied. The present computational results confirm the suitability of simulated annealing to deal with this problem.