Project Report on Travelling Salesman Probelm using Genetic algorithm

We call ourselves Homo sapiens – man the wise –because our mental capacities are so important to us. For thousands of years, we have tried to understand how we think; that is, how a mere handful of stuff can perceive, understand, predict, and manipulate a world of far larger and more complicated than itself- which the field of Artificial Intelligence. AI currently encompasses a huge variety of subfields, ranging from general- purpose areas, such as learning and perception to such specific tasks as playing chess, proving mathematical theorems, and diagnosing diseases.

Much of the earlier works in AI focused on formal tasks – game playing and theorem proving. One of the classical AI optimization problem and constraint satisfaction problem is Travelling Salesman Problem (TSP) defined in 1800s by the Irish mathematician William Rowan Hamilton and the British mathematician Thomas Kirkman, which falls under the family of NP-Complete problem. In this problem, a salesman has a list of cities, each of which he must visit exactly once. There are direct roads between each pair of cities on the list and the goal is to find the route the salesman should follow for the shortest possible round trip that both starts and finishes at any one of the cities.

Travelling salesman problem (TSP) is one of the classical but the most fundamental constraint satisfaction and optimization problem in computer science and engineering. The problem is NP-hard and so far no efficient algorithm has been developed. The TSP has many applications in the industrial world like transportation, factory set-ups, and industrial design etc.

In this problem, a salesman has a list of cities, each of which he must visit exactly once. There are direct roads between each pair of cities on the list and the goal is to find the route the salesman should follow for the shortest possible round trip that both starts and finishes at any one of the cities.

In this project, I have used one of the popular algorithm in AI known as Genetic Algorithm. This algorithm exploits the evolutionary process relating Charles Darwin’s famous theory of ‘Survival of the Fittest’ and the biological background of the reproduction (meiotic). This algorithm consists of three major phases of reproduction- selection, cross-over (aka recombination) and mutation. After several epochs, an optimum solution to the problem is obtained.

 full report is available here for download 

Use case diagram , state chart diagram of ATM machine

State chart diagram:

State chart diagram(advance):

Use case diagram:

Use Case diagram, Activity Diagram, State Chart diagram, Sequence diagram of Hospital Management System

1) Use Case diagram of Hospital management system

2) Activity Diagram

3) State Chart Diagram

4) Sequence Diagrm

Use case diagram of library management system

In library management system, the  borrower borrows the book available and the returns the book within specified time and the system needs to check the available books before uses borrows book and during returning of books, system needs to check the return data to verify the return book.

further the system also need to register the new user before the user borrows the book.


USE CASE diagram of library management"

Proposal Report on android based minor project(GPS based travel)

GPS Based travel Project is aimed at people with Smart Phones helps them to figure out the effective route from their current place to their friend’s place. It will be developed as an application for android based phone systems which utilizes the GPS service of the phone system and Google Maps to show the effective route to his destination.

The positions of the bus stops are stored in the database which is used as nodes to form a graph for finding the shortest path. The position of the bus// vehicles   is tracked in every nodes (bus stops) it passes through. The location of the application user is found out by the GPS service of the phone system. After obtaining the destination, the effective path is calculated based on the position and route of the vehicles. This effective/optimum path is then plotted in the map and provided to the user.

The proposed system is an application for android phones which helps the  user to show the optimal routes from his current place to a particular destination. The optimal route is displayed in pictorial form by using google maps and highlighting the route.

Considering the privacy and security of the application user , the user can choose whom to display the information about his location as his will. This will create a network of friends which are able to share their real time location with each other.

The application that we are developing is aimed mostly at people of Kathmandu Valley. Since this application is developed on Android platform, a smart phone with Android OS with GPS support is needed for running the application. By acquiring information about location of user through GPS and the destination through the user, the effective route between the users place and the destination is then provided to the user through the use of Google Map.

The full copy of this Report is available here for download