In each of the following instances, describe the data elements (cities and distances)

needed to model the problem as a TSP.

(a) Seers Service Center schedules its daily repair visits to customers. The jobs are categorized and grouped and each group assigned to a repairperson. At the end of the assignment, the repairperson reports back to the service center.

(b) A baseball fan wishes to visit eight major league parks in (1) Seattle, (2) San Francisco, (3) Los Angeles, (4) Phoenix, (5) Denver, (6) Dallas, (7) Chicago, and

(8) Tampa before returning home in Seattle. Each visit lasts about one week. The goal is to spend the least money on airfare.

(c) A tourist in New York City wants to visit 8 tourist sites using local transportation.

The tour starts and ends at a centrally located hotel. The tourist wants to spend the least money on transportation.

(d) A manager has m employees working on n projects. An employee may work on more than one project, which results in overlap of the assignments. Currently, the manager meets with each employee individually once a week. To reduce the total meeting time for all employees, the manager wants to hold group meetings involving shared projects. The objective is to reduce the traffic (number of employees) in and out of the meeting room.

(e) Meals-on-Wheels is a charity service that prepares meals in its central kitchen for delivery to people who qualify for the service. Ideally, all meals should be delivered within 20 minutes from the time they leave the kitchen. This means that the return time from the last location to the kitchen is not a factor in determining the sequence of deliveries.

(f) DNA sequencing. In genetic engineering, a collection of DNA strings, each of a specified length, is concatenated to form one universal string. The genes of individual DNA strings may overlap. The amount of overlaps between two successive strings is measurable in length units. The length of the universal string is the sum of the lengths of the individual strings less the overlaps. The goal is to concatenate the individual strings in a manner that minimizes the length of the universal string.

(g) Automatic guided vehicle. An AGV makes a round-trip, starting and ending at the mailroom, to deliver mail to departments on the factory floor. The AGV moves along horizontal and vertical aisles. The goal is to minimize the length of the round-trip.

(h) Integrated circuit board. Holes in identical circuit boards are drilled to mount electronic components. The boards are fed sequentially under a moving drill. The goal is to determine the sequence that completes drilling all the holes in a board in the shortest time possible.

(i) Protein clustering. Proteins are clustered using a numeric measure of similarity based on protein-to-protein interaction. Clustering information is used to predict unknown protein functions. The best cluster is the one that maximizes (minimizes) the sum of the measures of similarity (dissimilarity) between adjacent proteins.

(j) Celestial objects imaging. The US space agency NASA uses satellites for imaging celestial objects. The amount of fuel needed to reposition the satellites depends on the sequence in which the objects are imaged. The goal is to determine the optimal imaging sequence that minimizes fuel consumption.

(k) Mona Lisa TSP art. This intriguing application re-creates Leonardo da Vinci’s Mona Lisa using a continuous line drawing. The general idea is to approximate the original painting by using computer graphics to cluster dots on a graph. The dots are then connected sequentially by piecewise-linear segments.