Travelling salesman problem

**Project definition **This project aims to develop an understanding of Evolutionary Algorithms with a view of solving The Travelling Salesman problem. An evolutionary algorithm programme will be designed to solve the travelling salesman problem for up to one hundred cities. The design of the Evolutionary Algorithm programme will be tested against traditional optimisation techniques and comparisons will be made on each algorithm. From these comparisons the fastest algorithm can be identified and used to solve the TSP in the fastest computational time. The complexity of the problem will be increased further by incorporating additional aspects of real-world problems such as minimising the travelling required during peak traffic hours or requiring that there are certain customers to be visited, say, in the afternoon or only after other customers are visited. **Project purpose and scope. **The purpose of this project is to design and implement an Evolutionary Algorithm solution to solve the TSP in C++ and thento find the best tour through any given number of cities situated randomly in a wide geographical area. The user will also add constraints such as customers to be visited first or towns to avoid because of rush hour traffic. A visual basic user interface that will ask the user for certain inputs will be used and then display the results of the Evolutionary Algorithm on to a Screen which will also show the distance travelled, cities toured and generation needed. This programme should be easy to use and have a clear interface displaying the resulting tour for visual inspection. The programme must be developed in a specified time limit and the development process must be visible test procedures and the code must be well commented. ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request. 3) **5. Traditional Method.** The NearestNeighbour solution is based on the principles of sequentially selecting the shortest remaining link such that its inclusion does not complete a circuit too fast. This solution requires the distance between each of the cities to be put into a matrix and then the distance can be used to implement this matrix. **Initial Design.** This programme will: **(1) ** Get the number of cities to be used in the problem n, from the user. The user will also add some controlled constraints like rush-hour traffic or certain customers to be seen first. The user will also control the size (number of solutions) of each population and how many generations of populations are to be created. **(2) ** Randomly generate X and Y co-ordinates for the n cities and populate an n by n matrix with the distances between each pair of cities to be used as a look-up table. **(3) ** Generate a random population. Each member of this initial population goes through heavy positive mutation ensuring as good a starting population as possible. **(4) ** The tours must be ranked in the population. **(5) ** Using the existing population create child tours. This is done by performing crossover between the worst tours in the population, the second best and second worst tours in the population and so on. This method was used to keep diversity in the populations. **(6) ** These child tours make up the next population. Then the best tours from the previous generation are added and the worst new (child) solutions are dropped from this population. **(7) ** If the correct number of generations has been run then output the best solution from the last population, otherwise return to step 4. **(8) ** The best solution is then output to screen along with a graph showing the average length of tours in each population. 6.3 **Proposed** **Implementation** This programme is to be coded in C++. Borland C++ will be used to compile this programme and will be embedded into the Visual Basic interface to display the graphical output of the TSP. **Visual basic Interface.** **Initial design of a User interface in Visual Basic.** The project must have an interface to take inputs from the user i.e. (number of cities, cities to be visited first, populations Generations,crossover percentage; etc.) and from these inputs the interface must produce a graphical output to display how many cities a travelling salesman has visited, the total distance covered and how the computational time taken. ## Platform VB,windowXp,windows98 ,