Circuit boards are fitted with holes to allow mounting different electronic comp

Question

Circuit boards are fitted with holes to allow mounting different electronic components The holes are drilled with a movable drill. The following table provides the distances (in centimeters) between 6 holes of a specific circuit board. The objective is to determine the optimum sequence for drilling all the holes by finding a sequence that minimizes the total distance traveled by the moveable drill during operation. Note: the drill must start at hole 1 and then return to hole 1 for the start of the next circuit board (a) Describe a way (method) to determine the optimal sequence. (b) Describe a way (method) to find a quick solution and identify a sequence using your chosen methodology. Is your sequence guaranteed to be optimal? To From 3.2 5.2 6.2 0.9 0.5 3.4 2.6 4.6 3.5 2.9 4.6 3.8 3.4 4.6 2.9 5.2 0.5 2.6 3.5 4.6 6.2 4 3.8 0.9 3.2 0

Explanation / Answer

(a)

This is a traveling salesman problem (TSP). There are primarily two methods for finding the optimal solution.

The formulation of linear programming is as follows:

Let Xij be the sets of binary integers such that Xij=1 when movement is from 'i' to 'j' immediately and Xij=0 otherwise.

Minimize Z = ijCij.Xij
Subject to,
j Xij = 1 for all 'i'
iXij = 1 for all 'j'

Xij = 0 when i=j
Xij + Xji <= 1 when i j (Subroute elimination constraints)

Xij = {0,1}

(b)

For a quick solution, we often use several heuristics including the Nearest Neighbor algorithm, Clark & Wright algorithm, Double spanning tree algorithm, and so on. We describe the Nearest Neighbor (NN) heuristic as it is the simplest of all.

Steps:

So, the sequence in this method is 1-3-2-5-6-4-1. This cannot be guarnteed as optimal. In fact, the optimal solution will be 1-2-5-6-4-3-1 (if we implement the part (a) in some computer program).

Travel distance under optimality = 10.9
Travel distance using NN heuristic = 12.2

Visited Now at Unvisited Nearest neighbor 1,2,3,4,5,6 1 1 2,3,4,5,6 3 1,3 3 2,4,5,6 2 1,3,2 2 4,5,6 5 1,3,2,5 5 4,6 6 1,2,2,5,6 6 4 4

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.