On the complexity of the k-customer vehicle routing problem

被引：17

作者：

Hassin, R ^{[1
]}

Rubinstein, S ^{[1
]}

机构：

[1] Tel Aviv Univ, Sch Math Sci, Dept Stat & Operat Res, IL-69978 Tel Aviv, Israel

来源：

OPERATIONS RESEARCH LETTERS | 2005年 / 33卷 / 01期

关键词：

approximation algorithms; vehicle routing problem;

D O I：

10.1016/j.orl.2004.04.003

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We investigate the complexity of the k-CUSTOMER VEHICLE ROUTING PROBLEM: Given an edge weighted graph, the problem requires to compute a minimum weight set of cyclic routes such that each contains a distinguished depot vertex and at most other k customer vertices, and every customer belongs to exactly one route. (C) 2004 Elsevier B.V. All fights reserved.

引用

页码：71 / 76

页数：6

共 7 条

[1] Ahuja RK, 1993, NETWORK FLOWS THEORY
[2] Bazgan C, 2003, LECT NOTES COMPUT SC, V2653, P277
[3] BOUNDS AND HEURISTICS FOR CAPACITATED ROUTING-PROBLEMS
HAIMOVICH, M
KAN, AHGR
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1985, 10 (04) : 527 - 542
[4] Haimovich M, 1988, VEHICLE ROUTING METH, P47
[5] Karp R. M., 1972, COMPLEXITY COMPUTER, P85, DOI DOI 10.1007/978-1-4684-2001-2_9
[6] Kirkpatrick D., 1978, P 10 ANN ACM S THEOR, P240
[7] On the k-path partition of graphs
Steiner, G
[J]. THEORETICAL COMPUTER SCIENCE, 2003, 290 (03) : 2147 - 2155

← 1 →