A hybrid heuristic algorithm for single and multi-objective imprecise traveling salesman problems

3.1 Classical TSP with cost minimization (Problem 1A):

In a classical two-dimensional TSP, a salesman has to travel N cities at minimum cost. In this tour, the salesman starts from a city, visits all the cities exactly once and comes to the starting city in minimum cost. Let c _ij be the cost for travelling from ith city to jth city. Then the problem is mathematically formulated as: Determine x ij , i = 1 , 2 , . . . N , j = 1 , 2 , . . . N . to minimize Z = ∑ i = 1 N ∑ j = 1 N x ij c ij subject to ∑ i = 1 N x ij = 1 i = 1 , 2 , . . . , N ∑ j = 1 N x ij = 1 j = 1 , 2 , . . . , N }(4) Here x _ij = 1 if the salesman travels from ith city to jth city, otherwise x _ij = 0.

Let (x₁, x₂, . . . , x _N , x₁) be a complete tour of a salesman, where x _i  ∈ {1, 2, . . , N} for i = 1, 2,...,N and all x _i are distinct in a complete tour. Then the above problem reduces to

Determine a complete tour ( x 1 , x 2 , . . . , x N , x 1 ) To minimize Z = ∑ i = 1 N - 1 c x i , x i + 1 + c x N , x 1 }(5)Classical TSP with time minimization (Problem 1B): If t _ij be the time for travelling from ith city to jth city, Then time minimization problem is mathematically formulated in (6). Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ∑ i = 1 N - 1 t x i , x i + 1 + t x N , x 1 }(6)

In Problem 1A, let us add travel time t _ij to travel from ith city to jth city along with cost c _ij . There is also a restriction on total travel time of the tour. Then the problem belongs to the class of classical TSP with time constraint. Let t _max is the maximum time that a traveler is allowed for his/her tour. Then the problem can be mathematically formulated as in (7): Determine a complete tour ( x 1 , x 2 , . . . , x N , x 1 ) to minimize Z = ∑ i = 1 N - 1 c x i , x i + 1 + c x N , x 1 subject to ∑ i = 1 N t x i , x i + 1 + t x N , x 1 ≤ t max }(7)

In Problem 3, decision maker (DM) likes to minimize total cost as well time. Then the problem is a bi-objective TSP and can be mathematically represented as follows in (9).

Determine a complete tour ( x 1 , x 2 , . . . , x N , x 1 ) to minimize Z 1 = ∑ i = 1 N - 1 c x i , x i + 1 + c x N , x 1 and minimize Z 2 = ∑ i = 1 N - 1 t x i , x i + 1 + t x N , x 1 }(9)

In Problem 1A, if all the costs c _ij are fuzzy numbers then it reduces to a classical two-dimensional TSP with fuzzy costs. Similar to previous problems this problem can also be mathematically represented as given below: Let (x₁, x₂, . . . , x _N , x₁) be a complete tour of a salesman, where x _i  ∈ {1, 2, . . , N} for i = 1, 2, ⋯ , N and all x _i are distinct. Then the above problem can be represented as Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ∑ i = 1 N - 1 c ˜ x i , x i + 1 + c ˜ x N , x 1 }(10) If all c ˜ ij are TFN type, then taking c ˜ ij = ( c ij 1 , c ij 2 , c ij 3 ), the above problem reduces to Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ( Z 1 , Z 2 , Z 3 ) where Z k = ∑ i = 1 N - 1 c x i x i + 1 k + c x N x 1 k for k = 1 , 2 , 3 }(11)

In Problem 4, let t ˜ ijs are the fuzzy traveling times from i - th city to j - th city along with cost c ˜ ij. Also let there is a restriction on total travel time of the tour. Then the problem belongs to the class of fuzzy TSP with fuzzy time constraint. Let t ˜ max is the maximum allowable fuzzy time that a traveler can use for his/her tour. Then the problem can be mathematically formulated as follows. Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ∑ i = 1 N - 1 c ˜ x i x i + 1 + c ˜ x N x 1 subject to ∑ i = 1 N t ˜ x i x i + 1 + t ˜ x N x 1 ≤ t ˜ max }(12) If all c ˜ ijs and t ˜ ijs are TFN type, and c ˜ ij = ( c ij 1 ,c_ij2, c_ij3), t ˜ ij = ( t ij 1 , t ij 2 , t ij 3 ) and t ˜ max = ( t max 1 ,t_max2, t_max3), the above problem can be represented as given bellow in (13). Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ( Z 1 , Z 2 , Z 3 ) where Z k = ∑ i = 1 N - 1 c x i x i + 1 k + c x N x 1 k for k = 1 , 2 , 3 subject to ( T 1 , T 2 , T 3 ) ≤ ( t max 1 , t max 2 , t max 3 ) where T k = ∑ i = 1 N t x i x i + 1 k + t x N x 1 k for k = 1 , 2 , 3 }(13) Now considering credibility measure of fuzzy event, the above problem can be equivalently presented as in (14). Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ( Z 1 , Z 2 , Z 3 ) where Z k = ∑ i = 1 N - 1 c x i x i + 1 k + c x N x 1 k for k = 1 , 2 , 3 subject to cr ( ( T 1 , T 2 , T 3 ) ≤ ( t max 1 , t max 2 , t max 3 ) ) > 0.5 where T k = ∑ i = 1 N t x i x i + 1 k + t x N x 1 k for k = 1 , 2 , 3 }(14)

In Problem 4, if decision maker (DM) likes to minimize both total fuzzy cost as well fuzzy time, then the bi-objective problem with TFN costs and times is Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ( Z 1 , Z 2 , Z 3 ) where Z k = ∑ i = 1 N - 1 c x i x i + 1 k + c x N x 1 k for k = 1 , 2 , 3 and minimize T = ( ( T 1 , T 2 , T 3 ) ) where T k = ∑ i = 1 N t x i x i + 1 k + t x N x 1 k for k = 1 , 2 , 3 }(15)

In Problem 1A, if all the costs c _ij are rough in nature then it reduces to a classical two-dimensional TSP with rough cost. The problem can be represented as Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ∑ i = 1 N - 1 c ˇ x i , x i + 1 + c ˇ x N , x 1 }(16) Then taking c ˇ ij = ( [ c ij 1 , c ij 2 ] , [ c ij 3 , c ij 4 ] ), the above problem reduces to Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ( [ Z 1 , Z 2 ] , [ Z 3 , Z 4 ] ) where Z k = ∑ i = 1 N - 1 c x i x i + 1 k + c x N x 1 k for k = 1 , 2 , 3 , 4 }(17) This is equivalent to

minimize r subject to Tr ( Z ≤ r ) ≥ α , where α is a trust level determined by the decision maker ( DM ) , }(18) which implies minimize 2 ( α - 1 ) Z 3 + ( 2 α - 1 ) Z 4 .

If all c ˇ ij and t ˇ ij are rough in problem 2A, then taking c ˇ ij = ( [ c ij 1 , c ij 2 ] , [ c ij 3 , c ij 4 ] ), t ˇ ij = ( [ t ij 1 , t ij 2 ] ,[t_ij3, t_ij3]), t ˇ max = ( [ t max 1 , t max 2 ] , [ t max 3 , t max 4 ] ) the above problem reduces to Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ( [ Z 1 , Z 2 ] , [ Z 3 , Z 4 ] ) where Z k = ∑ i = 1 N - 1 c x i x i + 1 k + c x N x 1 k for k = 1 , 2 , 3 subject to E ( ( [ T 1 , T 2 ] , [ T 3 , T 4 ] ) ) ≤ E ( ( [ t max 1 , t max 2 ] , [ t max 3 , t max 3 ] ) ) where T k = ∑ i = 1 N t x i x i + 1 k + t x N x 1 k for k = 1 , 2 , 3 }(19) where crisp transformation of rough costs is same as in Problem 7.

In Problem 4 if DM likes to minimize total rough cost as well rough time, then the problem can be mathematically formulated as Determine a complete tour ( x 1 , x 2 , ⋯ , x N , x 1 ) to minimize Z = ∑ i = 1 N - 1 c ˇ x i x i + 1 + c ˇ x N x 1 and To minimize ∑ i = 1 N t ˇ x i x i + 1 + t ˇ x N x 1 }(20) this is equivalent to minimize r 1 and r 2 subject to Tr ( Z ≤ r 1 ) ≥ α 1 and Tr ( T ≤ r 2 ) ≥ α 2 where α 1 and α 2 are a trust levels determined a trust by the DM }(21) which implies the minimization of 2 ( α - 1 ) Z 3 + ( 2 α - 1 ) Z 4 and 2 ( α - 1 ) T 3 + ( 2 α - 1 ) T 4 These single and bi- objective crisp, fuzzy and rough TSPs are now solved by the hybrid algorithm developed in Section 4.

4.1 Proposed hybrid Algorithm

Both algorithms GA and ACO have some merits and demerits in solving combinatorial optimization problems. Here combining the features of these algorithms, a hybrid algorithm is proposed to solve TSP in some modified forms. The algorithm is strong enough to solve single-objective as well as multi-objective constraint TSP. In the algorithm, initially ant colony system is used to produce a set of paths which is a set of potential solutions. Then before updation of pheromone, genetic operations are done on the solution(path of an ant) set and produced children to replace the weaker parents, i.e., if fitness of a child is better than a parent then it replaces the parent. This process continues until termination conditions hold. To improve the performance of the algorithm, different types of cross over and mutation operations are used. For large size problems, this algorithm is used a finite number of times (under small size iterations) to create a set of potential solutions. Then only GA operations are operated on this set of solutions to find better solutions. The hybrid ACO-GA system is presented below. In the algorithm, τ _ij represents amount of pheromone lies on the path between node i and node j, iter represents iteration counter, maxiter represents maximum iteration number of the algorithm, p _c and p _m represent probabilities of crossover and mutations respectively. n represents number of ants or population size and N represents number of nodes/cities in the problem, B is best solution:

Algorithm:

1. Set iter = 0 and initialize maxiter.

2. Initialize pheromone τ _ij for i = 1, 2, ⋯ , N and

j = 1, 2, ⋯ , N.

3. Construct a solution and store it to B.

4. Do

5. Construct paths of n ants, i.e., create n solutions

using τ _ij . Let this set be P.

6. Find fitness of each solution of P.

7. Select solutions from P for mating pool using

Roulette-wheel selection process [19]. Let

this set be M.

8. Made crossover on the solutions of M depending

on p _c .

9. If cost of a child solution is less than cost of it’s

one parent then parent is replaced by the child

solution.

10. Made mutation on M depending upon p _m .

11. If cost of a muted solution is less than cost of

it’s parent then parent is replaced by the child

solution.

12. Made pheromone evaporation.

13. Updated pheromone for all the paths in M.

14. Find best solution from MU {B} and store it to B.

15. While (iter < maxiter).

16. Output B.

17. End Algorithm

4.2 Procedures for the proposed hybrid algorithm

(a) Representation: Here a complete tour on N cities represents a path of an ant, i.e., a potential solution. So a’n dimensional integer vector’, X _i  = (x_i1, x_i2, ⋯ , x _in ), is used to represent a solution, where x_i1, x_i2, ⋯ , x _in represent n consecutive cities in a tour.

(b) Pheromone Initialization: As aim of a TSP is to minimize the cost of a tour,

i. For crisp problems it is assumed that initial value of pheromone = 1 / c ij γ, where c _ij is the cost of travelling from city i to city j and γ is a parameter. Here value of γ is considered as 1.1 as this value of γ gives better result.

ii. For fuzzy problems it is assumed that initial value of pheromone = 1/{GMIV( c ˜ ij ) } γ=1/{(c_ij1 + 4c_ij2 + c_ij3)/6}  ^γ using GMIV, where c ˜ ij = ( c ij 1 , c ij 2 , c ij 3 ) is the fuzzy cost of travelling from city i to city j which is considered as TFN type and γ is a parameter as defined above.

iii. For rough problems it is assumed that initial value of pheromone = 1/{E( c ˇ ij ) } γ=1/{(c_ij1 + c_ij2 + c_ij3 + c_ij4)/4}  ^γ using E, where c ˇ ij = ( [ c ij 1 , c ij 2 ] , [ c ij 3 , c ij 4 ] ) is the rough cost of travelling from city i to city j which is considered as rougn type and γ is a parameter as defined above.

(c) Path Construction: To construct a path X _k for k-th ant following steps are followed:

i. Let NS={1, 2, ⋯ , N} and l = 1.

ii.x _kl = A random element from the set NS.

iii. Let NS=NS - {x _kl }.

iv. Let node i be the present position of the ant i.e., x _kl  = i. Then next node j ∈ NS is selected by the ant with a probability p _ij given by the formula p ij = τ ij α ∑ j ∈ NS τ ij α where α is a positive constant used to amplify the influence of pheromone concentrations. Roulette-Wheel selection process [23] is used for the purpose.

v.l = l + 1, x _kl  = j.

vi. if l < n goto step (iii).

(d) Fitness Evaluation: To find fitness of a solution X _i of P following two steps are followed:

i. Determine the number of solutions in P dominated by X _i and let it be n _i . For single objective TSP if objective value of a solution X _i is better than that of X _j then X _i dominates X _j . For multi-objective TSP X _i dominates X _j if objective value of at least one of the objectives of X _i is better than that of X _j and values of other objectives of X _i are at least equal to that of X _j .

ii. For minimization of crisp objective a solution X _i dominates X _j if objective value of X _i is less than the objective value of X _j . For minimization of fuzzy objective if Z ˜ i and Z ˜ j be the objectives of X _i and X _j respectively then X _i dominates X _j with respect this objective if cr ( Z ˜ i < Z ˜ j ) > 0.5. This is a valid comparison operator as cr ( Z ˜ i < Z ˜ j ) + cr ( Z ˜ i ≥ Z ˜ j ) = 1. For rough objectives, the objectives are transformed to equivalent crisp objective using Trust Measure of rough events, then problems are treated as crisp optimization problem.

iii.n _i /n is taken as fitness of X _i .

(e) Crossover: Three types of crossover are used in the algorithm. Multi-point cycle crossover, order crossover, partially mapped crossover.One of these is selected randomly in each iteration. Each crossover process involves two steps. One is selection process of chromosomes (solutions) and another is crossover process. Selection process is same for each crossover but crossover process are different which are presented below.

Selection for crossover: For each solution X _i of P, generate a random number r in the interval [0, 1]. If r < p _c , the solution is reserve for crossover.

Crossover process: Different crossover process are randomly used and are listed below:

i. Multi-point cyclic crossover process: In multi-point cyclic crossover more than one single point cyclic crossover [3] are used. At first maximum number of point is randomly generated, let it be m where m (<9) which is the maximum limit of multi-point. Then single point crossover is made m times.

ii. Order crossover process: To generate new child using this process [9], subsequence of a tour from one parent are selected and preserving the relative order of cities from the other parent.

iii. Partially mapped crossover process: This process [9] builds an offspring by choosing a subsequence of a tour from one parent and preserving the order and position of as many cities as possible from the other parent. A subsequence of a tour is selected by choosing two random cut points, which serve as boundaries for swapping operations.

(f) Mutation: Here two types of mutation operations namely single point mutation and multi point mutation are used. At the time of mutation one of these are randomly selected. Each type mutation involves two different operations. One is selection process of chromosomes (solutions) and another is mutation process. Selection process is same for each mutation type but mutation process are different which are presented below.

Selection for mutation: For each solution of M generate a random number r from the range [0, 1]. If r < p _m then the solution is taken for mutation.

Single point mutation process: To mutate a solution X = (x₁, x₂, ⋯ , x _n ) of TSP select two random integers i,j in the range [1, N]. Then interchange x _i , x _j to get child solution. New solution, if satisfies the condition of the problem, replaces the parent solution provided its cost is less than that of parent.

Multi point mutation process: To mutate a solution X = (x₁, x₂, ⋯ , x _N ) of TSP select three random integers i, j, h in the range [1, N]. Then first interchange x _i , x _j and then interchange X _j , X _h to get child solution. New solution, if satisfies the condition of the problem, replaces the parent solution provided its cost is less than that of parent. The process similarly be extended to four or more points according to problem size.

(g) Pheromone Evaporation: For evaporation of pheromone the following formulas are used τ ij = ( 1 - ρ ) τ ij here ρ is in [0, 1]. The constant ρ, specifies the rate at which pheromone evaporates,causing ants to forget previous decisions.

(h) Pheromone Updating: Once all ants have constructed their complete tour pheromone is increased on the paths through which the ants move. Depending upon the nature of the problem after a complete tour pheromone is increased using the following rules.

i. For single objective crisp problem if C _k be the cost of path X _k , then for this path τ _{x ki x ki+1} is increased by 1 / C k β, where β is a parameter used to best fit the updating function.

ii. For single objective fuzzy problem if C ˜ k be the cost of path X _k , then for this path τ _{x ki x ki+1} is increased by 1/{GMIV (C _k )}  ^β , where β is a parameter as mentioned above. If travelling costs are considered as TFN type then C ˜ k is also a TFN and let C ˜ k = ( C k 1 , C k 2 , C k 3 ), then according to the rule τ _{x ki x ki+1} is increased by 1/{(C_k1 + 4C_k2 + C_k3)/6}  ^β .

iii. For single objective rough problem if C ˇ k be the cost of path X _k , then for this path τ _{x ki x ki+1} is increased by 1/{E (C _k )}  ^β , where β is a parameter as mentioned above. If travelling costs are considered as rough type then C ˇ k is also a rough and let C ˇ k = ( [ C k 1 , C k 2 ] , [ C k 3 , C k 4 ] ), then according to the rule τ _{x ki x ki+1} is increased by 1/{(C_k1 + C_k2 + C_k3 + C_k3)/4}  ^β .

iv. For bi-objective crisp problem if C _k and T _K be the cost and time of path X _k , then for this path τ _{x ki x ki+1} is increased by 2 / ( C k β + T k β ), where β is a parameter as stated above.

v. For bi-objective fuzzy problem if C _k and T _K be the cost and time of path X _k , then for this path τ _{x ki x ki+1} is increased by 2/[{GMIV (C _k )}  ^β  + {GMIV (T _k )}  ^β ], where β is a parameter as mentioned above. If travelling costs and times are considered as TFN type then C ˜ k and T ˜ k are also TFNs and let C ˜ k = ( C k 1 , C k 2 , C k 3 ) and T ˜ k = ( T k 1 , T k 2 , T k 3 ), then according to the rule τ _{x ki x ki+1} is increased by 2/[{(C_k1 + 4C_k2 + C_k3)/6}  ^β  + {(T_k1 + 4T_k2 + T_k3)/6}  ^β ].

vi. similarly For bi-objective rough problem τ _{x ki x ki+1} is increased by 2/[{E (C _k )}  ^β  + {E (T _k )}  ^β ], where β is a parameter as mentioned above. If travelling costs and times are considered as rough type then C ˜ k and T ˜ k are also rough and let C ˇ k = ( [ C k 1 , C k 2 ] , [ C k 3 , C k 4 ] ) and T ˇ k = ( [ T k 1 , T k 2 ] , [ T k 3 , T k 4 ] ), then according to the rule τ _{x ki x ki+1} is increased by 2/[{(C_k1 + C_k2 + C_k3 + C_k4)/4}  ^β  + {(T_k1 + T_k2 + T_k3 + T_k4)/4}  ^β ].

5.1 Testing of hybrid algorithm:

The hybrid algorithm developed in the Section 4 is tested against some standard test problems (single objective TSPs) with symmetric and asymmetric travel costs from TSPLIB. The names of the problems, their optimal costs as well as results obtained using the proposed algorithm are tabulated in Table 1 along with the results following usual GA and ACO. Number of iterations used to obtain the results of the problems following different approaches are also presented in the Table 1. For a particular test problem, result using proposed algorithm with specific mutation and crossover along with randomly selected types are presented in Table 2.

5.2 Input test data for different problems

The problems are illustrated for ten cities (N=10). The assumed values of travel costs and times between different cities are presented in Table 3 (times are presented under slash(/)). For the Problem 2A, the total travel time is limited to 30 or 50 time units (i.e t _max  = 30 or 50 units) and for Problem 2B, total travel cost is limited to 250 or 150 cost units. The imprecise travel costs and times between different cities are given in Tables 4 (fuzzy cost) and 5 (rough costs). Here, maximum permitted travel time are also fuzzy for fuzzy TSP with its value is [29.01,30,31.01] and rough for rough TSP and its value as [29.5,30,29,30.5].

TSP with virtual data set

Here we generate large TSP problems with virtual data set, travel costs (c _ij ) and travel times (t _ij ) for 40, 60 and 100 cities. These values are randomly generated within some specified values, (c _l , c _u ) and (t _l , t _u ) (Normally, when travel time is less (high), then travel cost is high (less). The feature is followed in some cases during the creation of these data). The above ranges differ for different problems. Random data sets are generated using rand() function in C++ language. For the present problem, t _ij s are obtained as t ij = random number in [ t l , t u ] + ( c n / c ij ) , where t _l  = 0, t _u  = 5 and c _n  = 200.

5.3 Solutions of different TSPs

The Problems-(1A, 1B, 2A, 2B, 3), (4, 5, 6) and (7, 8, 9) with the above crisp, fuzzy and rough input data’s are solved by the developed HA (cf. Section 2). The appropriate crisp representation of the fuzzy and rough problems are obtained followings the Section 4 and then the results are presented in Tables 6, 7, 8.

Statistical test

Performance of the proposed method is statistically tested running it 25 times and calculating the average value, standard deviation and percentage relative error according to optimal solution against virtual data problems given in Table 9. The percentage relative error is defined as Error ( % ) = ( average solution - bestknown solution ) bestknown solution × 100 .

Examining the Table 10, it is concluded that the proposed Problem 3, Problem 6 and Problem 9 which solved by Hybrid ACO-GA, is effective for the most of instances. The above Table shows that standard deviation (SD) low for 40, 60 node problems but for 100 node as well as percentage error propagate smoothly for every instances i.e. not too much high.

7.1 Problem size versus iteration number

Here a study is made for the number of iterations required for optimum results for different sizes of cost matrices. For crisp TSP (Problem 3), optimum results ware obtained with (5 ×5) , (6 × 6) , ⋯ , (10 × 10) matrices and corresponding iteration numbers were noted. These are plotted in Fig. 1. It is to be noted that (6 ×6) matrix size onwards, number of iterations required for optimum values increases sharply. But when matrix size increases from (5 ×5) size to (6 ×6) size, the increase in iteration number is less. On the other hand, when matrix size increases from (9 ×9) to (10 × 10), the increase in iteration number is very high. This is as per our expectation. As the problem is a NP-hard problem, the complexity and time increase with the size of cost matrices and hence the number of iterations for optimum results sharply increases with problem sizes.

7.2 Problem size versus population size

Another study is also presented for population size against different sizes of cost matrices. Here for crisp TSP (Problem 3), optimum results ware derived with (5 ×5) , (6 × 6) , ⋯ , (10 × 10) matrices and corresponding population sizes were noted. These are plotted in Fig. 2. It is observed that (6 ×6) matrix size onwards, number of population sizes required for optimum values increases sharply. However, for the TSPs with (5 ×5) and (6 ×6) cost matrices or with (9 ×9) and (10 × 10) cost matrices, the required population size for optimum results are almost same.

7.3 Efficiency of HA

Here, the efficiency of the proposed HA with respect to iteration numbers for problem eil76 is tested and presented in Fig. 3. It is observed that after initial high values and then slight fluctuation for small number of iterations, the optimum values converges after a certain number of iteration. For the test problem eil76 value is 100.