HEURISTICS FOR UNEQUAL WEIGHT DELIVERY PROBLEMS WITH A FIXED ERROR GUARANTEE

被引：49

作者：

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 [J].

BEASLEY, JE .

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 [J].

CHRISTOF.N ;

EILON, S .

OPERATIONAL RESEARCH QUARTERLY, 1969, 20 (03) :309-&

[8] EXACT ALGORITHMS FOR THE VEHICLE-ROUTING PROBLEM, BASED ON SPANNING TREE AND SHORTEST-PATH RELAXATIONS [J].

CHRISTOFIDES, N ;

MINGOZZI, A ;

TOTH, P .

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 →