Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán di truyền lai với lưu trữ giải pháp cho bài toán $$(r|p)$$ -tâm phân rời
Tóm tắt
Trong bài báo này, chúng tôi đề xuất một thuật toán di truyền lai cho bài toán $$(r|p)$$ -tâm phân rời. Chúng tôi xem xét bài toán định vị cơ sở cạnh tranh, trong đó hai công ty không hợp tác tham gia vào một thị trường theo thứ tự và cạnh tranh để giành thị phần. Quyết định viên đầu tiên, được gọi là lãnh đạo, muốn tối đa hóa thị phần của mình khi biết rằng sẽ có một người theo sau tham gia vào thị trường tương tự. Do đó, để đánh giá giải pháp của lãnh đạo, cần giải quyết một bài toán con tương ứng của người theo sau, và tổng thể bài toán vì vậy trở thành một bài toán tối ưu hóa hai cấp. Vấn đề này là NP-đầy đủ, tức là khó hơn bất kỳ bài toán nào trong NP (nếu $$\hbox {P}\not =\hbox {NP}$$). Một phương pháp heuristics được sử dụng, dựa trên thuật toán di truyền với tìm kiếm tabu làm quy trình cải thiện cục bộ và một kho lưu trữ giải pháp hoàn chỉnh. Kho lưu trữ được sử dụng để lưu trữ và chuyển đổi các giải pháp đã được thăm dò nhằm tránh việc đánh giá lại không cần thiết và tốn kém. Các phương pháp đánh giá giải pháp khác nhau được kết hợp thành một phương pháp đánh giá đa cấp hiệu quả. Thuật toán được thử nghiệm trên các bộ dữ liệu chuẩn đã biết với cả các trường hợp Euclidean và không Euclidean, cũng như trên các trường hợp mới được tạo ra lớn hơn. Đặc biệt, trên các trường hợp Euclidean, thuật toán của chúng tôi có khả năng vượt qua các phương pháp heuristics hiện đại trước đó về chất lượng giải pháp và thời gian thực hiện trong hầu hết các trường hợp.
Từ khóa
#thuật toán di truyền #tối ưu hóa hai cấp #bài toán định vị cơ sở #phương pháp heuristics #kho lưu trữ giải phápTài liệu tham khảo
Alekseeva, E., Kochetov, Y.: Matheuristics and exact methods for the discrete \((r|p)\)-centroid problem. In: Talbi, E.G. (ed.) Metaheuristics for Bi-Level Optimization, Studies in Computational Intelligence, vol. 482, pp. 189–219. Springer, Berlin (2013)
Alekseeva, E., Kochetova, N., Kochetov, Y., Plyasunov, A.: A hybrid memetic algorithm for the competitive \(p\)-median problem. In: Bakhtadze, N., Dolgui, A. (eds.) Information Control Problems in Manufacturing, vol. 13, pp. 1533–1537. International Federation of Automatic Control, Salvador (2009)
Alekseeva, E., Kochetova, N., Kochetov, Y., Plyasunov, A.: Heuristic and exact methods for the discrete \((r |p)\)-centroid problem. In: Cowling, P., Merz, P. (eds.) Evolutionary Computation in Combinatorial Optimization, LNCS, vol. 6022, pp. 11–22. Springer, Berlin (2010)
Bhadury, J., Eiselt, H., Jaramillo, J.: An alternating heuristic for medianoid and centroid problems in the plane. Comput. Oper. Res. 30(4), 553–565 (2003)
Biesinger, B., Hu, B., Raidl, G.: An evolutionary algorithm for the leader-follower facility location problem with proportional customer behavior. In: Pardalos, P.M., Resende, M.G., Vogiatzis, C., Walteros, J.L. (eds.) Learning and Intelligent Optimization, Lecture Notes in Computer Science, pp. 203–217. Springer, Berlin (2014)
Campos-Rodríguez, C., Moreno-Pérez, J., Noltemeier, H., Santos-Peñate, D.: Two-swarm pso for competitive location problems. In: Krasnogor, N., Melián-Batista, M., Pérez, J., Moreno-Vega, J., Pelta, D. (eds.) Nature Inspired Cooperative Strategies for Optimization (NICSO 2008), Studies in Computational Intelligence, vol. 236, pp. 115–126. Springer, Berlin (2009)
Campos-Rodríguez, C., Moreno-Pérez, J.A., Santos-Peñate, D.: Particle swarm optimization with two swarms for the discrete \((r|p)\)-centroid problem. In: Moreno-Díaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) Computer Aided Systems Theory (EUROCAST 2011), LNCS, vol. 6927, pp. 432–439. Springer, Berlin (2012)
Davydov, I., Kochetov, Y., Carrizosa, E.: VNS heuristic for the centroid problem on the plane. Electron. Notes Discret. Math. 39, 5–12 (2012)
Davydov, I., Kochetov, Y., Mladenovic, N., Urosevic, D.: Fast metaheuristics for the discrete \((r|p)\)-centroid problem. Autom. Remote Control 75(4), 677–687 (2014a)
Davydov, I., Kochetov, Y., Plyasunov, A.: On the complexity of the \((r|p)\)-centroid problem in the plane. TOP 22(2), 614–623 (2014b)
Drezner, T.: Optimal continuous location of a retail facility, facility attractiveness, and market share: an interactive model. J. Retail. 70(1), 49–64 (1994)
Drezner, T.: Location of multiple retail facilities with limited budget constraints in continuous space. J. Retail. Consum. Serv. 5(3), 173–184 (1998)
Drezner, T., Drezner, Z., Salhi, S.: Solving the multiple competitive facilities location problem. Eur. J. Oper. Res. 142(1), 138–151 (2002)
Ghosh, A., Craig, C.: A location allocation model for facility planning in a competitive environment. Geogr. Anal. 16(1), 39–51 (1984)
Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York (1997)
Hakimi, S.: On locating new facilities in a competitive environment. Eur. J. Oper. Res. 12(1), 29–35 (1983)
Hotelling, H.: Stability in competition. Econ. J. 39(153), 41–57 (1929)
Hu, B., Raidl, G.: An evolutionary algorithm with solution archives and bounding extension for the generalized minimum spanning tree problem. In: Soule, T. (ed.) Proceedings of the 14th annual conference on genetic and evolutionary computation (GECCO), pp. 393–400. ACM Press, Philadelphia (2012)
Kochetov, Y., Kochetova, N., Plyasunov, A.: A matheuristic for the leader-follower facility location and design problem. In: Lau H, Van Hentenryck P, Raidl G (eds) Proceedings of the 10th metaheuristics international conference (MIC 2013), Singapore, pp 32/1–32/3 (2013)
Kress, D., Pesch, E.: Sequential competitive location on networks. Eur. J. Oper. Res. 217(3), 483–499 (2012)
Laporte, G., Benati, S.: Tabu search algorithms for the \((r|x_p)\)-medianoid and \((r|p)\)-centroid problems. Locat. Sci. 2, 193–204 (1994)
Mladenović, N., Brimberg, J., Hansen, P., Moreno-Pérez, J.A.: The p-median problem: A survey of metaheuristic approaches. Eur. J. Oper. Res. 179(3), 927–939 (2007)
Noltemeier, H., Spoerhase, J., Wirth, H.C.: Multiple voting location and single voting location on trees. Eur. J. Oper. Res. 181(2), 654–667 (2007)
Raidl, G., Hu, B.: Enhancing genetic algorithms by a trie-based complete solution archive. In: Cowling, P., Merz, P. (eds.) Evolutionary Computation in Combinatorial Optimization, LNCS, vol. 6022, pp. 239–251. Springer, Berlin (2010)
Roboredo, M., Pessoa, A.: A branch-and-cut algorithm for the discrete \((r|p)\)-centroid problem. Eur. J. Oper. Res. 224(1), 101–109 (2013)
Serra, D., Revelle, C.: Competitive location in discrete space. In: Economics working papers 96, Department of Economics and Business, University of Pompeu Fabra, Spain, Technical Report (1994)