HEURISTICS FOR UNEQUAL WEIGHT DELIVERY PROBLEMS WITH A FIXED ERROR GUARANTEE

被引：48

作者：

ALTINKEMER, K ^{[1
]}

GAVISH, B ^{[1
]}

机构：

[1] UNIV ROCHESTER, WILLIAM E SIMON GRAD SCH BUSINESS ADM, ROCHESTER, NY 14627 USA

来源：

OPERATIONS RESEARCH LETTERS | 1987年 / 6卷 / 04期

关键词：

DATA PROCESSING - Critical Path Analysis - MATHEMATICAL PROGRAMMING - MATHEMATICAL TECHNIQUES - Heuristic - SCHEDULING - Mathematical Models;

D O I：

10.1016/0167-6377(87)90012-5

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The worst case error performance is given as a bound on the worst case ratio of the cost of the heuristic solution to the cost of the optimal solution. A fully polynomial procedure which consists of applying the optimal partitioning to a travelling salesman tour generated by Christofides' heuristic has a worst case error bound of 3. 5-3/Q where Q is the capacity limit of the vehicles. When optimal partitioning is applied to an optimal travelling salesman tour, the worst case error bound becomes 3-2/Q.

引用

页码：149 / 158

页数：10

共 22 条

[1] ALTINKEMER K, IN PRESS MANAGEMENT
[2] ALTINKEMER K, 1986, PARALLEL SAVINGS BAS
[3] ALTINKEMER K, 1985, QM8536 U ROCH GRAD S
[4] ALTINKEMER K, IN PRESS HEURISTICS
[5] ROUTE 1ST - CLUSTER 2ND METHODS FOR VEHICLE-ROUTING
BEASLEY, JE
[J]. OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1983, 11 (04): : 403 - 408
[6] BODIN L, 1983, COMPUT OPER RES, V10, P63, DOI 10.1016/0305-0548(83)90030-8
[7] AN ALGORITHM FOR VEHICLE-DISPATCHING PROBLEM
CHRISTOF.N
EILON, S
[J]. OPERATIONAL RESEARCH QUARTERLY, 1969, 20 (03) : 309 - &
[8] EXACT ALGORITHMS FOR THE VEHICLE-ROUTING PROBLEM, BASED ON SPANNING TREE AND SHORTEST-PATH RELAXATIONS
CHRISTOFIDES, N
MINGOZZI, A
TOTH, P
[J]. MATHEMATICAL PROGRAMMING, 1981, 20 (03) : 255 - 282
[9] Christofides N, 1979, VEHICLE ROUTING PROB
[10] Christofides N., 1976, 388 CARN MELL U GRAD

← 1 2 3 →