Application of the noising method to the travelling salesman problem

被引：20

作者：

Charon, I ^{[1
]}

Hudry, O ^{[1
]}

机构：

[1] Ecole Natl Super Telecommun, F-75634 Paris 13, France

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2000年 / 125卷 / 02期

关键词：

combinatorial optimization; noising method; simulated annealing; metaheuristics; travelling salesman problem;

D O I：

10.1016/S0377-2217(99)00457-9

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we study the application of the noising method, a recent combinatorial optimization metaheuristic, to the Travelling Salesman Problem (TSP). We first detail the features of the noising method in order to adapt it to the TSP. Then we "experimentally" compare it to the simulated annealing method, and we study its sensitiveness to different parameters involved in its design. Two types of TSPs have been considered: the randomly weighted TSP, for which the weights of the edges are randomly chosen, and the Euclidean TSP, for which the vertices belong to the Euclidean plane and where the weights of the edges are given by the Euclidean distances between the vertices. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：266 / 277

页数：12

共 15 条

[1]

Aarts E., 1997, LOCAL SEARCH COMBINA, P91, DOI DOI 10.1038/S41598-021-83315-9

[2]

AARTS E, 1997, LOCAL SEARCH COMBINA

[3]

[Anonymous], P CAMB PHILO SOC, DOI DOI 10.1017/S0305004100034095

[4]

[Anonymous], 1987, SIMULATED ANNEALING

[5] THE N-CITY TRAVELING SALESMAN PROBLEM - STATISTICAL-MECHANICS AND THE METROPOLIS ALGORITHM [J].

BONOMI, E ;

LUTTON, JL .

SIAM REVIEW, 1984, 26 (04) :551-568

[6] THE NOISING METHOD - A NEW METHOD FOR COMBINATORIAL OPTIMIZATION [J].

CHARON, I ;

HUDRY, O .

OPERATIONS RESEARCH LETTERS, 1993, 14 (03) :133-137

[7]

CHARON I, UNPUB TOTALLY SELF T

[8]

CHARON I, UNPUB NOISING METHOD

[9]

Johnson DS., 1997, Local search in combinatorial optimization, P215, DOI DOI 10.1108/01445150910987763

[10]

Lawler E.L., 1985, TRAVELLING SALESMAN

← 1 2 →