A Memetic Algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem

被引：79

作者：

Bontoux, Boris ^{[1
]}

Artigues, Christian ^{[2
]}

Feillet, Dominique ^{[3
]}

机构：

[1] Univ Avignon & Pays Vaucluse, Lab Informat Avignon, F-84911 Avignon 9, France

[2] Univ Toulouse, CNRS, LAAS, F-31077 Toulouse, France

[3] CMP Georges Charpak, Ecole Mines St Etienne, F-13541 Gardanne, France

来源：

COMPUTERS & OPERATIONS RESEARCH | 2010年 / 37卷 / 11期

关键词：

Genetic Algorithm; Traveling Salesman Problem; Large neighborhood search; EFFICIENT TRANSFORMATION; OPTIMIZATION;

D O I：

10.1016/j.cor.2009.05.004

中图分类号：

TP39 [计算机的应用];

学科分类号：

080201 [机械制造及其自动化];

摘要：

The Generalized Traveling Salesman Problem (GTSP) is a generalization of the well-known Traveling Salesman Problem (TSP), in which the set of cities is divided into mutually exclusive clusters. The objective of the GTSP consists in visiting each cluster exactly once in a tour, while minimizing the sum of the routing costs. This paper addresses the solution of the GTSP using a Memetic Algorithm. The originality of our approach rests on the crossover procedure that uses a large neighborhood search. This algorithm is compared with other algorithms on a set of 54 standard test problems with up to 217 clusters and 1084 cities. Results demonstrate the efficiency of our algorithm in both solution quality and computation time. (C) 2009 Elsevier Ltd. All rights reserved.

引用

页码：1844 / 1852

页数：9

共 35 条

[1]

A survey of very large-scale neighborhood search techniques [J].

Ahuja, RK ;

Ergun, Ö ;

Orlin, JB ;

Punnen, AP .

DISCRETE APPLIED MATHEMATICS, 2002, 123 (1-3) :75-102

[2]

[Anonymous], 2005, RECENT ADV MEMETIC A

[3]

[Anonymous], 1957, DYNAMIC PROGRAMMING

[4]

[Anonymous], 1969, RIRO B

[5]

[Anonymous], 1999, Genetic Algorithms: Concepts and Designs

[6]

Transformations of generalized ATSP into ATSP [J].

Ben-Arieh, D ;

Gutin, G ;

Penn, M ;

Yeo, A ;

Zverovitch, A .

OPERATIONS RESEARCH LETTERS, 2003, 31 (05) :357-365

[7]

Ant colony optimization for the traveling purchaser problem [J].

Bontoux, Boris ;

Feillet, Dorninique .

COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (02) :628-637

[8]

An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs [J].

Dimitrijevic, V ;

Saric, Z .

INFORMATION SCIENCES, 1997, 102 (1-4) :105-110

[9]

An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems [J].

Feillet, D ;

Dejax, P ;

Gendreau, M ;

Gueguen, C .

NETWORKS, 2004, 44 (03) :216-229

[10]

FISCHETTI M, 1997, OPERATIONS RES, V45

← 1 2 3 4 →