Parallelization of the scatter search for the p-median problem

被引：48

作者：

García-López, F ^{[1
]}

Melián-Batista, B ^{[1
]}

Moreno-Pérez, JA ^{[1
]}

Moreno-Vega, JM ^{[1
]}

机构：

[1] Univ La Laguna, Dept Estadist IO & Computac, San Cristobal la Laguna 38271, Spain

来源：

PARALLEL COMPUTING | 2003年 / 29卷 / 05期

关键词：

parallelization; metaheuristics; scatter search; p-median problem;

D O I：

10.1016/S0167-8191(03)00043-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This article develops several strategies for the parallelization of the metaheuristic called scatter search, which is a population-based method that constructs solutions by combining others. Three types of parallelization have been proposed to achieve either an increase of efficiency or an increase of exploration. The procedures have been coded in C using OpenMP and compared in a shared memory machine with large instances. The obtained algorithms are tested on the p-median problem. (C) 2003 Elsevier Science B.V. All rights reserved.

引用

页码：575 / 589

页数：15

共 40 条

[1]

[Anonymous], 1997, OPENMP PROPOSED IND

[2]

[Anonymous], HDB APPL OPTIMIZATIO

[3] A NOTE ON SOLVING LARGE P-MEDIAN PROBLEMS [J].

BEASLEY, JE .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1985, 21 (02) :270-273

[4]

Brunschen C., 1999, P 1 EUR WORKSH OP EW, P21

[5] LOCATION OF BANK ACCOUNTS TO OPTIMIZE FLOAT - ANALYTIC STUDY OF EXACT AND APPROXIMATE ALGORITHMS [J].

CORNUEJOLS, G ;

FISHER, ML ;

NEMHAUSER, GL .

MANAGEMENT SCIENCE, 1977, 23 (08) :789-810

[6] Stabilized column generation [J].

du Merle, O ;

Villeneuve, D ;

Desrosiers, J ;

Hansen, P .

DISCRETE MATHEMATICS, 1999, 194 (1-3) :229-237

[7] DUAL-BASED PROCEDURE FOR UNCAPACITATED FACILITY LOCATION [J].

ERLENKOTTER, D .

OPERATIONS RESEARCH, 1978, 26 (06) :992-1009

[8] GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES [J].

FEO, TA ;

RESENDE, MGC .

JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) :109-133

[9] A DUAL-BOUNDED ALGORITHM FOR THE P-MEDIAN PROBLEM [J].

GALVAO, RD .

OPERATIONS RESEARCH, 1980, 28 (05) :1112-1121

[10] The parallel variable neighborhood search for the p-Median Problem [J].

García-López, F ;

Melián-Batista, B ;

Moreno-Pérez, JA ;

Moreno-Vega, JM .

JOURNAL OF HEURISTICS, 2002, 8 (03) :375-388

← 1 2 3 4 →