An Efficient Genetic Algorithm for the p-Median Problem
Tóm tắt
We propose a new genetic algorithm for a well-known facility location problem. The algorithm is relatively simple and it generates good solutions quickly. Evolution is facilitated by a greedy heuristic. Computational tests with a total of 80 problems from four different sources with 100 to 1,000 nodes indicate that the best solution generated by the algorithm is within 0.1% of the optimum for 85% of the problems. The coding effort and the computational effort required are minimal, making the algorithm a good choice for practical applications requiring quick solutions, or for upper-bound generation to speed up optimal algorithms.
Tài liệu tham khảo
Avella, P. and tA. Sassano. (2001). “On the p-Median Polytope.” Mathematical Programming 89(3), 395–411.
Beasley, J.E. (1990). “OR-Library –Distributing Test Problems by Electronic Mail.” Journal of the Operational Research Society 41(11), 1069–1072.
Berman, O., tZ. Drezner, and G.O. Wesolowsky. (2002). “Locating Unreliable Service Facilities that Are Distance Sensitive.” Computers and Operations Research, in press.
Bozkaya, B., tJ. Zhang, and E. Erkut. (2002). “A Genetic Algorithm for the p-Median Problem.” In Z. Drezner and H. Hamacher (eds.), Facility Location: Applications and Theory. Berlin: Springer.
Chiyoshi, F. and tR.D. Galvão. (2000). “A Statistical Analysis of Simulated Annealing Applied to the p-Median Problem.” Annals of Operations Research 96, 61–74.
Cornuejols, G., tM.L. Fisher, and G.L. Nemhauser. (1977). “Location of Bank Accounts to Optimise Float: an Analytic Study of Exact and Approximate Algorithms.” Management Science 23, 789–810.
Daskin, M.S. (1995). Network and Discrete Location: Models, Algorithms and Applications. New York: Wiley (SITATION can be downloaded from http://users.iems.nwu.edu/~msdaskin/BookSoftware.htm –as of July 2002).
Densham, P.J. and tG. Rushton. (1992). “AMore Efficient Heuristic for Solving Large p-Median Problems.” Papers in Regional Science 71, 307–329.
Dibble, C. and tP.J. Densham. (1993). “Generating Interesting Alternatives in GIS and SDSS Using Genetic Algorithms.” In GIS/LIS 1993.
Dowsland, K.A. (1996). “Genetic Algorithms –A Tool for OR?” Journal of Operational Research Society 47, 550–561.
Erkut, E., tT. Myroon, and K. Strangway. (2000). “TransAlta Redesigns Its Service Delivery Network.” Interfaces 30(2), 54–69.
Fitzsimmons, J.A. and tA.L. Austin. (1983). “AWarehouse Location Model Helps Texas Comptroller Select Out-of-State Audit Offices.” Interfaces 13(5), 40–46.
Galvão, R.D. (1980). “A Dual-Bounded Algorithm for the p-Median Problem.” Operations Research 28(5), 1112–1121.
Galvão, R.D. and tL.A. Raggi. (1989). “A Method for Solving to Optimality Uncapacitated Location Problems.” Annals of Operations Research 18, 225–244.
Galvão, R.D. and tC. ReVelle. (1996). “A Lagrangean Heuristic for the Maximal Covering Location Problem.” European Journal of Operations Research 88, 114–123.
Hosage, C.M. and tM.F. Goodchild. (1986). “Discrete Space Location–Allocation Solutions from Genetic Algorithms.” Annals of Operations Research 6, 35–46.
Koerkel, M. (1989). “On the Exact Solution of Large-Scale Simple Plant Location Problems.” European Journal of Operations Research 39, 157–173.
Moreno-Perez, J.A., tJ.M. Moreno-Vega, and N. Mladenovic. (1994). “Tabu Search and Simulated Annealing in p-Median Problem.” In Proceedings of the Canadian Operational Research Society Conference, Montreal.
Murray, A.T. and R.L. Church. (1996). “Applying Simulated Annealing to Location-Planning Models.” Journal of Heuristics 2, 31–53.
Narula, S.C., tU.I. Ogbu, and H.M. Samuelsson. (1997). “An Algorithm for the p-Median Problem.” Operations Research 25, 709–712.
Pizzolato, N.D. (1994). “A Heuristic for Large-Size p-Median Location Problems with Application to School Location.” Annals of Operations Research, 50 473–485.
Reeves, C.R. (1993). “Genetic Algorithms.” In C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems. Chapter 4, pp. 151–196.
ReVelle, C. and tR. Swain. (1970). “Central Facilities Location.” Geographical Analysis 2, 30–42.
Rolland, E., tD.A. Schilling, and J.R. Current. (1997). “An Efficient Tabu Search Procedure for the p-Median Problem.” European Journal of Operational Research 96, 329–342.
Rosing, K.E. and tC.S. ReVelle. (1997). “Heuristic Concentration: Two-Stage Solution Construction.” European Journal of Operational Research 97, 75–86.
Rosing, K.E., tC.S. ReVelle, and D.A. Schilling. (1999). “A Gamma Heuristic for the p-Median Problem.” European Journal of Operational Research 117, 522–532.
Teitz, M.B. and tP. Bart. (1968). “Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph.” Operations Research 16, 955–961.