Principles of Mathematics in Operations Research

Solutions 277

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

GAIN

(AC)

(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)

-4 -8 -4 -4 -8 -10

-4 -3 -3 -7 -9

0 -3 -7 -9

-2 -6 -9

-2 -4

-4

-7

-6

-8

-9

-4

-6

-2

-8

-7

-7

-8

-6

-6

-2

-1

-8

-7 0

-7 -3

-6 -4

-2 2

2 0

0 0

0 -1

-1 0

-4

Delete (E,F) & (L,A): gain=2 Improved Tour: Length is 31

Fig. S.23. Nearest neighbor (in /oo metric): improvement

d)

Case 1: we need to complete the tour for the consecutive PCB's:

Current situation (/i norm): Tour duration is 44 time units.
Proposition 1 (l 2 norm): Tour duration is 35.42026 time units.
Proposition 2 (/<*, norm): Tour duration is 31 time units.

Proposition 1 is economically feasible if (44 - 35.42026)./VCo > C. Simi-
larly, proposition 2 is economically feasible if (44 - 31)NC 0 > C2.

Case 2: we may delete the most costly connection:

For the odd numbered PCBs among 1,..., N;