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

Abstract

Normally, Travelling salesman problems (TSPs) are formulated with deterministic parameters and either total cost or time is minimized. In real life TSPs, the travel costs and times are not defined precisely and represented by fuzzy or rough data. Very often, in addition to single objective cost or time, both total cost and time are also minimized. These uncertain problem are difficult to optimize. In this paper, some TSPs are formulated as linear programming’s problems with imprecise data and there cost, time, or both are minimized by a hybrid heuristic algorithm combining Ant colony optimization (ACO) and Genetic algorithm (GA). Here, hybrid algorithm consumes less resources such as CPU time, then the single heuristic methods. Developed algorithm is capable of solving both single and multi-objective constrained large TSPs with crisp, fuzzy and rough data. In the algorithm, different types of crossovers (multi-point crossover, order crossover, partially mapped crossover) and mutations (single point, multi point) are randomly used. Performance of the algorithm is tested against standard test problems from TSPLIB. Proposed TSPs are solved with proposed and existing algorithms and results are compared. Both the problems and algorithm are illustrated with numerical examples. Some sensitivity analyses are also presented.

Keywords

Ant Colony Optimization Genetic algorithm travel cost travel time

1 Introduction

In Travelling Salesman Problem (TSPs) a salesman visits a number of cities in his/her territory, going to each city exactly once and then returns to the starting point. The objective of a travelling salesman is to choose an appropriate path so that total travel cost or time is minimum. During the last decades, several TSPs have been investigated by researchers using several algorithms.

Recently several heuristic algorithms here emerged to approximate the optimal solutions of TSPs. These are Tabu search [16], Neural networks ([18]), Genetic algorithms (GA) [17, 20], Ant Colony Optimization (ACO) [1 , 10]. Genetic Algorithm (GA) is an important technique for solving optimization problems. Recently Turker and Erbill [23] used both GA and ACO simultaneously for process control. There are many approaches of GAs to solve TSP [17 , 24]. ACO is another important soft computing techique for solving optimization problems. ACO is a meta-huristic approach. In ACO, the behaviour of real ants to find the shortest path between their nest and food source, has been mimiced. Several ACO algorithms are available to solve the well-known NP-Hard TSP problems [1 , 10].

Sometimes, the application of single heuristic algorithm does not provide the desired results in TSP. Some hybrid algorithms have also been used to get approximate optimal solutions. Several algorithms incorporated other algorithms to improve the performance of the system. To improve the performance of ACO, GA is combined with it. In 2011, Chen and Chien [4] used a method based on parallelized genetic ant colony systems for solving a TSP. In 2012, Dong, Guo and Tichle [7] developed a method solving a TSP using cooperative genetic ant system.

In all the above investigations, normally it is assumed that TSP parameters- cost and times are precisely known and deterministic. But, in real life, the travelling costs or times between the cities depend on the conveyance used for travelling, availability of number of vehicles on the journey date, road condition, etc.. Hence these parameters vary and are uncertain in non-stochastic sense. This may be imprecise - either fuzzy or rough. For an unknown path, it is often said that unit travel cost is about R$ or nearer to R$ which can be represented by a fuzzy number. Sometimes, said cost or time is specified by upper and lower intervals [a, b] and [c, d] i.e, by a rough number, defined by a rough set. There are very few TSPs with these realistic parameters, recently, Changdar et al. [3] have developed solid TSPs and solved the problems using GA and ACO separately. Assuming the travel costs as intervals, they minimized travel cost only. But study of occurance of imprecise parameters in different routing problems is made by several authors [11 , 22].

Moreover, in some cases, a salesman is asked to complete his/her tour within a fixed time bound or against a limited budget. There are also some situations where a salesman desires to minimize both travel cost and time. In spite of several TSPs available in the literature, there are very few constrained TSPs and bi-objective TSPs with imprecise costs and times. To fill up this vacuum, the proposed TSPs are developed and solved by the appropriate hybrid heuristic algorithm.

In this paper, some TSP problems are considered in three different environments - crisp, fuzzy and rough environments, In each environment, for the first type, total travel cost is minimized; for the second type, cost is minimized with a travel time constraint and both total travel cost and time are minimized for the third type problem. In addition to these, two more problems - minimization total time without and with cost constraint are considered in crisp environment. Here, combining the features of ACO and GA, an algorithm is proposed which can solve single/multi-objective constrained TSPs in crisp, fuzzy, rough environment and is used to solve the proposed problems. To deal with fuzzy problems, following credibility measure of fuzzy events, an approach is proposed to compare fuzzy objectives. For rough parameters, trust measures [15] of the rough events are used. Again using dominance property of objectives, an approach is proposed to find fitness of a solution for both single as well as multi-objective problems in crisp, fuzzy and rough environments. In the algorithm, different types of crossover operations- multi-point crossover, order crossover and partially mapped crossover are randomly used to improve the performance of the algorithm. Two types of mutation are randomly used in the algorithm. Performance of the algorithm is tested against standard test problems from TSPLIB. Results show that performance of the proposed algorithm for single objective problems are comparable with other existing algorithms. The problems are illustrated with some numerical data. The proposed TSPs is solved by proposed hybrid algorithm (HA) and individual algorithms ACO and GA. It is established that HA fetches better results in terms of iteration, population size, etc. Some sensitivity analyses are done with respect to number of iterations, etc.

The contribution of the present work can be summarised as follows.

A hybrid algorithm using ACO and GA is developed which gives better results for the test and proposed TSP problems.

Several types of TSP problems are formulated with imprecise cost and times and solved in crisp, fuzzy and rough environments.

TSP problems with rough costs and times are also formulated and solved using trust measures.

2 Mathematical prerequisite

Definition 1. Possibility (Pos), Necessity and Credibility (Cr) measures: Let $\tilde{a}$ and $\tilde{b}$ be two fuzzy numbers (cf. Zadeh [25]) with membership functions $μ_{\tilde{a}}$ and $μ_{\tilde{b}}$ respectively. Then taking degree of uncertainty as the semantics of fuzzy number, according to Chakraborty [2], possibility (Pos), necessity (nes) and credibility (Cr) of two fuzzy numbers are: $\begin{matrix} Pos (\tilde{a} ★ \tilde{b}) & = \sup {\min (μ_{\tilde{a}} (x), μ_{\tilde{b}} (y)), \\ x, y \in R, x ★ y}, \end{matrix}$ (1) $Nes (\tilde{a} ★ \tilde{b}) = 1 - Pos (\bar{\tilde{a} ★ \tilde{b}}),$ (2) $Cr (\tilde{a} ★ \tilde{b}) = [Poss (\tilde{a} ★ \tilde{b}) + Nes (\tilde{a} ★ \tilde{b})] / 2,$ (3) where ★ is one of the relations >, < , = , ≤ , ≥. On the other hand necessity measure of an event $\tilde{a} ★ \tilde{b}$ is a dual of possibility measure, where $\bar{\tilde{a} ★ \tilde{b}}$ represents complement of the event $\tilde{a} ★ \tilde{b}$ .

Lemma 1.If $\tilde{a} = (a_{1}, a_{2}, a_{3})$ and $\tilde{b} = (b_{1}, b_{2}, b_{3})$ be two TFNs, where 0 < a₁ < a₂ < a₂and 0 < b₁ < b₂ < b₂then $Pos (\tilde{a} > \tilde{b})$ , $nes (\tilde{a} > \tilde{b})$ and $Cr (\tilde{a} > \tilde{b})$ is given by $Pos (\tilde{a} > \tilde{b}) = {\begin{matrix} 1 a_{2} \geq b_{2} \\ \frac{a_{3} - b_{1}}{(a_{3} - a_{2}) (b_{2} - b_{1})} a_{2} < b_{2} and a_{3} < b_{1} \\ 0 a_{3} \leq b_{1} \end{matrix}$ $nes (\tilde{a} > \tilde{b}) = {\begin{matrix} 1 b_{3} \leq a_{1} \\ \frac{a_{2} - b_{2}}{a_{3} - b_{2} + a_{2} - a_{1}} b_{2} \leq a_{2} and a_{1} < b_{3} \\ 0 b_{2} \leq a_{2} \end{matrix}$ $Cr (\tilde{a} > \tilde{b}) = {\begin{matrix} 1 b_{3} < a_{1} \\ \frac{1}{2} (1 + \frac{a_{2} - b_{2}}{b_{3} - b_{2} + a_{2} - a_{1}}) b_{2} \leq a_{2} and a_{1} < b_{3} \\ \frac{1}{2} (\frac{a_{3} - b_{1}}{a_{3} - a_{2} + b_{2} - b_{1}}) a_{2} < b_{2} and a_{3} > b_{1} \\ 0 a_{3} < b_{1} \end{matrix}$

Definition 2. Graded Mean Integration Value (GMIV) of Fuzzy Number: If $\tilde{a} = (a, b, c)$ be a TNF, then according to Chen and Hsieh [5], GMIV of $\tilde{a}$ is giving by (a + 4b + c)/6.

Definition 3. Trust measure (Tr): Let $\overset{ˇ}{ξ} = ([a, b]$ [c, d]) , c ≤ a ≤ b ≤ d be a rough variable. Lebesgue measure is used for trust measure of rough event associated with $\overset{ˇ}{ξ} \leq t$ . Trust measure of the rough event $\overset{ˇ}{ξ} \leq t$ is denoted by Tr( $\overset{ˇ}{ξ} \leq t$ ) and its function curve is presented below $Tr {\overset{ˇ}{ξ} \leq t} = {\begin{matrix} 0 for t \leq c \\ \frac{d - t}{2 (d - c)} for c \leq t \leq a \\ \frac{1}{2} (\frac{t - c}{d - c} + \frac{t - a}{b - a}) for a \leq t \leq b \\ \frac{1}{2} (\frac{t - c}{d - c} + 1) for b \leq t \leq d \\ 1 for d \leq t \end{matrix}$

Definition 4. Rough Expectation (E): Let $\overset{ˇ}{X}$ be a rough variable. The expected value of the rough variable $\overset{ˇ}{X}$ is denoted by $E [\overset{ˇ}{X}]$ and defined by $E [\overset{ˇ}{X}] = \int_{0}^{\infty} Tr (\overset{ˇ}{X} \geq t) dt - \int_{0}^{- \infty} Tr (\overset{ˇ}{X} \leq t) dt$ provided that at least one of the two integrals is finite.

Lemma 2.Let $\overset{ˇ}{ξ} = ([a, b] [c, d])$ is a rough variable wherec > 0, Then expected value of $\overset{ˇ}{ξ}$ is $E [\overset{ˇ}{ξ}] = (a + b + c + d) / 4$

3 Problem formulation

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: $\begin{matrix} Determine x_{ij}, i = 1, 2, . . . N, j = 1, 2, . . . N . \\ to minimize Z = \sum_{i = 1}^{N} \sum_{j = 1}^{N} x_{ij} c_{ij} \\ subject to \sum_{i = 1}^{N} x_{ij} = 1 i = 1, 2, . . ., N \\ \sum_{j = 1}^{N} x_{ij} = 1 j = 1, 2, . . ., N \end{matrix}}$ (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

$\begin{matrix} Determine a complete tour (x_{1}, x_{2}, . . ., x_{N}, x_{1}) \\ To minimize Z = \sum_{i = 1}^{N - 1} c_{x_{i}, x_{i + 1}} + c_{x_{N}, x_{1}} \end{matrix}}$ (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). $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = \sum_{i = 1}^{N - 1} t_{x_{i}, x_{i + 1}} + t_{x_{N}, x_{1}} \end{matrix}}$ (6)

3.2 Classical TSP with time constraint (Problem 2A)

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): $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, . . ., x_{N}, x_{1}) \\ to minimize Z = \sum_{i = 1}^{N - 1} c_{x_{i}, x_{i + 1}} + c_{x_{N}, x_{1}} \\ subject to \sum_{i = 1}^{N} t_{x_{i}, x_{i + 1}} + t_{x_{N}, x_{1}} \leq t_{\max} \end{matrix}}$ (7)

3.2.1 Classical TSP with cost constraint (Problem 2B)

If c_max is the maximum cost that a traveler can use for his/ her tour, then the problem of travel time minimization can be mathematically formulated as given bellow. $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, . . ., x_{N}, x_{1}) \\ to minimize Z = \sum_{i = 1}^{N - 1} t_{x_{i}, x_{i + 1}} + t_{x_{N}, x_{1}} \\ subject to \sum_{i = 1}^{N} c_{x_{i}, x_{i + 1}} + c_{x_{N}, x_{1}} \leq c_{\max} \end{matrix}}$ (8)

3.3 A bi-objective TSP (Problem 3)

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).

$\begin{matrix} Determine a complete tour (x_{1}, x_{2}, . . ., x_{N}, x_{1}) \\ to minimize Z_{1} = \sum_{i = 1}^{N - 1} c_{x_{i}, x_{i + 1}} + c_{x_{N}, x_{1}} \\ and minimize Z_{2} = \sum_{i = 1}^{N - 1} t_{x_{i}, x_{i + 1}} + t_{x_{N}, x_{1}} \end{matrix}}$ (9)

3.4 Fuzzy TSP (with fuzzy cost) (Problem 4)

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 $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = \sum_{i = 1}^{N - 1} {\tilde{c}}_{x_{i}, x_{i + 1}} + {\tilde{c}}_{x_{N}, x_{1}} \end{matrix}}$ (10) If all ${\tilde{c}}_{ij}$ are TFN type, then taking ${\tilde{c}}_{ij} = (c_{ij 1}, c_{ij 2}, c_{ij 3})$ , the above problem reduces to $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = (Z_{1}, Z_{2}, Z_{3}) \\ where Z_{k} = \sum_{i = 1}^{N - 1} c_{x_{i} x_{i + 1} k} + c_{x_{N} x_{1} k} \\ for k = 1, 2, 3 \end{matrix}}$ (11)

3.5 Fuzzy TSP with fuzzy time constraint (Problem 5)

In Problem 4, let ${\tilde{t}}_{ij}$ s are the fuzzy traveling times from i - th city to j - th city along with cost ${\tilde{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 ${\tilde{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. $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = \sum_{i = 1}^{N - 1} {\tilde{c}}_{x_{i} x_{i + 1}} + {\tilde{c}}_{x_{N} x_{1}} \\ subject to \sum_{i = 1}^{N} {\tilde{t}}_{x_{i} x_{i + 1}} + {\tilde{t}}_{x_{N} x_{1}} \leq {\tilde{t}}_{\max} \end{matrix}}$ (12) If all ${\tilde{c}}_{ij}$ s and ${\tilde{t}}_{ij}$ s are TFN type, and ${\tilde{c}}_{ij} = (c_{ij 1},$ c_ij2, c_ij3), ${\tilde{t}}_{ij} = (t_{ij 1}, t_{ij 2}, t_{ij 3})$ and ${\tilde{t}}_{\max} = (t_{\max 1},$ t_max2, t_max3), the above problem can be represented as given bellow in (13). $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = (Z_{1}, Z_{2}, Z_{3}) \\ where Z_{k} = \sum_{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}) \leq (t_{\max 1}, t_{\max 2}, t_{\max 3}) \\ where T_{k} = \sum_{i = 1}^{N} t_{x_{i} x_{i + 1} k} + t_{x_{N} x_{1} k} for k = 1, 2, 3 \end{matrix}}$ (13) Now considering credibility measure of fuzzy event, the above problem can be equivalently presented as in (14). $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = (Z_{1}, Z_{2}, Z_{3}) \\ where Z_{k} = \sum_{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}) \leq (t_{\max 1}, t_{\max 2}, t_{\max 3})) > 0.5 \\ where T_{k} = \sum_{i = 1}^{N} t_{x_{i} x_{i + 1} k} + t_{x_{N} x_{1} k} for k = 1, 2, 3 \end{matrix}}$ (14)

3.6 bi-objective TSP with fuzzy time and fuzzy cost constraint (Problem 6)

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 $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = (Z_{1}, Z_{2}, Z_{3}) \\ where Z_{k} = \sum_{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} = \sum_{i = 1}^{N} t_{x_{i} x_{i + 1} k} + t_{x_{N} x_{1} k} for k = 1, 2, 3 \end{matrix}}$ (15)

3.7 Rough TSP (with rough cost) (Problem 7)

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 $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = \sum_{i = 1}^{N - 1} {\overset{ˇ}{c}}_{x_{i}, x_{i + 1}} + {\overset{ˇ}{c}}_{x_{N}, x_{1}} \end{matrix}}$ (16) Then taking ${\overset{ˇ}{c}}_{ij} = ([c_{ij 1}, c_{ij 2}], [c_{ij 3}, c_{ij 4}])$ , the above problem reduces to $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = ([Z_{1}, Z_{2}], [Z_{3}, Z_{4}]) \\ where Z_{k} = \sum_{i = 1}^{N - 1} c_{x_{i} x_{i + 1} k} + c_{x_{N} x_{1} k} \\ for k = 1, 2, 3, 4 \end{matrix}}$ (17) This is equivalent to

$\begin{matrix} minimize r \\ subject to Tr (Z \leq r) \geq α, \\ where α is a trust level determined by \\ the decision maker (DM), \end{matrix}}$ (18) which implies $minimize 2 (α - 1) Z_{3} + (2 α - 1) Z_{4} .$

3.8 Rough TSP (with rough time constraint) (Problem 8)

If all ${\overset{ˇ}{c}}_{ij}$ and ${\overset{ˇ}{t}}_{ij}$ are rough in problem 2A, then taking ${\overset{ˇ}{c}}_{ij} = ([c_{ij 1}, c_{ij 2}], [c_{ij 3}, c_{ij 4}])$ , ${\overset{ˇ}{t}}_{ij} = ([t_{ij 1}, t_{ij 2}],$ [t_ij3, t_ij3]), ${\overset{ˇ}{t}}_{\max} = ([t_{\max 1}, t_{\max 2}], [t_{\max 3}, t_{\max 4}])$ the above problem reduces to $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = ([Z_{1}, Z_{2}], [Z_{3}, Z_{4}]) \\ where Z_{k} = \sum_{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}])) \leq \\ E (([t_{\max 1}, t_{\max 2}], [t_{\max 3}, t_{\max 3}])) \\ where T_{k} = \sum_{i = 1}^{N} t_{x_{i} x_{i + 1} k} + t_{x_{N} x_{1} k} for k = 1, 2, 3 \end{matrix}}$ (19) where crisp transformation of rough costs is same as in Problem 7.

3.9 bi-objective TSP with rough time and rough cost constraint (Problem 9)

In Problem 4 if DM likes to minimize total rough cost as well rough time, then the problem can be mathematically formulated as $\begin{matrix} Determine a complete tour (x_{1}, x_{2}, \dots, x_{N}, x_{1}) \\ to minimize Z = \sum_{i = 1}^{N - 1} {\overset{ˇ}{c}}_{x_{i} x_{i + 1}} + {\overset{ˇ}{c}}_{x_{N} x_{1}} \\ and To minimize \sum_{i = 1}^{N} {\overset{ˇ}{t}}_{x_{i} x_{i + 1}} + {\overset{ˇ}{t}}_{x_{N} x_{1}} \end{matrix}}$ (20) this is equivalent to $\begin{matrix} minimize r 1 and r 2 \\ subject to Tr (Z \leq r 1) \geq α 1 and Tr (T \leq r 2) \geq α 2 \\ where α 1 and α 2 are a trust levels determined a trust \\ by the DM \end{matrix}}$ (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 Hybrid ACO-GA system

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 $({\tilde{c}}_{ij})}^{γ}$ =1/{(c_ij1 + 4c_ij2 + c_ij3)/6} ^γ using GMIV, where ${\tilde{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 $({\overset{ˇ}{c}}_{ij})}^{γ}$ =1/{(c_ij1 + c_ij2 + c_ij3 + c_ij4)/4} ^γ using E, where ${\overset{ˇ}{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.

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} = \frac{τ_{ij}^{α}}{\sum_{j \in 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 ${\tilde{Z}}_{i}$ and ${\tilde{Z}}_{j}$ be the objectives of X_i and X_j respectively then X_i dominates X_j with respect this objective if $cr ({\tilde{Z}}_{i} < {\tilde{Z}}_{j}) > 0.5$ . This is a valid comparison operator as $cr ({\tilde{Z}}_{i} < {\tilde{Z}}_{j}) + cr ({\tilde{Z}}_{i} \geq {\tilde{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 ${\tilde{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 ${\tilde{C}}_{k}$ is also a TFN and let ${\tilde{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 ${\overset{ˇ}{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 ${\overset{ˇ}{C}}_{k}$ is also a rough and let ${\overset{ˇ}{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 ${\tilde{C}}_{k}$ and ${\tilde{T}}_{k}$ are also TFNs and let ${\tilde{C}}_{k} = (C_{k 1}, C_{k 2}, C_{k 3})$ and ${\tilde{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 ${\tilde{C}}_{k}$ and ${\tilde{T}}_{k}$ are also rough and let ${\overset{ˇ}{C}}_{k} = ([C_{k 1}, C_{k 2}], [C_{k 3}, C_{k 4}])$ and ${\overset{ˇ}{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 Numerical Illustration

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 (%) = \frac{(average solution - bestknown solution)}{bestknown solution} \times 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.

6 Discussion

From Table 1, it is observed that the proposed HA gives the optimum results exactly for four test problems out of nine test problems considered here. For the other test problems, it is marginally out i.e, it gives little higher values than the standard optimum results. However, it can be noticed that the usual GA and ACO furnish the optimum results only for a test problem (Br17) and much worse results for the others than the proposed HA. From this experiment, it can be concluded that the proposed algorithm is efficient to deal with TSPs compared to the existing ones. Moreover, HA takes less number of iterations than the usual GA and ACO to get the optimum results.

From Table 2, out of the proposed different types of crossovers and mutations for HA, the different combination of these types do not furnish the better result than the use of randomly selection of the types of crossover and mutation.

In Table 6, for Problem 3, three different paths including the optimum path for the salesman are presented. This is because, due to some reason or other, if the salesman fails to follow the optimum path, he/she can think of the next suitable path.

From Table 6, the results are as per the usual expectation with respect to the nature of the problems. In all the problems, behaviours of costs and times are contradictory i.e, less cost takes more time for journey where as higher expenditures (costs) require less time. When we minimize cost (Problem 1A), cost is 111 units (minimum of all costs of the problems) and required time is 80 units (maximum of times of the problems). In Problem 1B (minimization of total travel time), the above figures are exactly opposite i.e, minimum time is 27 units, where as corresponding maximum cost is 376 units. Other models (Problem 2A, Problem 2B) including the bi-objective Problem 3 (minimization of both cost and time) give intermediate values for total travel costs and times. For the Problem 4, Problem 5 and Problem 6, input data for travel costs and times are fuzzy and hence the optimum outputs are also fuzzy. As it is not possible to compare the fuzzy numbers directly like crisp numbers, we evaluate the crisp equivalent of fuzzy numbers following the GMIV formula (for triangular fuzzy number (a, b, c), GMIV value is ([a + 4b + c]/6). From the GMIV values, it is observed that the nature of optimum values for the Problem 4, Problem 5 and Problem 6 are same as the Problem 1A, Problem 2A andProblem 3.

Similarly, for the TSPs with rough data i.e, for Problem 7, Problem 8 and Problem 9, the optimum costs and times which are also rough numbers are presented in Table 8 along with their rough expected values (i.e, crisp numbers). Comparing these crisp values, it is seen that the nature of optimum values for the Problem 7, Problem 8, and Problem 9 are same as the corresponding crisp and fuzzy Problems as mentioned above.

In Table 9 large scale input data are taken and their results are given. Here also it is seen that the nature of optimum values for the Problems- 1A, 1B, 3, 4, 6, 7, 9 are same as the corresponding crisp and fuzzy Problems as mentioned in Section 3.

7 Sensitivity analyses

Here, using the proposed hybrid algorithm, some sensitivity analyses are presented for the crisp bi-objective problem (Problem 3) with respect to cost matrix size, iteration number and population size.

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.

8 Conclusion and future extension

In this paper, a hybrid algorithm is presented for the optimum results of single and multi-objective TSPs in crisp, fuzzy and rough environments. It works exactly upto 76 × 76 size TSPs and furnishes better results than the conventional algorithms-ACOs and GAs. The proposed algorithm is quite general and can be used to solve the decision making problems in other areas such as Inventory control system, Supply chain, Portfolio management, etc. It can be applied to the TSPs with multiple constraints such as total safety constraint, total distance constraint etc. in different environments. It can be extended to include other uncertainties such as random, fuzzy-random, random-fuzzy, etc in TSPs. It can be also extended to solve the three dimensional TSPs i,e. solid TSPs.

Footnotes

Acknowledgments

We are grateful to Dipak Kumar Jana, Department of Engineering Science, Haldia Institute of Technology, Haldia Purba Midnapur-721657, West Bengal, India for his advice to improve the paper.

References

Bai

, Yang

, Chen

, Hu

and Pan

, A model induced max-min ant colony optimization for asymmetric traveling salesman problem, Applied Soft Computing13 (2013), 1365–1375.

Chakraborty

, Jana

D.K.

and Roy

T.K.

, A new approach to solve multi-objective multi-choice multiitem Atanassov’s intuitionistic fuzzy transportation problem using chance operator, Journal of Intelligent and Fuzzy Systems28(2) (2015), 843–865.

Changdar

, Maiti

M.K.

and Maiti

, A constrained solid TSP in fuzzy Environment: Two heuristic approaches, Iranian Journal of Fuzzy Systems10 (2013), 1–28.

Chen

and Chien

, Parallelized genetic ant colony systems for solving the traveling salesman problem, Expert Systems with Applications38 (2011), 3873–3883.

Chen

S.H.

and Hsieh

C.H.

, Graded mean integration representation of generalized fuzzy numbers, Chinese Fuzzy Systems Association5(2) (1999), 1–7.

Dorigo

and Gambardlla

L.M.

, Ant colonies for the travelling salesman problem, Bio Systems43 (1997), 73–81.

Dong

, Guo

W.W.

and Tickle

, Solving the traveling salesmanproblem using cooperative genetic ant systems, Expert Systemswith Applications39 (2012), 5006–5011.

Engelbrecht

A.P.

, Fundamentals of computational swarm intelligence, John Wiley & Sons, Ltd, 2005.

Fiechter

, A parallel tabu search algorithm for large traveling salesman problems, Discrete Applied Mathematics51(3) (1994), 243–267.

10.

Ibez, C. Blum, Beam-ACO for the travelling salesman problem with time windows, Computers and Operations Research37 (2010), 1570–1583.

11.

Jiang

Z.-Z.

, Zhang

, Fan

Z.-P.

and Chen

, A fuzzy matching model with Hurwicz criteria for one-shot multi-attribute exchanges in E-brokerage, Fuzzy Optimization and Decision Making14(1) (2015), 77–96.

12.

Liu

and Iwamura

, Chance constraint Programming with fuzzy parameters, Fuzzy Sets and Systems94 (1998A), 227–237.

13.

Liu

and Iwamura

, A note on chance constrained programming with fuzzy coefficients, Fuzzy Sets and Systems100 (1998B), 229–233.

14.

Liu

and Liu

, A class of fuzzy random optimization: Expected value models, Information Science155 (2003), 89102–.

15.

Liu

Y.K.

and Liu

, Fuzzy random variable: A scalar expected value operator, Fuzzy Optimization and decision Making2(2) (2003), 143–160.

16.

C.C.

and Hus

C.C.

, Annealing framework with learning memory, IEEE Transactions on System, Man, Cybernetics Part A28 (1998), 113–.

17.

Majumdar

and Bhunia

A.K.

, Genetic algorithm for asymmetric traveling salesman problem with imprecise travel time, Computational and Applied Mathematics235 (2011), 3063–3078.

18.

Masutti

T.A.S.

and de Castro

L.N.

, A selforganizing neural network using ideas from the immune system to solve the traveling salesman problem, Information Sciences179 (2009), 1454–1468.

19.

Michalewicz

, Genetic Algorithms + data structures = evolution programs, Springer, Berlin, 1992.

20.

Nagata

and Soler

, A new genetic algorithm for the asymmetric traveling salesman problem, Expert Systems with Applications39 (2012), 8947–8953.

21.

Rehmat

, Saeed

and Cheema

M.S.

, Fuzzy multi-objective linear programming approach, Pakistan Journal of Statistics and Operation Research3(2) (2007), 87–98.

22.

Ruan

, Shi

, Lim

C.-C.

and Wang

, Relief supplies allocation and optimization by interval and fuzzy number approaches, Information Science303 (2015), 15–32.

23.

Turker

T.E.

and Erbill

, Process control using genetic algorithm and ant colony optimization algorithm, Journal of Intelligent and Fuzzy Systems26(1) (2014)–.

24.

Yong

, Selection of Algorithms to solve travelling salesman problems using meta-learning, Journal of Intelligent and Fuzzy Systems8(3) (2011)–.

25.

Zadeh

L.A.

, Fuzzy sets, Information and Control8 (1965), 338–356.