Principles of Mathematics in Operations Research

274 Solutions

^ i s-!

-—§*•#

, j»M 1

\

* •*-

r

te

"j

^

L

f

M_.

'

X

Delete {I, J) & (G,L): gain=12~8 Improved Tour: Length is 44

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

b) Use I2 norm:

h A B C D E F G H I J K L

ABCDEFGHI J K L

0 3 \/2 \/26 \/40 VT8 \/26 \/4l A/37 \/53 8 10

3 0^ V5 \/i3 3 y/41 ^ ViO V50 V73 V73

V2 VE 0 4 \/26 \/8 V^O 5 5 \/37 \/50 \/74

\/26 \/5 4 0 \/2 \/8 \/40 vT7 \/4T V45 \/74 \/50

\/40vT3\/26 \/2 0 Vl0 \/58 \/l3 \/4l Vil \/72 6

\/l8 3 v/Sv/Sv/lOOv/^Ov/syHv/rrv/slv/Si

V^6 \/4l V^O \/40 \/58 v^7 ^ 0 5 \/5 \/l3 v^ v/58

\/41\/26 5 VTf Vl3 VE 5 0 vTO >/8 5 \/l3

\/37\/40 5 x/ilv'ilx/is VE Vw 0 V2 VE v^

>/53 v^O \/37 V^45 v^41 V^7 Vl3 v^ "v^ 0 VE Vl7

8 ^73 \/50 V74 \/72 \/34 VTO 5 \/E VE 0 6

10 V73V74VE0 6 v/34 v^ \/T3 %/29 VT7 6 \/0

Nearest neighbor (in I2 metric):

<-+I>-+ G{G or K)^K^L^-A

Initial tour length is 38.3399. See Figure S.20.