Programming Assignment #2

Initial unconnected cities

subtour=HVN; unadded=HVN,ALB,MHT,BDL,ORH,PVD

Starting with 2 nearest cities

Find distance from each city not yet in the tour to all cities in the tour

MHT-ORH=82.27; MHT-PVD=134.28 — distance from MHT to tour = shortest = MHT-ORH=82.27

BDL-ORH=76.11; BDL-PVD=106.96 — distance from BDL to tour = shortest = BDL-ORH=76.11

HVN-ORH=139.61; HVN-PVD=132.08 — distance from HVN to tour = shortest = HVN-PVD=132.08

ALB-ORH=167.13; ALB-PVD=226.61 — distance from ALB to tour = shortest = ALB-ORH=167.13

BDL had the shortest distance to the tour; finding the place to insert it (thin red lines represent the segment to remove; medium green lines indicate the segments that replace it)

replacing ORH-PVD with ORH-BDL-PVD replaces a leg of length 70.82 with two of total length 76.11+106.96=183.06 for an increase of 112.25 — replace ORH-PVD with ORH-BDL-PVD;
increase=76.11+106.96-70.82=112.25

replacing PVD-ORH with PVD-BDL-ORH replaces a leg of length 70.82 with two of total length 106.96+76.11=183.06 for an increase of 112.25 — replace PVD-ORH with PVD-BDL-ORH;
increase=106.96+76.11-70.82=112.25

Adding BDL to tour at point that minimizes increase in distance

Find distance from each city not yet in the tour to all cities in the tour

MHT-ORH=82.27; MHT-PVD=134.28; MHT-BDL=150.72 — distance from MHT to tour = shortest = MHT-ORH=82.27

HVN-ORH=139.61; HVN-PVD=132.08; HVN-BDL=76.90 — distance from HVN to tour = shortest = HVN-BDL=76.90

ALB-ORH=167.13; ALB-PVD=226.61; ALB-BDL=128.81 — distance from ALB to tour = shortest = ALB-BDL=128.81

HVN had the shortest distance to the tour; finding the place to insert it (thin red lines represent the segment to remove; medium green lines indicate the segments that replace it)

replacing ORH-PVD with ORH-HVN-PVD replaces a leg of length 70.82 with two of total length 139.61+132.08=271.69 for an increase of 200.87 — replace ORH-PVD with ORH-HVN-PVD;
increase=139.61+132.08-70.82=200.87

replacing PVD-BDL with PVD-HVN-BDL replaces a leg of length 106.96 with two of total length 132.08+76.90=208.98 for an increase of 102.02 — replace PVD-BDL with PVD-HVN-BDL;
increase=132.08+76.90-106.96=102.02

replacing BDL-ORH with BDL-HVN-ORH replaces a leg of length 76.11 with two of total length 76.90+139.61=216.51 for an increase of 140.40 — replace BDL-ORH with BDL-HVN-ORH;
increase=76.90+139.61-76.11=140.40

Adding HVN to tour at point that minimizes increase in distance

Find distance from each city not yet in the tour to all cities in the tour

MHT-ORH=82.27; MHT-PVD=134.28; MHT-HVN=220.84; MHT-BDL=150.72 — distance from MHT to tour = shortest = MHT-ORH=82.27

ALB-ORH=167.13; ALB-PVD=226.61; ALB-HVN=181.55; ALB-BDL=128.81 — distance from ALB to tour = shortest = ALB-BDL=128.81

MHT had the shortest distance to the tour; finding the place to insert it (thin red lines represent the segment to remove; medium green lines indicate the segments that replace it)

replacing ORH-PVD with ORH-MHT-PVD replaces a leg of length 70.82 with two of total length 82.27+134.28=216.55 for an increase of 145.74 — replace ORH-PVD with ORH-MHT-PVD;
increase=82.27+134.28-70.82=145.74

replacing PVD-HVN with PVD-MHT-HVN replaces a leg of length 132.08 with two of total length 134.28+220.84=355.12 for an increase of 223.04 — replace PVD-HVN with PVD-MHT-HVN;
increase=134.28+220.84-132.08=223.04

replacing HVN-BDL with HVN-MHT-BDL replaces a leg of length 76.90 with two of total length 220.84+150.72=371.56 for an increase of 294.66 — replace HVN-BDL with HVN-MHT-BDL;
increase=220.84+150.72-76.90=294.66

replacing BDL-ORH with BDL-MHT-ORH replaces a leg of length 76.11 with two of total length 150.72+82.27=232.99 for an increase of 156.89 — replace BDL-ORH with BDL-MHT-ORH;
increase=150.72+82.27-76.11=156.89

Adding MHT to tour at point that minimizes increase in distance

Find distance from each city not yet in the tour to all cities in the tour

ALB-ORH=167.13; ALB-MHT=194.50; ALB-PVD=226.61; ALB-HVN=181.55; ALB-BDL=128.81 — distance from ALB to tour = shortest = ALB-BDL=128.81

ALB had the shortest distance to the tour; finding the place to insert it (thin red lines represent the segment to remove; medium green lines indicate the segments that replace it)

replacing ORH-MHT with ORH-ALB-MHT replaces a leg of length 82.27 with two of total length 167.13+194.50=361.63 for an increase of 279.36 — replace ORH-MHT with ORH-ALB-MHT;
increase=167.13+194.50-82.27=279.36

replacing MHT-PVD with MHT-ALB-PVD replaces a leg of length 134.28 with two of total length 194.50+226.61=421.10 for an increase of 286.82 — replace MHT-PVD with MHT-ALB-PVD;
increase=194.50+226.61-134.28=286.82

replacing PVD-HVN with PVD-ALB-HVN replaces a leg of length 132.08 with two of total length 226.61+181.55=408.16 for an increase of 276.08 — replace PVD-HVN with PVD-ALB-HVN;
increase=226.61+181.55-132.08=276.08

replacing HVN-BDL with HVN-ALB-BDL replaces a leg of length 76.90 with two of total length 181.55+128.81=310.36 for an increase of 233.46 — replace HVN-BDL with HVN-ALB-BDL;
increase=181.55+128.81-76.90=233.46

replacing BDL-ORH with BDL-ALB-ORH replaces a leg of length 76.11 with two of total length 128.81+167.13=295.94 for an increase of 219.83 — replace BDL-ORH with BDL-ALB-ORH;
increase=128.81+167.13-76.11=219.83

Adding ALB to tour at point that minimizes increase in distance

Tour produced by -insert