An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem

被引：54

作者：

Malik, Waqar

Rathinam, Sivakumar

Darbha, Swaroop ^{[1
]}

机构：

[1] Texas A&M Univ, Dept Mech Engn, College Stn, TX 77843 USA

[2] Univ Calif Berkeley, Dept Civil Engn, Berkeley, CA 94720 USA

来源：

OPERATIONS RESEARCH LETTERS | 2007年 / 35卷 / 06期

关键词：

approximation algorithms; travelling salesman; vehicle routing;

D O I：

10.1016/j.orl.2007.02.001

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we present an algorithm with an approximation factor of 2 for a Generalized, Multiple Depot, Multiple Travelling Salesman Problem (GMTSP) when the costs are symmetric and satisfy the triangle inequality. The algorithm requires finding a degree constrained minimum spanning tree which we compute using a Lagrangian relaxation. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：747 / 753

页数：7

共 26 条

[1] 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

[2]

Bellmore M., 1977, OPER RES, V25, P871

[3]

Chandler PR, 2002, P AMER CONTR CONF, V1-6, P1831, DOI 10.1109/ACC.2002.1023833

[4]

Chandler PR, 1998, P AMER CONTR CONF, P394, DOI 10.1109/ACC.1998.694698

[5]

CHAUDHURI K, 2005, P 8 INT WORKSH APPR, P26

[6]

CHAUDHURI K, 2006, P 33 INT C AUT LANG, P191

[7] A faster deterministic algorithm for minimum spanning trees [J].

Chazelle, B .

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, :22-34

[8]

CHRISTOFIDES N, 1976, 388 CARNEGIE MELLON

[9]

Cohen Edith, 1993, COMPLEXITY NUMERICAL, P74

[10]

DARBHA S, 2005, COMBINATORIAL MOTION

← 1 2 3 →