Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Vị trí của các mạng lưới tăng tốc
Tóm tắt
Cho một mạng với trọng số cạnh, một tập hợp các yêu cầu vận chuyển điểm-đến-điểm và một hệ số $$\alpha $$ đã cho. Mục tiêu của chúng tôi là thiết kế một mạng con có chiều dài xác định, trên đó chi phí vận chuyển được giảm bởi $$\alpha $$. Điều này làm giảm chi phí của lưu lượng mạng, mà sẽ chọn sử dụng các cạnh của mạng con mới nếu đây là lựa chọn hiệu quả hơn. Chúng tôi hướng đến việc thiết kế mạng con sao cho chi phí tồi tệ nhất của tất cả các yêu cầu định tuyến được giảm thiểu. Vấn đề này xuất hiện trong nhiều ứng dụng, trong đó có mạng giao thông, mạng xương sống, thông tin, truyền thông hoặc mạng điện. Chúng tôi phân loại vấn đề theo các loại mạng đã cho và mạng cần thiết lập. Chúng tôi có khả năng làm rõ tình trạng độ phức tạp trong tất cả các trường hợp đã xem xét. Kết quả cho thấy việc tìm kiếm một cây con tối ưu trong một cây hiện có đã là NP-khó. Do đó, chúng tôi tiếp tục nghiên cứu trường hợp này và đề xuất các kết quả cũng như một phương pháp giải quyết.
Từ khóa
#mạng lưới #yêu cầu vận chuyển #chi phí định tuyến #mạng con #NP-khó #tối ưu hóaTài liệu tham khảo
Chung, F. (1986). Diameters of communication networks. In Mathematics of information processing. Proceedings of Symposia in Applied Mathematics, 34, pp. 1–18.
Contreras, I., & Fernández, P. (2012). General network design: A unified view of combined location and network design problems. European Journal of Operational Research, 219(3), 680–697.
Demaine, E. & Zadimoghaddam, M. (2010). Minmizing the diameter of a network using shortcut edges. In: Algorithm theory: SWAT 2010, Lecture Notes in Computer Science (Vol. 6139, pp. 420–431), New York: Springer.
Eggemann, N., & Noble, S. (2009). Minimizing the oriented diameter of a planar graph. Electronic Notes in Discrete Mathematics, 34, 267–271.
Engelhardt-Funke, O., & Kolonko, M. (2001). Cost-benefit analysis of investments into railway networks with randomly pertubed operations. In S. Voß & J. Daduna (Eds.), Computer-aided transit scheduling, Lecture Notes in Economics and Mathematical Systems (Vol. 505, pp. 442–459). New York: Springer.
Fernández, P., & Marín, A. (2003). A heuristic procedure for path location with multisource demand. Information Systems and Operational Research, 41(2), 165–177.
Garey, M., & Johnson, D. (1979). Computers and intractability—A guide to the theory of NP-completeness. San Francisco: Freeman.
Gutierrez, G., Donoso, M., Obreque, C., & Marianov, V. (2010). Minimum cost path location for maximum traffic capture. Computers & Industrial Engineering, 58(2), 332–341.
Hakimi, S. L., Schmeichel, E. F., & Labbé, M. (1993). On locating path- or tree-shaped facilities on networks. Networks, 23(6), 543–555.
Hedetniemi, S. M., Cockayne, E. J., & Hedetniemi, S. T. (1981). Linear algorithms for finding the jordan center and path center of a tree. Transportation Science, 15(2), 98–114.
Hofmann, H. (2009). Heuristiken zur Platzierung von Bäumen in Bäumen (2009). Bachelors Thesis, (in German).
Koster, A. & Munoz, X. (Eds.). (2010). Graphs and algorithms in communication networks—studies in broadband, optical, wireless and Ad Hoc networks. Texts in Theoretical Computer Science. An EATCS Series. New York: Springer.
Labbé, M., & Laporte, G. (2005). Locating median cycles in networks. European Journal of Operational Research, 160(2), 457–470.
Lamb, J. D. (2010a). Insertion heuristic for central cycle problems. Networks, 56(1), 70–80.
Lamb, J. D. (2010b). Variable neighbourhood structures for cycle location problems. European Journal of Operational Research, 223(1), 15–26.
Laporte, G., Marín, A., Mesa, J., & Ortega, F. (2006). An integrated methodology for rapid transit network design. Algorithmic methods for railway optimization, Lecture Notes on Computer Science. New York: Springer.
Laporte, G., Mesa, J., Ortega, F., & Perea, F. (2011). Planning rapid transit networks. Socio-Economic Planning Sciences, 45(3), 95–104.
Mesa, J. A., & Boffey, T. (1996). A review of extensive facility location in networks. European Journal of Operational Research, 95(3), 592–603.
Meyerson, A., & Tagiku, B. (2009). Minimizing the average shortest path distances via shortcur edge addition. Proceedings of the International Workshop on Approximation Algorithms for Combinatorial optimization Problems, Lecture Notes in Computer Science, 5687, 272–285.
Nickel, S., Schöbel, A., & Sonneborn, T. (2001). Hub location problems in urban traffic networks. In Pursula Niittymäki (Ed.), Mathematical methods and optimization in transportation systems (pp. 95–107). Dordrecht: Kluwer Academic.
Puerto, J., Ricca, F., & Scozzari, A. (2012). Range minimization problems in path-facility location on trees. Discrete Applied Mathematics, 160(15), 2294–2305.
Puerto, J., & Tamir, A. (2007). Locating tree-shaped facilities using the ordered median objective. Mathematical Programming, Series A, 102(2), 313–338.
Ruzika, S. & Thiemann, M. (2011). Reliable and restricted quickest path problems. In J. Pahl, T. Reiners & S. Vo (Eds.) INOC 2011, no. 6701 in LNCS, pp. 309–314. Heidelberg: Springer.
Schmidt, M. (2009). Netzwerkstandortprobleme mit OD-Paaren. Master’s thesis, Georg August Universität Göttingen, Göttingen (in German).
Schöbel, A. (2012). Line planning in public transportation: Models and methods. OR Spectrum, 34(3), 491–510.
Székely, L. A., & Wang, H. (2005). On subtrees of trees. Advances in Applied Mathematics, 34(1), 138–155.