Introduction Optimization is often encountered in engineering problems. More oft

Question

Introduction

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. For a higher mark in this assignment you need to research, find, and implement a better solution to the problem.

Your task:

Basic Solution (for a maximum of 80/100 Marks):

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. You can observe an example of this by running the MATLAB demo program travel. Run this demo and you will see one possible approach. We will use a different approach and you may use your imaginations in designing your solution. It need not necessarily be similar to the demo.

Advanced Solution (for a maximum of 100/100 Marks)

Find an alternative (preferably better) solution to the problem by studying the problem in text books in the library or on the internet. Do not use the MATLAB demo!! This is not allowed. 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.

You must fully document the alternative solution in a Word document, together with a copy of the source material for your solution (if it is brief) or an exact reference.

Graphic User Interface Requirements:

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

Pull-down menu specifying the number N of cities (from the set {10,20,30,

Explanation / Answer

here is the link for the basic solution to TSP :

http://www.maths.uq.edu.au/CEToolBox/node8.html

here is the link to Advanced Solution to Traveling Salesman Problem (TSP) using Simulated Annealing :

http://www.mathworks.in/matlabcentral/fileexchange/9612-traveling-salesman-problem--tsp--using-simulated-annealing

just download the submission and run it using matlab

Please Rate Me

Thanks

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.