Actual Aspects of Information Technologies Application at the Problem Decision of the Movement Organisation by a Convoy of Vehicles

Abstract

The analysis of the known approaches to solving the problem of organization of transportation by a convoy of vehicles showed that due to the existence of a large number of brands and types of vehicles, from which the convoys are formed, various tactical and technical characteristics of the samples of technology, a branched network of roads, multi-variants the choice of route, the possible development of the traffic situation, they do not solve the problem of efficient organization of traffic, although the article shows the urgency and weight of such a problem. Therefore, the purpose of this study is to substantiate possible approaches to the solution of the problem of organizing transportation by a convoy of vehicles, as well as their formalization. The article analyzes the problems of optimization of the military convoy composition and the choice of the optimal route for its movement from the point of their complex combination to solve the systematic problem of the organization of transportation by the convoy of vehicles. On the basis of the analysis, a multicriteria optimization problem was formulated, including criteria and a system of constraints which included all criteria and limitations of the constituent problems, and substantiation of possible approaches to its solution. The proposed approaches make it possible to: classify the tasks of organizing the march; generate algorithms for solving the problem under study in each of the productions; to evaluate the limited possibilities of the analytical methods available to solve the applied tasks of organizing a march; evaluate possible approaches to forming a mathematical apparatus to solve these problems; to conclude the need to develop information technology that would ensure the solution of the problem of organizing the march in any setting.

-

problem, Multicriteria,

Mathematical

Model,

Algorithms, Information

1. Introduction

To date, the issue of optimization of transportation is extremely important in various fields of human activity, in particular, when solving various tasks of the logistics sphere. The successful implementation of many relocations is highly dependent on the timely arrival of the military convoy at the intended destination. For effective transportation of various cargoes by land various modern vehicles with wide possibilities are used. Before scheduling transportation, it is possible to optimize the composition of the convoy of vehicles taking into account a wide range of factors [1]. In the next step, it is necessary to solve the problem of determining the optimal route of movement of the military convoy. A sufficiently extensive network of highways provides a significant number of possible routes that combine the departure point with the destination. Such variance, of course, is observed even at the small distances that need to be overcome. The choice of the optimal route can be significantly influenced by the dynamics of the development of the road situation. Due to the influence of the predicted and stochastic factors, the speed of movement of the convoy on individual sections of the route can change significantly. Failure to adequately account for changes in traffic conditions can lead to incorrect route selection, which will not ensure timely arrival of the convoy at the destination. Such delay may result in the failure of certain tasks. Therefore, the task of organizing a march is relevant, and the presence of multivariance, a large number of factors that must be considered in its solution, their complex interaction and impact on the result causes a significant computational complexity of the task and the need to use powerful computing tools and the development of appropriate information technology for solving the problem.

The issue of forming a convoy of vehicles for efficient movement of cargo has been given attention in a number of works, in particular [1-4]. Thus, in [2] the method of tactical calculations for determining the number of vehicles for transportation of goods took into account the characteristics of cargo, load capacity and speed of movement of vehicles, range of movement, loading time, unloading, refueling, rest of drivers between flights (if provided), as well as the timing of the movement of goods. The paper [3] reflects the issues of predicting the effectiveness of the march of military formation on the reliability of weapons and military equipment, as well as the impact on the march efficiency of the number of repair units, the technical state of technology in terms of reliability, the level of efficiency of repair bodies in carrying out repair work and This is the cost of repairing weapons and military equipment. In [4], a variant of a cargo transportation model for finding the optimal route of cargo transportation from one sender to several consumers is presented in the transport network. However, in the analyzed works [2-4], such requirements for the formation of the optimal composition of the convoy of vehicles, such as the level of readiness, the power reserve on motoresource, the number of brands and samples, the availability of fuel for refueling, etc., were ignored. These requirements were reflected in the author's work [1].

The choice of movement routes 8of the military convoy for the efficient movement of goods, as well as related problems, was focused in a number of works, in particular in [5-17]. An approach to choosing the route based on "edgelabels" is given in [5]. Its application makes it possible to accelerate the search for the shortest path by 500 times compared to Dijkstra's algorithm over a large graph. In [6], an algorithm for selecting optimal routes in a multimodal mode of a public transport network is presented. According to the results of this study, the approach to routing of transit nodes was adapted to plan for relocation by public transport. In the scientific work [7], the method of contraction hierarchy was used to find the shortest path. In the study [8], based on the application of the SHARC algorithm, the possibilities of finding the shortest paths for arbitrary means of transportation in a continental-scale transport network are presented. The problem of multimodal route planning has been investigated in a scientific paper [9]. In the work [10] a model for estimating traffic delays of vehicles is presented, taking into account arbitrary loads during traffic. The study [11] provides mapping of marshrutes for military ground vehicles on the battlefield. In a scientific paper [12], an algorithm for solving the problem of finding the shortest time paths in urban commuting networks using the branch and boundary method was developed. The issues [1314] investigate the use of geoinformation technologies in solving logistical problems in military affairs, based on the use of modern ArcGIS information systems [15-17]. In the author's work [18], the problem of choosing the optimal route of convoy movement of the border commanding rapid response technique was taken into account, taking into account the peculiarities associated with the preliminary establishment and maintenance of the reliability of the initial data based on the use of spline functions [19-21] ; mathematical models of the studied problem for three cases (discrete-stochastic, discretelydeterministic and continuous-indefinite) are constructed, which depend on the peculiarities of realization of the convoy motion; algorithms for choosing the optimal route of movement of the Rapid Response Command Border Convoy of vehicles for each possible case are proposed.

However, despite the sufficient attention that was given to the authors, including the tasks of forming the optimal composition of the military convoy and choosing the route of its movement, the task of organizing a march that organically combines both one and the other of these tasks has not been fully explored. This is explained by the non-obviousness of approaches to solving such a problem.

Given the above urgency and importance of the problem of efficient movement organization, the important and urgent task now is to formalize the task of organizing transportation by a convoy of vehicles. The purpose of this study is to substantiate possible approaches to the solution of the specified problem and its formalization in different formulations taking into account the criteria and the system of limits of constituent problems.

2. Formulation of the task of organizing transportation of the military convoy at a meaningful level and its formalization

At the substantive level, the problem under study looks like this.

Given: complex M  x1; x2 ;...; xn  vehicles from which the composition of the engineering convoy may be formed for the carriage of personnel and cargo ( xi - symbol of a definite ____ specific vehicle, i  1, n ) U1 ;

the tactical and technical characteristics of each vehicle of this group U2  .

Also, set up a network of roads that connect the departure point (point А) with destination (point В). The mathematical model of the road network is a marked graph G , the weight of the edges of which represents the time of movement of the convoy along them U3  .

It is necessary to arrange transportation from point A to point B so that:

vehicles arrived at point B with maximum readiness K1  ; the number of vehicles in the convoy was minimal ( K2 );

the number of vehicle brands in the convoy was minimal K3  ; the duration of the march was minimal ( K4 ); the rate of the readiness factor of each vehicle shall not be less than the permitted level ( O1 ); the total capacity of vehicles from the the convoy allowed to carry the goods ( O2 ); the total volume of the body of vehicles from the warehouse allowed to transport the cargo ( O3 ); the total passenger capacity allowed to transport personnel ( O4 );

the total fuel consumption of vehicles from the convoy did not exceed the amount of fuel available to march by fuel type ( O5,...,O8 ); the stock of motorsource was not less than the distance of transportation ( O9 ).

However, it should be taken into account that during the movement of the convoy, the motion time along the individual edges can be variable. This condition is determined by the influence on the time of movement along a single edge of different conditions, such as climatic (rain, ice, fog, etc.), man-made (blockage of the roadway, its post-damage due to flooding of the terrain, etc.), changes in the period of day (day, night). etc.

It should also be noted that the weights of the edges can be changed:

at times when the convoy is at a certain vertex of the graph, and the matrix of weights is updated at these moments. This is a case where the decision on the further route of traffic is made at the points of branching of roads taking into account the situation regarding the condition of individual sections, which changes dynamically and the data on which appear periodically; at the times when the convoy is at a certain vertex of the graph, and for these moments the weights matrix that will take place when the convoy enters the vertex are well known in advance. This is a case where a route decision can be made at the beginning of the traffic, taking into account the well-known situation regarding the state of the roads, which will change dynamically, but the data on which can be taken into account in advance.

At the physical level, the formulated task of organizing a march consists in the complex solution of two interrelated problems: problem 1 choosing the appropriate composition of the convoy of vehicles; problem 2 - choosing the appropriate route of its movement.

It should be noted that each of problems 1, 2 is solved separately from each other. The corresponding solutions are given in [1, 18].

The problem 1 is solved as a single-criterion optimization problem of the form:

Initial data ( 8 ) ( 9 )

Criterion

f K1, K2 , K3   min System of restrictions: , U1,U2 ,U3 .

O1,...,O9 ,

O10 . ( 4 )

In problems ( 1 )-( 4 ), one-criteria is obtained by the functional combination of three separate criteria K1, K2 , K3 , which appeared in the direct statement of problem 1, and restriction O10 obtained by converting the criterion K . 4

The result of solving problem 1 is some set M  x1; x2;...; xm, the elements of which are 1 specific vehicles that are part of the convoy.

Herewith, m  n і M  M .

1

Task 2 is solved as a single-criterion optimization problem of the form:

Initial data

Criterion

M1 , U2 ,U3 .

K4  min .

Tasks ( 5 ) - ( 6 ) take into account the variability of the edges of the road network graph, and also format of such change is how it occurs, at what moments, at which stage, the dynamic matrixes of the edges are known.

The result of solving task 2 is the route of movement of the convoy V  v1;v2;...;vs  - the 2 set of vertices through which the route of travel must be passed.

Herewith, v1  A , vs  B .

The problem studied in the following notations can be represented as a multicriteria optimization problem of the following form:

Initial data

Criterion

U1,U2 ,U3 . ( 1 ) ( 2 ) ( 3 ) ( 5 ) ( 6 ) ( 7 ) K 2  min, K3  min, K 4  min . O1,..., O9 .

System of restrictions

Find

Mo  x1; x2;...; xr , ( 10 )

Vo  v1;v2;...;vz . ( 11 )

In the tasks ( 7 )-( 11 ) Mo  x1; x2;...; xr  appropriate composition of the convoy of vehicles, аnd V  v1;v2;...;vz  - expedient route o of its movement.

The analysis of task 1 in the form ( 1 ) - ( 4 ) and task 2 in the form ( 5 ) - ( 6 ) leads to the conclusion that the solution of the studied problem in the form ( 7 ) - ( 11 ) can be following Mo  x1; x2;...; xr  M1  x1; x2;...; xm, аnd V  v1;v2;...;vz   V2  v1;v2 ;...;vs .

o

3. Foundation of approaches to solving the problem of organization of transportation by a convoy of technique

Conditions for partial problems of the general task of organizing the march, justification of approaches to solving the common problem, algorithms for the implementation of each of the variants are structured below.

Variant 1.

Task 1.

Mathematical model: U1,U2 ,U3 , O1,..., O9 , O10 , f K1, K2 , K3   min .

The result of the solution: The composition of the convoy is obtained in the form of a plurality M  x1; x2;...; xm.

1

Problem Solving Technology 1. Problem 1 in statement ( 1 ) - ( 4 ) is solved as an optimization problem.

Task 2.

Mathematical model: M1 , U2 ,U3 , K4  min .

The result of the solution: The route of movement of the convoy in the form of a set is obtained V2  v1;v2;...;vs .

Problem Solving Technology 2. Problem 2 in statement ( 5 ) - ( 6 ) is solved.

Investigated task.

The solution to the problem under study is following: Mo  M1 , Vo  V2 .

Variant 2.

Task 1.

Mathematical model: U1,U2 ,U3 , O1,...,O9 , O10 .

The result of the solution: The variants of the composition of the convoy in the form of sets are obtained

M 1  x11; x1;...; x1

1 2 m1 , M 2  x12; x22;...; xm22,…,

1 M d   xd ; x2d ;...; xd 

1 1 ms .

Problem Solving Technology 1. Problem 1 in statement ( 1 ), ( 3 ), ( 4 ) is solved as a combinatorial problem.

Task 2.

Mathematical model:

M1i , U2 ,U3

____ i  1, d , K4  min .

The result of the solution: For each fixed value, the path of the convoy motion in the form of a set is obtained

V 1  v1 ; v21 ;...; vs11 ; vs , 2 V 2  v1;v22;...;vs21 ;vs ,…, 2 V d   v1;v2d ;...;vsd1;vs .

2

Problem Solving Technology 2. Task 2 in statement ( 5 ) - ( 6 ) is solved.

Investigated task.

The solution to the problem under study is following: M o  M1k  , Vo  V2k  , where M1k  - is the composition of the convoy that provides V2k  .

Problem Solving Technology. It is established that the set V2k  of the number of sets V21 , V22 ,…, V2d  , which corresponds to the minimum time of movement of the convoy from point A to point B, that is min K4 .

Note to variant 2.

In variant 2

M 1  x1; x1;...; xm11,

1 1 2 M 2  x12; x22;...; xm22, …, 1 M d   x1d ; x2d ;...; xd 

1 md - sets that determine possible composition of convoys. The elements of these sets are specific vehicles from among the elements of the set M . So, M 1  M , M 2  M , …, M d   M . should 1 1 1 be noted that the capacity of the sets M11 , M12 , …, M d  may be different, and the elements of 1 these sets may also not coincide.

Variant 3.

Task 1.

Mathematical model: U1,U2 ,U3 , O1,..., O9 , O10 ,O11,O12 ,O13

The result of the solution: The variants of the composition of the convoy in the form of sets are obtained

M 1  x1; x1;...; xm11 ,

1 1 2 M 2  x12; x22;...; xm22,…,

1 M d   x1d ; x2d ;...; xmds.

1

Problem Solving Technology 1. Problem 1 in statement ( 1 ), ( 3 ), ( 4 ) is solved with additional restrictions O11,O12 ,O13 , as a combinatorial task.

Task 2.  ____  Mathematical model: M1i , U2 ,U3  i  1, d  ,  K4  min .

The result of the solution: For each fixed value ____ i  1, d the route of movement of the convoy in the form of a set is obtained

V 1  v1;v21;...;vs11;vs ,

2 V 2  v1;v22;...;vs21 ;vs ,…, 2 V d   v1;v2d ;...;vsd1;vs .

2

Problem Solving Technology 2. Problem 2 in statement ( 5 ) - ( 6 ) is solved at each fixed value ____ i  1, d .

Investigated task.

The solution to the problem under study is following: V 1 , V22 ,…,V2d  are such that provide the same 2 value of the minimum time of movement of the convoy from point A to point B, so that min K4 , for each of these routes the composition of the corresponding convoys and by criterion are determined ( 2 ) f K1, K2 , K3   min expedient composition of convoy is determined M1k  .

Variant 4.

Investigated task.

Mathematical model: U1,U2 ,U3 , O1,..., O9 , K1  max, K2  min, K3  min, K4  min .

Result of solution: The solution to the problem under study is following: Mo  M1 , Vo  V2 .

Here M1 і V2 are sets, that satisfy all the restrictions of the studied problem in the formulation of variant 4, and under which the criterion is fulfilled gK1, K2 , K3, K4   min .

Note to variant 4.

In such formulation, the studied problem should be reduced first to an optimization singlecriterion problem. For example, this can be done by entering a criterion gK1, K2 , K3, K4   min . The function g should be presented in a multiplicative form.

Next, it is nessessary to create a dynamic matrix of weights of the edges of the graph for each of the possible solutions to the task. o do this, the procedure described in [18] should be applied.

After that, the studied problem can be solved as a combinatorial optimization problem.

Variant 5.

Task 1.

Mathematical model: U1,U2 ,U3 , O1,..., O9 , O10 .

Result of the solution: The variants of the composition of the convoy in the form of sets are obtained

M 1  x1; x1;...; xm11,

1 1 2 M 2  x12; x22;...; xm22,…, 1 M d   x1d ; x2d ;...; xmds.

1

Problem Solving Technology 1. Task 1 in statement ( 1 ), ( 3 ), ( 4 ) is solved as a combinatorial search problem.

Task 2.

Mathematical model: M1 , U2 ,U3 , K4  min . Result of the solution: For every fixed value ____ i  1, d movement route of the convoy is obtained in the form of set

V 1  v1;v21;...;vs11;vs ,

2 V 2  v1;v22;...;vs21;vs ,…, 2 V d   v1;v2d ;...;vsd1;vs .

2

Problem Solving Technology 2. Problem 2 in statement ( 5 ) - ( 6 ) is solved at each fixed value ____ i  1, d .

Investigated task.

Solution of the investigated task is following:

M o  M1k , Vo  V2k  .

The pair is selected M1k  , V k among the sets 2 in the note for which the value of the complex performance indicator is maximum.

Note to variant 5.

In Option 5, to solve the problem under study ____  for each pair of sets M1i , V i  i  1, d  the 2   efficiency of transportation is evaluated by tactical, technical, economic and comprehensive performance index. The materials of the work are used [22].

Variant 6.

Task 1.

Mathematical model: U1,U2 ,U3 , O1,..., O9 , O10 ,O11,O12 ,O13 .

Result of the solution: The variants of the composition of the convoy in the form of sets are obtained

M 1  x1; x1;...; xm11,

1 1 2 M 2  x12; x22;...; xm22,…, 1 M d   x1d ; x2d ;...; xmds.

1

Problem solving technology 1. Problem 1 in statement ( 1 ), ( 3 ), ( 4 ) is solved with additional restrictions O11,O12 ,O13 , as a combinatorial task.

Task 2.

Mathematical model: M1 , U2 ,U3 , K4  min . Result of the solution: For each fixed value ____ i  1, d route of convoy movement is obtained in the form of a set

V 1  v1;v21;...;vs11;vs ,

2 V 2  v1;v22;...;vs21;vs ,…, 2 V d   v1;v2d ;...;vsd1;vs .

2

Problem solving technology 2. Problem 2 in statement ( 5 ) - ( 6 ) is solved at each fixed value ____ i  1, d .

Investigated task.

Solution of the investigated task is following:

The pair is selected M1k  , V2k  among the sets in the note for which the value of the complex performance indicator is maximum.

Note to variant 6.

In variant 6, to solve the problem under study ____  for each pair of sets M1i , V2i  i  1, d  the efficiency of transportation is evaluated by tactical, technical, economic and comprehensive performance index. The materials are used in paper [22].

General note.

It should be noted that the problem under study for each of the productions given in variants 1-6 should be solved in two productions, depending on how the edges are changed.

An analysis of the approaches described in variants 1-6 to solve the problem under study indicates that each of the options has the right to exist The ability to apply individual approaches to solving application problems depends on the solution of optimization problems in each case, which, in turn, depends on the search for analytical solutions or numerical applications of modern information technologies. The appropriateness of applying this or that approach also depends on the existence and time resources. The interesting thing is the question of the coincidence of the solutions of the tasks in each of the productions.

4. Conclusions

Therefore, as a result of the conducted research, an overview of possible approaches to solving the problem of transportation organization by a military convoy was carried out. The above approaches were the result of the analysis of the optimization decisions made by the authors for the choice of the appropriate composition of the military convoy and the appropriate route of its movement. Some of the approaches are based on the application of methods that have been worked out to solve the specified march organization tasks, and some of them are based on the use of the author's method of assessing the effectiveness of the march. In addition, the paper formalizes each of these approaches and outlines the algorithms for solving the problem under study in each statement. The proposed approaches make it possible to: classify the organization of the march; generate algorithms for solving the problem under study in each of the productions; to evaluate the limited possibilities of analytical methods available to solve the applied tasks of organizing a march; evaluate possible approaches to the formation of a mathematical tools for solving these problems; to conclude on the need to develop information technology that would provide the solution to the task of organizing the march in any setting.

5. Acknowledgements

The work was performed within the framework of joint research of the Department of General Scientific and Engineering Disciplines, the Department of Telecommunication and Information Systems and the Department of Vehicles and Engineering Support of the State Border Guard of the National Academy of the State Border Guard Service of Ukraine.

6. References

References

[1] O. V. Borovyk , R. V. Rachok , L. V. Borovyk , V. V. Kupelskiy , Mathematical model of the problem of formation of the composition of the transport convoy of the frontier commandant rapid response and its software-algorithmic implementation. Compilation of scientific works of the Military Institute of Kyiv National University named after Taras Shevchenko . 55 , 17 - 30 ( 2017 ).

[2] A. Y. Vayner , Tactical calculations . Military Publishing House , Moscow ( 1982 ).

[3] M. V. Chornyi , S. S. Stepanov , Predicting the effectiveness of a march of military formation by the reliability of weapons and military equipment by analytical modeling . Military Technical Compilation . 2 ( 14 ), 64 - 69 ( 2014 ).

[4] T. A. Matveychuk , Modeling and program implementation of the process of cargo transportation planning in military logistics . Military Technical Compilation . 14 , 18 - 25 ( 2016 ).

[5] M. Hilger , E. Kohler, R. Mohring , H. Schilling , Fast point-to-point shortest path computations with arc-flags. The Shortest Path Problem, (Discrete Mathematics and Theoretical Computer Science; vol. 74 ). 41 - 72 ( 2009 ).

[6] L. Antsfeld , T. Walsh, Finding Multi-criteria Optimal Paths in Multi-modal Public Transportation Networks using the Transit Algorithm . Artificial Intelligence and Logistics AILog 2012 Workshop Proceedings. 1 , 7 - 11 ( 2012 ).

[7] R. Geisberger , P. Sanders , D. Schultes , Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. Experimental Algorithms, (Theoretical informatics and general questions ; vol. 5038 ), 319 - 333 ( 2008 ).

[8] D. Delling , Time-dependent SHARCrouting . Cham: Springer International Publishing AG, Special Issue: European Symposium on Algorithms; vol. 60 ), 60 - 94 ( 2011 ).

[9] H. Bast , D. Delling , A. Goldberg , Route Planning in Transportation Networks . Cham: Springer International Publishing AG, ( Theoretical informatics and general questions ; vol. 9220 ), 19 - 80 ( 2016 ).

[10] A. Ganin , M. Kitsak , D. Marchese , Resilience and efficiency in transportation networks . Science Advances. 3 , 1 - 8 ( 2017 ).

[11] T. Zhao , J. Huang , J. Shi , Route Planning for Military Ground Vehicles in Road Networks under Uncertain Battlefield Environment . Journal of Advanced Transportation Received. 1 , 1 - 10 ( 2018 ).

[12] O. F. Kuzkin , Searching routes in city route networks using the branch and border method . Utilities of cities. 103 , 378 - 388 ( 2012 ).

[13] O. V. Vasylenko , D. P. Kucherov , O. O. Zacaryshyn , Geoinformation control systems for troop navigation tasks. Geoinformation systems in military tasks. Second scientific and technical seminar . Lviv ( 2011 ).

[14] I. V. Petlyuk , S. G. Vlasenko , O. I. Petlyuk , GIS technology in military affairs. Geoinformation systems and information technologies in military and special tasks "January GIS" . Third scientific and practical seminar . Lviv ( 2012 ).

[15] A. Perencsik , S. Woo , B. Booth , ArcGIS: Building a Geodatabase. Redlands: ESRI Press ( 2014 ).

[16] ArcGIS Resource Center . ESRI. http://doc.arcgis.com/ru/arcgis-online.

[17] T. G . Leys, ArcGIS. ArcMap. User Manual. MSU, Moscow ( 2005 ).

[18] O. V. Borovyk , R. V. Rachok , L. V. Borovyk , V. V. Kupelskiy , The technique of choosing the optimal route of movement of the column of equipment on a non-stationary road network. Radio electronics, informatics , control (RIC) . 4 ( 51 ), 111 - 120 ( 2019 ).

[19] B. P. Dovgiy , A. V. Loveykin , Y. S. Vakal , Y. Y. Vakal , Spline functions and their application . Publishing and Printing Center “Kyiv University”, Kyiv ( 2016 ).

[20] I. Y. Aleshin , A. V. Sycheva , D. K. Agisheva , T. A. Matveeva , Interpolation of unknown functions by cubic splines . Modern high technology. 5-2 , 188 - 189 ( 2014 ).

[21] Y. I. Pershyna , V. O. Pasichnyk , Approximation of discontinuous functions by discontinuous splines by the minimax method . Bulletin of KhNTU . 3 ( 66 ), 82 - 87 ( 2018 ).

[22] O. V. Borovyk , V. V. , Kupelskiy , Methods of estimation of efficiency of military transportations by a convoy of equipment . Weapons systems and military equipment . 3 ( 59 ), 25 - 35 ( 2019 )