Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Vấn đề định tuyến vị trí 2-Facility trên đa tạp
Tóm tắt
Vấn đề định tuyến vị trí (LRP), được biết đến như sự kết hợp giữa vấn đề định vị cơ sở hạ tầng và vấn đề định tuyến phương tiện, đã được giải quyết trong tài liệu bằng cách giả định các bề mặt phẳng hoặc cầu. Trong công trình này, chúng tôi giải thích vấn đề định tuyến vị trí trên đa tạp (MLRP), đó là một LRP trên bề mặt đa tạp Riemann, cho trường hợp 2 cơ sở hạ tầng (2-MLRP) với giải pháp thuật toánheuristic tương ứng. Vấn đề 2-MLRP là một bài toán lập trình phi tuyến hỗn hợp số nguyên được xác định là NP-khó. Các trường hợp đặc biệt của MLRP bao gồm LRP trên các bề mặt phẳng, khi độ cong của đa tạp bằng 0, và LRP trên các bề mặt cầu khi độ cong của đa tạp bằng 1.
Từ khóa
#Vấn đề định tuyến vị trí #Đa tạp Riemann #Lập trình phi tuyến #NP-khó #Thuật toán heuristic #Độ congTài liệu tham khảo
Altinel, K., Oncan, T.: A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem. J. Oper. Res. Soc. 56, 954–961 (2005)
Aly, A.A., Kay, D.C., Litwhiler Jr, D.W.: Location dominance on spherical surfaces. Oper. Res. 27, 972–981 (1979)
Ambrosino, D., Sciomachen, A., Grazia, M.: Scutella: a heuristic based on multi-exchange techniques for a regional fleet assignment location-routing problem. Comput. Oper. Res. 36, 442–460 (2009)
Barreto, S., Ferreira, C., Paixao, J., Sousa, B.: Santos: using clustering analysis in a capacitated location-routing problem. Eur. J. Oper. Res. 179, 968–977 (2007)
Cristiannini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-Based Methods. Cambridge University Press, Cambridge (2003)
Clarke, G., Wright, J.W.: Scheduling of vehicle from central depot to a number of delivery points. Oper. Res. 12, 568–581 (1964)
Cooper, L.: Heuristic methods for location-allocation problems. Siam Rev. 6, 37–53 (1964)
Daskin, M.S.: What you should know about location modeling. Naval Res. Logist. 55, 283–294 (2008)
doCarmo, M.P.: Differential Geometry of Curves and Surfaces. Prentice Hall Inc, Englewood Cliffs (1976)
Drezner, Z., Wesolowsky, G.O.: Facility location on a sphere. J. Oper. Res. Soc. 29, 997–1004 (1978)
Gamal, M.D.H., Salhi, S.: Constructive heuristics for the uncapacitated continuous location-allocation problem. J. Oper. Res. 52, 821–829 (2001)
Huang, R., Kim, S., Menezes, M.B.C.: Facility location for large-scale emergencies. Ann. Oper. Res. 181(1), 271–286 (2010)
Johnson, M.P., Gorr, W.L., Roehrig, S.: Location of service facilities for the elderly. Ann. Oper. Res. 136(1), 329–349 (2005)
Perl, J., Daskin, M.S.: A warehouse location-routing problem. Transport. Res. B 19, 381–396 (1985)
Riemann, B.: Grundlagen für eine allgemeine Theorie der Functionen einer veränderlichen complexen Grösse. Inauguraldissertation, Göttingen (1851)
Laporte, G.: What you should know about the vehicle routing problem. Naval Res. Logist. 54, 811–819 (2007)
Manzour-al-Ajdad, S.M.H., Torabi, S.A., Salhi, A.: A hierarchical algorithm for the planar single-facility location routing problem. Comput. Oper. Res. 39, 461–470 (2012)
Marianov, V.: Location of multiple-server congestible facilities for maximizing expected demand, when services are non-essential. Ann. Oper. Res. 123(1–4), 125–141 (2003)
Nagy, G., Salhi, S.: Location-routing: Issues, models, and methods. Eur. J. Oper. Res. 177, 649–672 (2007)
Salhi, S., Rand, G.K.: The effect of ignoring routes when locating depots. J. Oper. Res. 39, 150–156 (1989)
Salhi, S., Nagy, G.: Consistency and robustness in location routing. Stud. Locat. Anal. 13, 3–19 (1999)
Salhi, S., Nagy, G.: Local improvement in planar facility location using vehicle routing. Ann. Oper. Res. 167, 287–296 (2009)
Schwardt, M., Dethloff, J.: Solving a continuous location routing problem by use of a self-organizing map. Int. J. Phys. Distrib. Logist. Manag. 35, 390–408 (2005)
Schwardt, M., Fischer, K.: Combined location-routing problems—a neural network approach. Ann. Oper. Res. 167, 253–269 (2009)
Sherali, H.D., Noradi, F.L.: NP-hard, capacitated, balanced p-median problems on a chain graph with a continuum of link demands. Math. Oper. Res. 13, 32–49 (1988)
Tellier, L.-N.: The Weber problem: solution and interpretation. Geo Anal. 4(3), 215–233 (1972)
Tokgöz, E., Alwazzi, S., Trafalis, T.B.: A heuristic algorithm to solve the single-facility location routing problem on Riemannian surfaces. Comput. Manag. Sci. Springer 12, 397–415 (2015)
Weiszfeld, E.: Sur le point pour lequel la somme des distances de n points donnes est minimum. Tohoku Math. J. 43, 355–386 (1937)