Principles of Mathematics in Operations Research

Solutions 273

Fig. S.17. Nearest neighbor (in h metric): initial solution

-6-

Delete (E, F) k, (L, A): gain=18-12 Improved Tour: Length is 48

Fig. S.18. Nearest neighbor (in h metric): first improvement

The gain values are tabulated below. See Figure S.18.

GAIN

(A,C)

(C,B)

(B,D)

(D,E)

(E,F)

(F,H)

(H,I)

(I, J)

(J,K)

(K,G)

(B,D) (D,E) (E,F) (F,H) (H,I) (I, J) (J,K) (K,G) (G,L) (L,A)

-2 -8 -6 -8

-4 -2 -4

-2 -2

-4

-8 -10 -12

-8 -8 -12

-8 -12 -14

-8 -14 -16

-2 -8 -10

-4 -6

0

-8

-14

-14

-16

-10

-6

-2

-2

-6

-4 2

-4 0

-4 0

-4 6

2 0

2 6

4 0

2 4

6

The maximum gain is 6, due to the deletion of (E, F) and (L, A). The situation
after this step is illustrated in Figure S.19.