مدل ناشی از بهینه سازی حداقل و حداکثری کلونی مورچه ها برای مسئله فروشنده دوره گرد نامتقارن

A large number of hybrid metaheuristics for asymmetric traveling salesman problem (ATSP) have been proposed in the past decades which produced better solutions by exploiting the complementary characteristics of different optimization strategies. However, most of the hybridizations are criticized due to lacking of sufficient analytical basis. In this paper, a model induced max-min ant colony optimization (MIMM-ACO) is proposed to bridge the gap between hybridizations and theoretical analysis. The proposed method exploits analytical knowledge from both the ATSP model and the dynamics of ACO guiding the behavior of ants which forms the theoretical basis for the hybridization. The contribution of this paper mainly includes three supporting propositions that lead to two improvements in comparison with classical max-min ACO optimization (MM-ACO): (1) Adjusted transition probabilities are developed by replacing the static biased weighting factors with the dynamic ones which are determined by the partial solution that ant has constructed. As a byproduct, nonoptimal arcs will be indentified and excluded from further consideration based on the dual information derived from solving the associated assignment problem (AP). (2) A terminal condition is determined analytically based on the state of pheromone matrix structure rather than intuitively as in most traditional hybrid metaheuristics. Apart from the theoretical analysis, we experimentally show that the proposed algorithm exhibits more powerful searching ability than classical MM-ACO and outperforms state of art hybrid metaheuristics.

Asymmetric traveling salesman problem (ATSP) is one of a class of difficult problems in combinatorial optimization that is representative of a large number of scientific and engineering problems. ATSP and its variants are commonly used models for formulating many practical applications in manufacturing scheduling problem. For example, the scheduling problem in a discrete manufacturing is mainly concerned with how to determine the sequence of jobs so as to minimize the total set-up cost. This problem can be easily formulated into an ATSP problem. Considerable industrial applications on the basis of ATSP can be found in [1], [2], [3] and [4]. Hence, ATSP has always been one of the most attractive problems in academic community. Before the early 1990s, exact algorithms, form the main stream of solvers. However, solving ATSP optimally is NP-hard and the exact algorithm may be difficult to produce a provably optimal solution in a reasonable time. Metaheuristics have found wide acceptance in the arena where suboptimal or satisfied solutions are expected to be generated in a given time period. Among those metaheuristics ant colony optimization (ACO) which was proposed by Dorigo and Gambardella [5], is considered to be one of the most representative ones [6]. It is an iterative approach in which a number of artificial ants construct solutions randomly but are guided by pheromone information that stems from former ants building good solutions. Blum and Dorigo [7] presented a hyper-cube ACO by introducing a normalized way for the pheromone value by which the pheromone values were limited in the interval [0,1]. A survey was given of recent applications and variants of ACO methods by Dorigo and Blum [8]. Recently, many hybrid algorithms that combine ACO and other optimization algorithms have received more and more attention. These hybrid algorithms can produce better solutions by exploiting the complementary characteristics of different optimization strategies. Roughly speaking, ACO based hybrid algorithms fall into two categories. This first category is the hybrid optimization that combines local heuristic search, such as 2-OPT [9] with ACO algorithm. Cheng and Mao [10] developed ACS-TSPTW to solve TSP problem with time window where two local heuristics were embedded to manage the time window constraints. A hybrid ACO algorithm combined with a mutation and 2-OPT heuristic for generalized TSP was proposed by Yang et al. [11]. A web-based simulation and analysis software based on ACO for TSP was developed by Aybars et al. [12]. Puris et al. [13] presented a two-stage ACO in order to obtain good exploration of the search space. ACO optimization applied to multiple TSP problem can be found in Ghafurian and Javadian [14]. Chen and Chien [15] proposed a hybrid algorithm with a combination of ACO algorithm, Simulated Annealing (SA), Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) for solving TSP. Dong and Guo [16] developed a cooperative ACO & GA algorithm in which mutual information exchange between ACO and GA helps conduct the selection of the best solutions for next iteration. ACO hybridized with heuristic rules was also investigated by Keskinturk et al. [4] to solve sequence-dependent setup parallel machine scheduling problem. The second category is concerned with the combination of exact methods and ACO algorithm. A hybrid algorithm called Approximate Nondeterministic Tree Search (ANTS) is the first to integrate branch-and-bound techniques into ACO for quadratic assignment problem (QAP) [17]. According to our investigation, algorithms for ATSP problem that combine ACO and exact methods are very scarce. However, there are a number of schemes that hybridize metaheuristics other than ACO with exact methods. For example, Choi et al [18] developed a hybrid algorithm for ATSP problem that embedded an integer programming solver into GA. Cowling and Keuthen [19] employed a decomposition-recombination scheme for TSP problem in which the original problem is first decomposed into small subproblems. These subproblems are then solved using exact algorithms and the solutions are re-embedded into the original problem. Note that most of the hybrids between exact methods and metaheuristics are operated in a heuristic way. Although the hybrid algorithms can produce high performance as mentioned by the references above, these methods are somewhat unreliable because advantages coming with the hybridization are mostly demonstrated by means of experimental study. As pointed out by the “no free lunch theorems for optimization” [20], any elevated performance over one class of problems is offset by lower performance over another class. In other words, the hybridization in a heuristic manner may not always produce better solutions. Blum et al. [21] and Jourdan et al. [22] surveyed and categorized current hybrid algorithms. Their statistical results indicate that more efforts are needed to design hybrids of exact methods and metaheuristics in a systematic and cooperative way in terms of analytical results. This paper aims to develop a well-suited hybrid algorithm for ATSP problem in which analytical results can be utilized and embedded into ACO algorithm. The information obtained by analyzing both the ATSP model and the dynamics of ACO algorithm itself is used to guide the search of ants in one of the most powerful variant of ACO for TSP problem, i.e., max-min ACO algorithm [23]. Hence, we name the method model induced max-min ant colony optimization (MIMM-ACO). Specifically, our contributions lie in two aspects: • Adjusted transition probabilities are developed by replacing the static biased weighting factors with the dynamic ones. The dynamic weighting factor is closely dependent on the partial solution that ant has constructed. The ideal behind it is that we favor the choice of edges with small residual cost instead of with the small actual cost. As a byproduct nonoptimal arcs will be indentified at each step of tour construction using the dual information derived from solving the associated assignment problem (AP) and these arcs will be discarded from future consideration. • A terminal condition is determined analytically based on the state of pheromone matrix structure. The result comes with a necessary condition for obtaining one optimal solution. The rest of the paper is organized as follows. In the next section, the relevant background contents about the ATSP formulation and the MM-ACO optimization are briefly reviewed. Section 3 is dedicated to the design of MIMM-ACO algorithm in which several supporting analytical results are presented. Section 4 presents some computational results with which we show that the proposed algorithm has a remarkable performance, in particular on the running-time efficiency compared with several state of the art algorithms. Section 5 offers a summary and outlines future work.

In this paper, we have proposed a novel hybrid metaheuristic algorithm for ATSP problem with analytical mechanisms. The MIMM-ACO optimization utilizes the information acquired from both the ATSP problem and the employed algorithm itself. It provides an analytical way to incorporate exact methods with ACO and thus is capable of improving the searching efficiency in a definite way. The idea behind it is that any well-suited algorithm requires one should have deep understanding and explicit knowledge of the problem. The more information one has, the more efficient the algorithm would be. However, the knowledge coming from the lower bound structure is always associated with the structure of the particular problem being solved. This puts forward a new interesting problem on selection of good lower bound structures to provide in-depth insight into the problem under consideration. This also points out a good direction for the future research.