Operational Research Notes > Lse Operational Research Notes > Operational Research Techniques Notes

Further Heuristic Methods In Tsp Notes

This is a sample of our (approximately) 3 page long Further Heuristic Methods In Tsp notes, which we sell as part of the Operational Research Techniques Notes collection, a 1st Class package written at LSE in 2011 that contains (approximately) 104 pages of notes across 17 different documents.

Learn more about our Operational Research Techniques Notes

Further Heuristic Methods In Tsp Revision

The following is a plain text extract of the PDF sample above, taken from our Operational Research Techniques Notes. This text version has had its formatting removed so pay attention to its contents alone rather than its presentation. The version you download will have its original formatting intact and so will be much prettier to look at.

Lecture 10: Further Heuristic Methods in TSP Topics

• The "One-Step Greedy" Method

• The "Two-Steps-Ahead" Method

• The "Penalty" Method

Reading

Key Points

• One step greedy method

• Two steps ahead method

• Penalty method

The "One-Step Greedy" Method

• Again, every iteration contributes one leg towards the N+1 legs in the full tour

• However, the generated partial tours may be disjointed

• Because each iteration looks for the best potential leg regardless of whether it adds on to the current partial tour

• "Greedy" because you want to get the most out of every iteration

• The total sum of the decisions may still not add to an optimal tour

• A short term decision in an iteration may side-track you into less optimal areas Example of the "One-Step Greedy" Method

• Again, we should always check the reverse tour, which in this case is not so good at 53 minutes

• There are 4! = 24 possible tours

• Other methods we will examine seek to reduce the chances of getting stuck in a bad area such at in iteration 4

The "Two-Steps-Ahead" Method

• There is reduced chance of getting stuck in a relatively expensive dead-end

• Two versions of the method:

• Start from O and always build a continuous partial tour

• Start from the cheapest and use a greedy approach again

• Will generally find better tours but requires more effort

• The basic idea is at any iteration, find the cheapest double-link
○ i.e. from X→ Y→ Z then add to the tour only the first of these two links

• When faced with a tie:

• Look another step ahead (i.e. 3 steps ahead)

• Method of Complete Enumeration (MCE) = Trying every possible tour to find the optimal one Example of the "Two-Steps-Ahead" Method

Course Notes Page 19

• Method of complete enumeration

Definitions

• Method of Complete Enumeration (MCE) = Trying every possible tour to find the optimal one

• Penalty = The difference between the two best links from a given point

****************************End Of Sample*****************************

Buy the full version of these notes or essay plans and more in our Operational Research Techniques Notes.