Principles of Mathematics in Operations Research

Solutions 275

Fig. S.20. Nearest neighbor (in £ 2 metric): initial solution

The gain values are tabulated below. See Figure S.21 for the improvement.

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)

-3.35 -7.37

-3.96

-4.58 -5.59 -8.24

-2.70 -3.46 -7.01

-1.04 -2.65 -6.74

-2.78 -6.28

-1.74

(I, J)

-9.45

-8.76

-9.82

-10.28

-5.43

-3.64

(J,K) (K,G)(G,L)(L,A)

-6.90 -7.59 -9.19

-6.93 -7.62 -7.38 0.63

-9.06 -9.61 -7.38 -1.41

-10.37 -11.12 -7.19 -1.98

-5.48 -7.12 -5.15 2.92

-4.13 -4.07 -1.20 0.00

-1.70 -1.25 -0.29 1.94

-1.27 -0.21 1.21

-1.62 1.75

-2.45

J. jE

Delete (E,F) k (L,A): gain=2.9196 Improved Tour: Length is 35.42026

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