! TSP = Travelling Salesman Problem
! The idea is to visit a set of N cities once and once only
! and return to the starting city.
!
! This program generates all possible combinations of tours
! with no duplicates. Then it finds the cost of doing the tour
! in either direction in case the cost matrix is not symmetric.
!
! The algorithm uses a N x N matrix (actually half of it) to generate
! and store cities not visited so far. This is equivalent to generating
! the complete tree of tours and then traversing the tree in order.
!
! Programmed in FORTRAN 90 (ELF90 from Lahey - check www.lahey.com)
! Copyright Gerald Ratzer, February 1999
!
! Approximate timing on 366MHz Pentium II
! 11 city tour - 20 seconds - 3,628,800 tours
! 12 city tour - 250 seconds - 39,916,800 tours
! 13 city tour - 53 minutes - 479,001,600 tours
! 14 city tour - 12 hours - 6.22 billion tours
!
! 20 city tour - over 25,000 years (estimated of course!)
program tspn
implicit none
integer :: i,j,k,m,n,ntours
integer :: cost(20,20),city(20,20)
integer :: visit(21),tour(21),best(21)
integer :: cost1,cost2,mincost
real:: notours,nobest
!
write(*,*) 'This is Program >> TSPN - Travelling Salesman'
write(*,*) 'General Program for TSP tours of size N'
! READ IN cost matrix size
read (*,*)n
write(*,*)'TSP tours with n=',n
if(n < 3 .or. n > 20) then
write(*,*)'Invalid value of n - stopping - Bye now'
stop
end if
!
! READ IN cost matrix and zero city matrix
L1: DO i=1,n
READ (*,*) (cost(i,j),j=1,n)
do j=1,n
city(i,j)=0
end do
END DO L1
!
! PRINT cost MATRIX
write(*, 100)
!
L2: DO i=1,n
write(*, 101) (cost(I,j),j=1,n)
END DO L2
101 FORMAT (20i4)
100 FORMAT(/' Input Cost MATRIX '/)
ntours=0 ! Counter from 1 to 50,000
notours=0 ! Counter for greater than 2 billion
mincost=1E8 ! Some big number
!
! Initialization of city data structure
! Generate first row of city matrix
!
L3: do i=1,n-1
city(1,i)=i+1 ! As in 2 3 4 5 . . n in Row 1
end do L3
!
! Main Calculation loop starts here
!
L4: do while (city(1,1) /= 0)
! Generate - expands the matrix with cities not visited so far
!
L5: do k=2,n-1
if(city(k,1) == 0) then
L6: do i=1,n-1 ! Generate all cities to visit
visit(i)=i+1 ! visit is 2 3 4 5 .. n
end do L6
!
L61: do i=1,n-1 ! Run down Column 1
if(city(i,1) /= 0 ) visit(city(i,1)-1)=0
end do L61 ! Build up list of places visited
! What's left - cities to be visited
m=0
L7: do i=1,n-1
if(visit(i) /= 0) then
m=m+1
city(k,m)=visit(i)
end if
end do L7
m=m+1
city(k,m)=0 ! Mark end of this row with a 0
end if ! We have generated 1 new row
end do L5 ! Repeat for rows below
!
! Extract the tour from column 1 of city matrix
!
tour(1)=1 ! Start from home
L8: do i=1,n-1
tour(i+1)=city(i,1) ! Straight down column 1
end do L8
tour(n+1)=1 ! Return home
!
cost1=0 ! cost going
cost2=0 ! cost coming back - in case cost matrix is not
! symmetric
L9: do i=1,n
j=tour(i) ! i and i+1 point to adjacent pairs
k=tour(i+1) ! in the tour array
cost1=cost1+cost(j,k) ! j is a start city of 1 leg
cost2=cost2+cost(k,j) ! k is the next city
end do L9
ntours=ntours+1 ! Total number of tours so far
if (cost1 < mincost) then
mincost=cost1 ! Find minimum cost so far
nobest=notours+ntours
do i=1,n+1 ! Remember the best tour
best(i)=tour(i)
end do
end if
if (cost2 < mincost) then
mincost=cost2
nobest=notours+ntours
do i=1,n+1 ! Remember the best tour
best(i)=tour(i)
end do
end if
if(mod(ntours,50000) == 0) then
notours=notours+50000.
ntours=0
write(*,99)notours,(tour(j),j=1,n+1),cost1,cost2,mincost
99 format(' Tour# ',e11.3, 20i3)
end if
!
! Compress city matrix starting from the foot and move up
!
city(n-1,1)=0 ! Zero out the last city visited
m=n-1
L27: do while (m > 1)
if(city(m,1) == 0) then
! Compress the (m-1)th row - the one above.
i=1
m=m-1 ! Shift previous row 1 column left
L28: do while(city(m,i) /= 0)
city(m,i) = city(m,i+1)
i=i+1
end do L28
end if
if(city(m,1) /= 0) exit
end do L27
! Repeat the main loop over again
end do L4
write(*,*)'Total number of tours = ',notours+ntours, &
& ' and best cost is =',mincost
Write(*,*)'The (first) best tour is number',nobest,' and is -'
write(*,127)(best(i),i=1,n+1)
127 Format(20i4)
stop
end program tspn