Zastosowanie metod wyznaczania przepływu w sieciach do planowania manewru wojsk

• Autorzy: Tarapata Z.

Warianty tytułu

EN

Application of methods for determining flows in networks to military forces manoeuvre planning

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono opis sposobu wykorzystania metod wyznaczania przepływu w sieciach do rozwiązania specyficznego problemu planowania manewru wojsk. Zdefiniowano model sieci formalnej, bazującej na danych z cyfrowej mapy terenu, wykorzystywanej jako model środowiska w problemie planowania manewru. Sformułowano optymalizacyjny problem planowania przegrupowania K obiektów z rejonu startowego (reprezentowanego przez podzbiór wierzchołków sieci formalnej) do rejonu docelowego, z dodatkowym ograniczeniem na rozłączność dróg. Opisano sposób modyfikacji sieci pierwotnej oraz poszukiwania jednego z rozwiązań dopuszczalnych sformułowanego problemu planowania przegrupowania z użyciem metody znajdowania przepływu maksymalnego w sieci zmodyfikowanej. Przedyskutowano metodę poszukiwania rozwiązania optymalnego bazującą na algorytmie znajdowania przepływu zaspokajającego o minimalnym koszcie w pewnej sieci zastępczej. Opisane metody zilustrowano przykładami obliczeniowymi. Oszacowano złożoność obliczeniową prezentowanych algorytmów. Artykuł kończy omówienie rozszerzeń sformułowanego problemu wyjściowego oraz metod ich rozwiązywania.

EN

In the paper an application of methods for determining flows in networks to military forces maneuver planning is presented. Model of formal network as environment model for manoeuvre planning based on digital maps is defined. Optimization problem of redeployment planning of K objects from source region to destination one taking into account paths disjointness is considered. The method for finding one of the acceptable solution of considered redeployment problem based on method of solving maximum flow problem is described. The method for finding optimal solution of considered problem based on method of solving minimum cost network flow problem in some substitute network is defined. For both of the methods computational complexity is estimated. Some computational examples of presented methods are shown.

Słowa kluczowe

PL

planowanie manewru; drogi rozłączne; przepływy w sieciach

EN

manoeuvre planning; disjoint paths; flows in networks

• Wydawca: Institute of Computer and Information Systems, Faculty of Cybernetics, Military University of Technology
• Czasopismo: Biuletyn Instytutu Systemów Informatycznych
• Rocznik: 2008
• Tom: nr 2
• Strony: 31--44
• Opis fizyczny: Bibliogr. 39 poz.

Twórcy

autor

Tarapata Z.

• Wojskowa Akademia Techniczna, Wydział Cybernetyki, ul. Gen. S. Kaliskiego 2, 00-908 Warszawa,

Bibliografia

• [1] Ahuja R.K., Magnanti T.L., Orlin J.B.: Network Flows: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs 1993.
• [2] Benton J.R., Iyengar S.S., Deng W., Brener N., Subrahmanian V.S.: Tactical route planning: new algorithms for decomposing the map, Proceedings of the IEEE International Conference on Tools for AI, 6-8 November, Herndon 1995, pp. 268-277.
• [3] Busacker R.G., Gowen P.J.: A procedure for determining a family of minimum-cost flow patterns, Operations Research Office Technical Report 15, John Hopkins University, Baltimore 1961.
• [4] Cai X., Kloks T., Wong C.K.: Time-varying shortest path problems with constraints, Networks 29 (1997), pp.141-149.
• [5] Campbell C., Hull R., Root E., Jackson L.: Route planning in CCTT, in Proceedings of the 5th Conference on Computer Generated Forces and Behavioural Representation, Technical Report, Institute for Simulation and Training, pp. 233-244, 1995.
• [6] Cormen T.H., Leiserson Ch.E., Rivest R.L.: Wprowadzenie do algorytmów, WNT, Warszawa 1997.
• [7] Cormican K., Morton D., Wood K.: Stochastic network interdiction, Operations Research 46 (1998), pp. 184-197.
• [8] Corps Battle Simulation (CBS), Version 1.6.0, Analyst's Guide, Volume 1, Ground, U.S. Army Simulation, Training, and Instrumentation Command Orlando, Florida, June 2001.
• [9] Deo N.: Teoria grafów i jej zastosowanie w technice i informatyce, WNT, Warszawa 1980.
• [10] Deo N., Sysło M., Kowalik J.: Algorytmy optymalizacji dyskretnej, wyd. II, PWN, Warszawa 1995.
• [11] Dijkstra E.: A note on two problems in connection with graphs, Numerische Mathematik 1 (1959), 269-271.
• [12] Dreyfus S.E.: An appraisal of some shortest path algorithms, Operations Research 17 (1969), pp. 395-412.
• [13] Edmonds J., Karp R.M.: Theoretical improvement in algorithmic efficiency for network flow problems, J. ACM 19 (1972), pp. 248-264.
• [14] Golden B.L., Skiscim C.C.: Solving k-shortest and constrained shortest path problems efficiently, Network Optimization and Applications 20 (1989), Texas A&M University, College Station.
• [15] James J., Sayrs B., Benton J., Subrahmanian V.S.: Uncertainty management: keeping battlespace visualization honest, Proceedings of the 3rd Annual Conference on Advanced Telecommunications and Information Distribution Research Program (ATIRP), University of Maryland, College Park, MD, February 1-5, 1999.
• [16] Kaszubowski Z., Mizera R., Piasecki S.: Problemy przegrupowania wojsk. WAT, Warszawa 1970.
• [17] Korzan B.: Elementy teorii grafów i sieci, Metody i zastosowania. WNT, Warszawa 1978.
• [18] Kreitzberg T., Barragy T., Nevin B.: Tactical movement analyzer: a battlefield mobility tool, Proceedings of the 4th Join Tactical Fusion Symposium, Laurel, 1990.
• [19] Longtin M., Megherbi D.: Concealed routes in ModSAF, in Proceedings of the 5th Conference on Computer Generated Forces and Behavioural Representation, Technical Report, Institute for Simulation and Training, pp. 305-314, 1995
• [20] Minieka E. : On computing sets of shortest path in a graph, Comm. Assoc. Comput. Mach. 17 (1974), 351-353.
• [21] Mitchell J.S.B.: Geometric shortest paths and network optimization, in J.R. Sack and J. Urrutia: Handbook of Computational Geometry, Elsevier Science Publishers, B.V. North-Holland, Amsterdam 1999.
• [22] Mizera R.: Teoria badań operacji. Algorytmy planowania transportu, WAT, Warszawa 1972.
• [23] Petty M.D.: Computer generated forces in Distributed Interactive Simulation, Proceedings of the Conference on Distributed Interactive Simulation Systems for Simulation and Training in the Aerospace Environment, 19-20 April, Orlando (USA) (1995), 251-280.
• [24] Rajput S., Karr C.: Unit Route Planning, Technical Report IST-TR-94-42, Institute for Simulation and Training, Orlando (USA) (1994).
• [25] Schrijver A., Seymour P.: Disjoint paths in a planar graph - a general theorem. SIAM Journal of Discrete Mathematics 5 (1992), 112-116.
• [26] Schrijver A.: Combinatorial Optimization. Polyhedra and Efficiency, Springer-Verlag, Berlin - New York (2004).
• [27] Software Engineer Maintenance Manual, Volume I. Model Overview and interface Specification, Joint Theater Level Simulation (JTLS), Defense Information Systems Program, Jet Propulsion Laboratory, Pasadena, California, September 1985.
• [28] Tarapata Z.: Multi-paths optimization in an unreliable time-dependent networks, Proceedings of The 2nd NATO Regional Conference on Military Communication and Information Systems, 04-06 October, Zegrze (Poland) 2000, vol.I, 181-189.
• [29] Tarapata Z.: Modelling, optimisation and simulation of groups movement according to group pattern in multiresolution terrainbased grid network, Proceedings of The 3rd NATO Regional Conference on Military Communication and Information Systems, 10-12 October, Zegrze (Poland) 2001, vol.I, 241-251.
• [30] Tarapata Z.: Algorithm for simultaneous finding a few independent shortest paths, Conference Proceedings of the 9th European Simulation Symposium, Passau (Germany) 1997, pp. 89-93.
• [31] Tarapata Z.: Modelling of terrain for necessities of military objects movement simulation, Bulletin of Military University of Technology, Noo 1 (2000), pp. 127-146.
• [32] Tarapata Z.: Military route planning in battlefield simulation: effectiveness problems and potential solutions, Journal of Telecommunications and Information Technology, Noo 4 (2003), pp. 47-56.
• [33] Tarapata Z.: Models and methods of movement planning and simulation in simulation aided system for operational training, Proceedings of The 6th NATO Regional Conference on Military Communication and Information Systems, ISBN 83-920120-0-3, 06-08 October, Zegrze (Poland) 2004, pp. 152-161.
• [34] Tarapata Z.: Selected multicriteria shortest path problems: an analysis of complexity, models and adaptation of standard algorithms, International Journal of Applied Mathematics and Computer Science, Vol.17, No.2 (2007), 269-287.
• [35] Tarapata Z.: Automatization of decision processes in conflict situations: modelling, simulation and optimization, w: Arreguin J.M.R. (edt.): Automation and Robotics, ISBN 978-3-902613-41-7, I-Tech Education and Publishing, Vienna (Austria) 2008, 297-328.
• [36] The Analyst Guide, Joint Theater Level Simulation (JTLS), Version 1.65, Modern Aids to Planning Program (MAPP), Force Structure and Assessment Directorate (J-8), Joint Staff, The Pentagon, September 1988.
• [37] Wagner R. A.: A shortest path algorithm for edge-sparse graphs, Journal Assoc. Comp. Mach. 23 (1976), 50-57.
• [38] Warburton A.: Approximation of Pareto optima in multiple-objective, shortest-path problems, Operations Research 35 (1987), pp. 70-79.
• [39] Wilson R.J.: Wprowadzenie do teorii grafów, PWN, Warszawa 1998.