COST ALLOCATION - THE TRAVELING SALESMAN, BINPACKING, AND THE KNAPSACK

被引：19

作者：

DROR, M ^{[1
]}

机构：

[1] UNIV MONTREAL, CTR RECH TRANSPORTS, MONTREAL H3C 3J7, QUEBEC, CANADA

来源：

APPLIED MATHEMATICS AND COMPUTATION | 1990年 / 35卷 / 02期

关键词：

D O I：

10.1016/0096-3003(90)90116-K

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We examine the problem of cost allocation for the traveling-salesman problem (TSP). We note the significance of a "home" city in the TSP for designing cost allocation schemes, focusing on TSPs with triangular inequality. In addition, a similar cost allocation question is stated for the binpacking and the knapsack problems. © 1990.

引用

页码：191 / 207

页数：17

共 14 条

[1] BODIN L, 1983, COMPUT OPER RES, V10, P63, DOI 10.1016/0305-0548(83)90030-8
[2] DROR M, 1987, NAV RES LOG, V34, P891, DOI 10.1002/1520-6750(198712)34:6<891::AID-NAV3220340613>3.0.CO
[3] 2-J
[4] DROR M, 1985, PUBLICATION U MONTRE, V435
[5] FISHBURN PC, 1983, AM MATH MONTHLY JUN, P366
[6] Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[7] An effective implementation of the Lin-Kernighan traveling salesman heuristic
Helsgaun, K
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 126 (01) : 106 - 130
[8] INTEGER PROGRAMMING FORMULATION OF TRAVELING SALESMAN PROBLEMS
MILLER, CE
TUCKER, AW
ZEMLIN, RA
[J]. JOURNAL OF THE ACM, 1960, 7 (04) : 326 - 329
[9] Shapley L. S, 1981, P U OKL C COSTS ALL, P131
[10] Shapley Lloyd S, 1971, INT J GAME THEORY, V1, P11, DOI DOI 10.1007/BF01753431

← 1 2 →