4.4 Two-Stage Approaches
67
x
y
10
20
30
40
50
10
20
30
40
50
A(5,30)
B(15,12)
C(30,15)
D(48,5)
E(45,25)
F(55,35)
G(32,40)
H(25,55)
Fig. 4.5 Delaunay triangulation on a set of eight points
To achieve this, we use a triangulation of the plane. A triangulation is a division
of a polygon into a set of triangles with the restriction that any two adjacent
triangles share one side entirely. We are interested in triangulations that have all the
vertices of the triangles at one of the points corresponding to the department centres.
Furthermore, we use a specific triangulation called the Delaunay triangulation that
has the property of maximizing the minimum angle of all the angles of the triangles
in the triangulation. In practice, such a triangulation is unlikely to have thin triangles,
and in our context, this results in a better space allocation to the departments. The
Delaunay triangulation for a set of eight points is illustrated in Fig. 4.5.
Once we have computed the triangulation, we take the edges of the triangulation
to represent the relative positions of the departments, and these positions are then
enforced by appropriately fixing the binary variables (α ij , β ij ). In terms of the
model in Sect. 4.2, this is equivalent, for each pair of departments i and j , to
replacing the constraints (4.21) and (4.22) by a single linear constraint that achieves
the relative positioning of these two departments in the model for the second stage,
in accordance with the edges of the triangulation. Specifically, suppose that the
67
x
y
10
20
30
40
50
10
20
30
40
50
A(5,30)
B(15,12)
C(30,15)
D(48,5)
E(45,25)
F(55,35)
G(32,40)
H(25,55)
Fig. 4.5 Delaunay triangulation on a set of eight points
To achieve this, we use a triangulation of the plane. A triangulation is a division
of a polygon into a set of triangles with the restriction that any two adjacent
triangles share one side entirely. We are interested in triangulations that have all the
vertices of the triangles at one of the points corresponding to the department centres.
Furthermore, we use a specific triangulation called the Delaunay triangulation that
has the property of maximizing the minimum angle of all the angles of the triangles
in the triangulation. In practice, such a triangulation is unlikely to have thin triangles,
and in our context, this results in a better space allocation to the departments. The
Delaunay triangulation for a set of eight points is illustrated in Fig. 4.5.
Once we have computed the triangulation, we take the edges of the triangulation
to represent the relative positions of the departments, and these positions are then
enforced by appropriately fixing the binary variables (α ij , β ij ). In terms of the
model in Sect. 4.2, this is equivalent, for each pair of departments i and j , to
replacing the constraints (4.21) and (4.22) by a single linear constraint that achieves
the relative positioning of these two departments in the model for the second stage,
in accordance with the edges of the triangulation. Specifically, suppose that the