The p-median problem is difficult to solve and many heuristic methods have been developed. This paper discusses a new hybridization approach in which existing heuristics are used as ‘experts’ in a problem-solving team where they cooperate by sharing their solutions with each other. This approach is demonstrated using two heuristics called the ‘vertex substitution method’ and ‘simulated annealing’. Five cooperation strategies are designed and implemented using an application program interface for parallel programming. Computational experiments show that the strategy named ‘parallel consensus’ can significantly improve the quality of solutions found when compared with the original heuristics. The results also show significant speedups of the program in a multicore parallel computing environment.
AartsE H LKorstJ H Mvan LaarhovenP J M, 2003, “Simulated annealing”, in Local Search in Combinatorial Optimization Eds AartsE H LLenstraJ K (Princeton University Press, Princeton, NJ)
2.
AlpODreznerZErkutE, 2003, “An efficient genetic algorithm for the p-median problem”Annals of Operations Research12221–42
3.
AxelrodR, 1997The Complexity of Cooperation: Agent-based Models of Competition and Collaboration (Princeton University Press, Princeton, NJ)
4.
BeasleyJ E, 1985“A note on solving large p-median problems”European Journal of Operational Research21270–273
5.
BlumCRoliA, 2003, “Metaheuristics in combinatorial optimization: Overview and conceptual comparison”ACM Computing Surveys35268–308
6.
BrillE DJr, 1979, “The use of optimization models in public-sector planning”Management Science25413–422
7.
Cantú-PazE, 2000Efficient and Accurate Parallel Genetic Algorithms (Kluwer Academic, Boston, MA)
8.
CernyV, 1985, “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm”Journal of Optimization Theory and Application45(1) 41–51
ChiyoshiFGalvãoR D, 2000, “A statistical analysis of simulated annealing applied to the p-median problem”Annals of Operations Research9661–74
11.
ChurchR L, 2008, “BEAMR: An exact and approximate model for the p-median problem”Computers and Operations Research35417–426
12.
ChurchR LSorensenP, 1996, “Integrating normative location models into GIS: Problems and prospects with the p-median model”, in Spatial Analysis: Modelling in a GIS Environment Eds LongleyPBattyM (Longman Geoinformation, Harlow, Essex) pp 167–183
13.
ChurchR LWeaverJ R, 1986, “Theoretical links between median and coverage location problems”Annals of Operations Research61–19
14.
CrainicT, 2002, “Parallel computation, co-operation, tabu search”, in Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search Eds RegoCAlidaeeB (Kluwer Academic, Norwell, MA) pp 283–302
15.
CrainicT GToulouseM, 2008, “Explicit and emergent cooperation schemes for search algorithms”, in Learning and Intelligent Optimization Eds ManiezzoVBattitiRWatsonJ-P (Springer, Berlin) pp 95–109
16.
CrainicT GGendreauMHansenPMladenovićN, 2004, “Cooperative parallel variable neighborhood search for the p-median problem”Journal of Heuristics10293–314
17.
CungV-DMartinsS LRibeiroC CRoucairolC, 2002, “Strategies for the parallel implementations of metaheuristics”, in Essays and Surveys in Metaheuristics Eds RibeiroC CHansenP (Kluwer Academic, Norwell, MA) pp 263–308
18.
DaskinM S, 1995Network and Discrete Location: Models, Algorithms, and Applications (John Wiley, New York)
19.
DenshamP JRushtonG, 1992a, “Strategies for solving large location-allocation problems by heuristic methods”Environment and Planning A24289–304
20.
DenshamP JRushtonG, 1992b, “A more efficient heuristic for solving large p-median problems”Papers in Regional Science41307–329
21.
DomínquezEMuñozJ, 2008, “A neural model for the p-median problem”Computers and Operations Research35404–416
22.
Estivill-CastroVTorres-VelázquezR, 1999, “Hybrid genetic algorithm for solving the p-median problem”, in Second Asia-Pacific Conference on Simulated Evolution and Learning, SEAL '98 Ed. YaoX (Springer, Berlin) pp 18–25
23.
FosterI, 1995Designing and Building Parallel Programs (Addison-Wesley, Reading, MA)
24.
FosterIKesselmanC (Eds.), 2003The Grid 2: Blueprint for a New Computing Infrastructure2nd edition (Morgan Kaufmann, San Francisco, CA)
25.
García-LópezFMelían-BatistaBMoreno-PérezJ AMoreno-VegaJ M, 2002, “The parallel variable neighborhood search for the p-median problem.”Journal of Heuristics8375–388
26.
García-LópezFMelían-BatistaBMoreno-PérezJ AMoreno-VegaJ M, 2003, “Parallelization of the scatter search for the p-median problem”Parallel Computing29575–589
27.
GareyM RJohnsonD S, 1979Computers and Intractability: A Guide to the Theory of NP-completeness (W H Freeman, San Francisco, CA)
28.
GendreauMLaporteGSemetF, 1997, “Solving an ambulance location model by tabu search”Location Science5(2) 75–88
29.
GorderP F, 2007, “Multicore processors for science and engineering”Computing in Science and Engineering9(2) 3–7
30.
HakimiS L, 1964, “Optimum location of switching centers and the absolute centers and medians of a graph”Operations Research12450–459
31.
HakimiS L, 1965, “Optimum distribution of switch centers in a communication network and some related graph theoretic problems”Operations Research13462–475
32.
HanJKamberMTungA K H2001, “Spatial clustering methods in data mining: A survey”, in Geographic Data Mining and Knowledge Discovery Eds MillerHHanJ (Taylor and Francis, London) pp 188–217
33.
HansenPMladenovićN, 1997, “Variable neighborhood search for the p-median”Location Science5207–226
34.
HillsmanE L, 1984, “The p-median structure as a unified linear model for location-allocation analysis”Environment and Planning A16305–318
35.
ILOG, 2007ILOG CPLEX 11 User's ManualILOG Inc., Mountain View, CA
36.
JohnsonD SAragonC RMcGeochL ASchevonC, 1989, “Optimization by simulated annealing: An experimental evaluation; part I, graph partitioning”Operations Research37865–892
37.
KarivOHakimiS L, 1979, “An algorithmic approach for network location problems II: The p-medians”SIAM Journal on Applied Mathematics37539–560
38.
KirkpatrickSGelattC DVecchiM PJr, 1983, “Optimization by simulated annealing”Science220671–680
39.
MetropolisNRosenbluthA WRosenbluthMTellerA HTellerE, 1953, “Equation of state calculations by fast computing machines”Journal of Chemical Physics211087–1092
40.
MladenovićNMoreno-PérezJMoreno-VegaJ, 1995“Tabu search in solving p-facility location-allocation problems”, G-95-38, Les Cahiers du GERAD, Montreal
41.
MladenovićNBrimbergJHansenPMoreno-PérezJ A, 2007“The p-median problem: A survey of metaheuristic approaches”European Journal of Operational Research179927–939
42.
MurrayA TChurchR L, 1996, “Applying simulated annealing to location-planning models”Journal of Heuristics2(1) 31–53
43.
PageS E, 2007The Difference: How the Power of Diversity Creates Better Groups, Firms, Schools, and Societies (Princeton University Press, Princeton, NJ)
44.
ResendeM G CWerneckR F, 2003, “On the implementation of a swap-based local search procedure for the p-median problem”, in Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments Ed. LadnerR E, pp 119–127, SIAM
45.
ResendeM G CWerneckR E, 2004, “A hybrid heuristic for the p-median problem”Journal of Heuristics1059–88
RosingK E, 1997, “An empirical investigation of the effectiveness of a vertex substitution heuristic”Environment and Planning B: Planning and Design2459–67
48.
RosingK EReVelleC S, 1997, “Heuristic concentration: Two stage solution construction”European Journal of Operational Research9775–86
49.
RosingK EHillsmanE LRosing-VogelaarH, 1979“A note comparing optimal and heuristic solutions to the p-median problem”Geographical Analysis1186–89
50.
SimonH A, 1960The New Science of Management Decision (Harper and Row, New York)
51.
SurowieckiJ, 2004The Wisdom of Crowds (Anchor Books, New York)
52.
TapscottDWilliamsA D, 2008Wikinomics: How Mass Collaboration Changes Everything (Portfolio, New York)
53.
TeitzM BBartP, 1968, “Heuristic methods for estimating the generalized vertex median of a weighted graph”Operations Research16955–961
54.
VerhoevenMAartsE, 1995, “Parallel local search”Journal of Heuristics1(1) 43–65
55.
VossS, 1996“A reverse elimination approach for the p-median problem”Studies in Locational Analysis849–58
56.
WhitakerR, 1983, “A fast algorithm for the greedy interchange of large-scale clustering and median location problems”INFOR2195–108
57.
WolpertDMacreadyW, 1997, “No free lunch theorems for optimization”IEEE Transactions on Evolutionary Computation1(1) 67–82
58.
XiaoNArmstrongM P, 2003, “A specialized island model and its application in multiobjective optimization”, in Genetic and Evolutionary Computation—GECCO 2003 Eds Cantú-PazE (Springer, Berlin) pp 1530–1540
