SECTION 17.3 TRAVELING SALESMAN PROBLEM

Given n cities, and a matrix c(i,j) containing the costs of travelling from city i to city j, find a closed path that visits every city exactly once and minimizes total cost.

An approximate solution to this problem is obtained using a genetic algorithm. See R. L. Haupt and S. E. Haupt, Practical Genetic Algorithms, John Wiley & Sons, 1998.

Genetic algorithms start by generating a set of random feasible solutions. The best of these solutions are permitted to "mate" and produce offspring and mutations are occasionally introduced. The worst solutions in every generation are discarded and the process continues until either an iteration limit is reached or convergence takes place.

The MAIN program should include

        COMMON/BPRINT/IPT,NFILE,NDIG,NPUNCH,JPT,MFILE
        CALL DFLT

The call to TRAVSAL is as follows:

       CALL TRAVSAL(NP,NIPOP,NPOP,NGOOD,CC,PP,C,CPP,MATES,X,Y,POP,
     * FVAL,ITERC,IER,IVAL)

where

   NP    = the number of cities
   NIPOP = the size of the initial population (a power of 2; 64
           is often useful)
   NPOP  = the size of the continuing population, after the worst
           of the NIPOP solutions are discarded (a power of 2; 32
           is often useful)
   NGOOD = the number of parents who are allowed to mate (a power
           of 2; 16 is often useful); each pair of parents
           generates two offspring and thus the population
           temporarily increases to NPOP+NGOOD; but the NGOOD worst
           are discarded
   CC, PP, CPP = DOUBLE PRECISION work arrays that should be
           dimensioned CC(NGOOD), PP(NGOOD), CPP(NGOOD)
   C     = DOUBLE PRECISION array dimensioned C(NP,NP), should
           contain the costs of going from city i to city j. Set
           the diagonal elements C(I,I) = 0. It is required that
           C(I,J) = C(J,I).
   MATES = a work array dimensioned MATES(2,NGOOD/2)
   X,Y   = DOUBLE PRECISION work arrays dimensioned X(NP),Y(NP)
   POP   = INTEGER array dimensioned POP(NIPOP,NP); it contains the
           city identifiers of the tours in the subsequent
           generations. After convergence, POP(1,1),...,POP(1,NP)
           contains the solution; i.e., the optimal tour starts in
           the city with identifier contained in POP(1,1),
           continues to the city the identifier of which is
           contained in POP(1,2), etc.; after the city contained
           in POP(1,NP) is reached, the tour returns to POP(1,1).
   FVAL  = DOUBLE PRECISION array dimensioned FVAL(NIPOP); it will
           contain the costs of the tours (after convergence,
           FVAL(1) is the optimal cost)
   ITERC = upon returning from TRAVSAL, it contains the number of
           generations
   IER   = error return; -1 iteration limit exceeded, -3 input
           error
   IVAL  = upon returning from TRAVSAL, it contains the number of
           function evaluations

Other parameters can also be set, but will be initialized by CALL DFLT (See Section 1.1). The following COMMON blocks are relevant:

        COMMON/BENALG5/JNITGEN,JPAIR,JTERL,JTEST

where

   JNITGEN = 2 members of the initial population are generated
               at random (default=2)
           = 4 The user read in the members of the initial
               population into the array POP (NIPOP sets of values)
   JPAIR   = 1 parents are selected for pairing as follows: the
               lowest-cost parent mates with the second-lowest
               cost parent, the third-lowest with the
               fourth-lowest, and so on
           = 2 pairing by rank-weighting (See Haupt and Haupt,
               p. 39)
           = 3 pairing by cost weighting (See Haupt and Haupt,
               pp. 39-40) (default=3)
           = 4 random pairing
   JTERL   =   iteration limit (default=99)
   JTEST   = 1 if testing for convergence should be based on the
               optimal value achieved in a population (default=1)
           = 2 if testing should be based on the mean value of the
               population (this latter is likely to give a better
               optimum, but may take a great deal more computation)

       COMMON/BENALG6/YMUTE,BCC

where

    YMUTE   = DOUBLE PRECISION constant defining the mutation rate;
              the number of mutations in a population will be
              (NPOP+NGOOD)*NP*YMUTE. The required number of
              individuals in the population will be chosen at random
              (except the best element in the population will not
              be subject to mutation) and then two randomly
              chosen city pairs will be exchanged (default=0.06)
    BCC     = DOUBLE PRECISION required relative accuracy (default=
              0.001)
  

Return to the Beginning