#980 - Further Heuristic Methods In Tsp - Operational Research Techniques

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