Map Labelling

Mike Preuss has developed a software package for placement and layout optimization problems. These belong to an important class of problems where objects need to be placed into a fixed geometrical form according to constraints which need to be taken into account during the placement, e.g.

• the optimal placement of production units in a facility layout in order to maximize the total efficiency of the production process, i.e. minimize the total costs,
• the optimal packing of containers / trucks in order to exploit the total capacity in the best possible way while taking into account the delivery order for an efficient access to the goods,
• the optimal placement of subunits on VLSI chips in order to minimize the interconnection lengths while considering production constraints of the chips,
• the optimal assignment of name labels to geographic maps in order to avoid label and boundary overlaps and provide the best aesthetic appearance of the labelling.

As an example application, the following software demonstration focuses on map-labelling. The algorithm is based on a standard evolution strategy and generates very good labellings even for a large numbers of labels.

Start the applet and label a small map (13 objects) | medium-size map (52 objects) | large map (200 objects).

©Mike Preuß, Frank Kursawe,