TSP project

INTRODUCTION

(TSP) Travelling salesman problem describes a travelling salesman who is visiting a number of cities and wishes to find the shortest route between them, and also must reach the city from where he started. In addition, the project also gives a superficial analysis of the use of Graph theory. This problem can also be expressed in terms of graph theory as: Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight.

SOLUTION

I have solved this problem by using Branch and bound algorithm.

File:TSP project.pdf

This represents a .pdf file of a project which is made on travelling salesman problem by Jeet Nakum.

.

APPLICATIONS

• In most pick-up problems, the TSP algorithm is widely used.
• The problem of arranging school bus routes to pick up the children in a city.
• Transportation of farming equipment from one location to another to test soil.
• The scheduling of service calls at cable firms.
• The delivery of meals to home-bound persons.
• The scheduling of stacker cranes in warehouses.
• The routing of trucks for parcel post pickup, and a host of others.
• The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips.
• Slightly modified, it appears as a sub-problem in DNA sequencing. In these applications, the concept of a city represents, for example, customers, soldering points, or DNA fragments, and the concept of distance represents travelling times or cost, or a similarity measure between DNA fragments.
• The TSP also appears in astronomy, as astronomers observing many sources will want to minimize the time spent moving the telescope between the sources.

Discrete mathematics

This article "TSP project" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:TSP project. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---