The Generalized Traveling Salesman Problem solved with Ant Algorithms
A well known N P-hard problem called the Generalized Traveling Salesman Problem (GTSP) is considered. In GTSP the nodes of a complete undirected graph are partitioned into clusters. The objective is to find a minimum cost tour passing through exactly one node from each cluster. An exact exponential time algorithm and an effective meta-heuristic algorithm for the problem are presented. The meta-heuristic proposed is a modified Ant Colony System (ACS) algorithm called Reinforcing Ant Colony System (RACS) which introduces new correction rules in the ACS algorithm. Computational results are reported for many standard test problems. The proposed algorithm is competitive with the other already proposed heuristics for the GTSP in both solution quality and computational time.
Code (0)
등록된 구현이 없습니다.
Tasks
Traveling Salesman ProblemSimilar Papers 제목 키워드 기반
A Discrete State Transition Algorithm for Generalized Traveling Salesman Problem
Generalized traveling salesman problem (GTSP) is an extension of classical traveling salesman problem (TSP), which is a combinatorial optimization problem and an NP-hard problem. In this paper, an efficient discrete stat…
Combinatorial OptimizationTraveling Salesman ProblemEfficient Bit Labeling in Factorization Machines with Annealing for Traveling Salesman Problem
To efficiently find an optimum parameter combination in a large-scale problem, it is a key to convert the parameters into available variables in actual machines. Specifically, quadratic unconstrained binary optimization …
Traveling Salesman ProblemGeneralized Nested Rollout Policy Adaptation
Nested Rollout Policy Adaptation (NRPA) is a Monte Carlo search algorithm for single player games. In this paper we propose to generalize NRPA with a temperature and a bias and to analyze theoretically the algorithms. Th…
Traveling Salesman ProblemAMR-to-text generation as a Traveling Salesman Problem
The task of AMR-to-text generation is to generate grammatical text that sustains the semantic meaning for a given AMR graph. We at- tack the task by first partitioning the AMR graph into smaller fragments, and then gener…
AMR-to-Text GenerationText GenerationTranslationTraveling Salesman ProblemTwo-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles
The Moving-Target Traveling Salesman Problem (MT-TSP) seeks a minimum cost trajectory for an agent that departs from a static depot, visits a set of moving targets, each within one of their assigned time windows, and ret…