Majalah Ilmiah UNIKOM

Vol.8, No. 1

5

H a l a m a n

Travelling Salesman Problem

Travelling Salesman Problem (TSP) is one

of the most basic combinatorial optimization

problems. The idea of the traveling sales-

man problem (TSP) is to find a tour of a

given number of cities, visiting each city ex-

actly once and returning to the starting city

where the length of this tour is minimized.

The traveling salesman problem has many

different real world applications, making it a

very popular problem to solve. For example,

some instances of the vehicle routing prob-

lem can be modelled as a traveling sales-

man problem. Here the problem is to find

which customers should be served by which

vehicles and the minimum number of vehi-

cles needed to serve each customer. There

are different variations of this problem in-

cluding finding the minimum time to serve

all customers. We can solve some of these

problems as the TSP. The problem of com-

puter wiring can also be modelled as a TSP.

The schedulling of jobs on a single machine

given the time it takes for each job and the

time it takes to prepare the machine for

each job is also TSP. We try to minimize the

total time to process each job.

There is a various type of traveling sales-

man Problem. The asymmetric traveling

salesman problem is when the cost of trav-

ij

ji

solved in the same way as the standard TSP

if we apply certain edge weights that ensure

that there is a Hamiltonian cycle in the

graph. The multisalesmen problem is the

same as the standard TSP except that we

have more than one salesman. We need to

decide where to send each salesman so

that every city is visited exactly once and

each salesman returns to the original city.

Problems with 100 or fewer cities are now

routinely solved within a few minutes on a

workstation (although there are isolated

instances in this range that take much

longer) and instances in the 1,000-city

range typically take only a few hours (or