A location problem deals with finding optimal locations for one or several new facilities. These optimal locations are influenced by several parameters given by demand points, sometimes referred to as existing facilities (for example train stations or parking spaces), the amount of clients the new facilities have to serve, and many more.
Location problems are distinguished in three major parts: planar, network and discrete location problems.
Like the name says, in a planar or also called continuous location problem, one is interested in finding new locations in the plane. In contrast to the other location problems, where the locations are kind of predefined, these locations are given by the x- and y-coordinates and can be anywhere except in the forbidden regions if existent.
Feasible parameters for this problem would be a distance measure to other facilities and, if necessary, the importance/priority to these demand points, which is usually given by different weights.
One easily sees, that sometimes it is not reasonable to use the planar location model, for example, when placing a new facility in the street network of a city. Because of streets, walls, or other possible structures, one cannot use straight lines, but has to navigate through the infrastructure of the city. This observation leads to the idea of using graphs and networks, where the name Network Location Problem comes from.
The nodes, denoted by the capital letters, represent crossings and locations of existing facilities. The numbers next to the arrows between two nodes represent the time or effort to pass from one node to the other. This example represents a directed graph, in which all edges are directed, hence the roads are only one way. In an undirected graph the direction one can pass an edge is not specified.
We recognize some differences to the Planar Location Problem:
In general, optimal solutions can be allowed to be on edges or only on nodes.
In contrast to location problems, where the focus for each facility is the absolute location, in layout problems the location relative to the other (new) facilities is more important. The location of one facility influences the quality of the locations of the other facilities.
With the help of layout problems, optimal locations and assignments of food stands at a public event can be found. In this example the goal is to spread the stands over the area, such that people are not concentrated at one place as this might lead to problems in an emergency situation. Another goal can be to locate stands, where they attract visitors, which will maximize the profit. One might also be wishing to locate food stands far from other facilities such as stages or toilets.
The Quadratic Assignment Problem (QAP) is often used to model layout problems. In this model, facilties are assigned to locations. This is done by minimizing a weighted sum of distances between the new facilities.
In urban event planning, it is possible that the number of possible locations is bigger than the number of facilities to place. Also, some locations of facilities are already predefined, for example the stage or electrcity connectors. Therefore, the Quadratic Assignment Problem is extended in the following definition.
For and define
Assuming that the fixed facilities are assigned to locations , is extended to
Then the optimization problem can be formulated as:
In the Camera Location Problem or Art Gallery Problem, synonymously, optimal positions of cameras or guards are determined to monitor as much of a given polygonal area as possible with as little cameras as possible.
As an example, one can imagine an art gallery where guards are placed such that each painting is in sight of at least one guard. To save cost, as little guards as possible are hired.
The polygonal monitoring area is subdivided into grid cells of uniform size. Some areas can be more important than others. In these important areas, weights higher than 1 can be assigned to the cells of the area.
Furthermore, obstacles can be defined, i.e. areas which interfere the vision of the cameras.
Cameras have a uniform depth and range of vision.
A cell is said to be monitored if the segment from the camera to the midpoint of the respective cell lies in the polygon and does not cross an obstacle.
The objective is to maximize the weighted monitored area while minimizing the number of cameras. One can bound this number by a maximal number of cameras.
The problem is solved in its discrete version, i.e. a set of possible camera locations is given. The algorithm then calculates the maximal percentage of monitored area for each number of cameras smaller or equal to the maximal number until no further improvement is possible.