Consider a simplified Vehicle Routing Problem (VRP) over the customer sites in the following plot (refer to Section 11.5).

Two 5-customer routes are to be designed, both originating and returning to terminal site x1 = x2 = 0. All point-to-point distances are assumed Euclidean, and the goal is to minimize the total travel length of the two routes.

(a) Parallel the constructive solution of routes in the KI Trucking application of Section 15.1 to construct two approximately optimal routes. Begin with seed routes to sites 6 and 10. Then iteratively insert all other points in order of their distance from centers of gravity computed as the average coordinates of sites already inserted in each of the two emerging routes.

(b) Comment on the quality of the two ultimate routes and whether similar constructive techniques could be used in more realistic (VRP) applications.

Transcribed Image Text:

6) (-2,4) x2 2 (1,4) 1 (0.3) 7)(-2,2) 8)(-3/2,-1) T 3(1.1) (45,12) (4,0) 5 xX1 (10) (4.-1) 9) (2.-3/2)