Further Heuristic Methods In Tsp Notes

This is a short sample from our Operational Research Techniques Notes collection which contains 52 pages of notes in total. If you find this useful you might like to consider purchasing our Operational Research Techniques Notes.

Pages In Full Document 3
Category: Operational Research Notes
Original Document File Type: PDF
Price: Part of a package Operational Research Techniques Notes containing 15 other documents which retails for £24.99.

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 Reading Key Points
• The "One-Step Greedy" Method • One step greedy method
• The "Two-Steps-Ahead" Method
• Two steps ahead method
• The "Penalty" Method
• Penalty method
The "One-Step Greedy" Method • Method of complete enumeration
• Again, every iteration contributes one leg towards the N+1 legs in the full tour
• However, the generated partial tours may be disjointed Definitions
• Because each iteration looks for the best potential leg regardless of whether it adds • Method of Complete Enumeration (MCE) = Trying every
on to the current partial tour possible tour to find the optimal one
• "Greedy" because you want to get the most out of every iteration
• Penalty = The difference between the two best links from
• The total sum of the decisions may still not add to an optimal tour
a given point
• 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

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

Buy the full version of these notes and essays alongside much more in our Operational Research Techniques Notes.