The parallel row ordering problem (PROP)

Given a partitioning of the set of facilities into two subsets, the PROP asks to arrange one subset of facilities on one line and the other subset of facilities on a parallel line with the goal of minimizing the weighted sum of the distances between all pairs of facilities. The distance between two facilities (with given lengths) is taken as the x-distance between their centers. Each distance is weighted by the material transportation cost per distance unit between the corresponding facilities.

For solving the PROP, I have developed a memetic algorithm (MA) utilizing a fast local search procedure which is based on repeatedly applying insertion moves to the current solution. The source code (in the C++ programming language, Borland version) of MA can be found in MA_code.zip.

The algorithm was tested on the PROP instances with up to 500 facilities. This set of instances can be found in the file PROP_instances.zip. Instance is provided in the following format:
- the total number of facilities;
- the number of facilities in the first row;
- the lengths of facilities;
- the (symmetric) flow matrix (its upper triangle is used in the objective function).