University professor
Dr.-Ing. Bernd
Hellingrath
Chair for Information Systems and
Leonardo-Campus 3
48149 Münster
Tel. +49 251 83-38000
Fax +49 251 83-38009
Tutorial Operations Management
Chapter 3 – Location Planning
Solutions
Please note: Round off to two digits, if not indicated otherwise.
Exercise 1: Manhattan Distances
a)
Optimizing assignment as well as optimizing locations is part of this heuristic. Through the
optimization of assignment, an optimal assignment of locations to buildings is achieved. For
the following optimization of canteen locations, optimal locations for the respective assign-
ments are determined. Both optimizations are executed in rotation several times. The heuristic
works as follows:
1. Selection of initial solution: First of all, free selectable locations of canteens are chosen
on a provisional basis. Therefore, any location can be picked. Examples could be locations,
which are located close to building complexes.
2. Optimize assignment: To determine the optimal assignment of buildings, each building is
assigned to the closest located canteen.
3. Optimize locations: The optimal canteen locations for the given assignment of buildings
to canteens are determined. Therefore, the optimal location for each canteen is determined
under the assumption that only those buildings are delivered by the canteen, which have al-
ready been assigned to the building.
4. Termination of the algorithm: Step two and three are executed in rotation until the can-
teen locations between two following iterations do not change anymore. Then, the algo-
rithm terminates with the current assignment of buildings to canteens as the final solution.
Since this optimization problem is mathematically very complex and hard to solve optimally,
we use the heuristic described above. It usually yields a good, but not always the optimal so-
lution.
, 2
b)
First Iteration
The initial solution (step 1) is (xA,yA)=(3,7) and (xB,yB)=(8,7). You start with optimizing the
assignment of buildings to canteen locations (step 2). See fig. 1 for the assignment:
Distance to Distance to
Building Coordinates Employees
Canteen A Canteen B
j aj bj wj d(3,7) d(8,7)
1 8 11 79 9 4
2 6 6 53 4 3
3 2 5 35 3 8
4 13 9 48 12 7
5 4 2 67 6 9
6 14 13 24 17 12
Fig. 1: Assignment of buildings to canteen locations (first iteration)
Corresponding to the first iteration, employees of building 3 and 5 are assigned to canteen A,
employees of building 1, 2, 4 and 6 are assigned to canteen B. See figure 2 for optimizing the
locations (step 3).
First Iteration: Canteen A
Building j Location aj Employees wj Cumulated
3 2 35 35
5 4 67 102
Building j Location bj Employees wj Cumulated
5 2 67 67
3 5 35 102
First Iteration: Canteen B
Building j Location aj Employees wj Cumulated
2 6 53 53
1 8 79 132
4 13 48 180
6 14 24 204
Building j Location bj Employees wj Cumulated
2 6 53 53
4 9 48 101
1 11 79 180
6 13 24 204
Fig. 2: Optimization of locations (first iteration)
The new canteen locations are (xA,yA)=(4,2) and (xB,yB)=(8,11).
Dr.-Ing. Bernd
Hellingrath
Chair for Information Systems and
Leonardo-Campus 3
48149 Münster
Tel. +49 251 83-38000
Fax +49 251 83-38009
Tutorial Operations Management
Chapter 3 – Location Planning
Solutions
Please note: Round off to two digits, if not indicated otherwise.
Exercise 1: Manhattan Distances
a)
Optimizing assignment as well as optimizing locations is part of this heuristic. Through the
optimization of assignment, an optimal assignment of locations to buildings is achieved. For
the following optimization of canteen locations, optimal locations for the respective assign-
ments are determined. Both optimizations are executed in rotation several times. The heuristic
works as follows:
1. Selection of initial solution: First of all, free selectable locations of canteens are chosen
on a provisional basis. Therefore, any location can be picked. Examples could be locations,
which are located close to building complexes.
2. Optimize assignment: To determine the optimal assignment of buildings, each building is
assigned to the closest located canteen.
3. Optimize locations: The optimal canteen locations for the given assignment of buildings
to canteens are determined. Therefore, the optimal location for each canteen is determined
under the assumption that only those buildings are delivered by the canteen, which have al-
ready been assigned to the building.
4. Termination of the algorithm: Step two and three are executed in rotation until the can-
teen locations between two following iterations do not change anymore. Then, the algo-
rithm terminates with the current assignment of buildings to canteens as the final solution.
Since this optimization problem is mathematically very complex and hard to solve optimally,
we use the heuristic described above. It usually yields a good, but not always the optimal so-
lution.
, 2
b)
First Iteration
The initial solution (step 1) is (xA,yA)=(3,7) and (xB,yB)=(8,7). You start with optimizing the
assignment of buildings to canteen locations (step 2). See fig. 1 for the assignment:
Distance to Distance to
Building Coordinates Employees
Canteen A Canteen B
j aj bj wj d(3,7) d(8,7)
1 8 11 79 9 4
2 6 6 53 4 3
3 2 5 35 3 8
4 13 9 48 12 7
5 4 2 67 6 9
6 14 13 24 17 12
Fig. 1: Assignment of buildings to canteen locations (first iteration)
Corresponding to the first iteration, employees of building 3 and 5 are assigned to canteen A,
employees of building 1, 2, 4 and 6 are assigned to canteen B. See figure 2 for optimizing the
locations (step 3).
First Iteration: Canteen A
Building j Location aj Employees wj Cumulated
3 2 35 35
5 4 67 102
Building j Location bj Employees wj Cumulated
5 2 67 67
3 5 35 102
First Iteration: Canteen B
Building j Location aj Employees wj Cumulated
2 6 53 53
1 8 79 132
4 13 48 180
6 14 24 204
Building j Location bj Employees wj Cumulated
2 6 53 53
4 9 48 101
1 11 79 180
6 13 24 204
Fig. 2: Optimization of locations (first iteration)
The new canteen locations are (xA,yA)=(4,2) and (xB,yB)=(8,11).
