Engineers are designing a fixed route to be followed by automatic guided vehicles in a large manufacturing plant. The following table shows the east–west and north–south coordinates of the 6 stations to be served by vehicles moving continuously around the same route.

1 2 3 4 5 6 E/W 20 40 180 130 160 50 N/S 90 70 20 40 10 80 Since traffic must move along east–west or north–

south aisles, designers seek a route of shortest total rectilinear length (see Section 4.6).

(a) Explain why this problem can be viewed as a traveling salesman problem.

(b) Explain why distances in this problem are symmetric, and compute a matrix of rectilinear distances between all pairs of points.

(c) Formulate this problem (incompletely)

as an ILP with main constraints requiring only that every point be touched by 2 links of the route.

(d) Use class optimization software to show that your ILP of part

(c) produces a subtour 1–2–6–1.

(e) Formulate a subtour elimination constraint that precludes the solution of part (d).

(f) Use class optimization software to show that an optimal route results when your subtour elimination constraint is added to the formulation of part (c).

(g) Formulate this problem as a quadratic assignment INLP.