A NOTE ON SOLVING LARGE P-MEDIAN PROBLEMS

被引：102

作者：

BEASLEY, JE

机构：

[1] Imperial Coll of Science &, Technology, Dep of Management, Science, London, Engl, Imperial Coll of Science & Technology, Dep of Management Science, London, Engl

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1985年 / 21卷 / 02期

关键词：

COMPUTER PROGRAMMING - Algorithms - MATHEMATICAL TECHNIQUES - Trees;

D O I：

10.1016/0377-2217(85)90040-2

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In a previous paper the author presented a tree search algorithm for the p-median problem, the problem of locating p facilities (medians) on a network, which was based upon Langrangean relaxation and subgradient optimization. That algorithm solved (optimally) problems with an arbitrary number of medians and having up to 200 vertices that it is possible to enhance that algorithm to solve (optimally) problems having up to 900 vertices using the Cray-1S computer.

引用

页码：270 / 273

页数：4

共 7 条

[1] PARA-MEDIANS AND MULTI-MEDIANS [J].

BOFFEY, TB ;

KARKAZIS, J .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1984, 35 (01) :57-64

[2] A TREE-SEARCH ALGORITHM FOR THE PARA-MEDIAN PROBLEM [J].

CHRISTOFIDES, N ;

BEASLEY, JE .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1982, 10 (02) :196-204

[3] SOLVING LARGE-SCALE ZERO-ONE LINEAR-PROGRAMMING PROBLEMS [J].

CROWDER, H ;

JOHNSON, EL ;

PADBERG, M .

OPERATIONS RESEARCH, 1983, 31 (05) :803-834

[4] THE LAGRANGIAN-RELAXATION METHOD FOR SOLVING INTEGER PROGRAMMING-PROBLEMS [J].

FISHER, ML .

MANAGEMENT SCIENCE, 1981, 27 (01) :1-18

[5] ALGORITHM-97 - SHORTEST PATH [J].

FLOYD, RW .

COMMUNICATIONS OF THE ACM, 1962, 5 (06) :345-345

[6]

Held M., 1974, Mathematical Programming, V6, P62, DOI 10.1007/BF01580223

[7] HEURISTIC METHODS FOR ESTIMATING GENERALIZED VERTEX MEDIAN OF A WEIGHTED GRAPH [J].

TEITZ, MB ;

BART, P .

OPERATIONS RESEARCH, 1968, 16 (05) :955-&

← 1 →