This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
This chapter deals with generating of an optimized route for mTSP. From the previous chapter it is shown that the performance of two phase hybrid GA is not good, comparing to ACO. The AI-heuristics algorithms normally consume more time for convergence. If initial solutions are provided by using some heuristic algorithms then the AI-heuristics algorithms will reach the convergence quickly Ganesh and Narendran (2007, 2007a). Initial solution based three stage hybrid AI-heuristics are proposed in this chapter.
Three stage simulated annealing, tabu search and ACO algorithms are not analyzed much by researchers. A three phase hybrid AI-heuristic is proposed for LS algorithms as well as for global search algorithms. This thesis used a methodology of clustering the given cities depending upon the number of salespersons and each cluster is allotted to a salesman. k-means clustering algorithm has been used for clustering of the cities. In this way, the mTSP has been converted into TSP which is simple in computation compared to mTSP.
After clustering, an optimized route is generated for each salesman in his allotted cluster. To achieve this, this thesis first generated a parent route using an algorithm called shrink wrap algorithm and this parent string is further optimized by using two other optimizing algorithms. For this purpose, TS and SA were extensively used. These methods generated two different optimized routes. The best optimized route is chosen by comparing the total distance covered by the two optimized routes. After completion of the route optimization for each cluster, the routes are balanced by using a simple heuristic. Finally, the proposed three phase algorithm is applied for benchmark TSPs using all the four AI-heuristics and the results are compared.
4.2 PROPOSED ALGORITHM
The solution to the problem is attained using three-stage AI-heuristics. The flowchart representing the heuristic is given in Figure 4.1.The first-stage involves the conversion of a mTSP to TSPs using k-means clustering algorithm. Even though at this stage, the cities are allocated to a salesperson, it is important to generate a tour and improve it. Second-stage of the heuristic comprises of forming the initial tour for m salespersons and is generated using an algorithm called Shrink Wrap Algorithm (SWA). The third-stage is AI-heuristic approach comprising SA and TS to optimize the tour for m salespersons. Route balancing is proposed based on SA based simple heuristic. Finally, the three phase approach is used with SA, TS, GA and ACO to benchmark problems.
To demonstrate the proposed three phase heuristics a 60 cities problem with 6 salespersons is selected. The nodes are randomly selected. Finally, the algorithms are extended to large size mTSPs. The coordinates of the cities are given in figure 4.2 and in table 4.1.
Figure 4.2 Plot of Cities Salesmen have to Travel
Table 4.1 Coordinates of the Cities on the Graph
4.3.1 Transformation of mTSP to TSP: k-means Clustering
The k-means clustering algorithm explained in the previous chapter is applied to the 60 cities mTSP. k-means Cluster Analysis heuristic is proposed for generating clusters. By applying k-means clustering the given mTSP is transformed in to simple TSPs. The results of k-means clustering are shown in table 4.2 and figure 4.3. Cities 2,3,4,58,59 and 60 are assumed as cluster centers. Table shows that 12,13,12,12,6 and 10 (including depot) are the number of cities allotted to salespersons 1 to 6 respectively.
Table 4.2 Results of k - means Clustering
No. of cities
21 -23 -24 -25 -26 -27 -28 -29 - 30 -33 -35 - 36
1- 2- 3- 4- 5- 8-9-10 -11-12-33 -34-48
13- 14 -15-16-17-18-19-20-22-31-32-33
6-7-33- 45- 46- 47- 49- 50- 51- 57- 58- 59
33- 52- 54- 55- 56- 60
Figure 4.3 Graph Showing Clustered Cities
4.3.2 Shrink Wrap Algorithm
After clustering the cities, an initial route for each cluster is determined using Shrink-Wrap Algorithm Sofge et al (2002). In order to find an initial solution for the problem, an algorithm called shrink wrap algorithm is proposed. SWA is an algorithm to orient the nodes along a path. The flowchart for the algorithm is given in figure 4.4. Initially the Cartesian coordinates of all the cities of a cluster are converted in to polar coordinates (r, Î¸). Then the cities are arranged based on Î¸ values in the ascending order. If Î¸ is equal for multiple cities then they are arranged in ascending order based on r values. Finally the cities are connected in the same order. The last city in the order is connected to the first city. This gives the initial route to be traversed within each cluster Ganesh and Narendran (2007).
The SWA is used to improve the routes within clusters and finally, the clusters are unwrapped using nearest neighbor heuristic. The results of the algorithm are given in table 4.3 and the output is shown in figure 4.5. The initial sequence of cities to be visited by each salesman is given in the results. The table 4.3 and figure 4.5 show that 12.3227, 13.3864, 10.3390, 12.5588, 10.7616 and 10.1510 are the distances to be travelled by the salespersons 1 to 6 respectively.
Table 4.3 Results of Cluster Analysis by SWA
Distance to travel
33 - 35 - 28 - 36 - 29 -27- 26 - 25- 24 - 23 - 21 - 30- 33
33 - 48 - 34 - 12 - 11 - 10 - 9 - 5 - 1 - 4 - 2 - 3 - 8 - 33
33 - 31- 22 - 20 - 19 - 18 -17 - 16 - 15 - 14 - 13- 32 -33
33 - 47 - 46 - 7 - 49 - 6 - 59 - 58 - 50 - 51 -57 -45 - 33
33 - 52 - 56 - 54 - 60 - 55 - 33
33 - 44 - 43 - 53 - 42 - 40 - 41 -39 - 37- 38- 33
Figure 4.5 Sequence Obtained from SWA
4.3.3 Route Improvement Heuristics
18.104.22.168 Simulated Annealing for Solving mTSP
After creating initial solutions using SWA, the solutions are improved using SA. The SA is based on the concept called annealing in metallurgy. In annealing, after heating a metal into high temperature, it will be allowed to cool slowly. During the cooling process, the system will reach the low energy state Kirkpatrick et al (1983). In SA, the objective function value (length of the route) of the mTSP is considered as equivalent to energy in annealing concept. An initial solution obtained from SWA is continuously improved by doing small local perturbations. This can be done by simply exchanging two cities or changing the position of a city from one location to another randomly in the sequence. The flowchart for SA is given in figure 4.7. The algorithm describing the SA concept is given in figure 4.8. The various steps involved in SA to solve the given mTSP are explained in the following section.
Solution encoding and initial solution: The sequence of cities obtained using the cluster analysis heuristic is considered as the initial solution for SA. The solution contains all the cities in the cluster as intermediate nodes and the depot as first and last nodes. All the cities appear once in the solution. For example, the initial solution for cluster 5 can be represented as follows:
a) Initial solution
b) Nighborhood solution
Figure 4.6 Solution representations in SA
Initial Temperature and objective function value: The algorithm is started with an initial temperature. Initial temperature T will be set with a high value. The objective function value of a particular solution fi = di, where di is the length of the route. The objective function value will be calculated for the initial solution. For the initial solution given in figure 4.6, the objective function value is 10.7616.
Neighborhood creation: The classical concept of generating a sequence of new solutions (neighborhood) from the initial solution for a particular temperature T is used in SA. In SA, 2(n-1) neighborhoods are created. A neighborhood is created by using a slight perturbation of the position of cities in the current sequence. From those neighborhoods the best one is selected according to the objective function.
Annealing schedule: The algorithm begins with an initial solution and at high temperature T. A new solution is selected from the neighborhood. The difference in the objective function values (âˆ†C) for these two solutions is calculated. If the difference in the objective function values, âˆ†C between the newly selected and the current solutions is negative, then the process is continued from the new solution. To come out from local minimum, SA uses the following concepts (Ingber, 1993). If âˆ†C â‰¥ 0, then the acceptance of the new solution is given by the Metropolis. The neighborhoods that increase the length of the route (objective function value) are also accepted sometimes based on the probabilistic condition that e-âˆ†C/T > R (0,1), where R(0,1) is a random number in the interval [0,1] and e-DC/T is the Boltzman function and is used to determine whether or not to accept a poorer solution at each iteration. That is if the second one has a smaller function value, it will be accepted, otherwise it will be accepted with a probability exp (-âˆ†C/T). When T is high, many such solutions are accepted in order to come out from the local minimum. If âˆ†C â‰¥ 0 and e-âˆ†C/T â‰¤ R (0,1), then current solution will be selected once again for the next iteration. This completes one iteration of the SA procedure. Then the T value is decremented by using cooling function T = aT, where a is the cooling rate. After lowering the temperature several times to a low value, then, only the good solutions are accepted. That is the solutions having reduced route lengths are accepted.
Figure 4.6 Flow Chart for SA
Stopping criteria: The SA is terminated when a sufficiently small temperature is reached or a preset number of iterations are over or a small enough change in objective function values is found (Wikipedia 2010). The algorithm is run with various T values ranging from 10 to 1000 and a value 1% to 10%.
X = Select an Initial Solution using SWA;
f(X) = Compute the objective function value of X;
best_value = f(X);
T = Set an Initial Temperature;
While (termination condition not met)
Repeat (pre-chosen number of times)
Choose the next neighbor X' of the current solution;
Transition = Select a Transition from Neighbourhood (X);
XÂ¢ = Apply Transition (X, Transition);
DC = Compute Change in objective function value (XÂ¢, X);
R = generate random number (0,1);
If ((DC < 0) OR (e-DC/T > R))
X = XÂ¢
f(X) = f(XÂ¢)
If (f(X) < bestsolution) then bestsolution = f(X);
T = Decrement the temperature slightly (T = aT);
Figure 4.7 Algorithm for Simulated Annealing
Table 4.4 Results of Simulated Annealing
Distance to travel
33 -35 -36 -28 -29 -27 -26 -25 -24 -21 -23 - 30- 33
33 -48 -34 -12 -11 -10 -5 -1 -2 -3 -4 -9 -8 - 33
33 -31 -22 -20 -19 -18 -17 -16 -15 -14 -13 -32 - 33
33 - 46 -47 -49 -50 -59 -7 -6 -58 -51 -57 45- 33
33 - 52 -56 -60 -55 -54- 33
33 -44 -43 -53 -42 -40 -41 -39 -37 -38 - 33
The output obtained using the cluster analysis heuristic is improved using route improvement heuristic which applied the AI-heuristic-SA. The results obtained in this stage of the heuristic are given in Table 4.4 and Figure 4.8. The optimized sequence of cities and the distance to be traveled by each salesman are given in the results.
Figure 4.8 Sequence Obtained from Simulated Annealing
22.214.171.124 Tabu Search for Solving TSP
TS is a local search algorithm based on memory concepts Glover and Laguna (1997). It enhances the performance of a local search method by using memory structures Gendreau and Potvin (2005). It starts with an initial solution, creates neighborhoods by slightly modifying the current solution to iteratively move from one route to another. TS uses escape mechanism to come out of local minimum. Tabus are also useful to help the search move away from previously visited portions of the search space and thus perform more extensive exploration. That is tabus are used to prevent solution cycling by using short term memory techniques. Visiting again to the already visited solutions is avoided by using the memory concept called tabu lists. Tabu list contains the details of already visited solutions. Use of already visited routes or used moves is prevented for some number of iterations. This number or the length of the tabu list is called the tabu tenure of the move.Â The various steps involved in TS are explained in the following section.
Step 1: Select the route obtained from SWA as current solution and current best route.
Step 2: Generate a number of neighborhood solutions from the current solution by changing the position of one or more cities randomly.
Step 3: Select a solution among the neighborhood solutions as a new solution. Compare the new solution with tabu list. If it exists in the list then go to step 4. Otherwise add it into the list, and remove one of the solutions that were already in the tabu list .
Step 4: If the new solution exists in the tabu list, check aspiration criteria. Aspiration criteria define aspiration conditions. If the new solution violates tabu conditions and satisfies any one of the aspiration conditions then it is allowed. Normally used aspiration criterion is one that selects solutions which are better than the current best solution.
Step 5: If the new solution satisfies step 3 or 4 than compare the objective function values of the neighborhood solutions. Otherwise go to step 3.
Step 6: Select a best neighborhood solution by using step 3,4 and 5.
Step 7: If the route length of best neighborhood solution is less than the current best route then set the best neighborhood solution as the current best route. Set the neighborhood as the current solution.
Step 8: Repeat from step 2 until stopping criterion is reached.
Step 9: Output the best sequence of cities and the route length.
Solution encoding and initial solution: A sequence of cities in a cluster represents a initial feasible solution. Each city appears only once and depot is the first and last cities in the sequence. In this example, the sequence obtained in SWA will be the initial solution. The initial solution is assumed as the current solution X. The initial solution representation for cluster 5 is shown in figure 4.10.
Neighborhood creation: For a given initial solution, the neighborhood solution is created by exchanging any two cities in the sequence randomly or changing the position of a city randomly from one location to another. For the current solution X, the neighborhood solutions are represented as N(X).
a) Initial solution
b) Neighborhood solution
Figure 4.10 Solution representations in TS
Objective function: In mTSP, the length of the route is assumed as the objective function value. For example, the objective function value of the initial solution given in figure 4.10 is 10.7616.
Tabu list: The details or some attributes of the recently visited solutions are maintained by TS in a memory structure called tabu list. By referring the tabu list TS avoids selecting the same solution or move again and again. The details are normally stored in the form of tabu structure. The entries in the tabu list are called as tabus. Different concepts are used in the implementation of tabu list. The tabu list may contain the recently visited solutions or only the recent moves or the recent objective function values. In this problem the pair of cities that have been exchanged recently are used as attributes for the tabu list.
Aspiration criteria: To avoid the restriction on good moves by tabus, TS uses aspiration criteria. It revokes tabus and allows the solution to search for further improved solutions. Based on the literature, the most commonly used criterion in the problem of mTSP is to allow a move, even if it is tabu, if it results in a solution with an route length value better than that of the current best-known solution.
Stopping criteria: Different stopping conditions commonly used in TS are:
After completion of the user specified number of iterations;
If TS runs with a series of non-improving moves in the route length value;
If no new neighbor can be generated;
If the objective function value reaches the known global optimum value.
The algorithm for TS is given in figure 4.11.
X = Obtain an Initial viable Solution (route) using SWA;
f(X) = Compute objective function (route length) value of X;
best_value = f(X); best_solution = X;
Initialise tabu list L = Æ;
While (termination condition not reached)
Initialize high best-neighbor-value;
Neighborhood list N(X) = Apply Transition (X, Transition);
For (s Î N(X))
DC = Compute Change in objective function values (X, s);
While (suitable neighbour available)
s Î N(X) &
If (s ÏL)
L = L U s;
f(s) = Compute objective function value of s;
found suitable neighbour = TRUE;
Else If (aspiration(s) = TRUE)
f(s) = Compute objective function value of s;
found suitable neighbour = TRUE;
If f(s) < best-neighbor-value then best-neighbor-value = f(s);
best-neighbor = s;
If best-neighbor-value < best_value then best_value = best-neighbor-value;
best_solution = best-neighbor;
Figure 4.11 Algorithm for Tabu Search with Short-Term Memory
Table 4.5 Results of Tabu Search
Distance to travel
33 - 35 - 36 - 28 - 29 - 27 - 26 - 25 - 24 - 23 - 21 - 30 - 33
33 - 48 - 34 - 12 - 11 - 10 - 9 - 4 - 1 - 5 - 2 - 3 - 8 - 33
33 - 31 - 22 - 20 - 18 - 19 - 17 - 16 - 15 - 14 - 13 - 32 - 33
33 - 46 - 47 - 7 - 49 - 6 - 59 - 58 - 50 - 51 - 57 - 45 - 33
33 - 52 - 54 - 56 - 60 - 55 - 33
33 - 44 - 43 - 53 - 42 - 40 - 41 - 39 - 38 - 37 - 33
The results of TS are given in the figure 4.10 and in the table 4.5. The optimized sequence of cities and the distance to be traveled are given in the table.
Figure 4.10 Sequence Obtained from Tabu Search
126.96.36.199 Balancing of Routes AI heuristics
The optimized route obtained from the route improvement heuristic gives a path for the salesperson to travel. But, it could be noticed that the distance traveled by the salespersons are not equal. Since, this may decrease the morale of the employees, any employee-oriented organization would like to balance their workload as far as possible. Allotting a suitable number of cities with balanced route distance is difficult at the clustering stage. Because lot of details such as number of cities in a mTSP and the distances between them are need to be considered while clustering the cities. This will increase the computational complexity. Hence, this section proposes a route balancing concept that can be used after the route optimization process.
The concept is based on mathematical standard deviation concept. The distances to be traveled by six salespersons can be balanced by minimizing the standard deviation of the outputs. Standard deviation actually indicates the variability of a route distance around its mean. The higher the standard deviation, the greater the variability in the route distances. By reducing the standard deviation value it is possible to balance the routes of clusters. So, the objective of balancing heuristic is to minimize the standard deviation up-to lowest possible value. If the standard deviation is 0, all the routes are equal. But in balancing the distance, this may not be possible because, it is not possible to get the exact distances for all the salespersons. Hence, this section chooses the criteria as minimizing the standard deviation up-to the lowest possible value (may be greater than zero) Bedeian and Mossholder (2000).
The standard deviation for this problem is given by
s = standard deviation
di = distance traveled by salesperson i.
= mean of routes
k = number of clusters.
After determining the final routes, one or more cities are moved to nearby lightly loaded clusters from the highly loaded clusters. This process will be repeated between clusters until the standard deviation reaches minimum possible level. Hence, by converging standard deviation to a minimum possible value, one can balance the route. The balancing of routes is explained with a simple example as shown in table 4.6. The table contains the results of routes for six salespersons based on SA with slightly more deviation between routes for salespersons. In this work, it is found that the initial standard deviation is 1.065654 and converging the same using AI heuristics it is found that the minimum possible value is 0.470163. The route distance traveled by the salespersons in this case is shown in Table 4.7.
Table 4.6 Results of Simulated annealing
Distance to travel
The sum of distances to be traveled by the six salespersons is 66.7322 (Optimum) and it is unbalanced. To balance the tour, the increase in the total tour length is to be accepted, but as far as possible this value should be minimum.
Table 4.7 Results of Balancing Rule
Distance to travel
33 - 48 - 34 - 46 - 8 - 9 - 4 - 3 - 1 - 5 - 10 - 11 - 13 - 32 - 33
33 - 30 - 31 - 23 - 21 - 24 - 25 - 26 - 27 - 29 - 36 - 35 - 33
33 - 12 - 14 - 15 - 16 - 17 - 18 - 19 - 20 - 22 - 28 -33
33 - 47 - 49 - 50 - 51 - 58 - 59 - 6 - 2 - 7 - 33
33 - 44 - 43 - 54 - 55 - 60 - 56 - 57 - 52 - 53 - 45 - 33
33 - 37 - 39 - 41 - 40 - 42 - 38 - 33
4.4 RESULTS AND DISCUSSIONS
In the first phase the distributed cities were divided into six clusters as there are six salesmen, that is the mTSP has been converted into TSP. This conversion is achieved by applying k-Means clustering algorithm. The results are shown in figure 4.3 and table 4.2. With this algorithm the cities were clustered into six with11,12,11,11,5 and 9 cities in each cluster respectively. In the first phase, the initial centroids for clustering approach affects the output quality of the clusters formed and this has been solved by taking alternatively the nearest and farthest city locations as centroids. This forms a better approach than random selection. After the conversion of mTSP into TSP, a parent path is generated using SWA. If second phase of the heuristic is skipped off, it may be noticed that achieving optimality for the salesperson's tour is difficult as the SA and TS are very slow processes and they take more time to converge. Hence, SWA is applied to form the initial tour and it serves as the input for SA and TS. The results are shown in figure 4.5 and table 4.3. The path obtained by SWA covered a distance of 69.5195 units. Though a path connecting the cities is obtained, it is not the optimum one. In order to generate more optimized path, route improvement heuristics like TS and SA were used. The results generated by SA are shown in figure 4.8 and table 4.4. The results of TS are given in table 4.5 and figure 4.10. Between the sequences generated by both methods, the sequence generated by SA was more optimized. The distances covered in each cluster and the total distance covered by all the three algorithms are tabulated in table 4.6 and compared. After optimizing the path using TS and SA it was observed that the total distances travelled by all the salesmen were 67.4608 and 63.1387 respectively. The total distance to be traveled by the six salespersons reduced from 69.5195 to 63.1387. From this it is evident that SA is a better algorithm for mTSP than TS. After applying the balancing rule of the third phase of heuristic, it may be noticed that the total increase in distance is only 2.5 % and the distances are almost balanced.
Table 4.6 Comparison of Optimized Distances
4.4.1 Application of 3-Phase Heuristics for Benchmark TSPs.
The proposed three phase heuristics is applied for the seven TSPLIB benchmark problems which are used in the previous chapter. The depot is selected randomly among the cities. It is assumed that six sales persons are in the mTSP. The clustering is done using k-means clustering. Then, by using the proposed SWA initial solutions are calculated. Finally, the GA, ACO, SA and TS are applied for optimization and the results are tabulated in table 4.7. From the results the three phase GA performs better for large sized mTSPs. ACO performs better for small sized mTSPs. Both ACO and GA perform better than other algorithms.
Table 4.7 Results of 3 Phase Heuristics for TSPLIB Problems
Number of salespersons
Total distance to be travelled (units)
This chapter has investigated a general multiple travelling salesman problem with only one objective of minimizing the travelling path. The three phase heuristics show that among the local search algorithms SA is efficient compared to TS. Among all the four algorithms GA and ACO provides significantly efficient solutions than SA and TS. GA provides better solutions for larger problems compared to ACO. Though ACO methods used in this research are not efficient in finding solutions for larger problems, they provide very good results for small ones. The results show that heuristics based route balancing is an effective concept for mTSPs. From the results, it clearly indicates that the three phase hybrid AI-heuristics provide well improved and balanced solutions for mTSPs.