Someone recently bought our

students are currently browsing our notes.

X

Further Heuristic Methods In Tsp Notes

Operational Research Notes > Operational Research Techniques Notes

This is an extract of our Further Heuristic Methods In Tsp document, which we sell as part of our Operational Research Techniques Notes collection written by the top tier of LSE students.

The following is a more accessble plain text extract of the PDF sample above, taken from our Operational Research Techniques Notes. Due to the challenges of extracting text from PDFs, it will have odd formatting:

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

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