A novel method for solving the multiple traveling salesmen problem with multiple depots

被引：14

作者：

Hou MengShu ^{[1
]}

Liu DaiBo ^{[1
]}

机构：

[1] Univ Elect Sci & Technol China, Sch Comp Sci & Engn, Chengdu 610054, Peoples R China

来源：

CHINESE SCIENCE BULLETIN | 2012年 / 57卷 / 15期

基金：

中国国家自然科学基金;

关键词：

combinatorial optimization; traveling salesman problem; MTSP; algorithm; COLUMNAR COMPETITIVE MODEL; HYBRID GENETIC ALGORITHM; OPTIMIZATION;

D O I：

10.1007/s11434-012-5162-7

中图分类号：

O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

Multi-traveling salesman problem (MTSP) is an extension of traveling salesman problem, which is a famous NP hard problem, and can be used to solve many real world problems, such as railway transportation, routing and pipeline laying. In this paper, we analyze the general properties of MTSP, and find that the multiple depots and closed paths in the graph is a big issue for MTSP. Thus, a novel method is presented to solve it. We transform a complicated graph into a simplified one firstly, then an effective algorithm is proposed to solve the MTSP based on the simplified results. In addition, we also propose a method to optimize the general results by using 2-OPT. Simulation results show that our method can find the global solution for MTSP efficiently.

引用

页码：1886 / 1892

页数：7

共 31 条

[1]

ALI AI, 1986, DISCRETE APPL MATH, V13, P259, DOI 10.1016/0166-218X(86)90087-9

[2]

ANGEL RD, 1972, MANAGE SCI B-APPL, V18, pB279

[3] A distributed robotic control system based on a temporal self-organizing neural network [J].

Barreto, GA ;

Araújo, AFR ;

Dücker, C ;

Ritter, H .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS, 2002, 32 (04) :347-357

[4] The multiple traveling salesman problem: an overview of formulations and solution procedures [J].

Bektas, T .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2006, 34 (03) :209-219

[5]

Brumitt BL, 1996, IEEE INT CONF ROBOT, P2396, DOI 10.1109/ROBOT.1996.506522

[6] A new approach to solving the multiple traveling salesperson problem using genetic algorithms [J].

Carter, Arthur E. ;

Ragsdale, Cliff T. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 175 (01) :246-257

[7] Optimization with extremal dynamics for the traveling salesman problem [J].

Chen, Yu-Wang ;

Lu, Yong-Zai ;

Chen, Peng .

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2007, 385 (01) :115-123

[8] See the forest before the trees: Fine-tuned learning and its application to the traveling salesman problem [J].

Coy, SP ;

Golden, BL ;

Runger, GC ;

Wasil, EA .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A-SYSTEMS AND HUMANS, 1998, 28 (04) :454-464

[9] A METHOD FOR SOLVING TRAVELING-SALESMAN PROBLEMS [J].

CROES, GA .

OPERATIONS RESEARCH, 1958, 6 (06) :791-812

[10] Ant system: Optimization by a colony of cooperating agents [J].

Dorigo, M ;

Maniezzo, V ;

Colorni, A .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (01) :29-41

← 1 2 3 4 →