An analysis of the extended Christofides heuristic for the k-depot TSP

被引：21

作者：

Xu, Zhou ^{[1
]}

Xu, Liang ^{[1
]}

Rodrigues, Brian ^{[2
]}

机构：

[1] Hong Kong Polytech Univ, Fac Business, Dept Logist & Maritime Studies, Hong Kong, Hong Kong, Peoples R China

[2] Singapore Management Univ, Lee Kong Chian Sch Business, Singapore, Singapore

来源：

OPERATIONS RESEARCH LETTERS | 2011年 / 39卷 / 03期

关键词：

Approximation algorithms; Christofides heuristic; Multiple depots; TSP; MULTIPLE DEPOT; ALGORITHM;

D O I：

10.1016/j.orl.2011.03.002

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study an extension of the classical traveling salesman problem (TSP) to a situation with k >= 2 depots at each of which a distinct salesman is based. We show that a non-trivial extension of the well-known Christofides heuristic has a tight approximation ratio of 2 - 1/k, which improves on the known 2-approximation algorithm from the literature. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：218 / 223

页数：6

共 18 条

[1]

[Anonymous], 1979, COMPUTERS INTRACTABI

[2]

[Anonymous], 5 3 APPROXIMATION AL

[3]

[Anonymous], 1976, WORST CASE ANAL NEW

[4] Approximations for minimum and min-max vehicle routing problems [J].

Arkin, EM ;

Hassin, R ;

Levin, A .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2006, 59 (01) :1-18

[5]

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

[6]

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

[7] ARC ROUTING-PROBLEMS .1. THE CHINESE POSTMAN PROBLEM [J].

EISELT, HA ;

GENDREAU, M ;

LAPORTE, G .

OPERATIONS RESEARCH, 1995, 43 (02) :231-242

[8] A variation of the generalized assignment problem arising in the New Zealand dairy industry [J].

Foulds, LR ;

Wilson, JM .

ANNALS OF OPERATIONS RESEARCH, 1997, 69 (0) :105-114

[9] New assignment algorithms for the multi-depot vehicle routing problem [J].

Giosa, ID ;

Tansini, I ;

Viera, IO .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2002, 53 (09) :977-984

[10]

Korte B, 2008, ALGORITHMS COMB, V21, P1

← 1 2 →