Loading
View RSS Feed

Angad Kumar Shukla's blog

C Code For Travelling Salesman Problem In Operational Research

Rating: 6 votes, 2.33 average.
TRAVELLING SALESMAN PROBLEM

Traveling salesman problem is a special case of Assignment problem.

A salesman is assigned ‘n’ cities to visit. He is given the distances (or cost to incur, or time to spend) between all pairs of cities and instructed to visit each of the cities once in one continuous trip and return to the starting city. His problem is to use the route that is of minimum length (or cost or time). Since a complete cycle is involved, it makes no difference which city is taken to be the starting city.
No general method of solution is available for this type of problem.
The available method of solution of such problems is enumerative in nature. If the number of cities to visit be two, then he has got only one choice [Kolkata--->Delhi --->Kolkata]. For three he has 2! different choices [Kolkata--->Delhi--->Mumbai--->Kolkata or Kolkata--->Mumbai--->Delhi--->Kolkata]. Thus starting from a given city, the salesman will have before him a total of n 1! different sequences of possible routes, if the total number ofcities be ‘n’ and each city be visited once only.


Even for small ‘n’, the total enumeration of these to find the tour of minimum distance is
not practicable.
Let Cij denote the distance (or cost or time) as the salesman goes from city i to the city j
and let
xij= 1 , if the salesman goes directly from city i to the city j
= 0, otherwise.
The problem is to minimize the total distance
z= (Summation of i)(summation of j)CijXij
Subject to the condition that Xij should be so chosen that no city is visited twice before the
completion of the tour, touching all the cities.

I am uploading a file that contains all the discussed details with examples and the proper solution with proof. Kindly Download it.
TRAVELLING SALESMAN PROBLEM.doc
How To solve Travelling Salesman problem?

The following is an algorithm and i have also provided the code for better understanding.


step 1:- prepare a cost matrix.if the cost matrix is not a square matrix then add a dummy row(column)
with zero cost element.

step 2:- subtract the minimum element in each row from all the elements of the respective rows.

step 3:- further modify the resulting matrix by subtracting the minimum elememnt of each column from
all the elements of the respective columns.thus obtain the modified matrix.

step 4:- then,draw minimum no of horizontal and vertical lines to cover all zeros in the resulting
matrix.let the minimum no of lines be N.now there are 2 possible cases.

case 1 - if N=n,where n is the order of matrix,then an optimal assignment can be made.so make
the assignment to get the required solution.

case 2 - if N<n,then proceed to step 5.

step 5:- determine the smallest uncovered element in the matrix(element not covered by N lines)subtract
this minimum element from all uncovered elements and add the same elements at the intersection
of horizontal and vertical lines.thus the second modified matrix is obtained.

step 6:- repeat step(3) and (4) until we get the case (1) of step 4.

step 7:- (to make zero assignments) examine the rows successively until a row-wise exactly single zero
is found.circle(o) this zero to make the assignment.then mark a cross(x) over all zeros if
lying in the column of the circled zero,showing that they can't be considered for future
assignment.continue in this manner until all the zeros have been examined.
repeat the same procedure for column also.

step 8:- repeat the step 6 successively until one of the following situation arises-
(i)if no unmarked zeros is left,then the process ends or
(ii) if there lies more than one of the unmarked zero in any column or row then,circle one
of the unmarked zeros arbitrarily and mark a cross in the cell of remaining zeros
in its row or column.repeat the process until no unmarked zero is left in the matrix.

step 9:- thus exactly one marked circled zero in each row and each column of the matrix is obtained.
the assignment corresponding to these marked circle zeros will give the optimal assignment.
CODE:
Code:
#include<stdio.h>
#include<conio.h>
void main()
{ int c[20][20],min,l,m,sr[20],sc[20],flag[20][20],i,j,k,rf[20],cf[20],n;
  int nrz[20],ncz[20],cn,a,noz,nrz1[20],ncz1[20];
  clrscr();
  printf("\nEnter the no of assignments:");
  scanf("%d",&n);
  printf("Enter the cost matrix:");
  for(i=0;i<n;i++)
  { for(j=0;j<n;j++)
     scanf("%d",&c[i][j]);
  }
  printf("Cost matrix:\n");
  for(i=0;i<n;i++)
  { for(j=0;j<n;j++)
     printf(" %d",c[i][j]);
    printf("\n");
  }
  for(i=0;i<n;i++)
  { min=c[i][0];
    for(j=0;j<n;j++)
    { if(min>c[i][j])
       min=c[i][j];
    }
    for(j=0;j<n;j++)
     c[i][j]=c[i][j]-min;
  }
  for(i=0;i<n;i++)
  { min=c[0][i];
    for(j=0;j<n;j++)
    { if(min>c[j][i])
       min=c[j][i];
    }
    for(j=0;j<n;j++)
     c[j][i]=c[j][i]-min;
  }
  printf("Cost matrix after row & column operation:\n");
  for(i=0;i<n;i++)
  { for(j=0;j<n;j++)
     printf(" %d",c[i][j]);
    printf("\n");
  }
  x:;
  a=0;noz=0,min=1000;
  for(i=0;i<n;i++)
  { for(j=0;j<n;j++)
     flag[i][j]=0;
  }
  for(i=0;i<n;i++)
  { cn=0;
    for(j=0;j<n;j++)
    { if(c[i][j]==0)
      { cn++;
    flag[i][j]=1;
      }
    }
    nrz[i]=cn;
    noz=noz+cn;
  }
  for(i=0;i<n;i++)
  { cn=0;
    for(j=0;j<n;j++)
    { if(c[j][i]==0)
      { cn++;
    flag[j][i]=1;
      }
    }
    ncz[i]=cn;
  }
  for(i=0;i<n;i++)
  { nrz1[i]=nrz[i];
    ncz1[i]=ncz[i];
  }
  k=0;
  while(nrz[k]!=0||ncz[k]!=0)
  {for(i=0;i<n;i++)
   { cn=0;
    for(j=0;j<n;j++)
    { if(flag[i][j]==1)
       cn++;
      nrz[i]=cn;
    }
    if(nrz[i]==1)
    { for(j=0;j<n;j++)
      { if(flag[i][j]==1)
    { flag[i][j]=2;
      for(k=0;k<n;k++)
      { if(flag[k][j]==1)
         flag[k][j]=0;
      }
    }
      }
    }
  }
  for(i=0;i<n;i++)
  { cn=0;
    for(j=0;j<n;j++)
    { if(flag[j][i]==1)
       cn++;
      ncz[i]=cn;
    }
    if(ncz[i]==1)
    { for(j=0;j<n;j++)
      { if(flag[j][i]==1)
    { flag[j][i]=2;
      for(k=0;k<n;k++)
      { if(flag[j][k]==1)
         flag[j][k]=0;
      }
    }
      }
    }
  }
  k++;
 }
  for(i=0;i<n;i++)
  { for(j=0;j<n;j++)
    { if(flag[i][j]==2)
    a++;
    }
  }
  getch();
  if(a==n)
  { printf("\nAssignments done!!\n");
    for(i=0;i<n;i++)
    { for(j=0;j<n;j++)
      { if(flag[i][j]==2)
      printf(" %d->%d ",i+1,j+1);
      }
      printf("\n");
    }
    getch();
    exit(0);    
  }
  else
  { for(i=0;i<n;i++)
    { rf[i]=0,sr[i]=0;
      cf[i]=0,sc[i]=0;
    }
    for(k=n;(k>0&&noz!=0);k--)
    { for(i=0;i<n;i++)
      { m=0;
    for(j=0;j<n;j++)
    { if((flag[i][j]==4)&&(c[i][j]==0))
       m++;
    }
        sr[i]=m;
      }
      for(i=0;i<n;i++)
      { if(nrz1[i]==k&&nrz1[i]!=sr[i])
    {  rf[i]=1;
       for(j=0;j<n;j++)
       { if(c[i][j]==0)
           flag[i][j]=4;
       }
       noz=noz-k;
    }
      }
      for(i=0;i<n;i++)
      { l=0;
    for(j=0;j<n;j++)
    { if((flag[j][i]==4)&&(c[j][i]==0))
       l++;
    }
        sc[i]=l;
      }
      for(i=0;i<n;i++)
      { if(ncz1[i]==k&&ncz1[i]!=sc[i])
    {  cf[i]=1;
       for(j=0;j<n;j++)
       { if(c[j][i]==0)
           flag[j][i]=4;
       }
       noz=noz-k;
    }
      }
      for(i=0;i<n;i++)
      { for(j=0;j<n;j++)
    { if(flag[i][j]!=3)
      { if(rf[i]==1&&cf[j]==1)
        {  flag[i][j]=3;
           if(c[i][j]==0)
         noz=noz+1;
        }
      }
    }
      }
    }
    for(i=0;i<n;i++)
    { for(j=0;j<n;j++)
      { if(rf[i]!=1&&cf[j]!=1)
    { if(min>c[i][j])
        min=c[i][j];
    }
      }
    }
    for(i=0;i<n;i++)
    { forri(j=0;j<n;j++)
      { if(rf[i]!=1&&cf[j]!=1)
      c[i][j]=c[i][j]-min;
      }
    }
    for(i=0;i<n;i++)
    { for(j=0;j<n;j++)
      { if(flag[i][j]==3)
      c[i][j]=c[i][j]+min;
      }
    }
  }
  printf("\n\nmatrix:");
  for(i=0;i<n;i++)
  { for(j=0;j<n;j++)
     printf(" %d",c[i][j]);
    printf("\n");
  }
  goto x;
}
CODE(ANOTHER WAY):
Code:
#include<conio.h>
#include<stdio.h>
#include<alloc.h>
int **matrix2d(int m)
{
    int **a,i;
    a=(int**)calloc(m,sizeof(*a));
    for(i=0;i<m;i++)
    a[i]=(int*)calloc(m,sizeof(int));
    return a;
}
int main()
{
    int i,j,**c,**g,*flag,*flag1,m,assign_row=0,*tot_zero,total=0,col_no;
    int row_no,min,max,slzero=0,*az,*k,t;
    clrscr();
    printf("enter the r&c in [] matrix\n");
    scanf("%d",&m);
    az=(int*)calloc((2*m),sizeof(int));
    flag=(int *)calloc(m,sizeof(int));
    flag1=(int*)calloc(m,sizeof(int));
    c=matrix2d(m);
    g=matrix2d(m);
    printf("enter the values of matrix\n");
    for(i=0;i<m;i++)
    {
    for(j=0;j<m;j++)
    {
    scanf("%d",&c[i][j]);
    g[i][j]=c[i][j];
    flag[j]=0;
    }
    flag1[i]=0;
    }
    for(i=0;i<m;i++)
    {
    min=c[i][0];
    for(j=0;j<m;j++)
    {
    if(min>=c[i][j])
    min=c[i][j];
    }
    for(j=0;j<m;j++)
    c[i][j]-=min;
    }
    printf("\n after row operation");
    for(i=0;i<m;i++)
    {
        for(j=0;j<m;j++)
        printf("%d\t",c[i][j]);
        printf("\n");
    }
    for(i=0;i<m;i++)
    {
        min=c[0][i];
        for(j=0;j<m;j++)
        {
        if(min>=c[j][i])
        min=c[j][i];
        }
        for(j=0;j<m;j++)
        c[j][i]-=min;
    }
        printf("\n after column operation");
    for(i=0;i<m;i++)
    {
        for(j=0;j<m;j++)
        printf("%d\t",c[i][j]);
        printf("\n");
    }
    tot_zero=(int *)calloc(2*m,sizeof(int));
    k=(int *)calloc((2*m),sizeof(int));
    x:;
    assign_row=0;
    total=0;
    for(i=0;i<m;i++)
    {
        flag1[i]=0;
        flag[i]=0;
    }
    for(i=0;i<m;i++)
    {
        tot_zero[i]=0;
        az[i]=0;
        for(j=0;j<m;j++)
        {
            if(c[i][j]==0)
            tot_zero[i]++;
            if(c[i][j]==0&&flag[j]==0)
            az[i]++;
            if(flag[j]==0&&c[i][j]==0&&az[i]==1)
            col_no=j;
        }
        k[i]=i;
        total+=tot_zero[i];
        if(az[i]==1)
        {
            printf("\nrow %d is assigned %d column",i,col_no);
            printf("\t%d",g[i][col_no]);
               assign_row++;
               flag[col_no]=1;
               flag1[i]=1;
        }
       }
       for(i=0;i<m;i++)
       {
        tot_zero[i+m]=0;
        az[i+m]=0;
        for(j=0;j<m;j++)
        {
            if(c[j][i]==0)
            tot_zero[i+m]++;
            if(c[j][i]==0&&flag1[j]==0&&flag[i]==0)
            az[i+m]++;
            if(flag1[j]==0&&c[j][i]==0&&flag[i]==0&&az[i+m]==1)
            row_no=j;
        }
        k[i+m]=i+m;
            if(az[i+m]==1)
            {
            printf("\n\n\nrow %d is assigned %d column",row_no,i);
            printf("\t%d",g[row_no][i]);
            assign_row++;
            flag[i]=1;
            flag1[row_no]=1;
            }
       }
       if(assign_row==m)
       {
        printf("all assignments done\n");
        getch();
        return 0;
       }
       for(i=0;i<(2*m);i++)
       {
        for(j=i+1;j<(2*m);j++)
        {
            if(tot_zero[j]>=tot_zero[i])
        {
            max=tot_zero[i];
            t=k[i];
            tot_zero[i]=tot_zero[j];
            k[i]=k[j];
            tot_zero[j]=max;
            k[j]=t;
        }
        }
       }
         printf("\nthe count of zeroes are\n");
       for(i=0;i<(2*m);i++)
       printf(" \n  %d   %d  ",k[i],tot_zero[i]);
       printf("\n");
       printf("the value of total is%d \n",total);
       i=0;
       while(total>slzero)
       {
        if(k[i]>=m)
        {
            flag[k[i]-m]=2;
            slzero+=tot_zero[i];
        }
        else
        {
            flag1[k[i]]=2;
            slzero+=tot_zero[i];
        }
        i++;

    }
    printf("\nthe value of slzero %d  ",slzero);
    for(i=0;i<m;i++)
    printf("  %d ",flag1[i]);
    for(i=0;i<m;i++)
    printf(" %d",  flag[i]);
       for(i=0;i<(m*m);i++)
       if(flag[i%m]!=2&&flag1[i/m]!=2)
       {
       min=c[i/m][i%m];
       break;
       }
       for(i=0;i<(m*m);i++)
    if((flag[i%m]!=2)&&(flag1[i/m]!=2)&&(min>=c[i/m][i%m]))
    min=c[i/m][i%m];
    printf("the min element is %d\n",min);
     for(i=0;i<(m*m);i++)
     {
    if((flag[i%m]!=2)&&(flag1[i/m]!=2))
    c[i/m][i%m]-=min;
    else
    if((flag[i%m]==2)&&(flag1[i/m]==2))
    c[i/m][i%m]+=min;
     }
     for(i=0;i<m;i++)
     {
     for(j=0;j<m;j++)
     printf("\t%d",c[i][j]);
     printf("\n");
     }
     getch();
     goto x;
}

Submit "C Code For Travelling Salesman Problem In Operational Research" to Digg Submit "C Code For Travelling Salesman Problem In Operational Research" to del.icio.us Submit "C Code For Travelling Salesman Problem In Operational Research" to StumbleUpon Submit "C Code For Travelling Salesman Problem In Operational Research" to Google

Updated 12-04-2011 at 05:10 PM by Harsh

Categories
C C++ , Software Solutions

Comments




Disclaimer: Users of techforum4u.com are responsible for ensuring that any material they post (article, blog posts, images or other mulitimedia content) does not violate or infringe upon the copyright, patent, trademark, or any personal or proprietary rights of any third party, and is posted with the permission of the owner of such rights.Anyone who violates these rules may have their access privileges removed without warning.