Problem:
Minimizing travel
A quarry consists of 8 quarry pits along a 4000 yard north-south section of land. Each pit is 500 yards away from the other. Rock must be removed from some quarry pits and relocated to others quarry pits as listed below.
Quarry 1: 0 to 500 yards - 7,000 tons of rock are needed
Quarry 2: 500 to 1000 yards - 3,000 tons of rock are needed
Quarry 3: 1000 to 1500 yards - 10,000 tons of rock needs to be removed
Quarry 4: 1500 to 2000 yards - 12,000 tons of rock is needed
Quarry 5: 2000 to 2500 yards - 9,000 tons of rock is needed
Quarry 6: 2500 to 3000 yards - 6,000 tons of rock needs to be removed
Quarry 7: 3000 to 3500 yards - 4,000 tons to rock need to be removed
Quarry 8: 3500 to 4000 yards - 5,000 tons of rock needs to be removed
If more rock is needed, an additional quarry deposit #9 is located 500 yards directly west of quarry #6 and can only be reached by traveling on a path that runs directly east/west.
Rock from quarry #9 is not suitable for rock needed in quarry #5.
Minimize travel needed accomplish all the rock removals and replacements