Optimization is often encountered in engineering problems. More often than not, a perfect solution is impossible or too expensive to find and implement. Therefore, we resort to sub-optimal, yet useful, solutions. This assignment tackles a classical problem in optimization called the Travelling Salesman problem, where this situation arises.

The Travelling Salesman problem involves a salesman who has to visit a number of cities in a single closed tour. The salesman always starts and ends the tour in his home city and visits each other city on the tour exactly once. The problem is to minimise the overall amount of distance travelled. This problem arises in many other situations familiar to engineers. For instance, the design of electrical wiring in a building or in a car, the optimisation of the movement of a read-write head on a disk drive, the planning of airliners movements, the design of bus routes or garbage collection truck routes.

You are required to design and implement a GUI that demonstrates a possible solution to the problem. The optimisation procedure is described in this assignment sheet.

Your task:

Basic Solution :

Write a MATLAB GUI driven program to demonstrate the solution to the TSP. The program must show a graphical display of the 2-dimensional map, with the cities suitably displayed on the map.

Advanced Solution

Find an alternative (preferably better) solution to the problem. The TSP problem is a classical problem and many solutions exist. You must adequately acknowledge the source of your solution and the nature of the material that you obtained (for instance, whether you found a description of the algorithm, source code for MATLAB, and so on).   In addition to incorporating the advanced solution in your program, the basic solution and the alternative solution must be evaluated and compared. This is to be done by running each at least 30 times on the same set of randomly generated set of 50 cities, and comparing the average difference in tour lengths and the standard deviation.

Graphic User Interface Requirements:

1.      The Basic Solution program is driven by a GUI with the following elements:

• • Pull-down menu specifying the numberNof cities (from the set {10,20,30,...,100})
  • Push-button to generate a random set ofNcities on the map
  • Push-button to optimise the tour and produce connected plot of the tour
  • Axes (plot area) to display the map of the journey - cities should be plotted as circles and the tour plotted as a connecting line through the cities.
  • The tour plot should be updated as the tour is optimised; use a suitable pause between plot updates so that the user can view the optimisation process.
  • The tour length should appear in the plot title and get updated as the optimisation progresses.
  • A Push-button to exit the program.

2.      The Advanced Solution has the following extension to the GUI :

• • Additional Push-button to optimise with your turbo charged algorithm. The tour produced by this push button should overlay the existing map and use a different line type (e.g. dash-dot) and different colour, so that it is possible to see the basic tour and the advanced tour on the same plot.
  • There is no requirement to update the tour as optimisation progresses (you may do this nevertheless). The tour length should be updated when advanced optimisation is complete.

Other requirements:

1.      No function can be more than 12 lines long (not counting comment lines)

2.      Use sub-functions to break down the solution into a set of solutions to smaller problems

3.      Only one command per line is allowed

4.      Document your functions clearly with comments

5.      Use meaningful variable and function names

6.      Structure your program so that functions perform small and well-defined tasks.

7.      The user should be able to try and optimise the same set of cities multiple times. The program must therefore seed the random number generator from the system clock each time it is run. Use MATLAB help function to find out more about random numbers and seeding the random number generator.

Useful Subfunctions:

d = distance(a,b) - a function that computes the number of kilometres d between two cities a and b [the distance is computed as sqrt ((x1-x2) 2 + (y1-y2) 2)].

[ tour, tourLength ] = tsp(position) - a function that computes the tour and its length in km.

Explanation of the basic tour optimisation algorithm

The optimisation problem we are considering is known as the Travelling Salesman Problem (TSP). It is NP-Complete which to us simply means it's not feasible to solve the problem exactly for large numbers of cities. Instead we use a heuristic approach to create a reasonable, though not necessarily optimal solution:

The tour starts with city 1 - the home city. We then add one city at a time to the tour. The tour is always closed - i.e. it starts and ends at the home city. Suppose that we already have N cities on the tour. When we insert the N+1 city it can be inserted at any one of N positions on the closed tour (the home city is always in position 1). We find the insertion point that leads to the shortest tour and insert the city there. We continue until all cities have been added.

For example, if the tour we have is [1 3 2 4] and we are about to insert city 5, then the possible tours are [1 5 3 2 4],   [1 3 5 2 4],   [1 3 2 5 4],   and   [1 3 2 4 5].   One of these will usually be shorter than the other tours, and we will adopt it. We then proceed to insert city 6 using the same approach.   Note that this does not imply that we get a globally minimal tour length, but it is usually quite reasonable approach.

The algorithm can always begin with 3 cities on the tour: the Post Office and two other cities (any two, picked at random)

Having inserted all the cities into the tour we proceed to optimise it. To do so, we attempt to move each of the cities to a better position on the tour. This is done by deleting the city (disconnecting it from its two neighbours, and closing the tour by connecting the neighbours) and then re-inserting the city into the tour in the best position (similar to the original insertion procedure). The process terminates when we cannot find any city that can be moved elsewhere by deletion and re-insertion thereby producing a shorter tour.

Your tsp function can therefore be designed around a loop that inserts one city at a time, in the best possible insertion point. After every insertion it can update the plot of the tour so far, and pause for a brief moment if necessary (for the user viewing the process). When insertion is complete the process continues by deleting each city in turn and re-inserting it. When all cities are re-inserted in the same position from which they were deleted the algorithm terminates (since there is no longer any shortening of the tour length by this process)