Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật Toán Nung Nóng Cho Các Vấn Đề Định Vị Tuyệt Đối Đa Nguồn Trên Đồ Thị
Tóm tắt
Một phương pháp được trình bày để áp dụng các kỹ thuật nung nóng cho các vấn đề định vị tuyệt đối đa nguồn trên đồ thị. Hai loại chức năng mục tiêu được xem xét: trung tâm trọng luợng (barycenters) và trung tâm (centers). Một lớp thuật toán mới được mô tả: phát triển của nó bắt đầu từ thuật toán lặp "cụm và định vị" và dựa trên việc nới lỏng các ràng buộc toàn vẹn trên các biến phân bổ. Các kết quả thực nghiệm được báo cáo.
Từ khóa
#định vị tuyệt đối #đồ thị #thuật toán nung nóng #trung tâm trọng luợng #thuật toán lặpTài liệu tham khảo
R.S. Garfinkel, A.W. Neebe, and M.R. Rao, "The m-center problem: Minimax facility location," Management Science, vol. 23, no. 10, pp. 1133–1142, 1977.
S.L. Hakimi, E.F. Schmeichel, and J.G. Pierce, "On p-centers in networks," Transportation Science, vol. 12, no. 1, pp. 1–15, 1978.
J. Halpern and O. Maimon, "Algorithms for the m-center problems: A survey," Europ. J. of Oper. Res., vol. 10, pp. 90–99, 1982.
G.Y. Handler and P.B. Mirchandani, Location on Networks-Theory and Algorithms, MIT Press, 1979.
R. Holzman, "An axiomatic approach to location on networks," Mathematics of Operations Research, vol. 15, no. 3, pp. 553–563, 1990.
O. Kariv and S.L. Hakimi, "An algorithmic approach to network location problems. Part I-II," SIAM J. on Appl. Math., vol. 37, pp. 513–538, 1979.
F. Maffioli and G. Righini, "An annealing approach to multifacility location problems in Euclidean spaces," Location Science, vol. 2, no. 4, pp. 205–222, 1994.
F. Maffioli and G. Righini, "Location of the absolute barycenter of a graph," Report 93.027, Dipartimento di Elettronica e Informazione, Politecnico di Milano, 1993.
E. Minieka, "A polynomial time algorithm for finding the absolute center of a network," Networks, vol. 11, pp. 351–355, 1981.
G. Righini, "Algoritmi per problemi di localizzazione multirisorse (Algorithms for multisource location problems)," Doctoral thesis, Dipartimento di Elettronica e Informazione, Politecnico di Milano, 1993.
A. Sepe and A. Sforza, "Un algoritmo per il problema del centro assoluto su rete (An algorithm for the absolute center problem on network)," Ricerca Operativa, vol. 39, pp. 71–105, 1986.
D.R. Shier and P.M. Dearing, "Optimal locations for a class of non-linear, single-facility location problems on a network," Operations Research, vol. 31, pp. 292–303, 1983.