462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
Consider the general domain of points shown above. The orientation of the points is arbitrary. The important point is not the points or their placement but the property exhibited by each point and its relative position. Our basic approach for the shortest route is that we start from the shortest and keep it shortest all the while. With the help of this approach we will get a shorter tour which is at least locally optimal, i.e. optimal
w.r.t. to the starting points. After that we apply corrections or arrays of corrections to get the optimal (Universal) tour. Even if the previous result is not used in general we start from any route and with the process of constantly improving our route and discarding longer routes in the process we reach at the shortest route. The method used is basically the method of elimination of longer routes and careful selection of shorter routes.
We start with the ouster most mesh of one map and join them so the maximum numbers of destinations lie on a standard convex polygon. From theorem the shortest route lies
on the periphery for these cities. Even if it does not hold good then also we join them to all the exterior points and proceed.
Our next object is to join to these branches the points which are nearest to them than any other two points, branch or segment. For this we calculate ‘ a +b - c’ for all ‘n’ cities for all the branches of Outer mesh if ‘ a +b - c’ is minimum for any of the branches we join it to the branch. This may be termed as nearest or cheapest insertion to the outer convex shell.
485
486
We would like to define ‘ a + b - c’ rule. In the Fig.[3] if point O is added to the network to the segment A1A2 then
487
a = Adding distance on the segment of the network due to new point O and
488
489
point A1 of line segment A1A2.
490
b = Adding distance on the segment of the network due to new point O and
491
point A2 of line segment A1A2.
492
493
c = Subtracting distance on the network due to the segment A1A2.