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
Muhammad Aria
Figure 3. Distribution City from Ulysses 16