A manufacturer of printed circuit boards uses programmable drill machine to drill five holes in each board. The x and y coordinates of each hole are given in the right table. The time (in seconds) it takes the drill machine to move from one hole to the next is equal to the Euclidean distance between the two holes. The company wants to find a drilling order of the five holes minimizing the total time that the drill machine spends moving between holes. Formulate this problem as a TSP problem, and then solve it using the branch and bound approach for TSP to find an optimal drilling order.
Hole x y
1 1 2
2 3 1
3 5 3
4 7 2