Automatic text placement is one of the most difficult, complex, and time-consuming problems in mapmaking and GIS (Geographic Information System).
– require good placement of labels as well, not to mention engineering drawings, and professional programs which produce these drawings and charts, like spreadsheets (e.g. Microsoft Excel) or computational software programs (e.g. Mathematica).
Naively placed labels overlap excessively, resulting in a map that is difficult or even impossible to read.
For example, an experienced cartographer repeats road names several times for long roads, instead of placing them once, or in the case of Ocean City depicted by a point very close to the shore, the cartographer would place the label "Ocean City" over the land to emphasize that it is a coastal town.
[2] For example, New York City, Vienna, Berlin, Paris, or Tokyo must show up on country maps because they are high-priority labels.
Slightly more complex algorithms rely on local optimization to reach a local optimum of a placement evaluation function – in each iteration placement of a single label is moved to another position, and if it improves the result, the move is preserved.
When the temperature is high, simulated annealing performs almost random changes to the label placement, being able to escape a local optimum.
Some versions of the map label placement problem can be formulated as multiple choices integer programming (MCIP) problems where the objective function is to minimize the sum of numerical penalties for moving individual labels away from their optimal placement to avoid overlaps.
The problem constraints are that each label be placed in one of a finite number of allowed positions on the map.
[5] The first commercial solution to the map label problem, formulated as a MCIP problem and solved by Lagrangian relaxation, was to place well and seismic shot point labels on petroleum industry base maps.
[6] Since that first solution was published there have many other mathematical optimization algorithms proposed and used to solve this MCIP for other cartographic applications.