Example 1 – Lecture I,

Example Page 24

1)
No multiple edges, no loops, not directed, fully connected, a cycle, simple
2)
No multiple edges, not directed, fully connected, a cycle
3)
No multiple edges, not directed, fully connected
4)
Loop, directed
5)
Not fully connected, not directed, cycles, multiple edges, an isolated node
6)
Not a graph
7)
Directed, fully connected, cycles, no multiple edges
8)
All isolated nodes, no edges
9)
Not a graph
10)
Partly directed – a mixed graph, fully connected, cycles
11)
A tree, undirected, simple
12)
Two isolated nodes, a perfect matching

Example 2, Lecture II
Example Page 16
1 semi-eulerian
2 neither
3 semi-eulerian
4 neither
5 semi-eulerian
6 not a graph
Example Page 50

Example 3, Lecture III Page 19

See Excel File

Example 4, Lecture IV
Example 1:

) Nearest-Neighbour heuristic
A–B–D–E–C–A
Distance: 3+2+3+1+6 = 15

b) MST-heuristic
Minimum Spanning Tree A-B-D-E-C
Double each edge for an Eulertour

Eulertour starting from node A: A-B-D-E-C-E-D-B-A

Remove edges to find a Hamiltonian tour: A-B-D-E-C-A

Distance: 3+2+3+1+6=15

c) Christofides-heuristic
Minimum Spanning Tree A-B-D-E-C

Only nodes A and C have an odd degree. For a perfect matching add the edge A-C

Hamiltonian tour A-B-D-E-C-A

Distance: 15

Example 2, Page 38

Minimum Spanning Tree (MST):

2−0−4−3−1

Nodes 2 and 1 are odd. The minimum distance between them is 110. Add the edge 2-1.

Eulerian / Hamiltonian Cycle:

0−4−3−1−2−0
Costs: 20+30+30+110+50=240

2opt with the first improvement!

1st Iteration:
0−4−3−1−2−0 = 240
1. 0−3−4−1−2−0 = 290
2. 0−4−1−3−2−0 = 250
3. 0−1−3−4−2−0 = 210 (!)

An improvement is found. The next iteration starts with the new solution:

2nd Iteration:
0−1−3−4−2−0 = 210 (!)
1. 0−3−1−4−2−0 = 250
2. 0−1−4−3−2−0 = 260
3. 0−1−3−2−4−0 = 250
4. 0−4−3−1−2−0 = 240
5. 0−1−2−4−3−0 = 290
6. 0−2−4−3−1−0 = 210 (!)

No more improvement! The best solution found is 0−1−3−4−2−0 with the costs of 210!
Example 5, Lecture V –
Page 24

Solution 241, 1-2-6-4-5-3-1

Page 25

Initial Route: 0-4-3-1-6-2-7-5-0 (465)

[Link]:

(4,3) 0-3-4-1-6-2-7-5-0 (515)

(3,1) 0-4-1-3-6-2-7-5-0 (515)
(1,6) 0-4-3-6-1-2-7-5-0(565)
(6,2) 0-4-3-1-2-6-7-5-0 (525)
(2,7) 0-4-3-1-6-7-2-5-0 (500) Best
(7,5) 0-4-3-1-6-2-5-7-0 (520)

Tabu List: (7,2)

Best Score: 465

[Link] 0-4-3-1-6-7-2-5-0 (500)

(4,3) 0-3-4-1-6-7-2-5-0 (550)

(3,1) 0-4-1-3-6-7-2-5-0 (590)
(1,6) 0-4-3-6-1-7-2-5-0 (555)
(6,7) 0-4-3-1-7-6-2-5-0 (525) Best
(7,2) 0-4-3-1-6-2-7-5-0 (465) Tabu
(2,5) 0-4-3-1-6-7-5-2-0 (560)

Tabu List: (7,2), (6,7)

Best Score: 465

3. Iteration 0-4-3-1-7-6-2-5-0 (525)

(4,3) 0-3-4-1-7-6-2-5-0 (575)
(3,1) 0-4-1-3-7-6-2-5-0 (525)
(1,7) 0-4-3-7-1-6-2-5-0 (530)
(7,6) 0-4-3-1-6-7-2-5-0 (500) Tabu
(6,2) 0-4-3-1-7-2-6-5-0 (465) Best
(2,5) 0-4-3-1-7-6-5-2-0 (560)
Tabu List: (7,2), (7,6), (6,2)
Best Score: 465

4. Iteration 0-4-3-1-7-2-6-5-0(465)

(4,3) 0-3-4-1-7-2-6-5-0 (515)

(3,1) 0-4-1-3-7-2-6-5-0 (465) Best
(1,7) 0-4-3-7-1-2-6-5-0 (530)
(7,2) 0-4-3-1-2-7-6-5-0 (500)
(2,6) 0-4-3-1-7-6-2-5-0 (525) Tabu
(6,5) 0-4-3-1-7-2-5-6-0 (535)

Tabu List: (7,2), (7,6), (6,2), (3,1)

Best Score: 465

5. Iteration 0-4-1-3-7-2-6-5-0 (465)

(4,1) 0-1-4-3-7-2-6-5-0 (475) Best

(1,3) 0-4-3-1-7-2-6-5-0 (465) Tabu
(3,7) 0-4-1-7-3-2-6-5-0 (575)
(7,2) 0-4-1-3-2-7-6-5-0 (545)
(2,6) 0-4-1-3-7-6-2-5-0 (525) Tabu
(6,5) 0-4-1-3-7-2-5-6-0 (535)

 Best Solution 465, 0-4-3-1-6-2-7-5-0

Tabu List: (7,2), (7,6), (6,2), (3,1), (4,1)

Best Score: 465

Example 6, Lecture VI – Page

Starting solution:
0-1-0, 0-2-0, 0-3-0, 0-4-0, 0-5-0, 0-6-0, 0-7-0, total distance 730
Distance Matrix:
0 1 2 3 4 5 6 7
0 - 30 50 50 20 100 55 60
1 30 - 75 30 50 70 45 90
2 50 75 0 100 70 145 30 50
3 50 30 100 - 30 90 75 70
4 20 50 70 30 - 120 75 40
5 100 70 145 90 120 - 115 160
6 55 45 30 75 75 115 - 80
7 60 90 50 70 40 160 80 -

Calculate savings: Sij=c0i+c0j−cij

1 2 3 4 5 6 7
1 - 5 50 0 60 40 0
2 5 - 0 0 5 75 60
3 50 0 - 40 60 30 40
4 0 0 40 - 0 0 40
5 60 5 60 0 - 40 0
6 40 75 30 0 40 - 35
7 0 60 40 40 0 35 -

Route construction and merging:

1. (2, 6): Saving = 75
o Merge customers 2 and 6 into the same route.
o New route: 0→2→6→0 with total demand 4+2=6

New solution 0-1-0, 0-2-6-0, 0-3-0, 0-4-0, 0-5-0, 0-7-0, total distance 655

1 2 3 4 5 6 7
1 - 5 50 0 60 40 0
2 5 - 0 0 5 75 60
3 50 0 - 40 60 30 40
4 0 0 40 - 0 0 40
5 60 5 60 0 - 40 0
6 40 75 30 0 40 - 35
7 0 60 40 40 0 35 -

2. (1, 5): Saving = 60

o Merge customers 1 and 5 into the same route.
o New route: 0→1→5→0 with total demand 3+1=4

New solution 0-1-5-0, 0-2-6-0, 0-3-0, 0-4-0, 0-7-0, total distance 595

1 2 3 4 5 6 7
1 - 5 50 0 60 40 0
2 5 - 0 0 5 75 60
3 50 0 - 40 60 30 40
4 0 0 40 - 0 0 40
5 60 5 60 0 - 40 0
6 40 75 30 0 40 - 35
7 0 60 40 40 0 35 -
3. (5, 3): Saving = 60
o Merge routes 0-1-5-0 and 0-3-0 into route 0-1-5-3-0
o total demand 4+3=7

New solution 0-1-5-3-0, 0-2-6-0, 0-4-0, 0-7-0, total distance 535

1 2 3 4 5 6 7
1 - 5 50 0 60 40 0
2 5 - 0 0 5 75 60
3 50 0 - 40 60 30 40
4 0 0 40 - 0 0 40
5 60 5 60 0 - 40 0
6 40 75 30 0 40 - 35
7 0 60 40 40 0 35 -

4. (7, 2): Saving = 60

Merge routes 0-7-0 and 0-2-6-0 into route 0-7-2-6-0
o total demand 3+4+2=9

New solution 0-1-5-3-0, 0-7-2-6-0, 0-4-0 total distance 475

1 2 3 4 5 6 7
1 - 5 50 0 60 40 0
2 5 - 0 0 5 75 60
3 50 0 - 40 60 30 40
4 0 0 40 - 0 0 40
5 60 5 60 0 - 40 0
6 40 75 30 0 40 - 35
7 0 60 40 40 0 35 -

5. (3, 1): Saving = 50 – infeasible/cycle

1 2 3 4 5 6 7
1 - 5 50 0 60 40 0
2 5 - 0 0 5 75 60
3 50 0 - 40 60 30 40
4 0 0 40 - 0 0 40
5 60 5 60 0 - 40 0
6 40 75 30 0 40 - 35
7 0 60 40 40 0 35 -

6. (3, 4): Saving = 40

o Merge routes 0-1-5-3-0 and 0-4-0 into 0-1-5-3-4-0

o total demand 7+1=8

New solution 0-1-5-3-4-0, 0-7-2-6-0 total distance 435.

 1 2 3 4 5 6 7
1 - 5 50 0 60 40 0
2 5 - 0 0 5 75 60
3 50 0 - 40 60 30 40
4 0 0 40 - 0 0 40
5 60 5 60 0 - 40 0
6 40 75 30 0 40 - 35
7 0 60 40 40 0 35 -

7. (4, 7): Saving = 40 – infeasible due to capacity

8. (6, 1): Saving = 40 – infeasible due to capacity
9. (6, 7): Saving = 35 – infeasible/cycle

Final solution 0-1-5-3-4-0, 0-7-2-6-0 total distance 435.