Development of a Method to Find the Location of a Logistics Hub

Abstract

The task of finding the optimal location of the logistics hub as the point closest to the given roads is considered in the paper. The mathematical formulation of the task is done in the form of finding the point that would be closest to the farthest road. The roads have been proposed to be represented as straight lines. The method of coordinate descent for the two-dimensional case has been analyzed. Based on the golden ratio method, the method for finding the optimal location point of the logistics hub for the two-dimensional and three-dimensional case has been developed. The results are generalized to the multidimensional case. It is shown that for the two-dimensional case the time complexity of the proposed approach is ( · 2 ), for the m-dimensional case - ( · ). The advantages of the developed method over the method of coordinate descent are theoretically shown. Numerical research has been performed. Advantages of the developed method over the method of ternary search are demonstrated. The considered task can be a subtask for larger problems, where it can be called repeatedly. Accordingly, its effective solution will lead to a significant acceleration of the search for the solution to big problems.

Keywords

• 1 Optimization
• golden ratio method
• minimization of many variables functions

1. Introduction

The problem of placing a logistics hub is solved based on many aspects. In papers [ 1-3 ] a system analysis of this problem is performed. It shows a variant of systematization of economic, social, geographical, political, and other factors that are appropriate to consider when determining the coordinates for the location of the logistics hub. In [ 4 ], a multi-method approach to the implementation of a two-stage study in solving this problem was developed. The research includes the usage of multi-criteria decision theory and data mining. In this kind of research, among others, there is the task of finding a field position that would be optimal in the criterion of proximity to roads, railroad connections, ports, etc. Such a task can be reduced to the problem of finding the shortest distance to the straight lines and represented through optimization of a multivariable function. The problem of optimization of a multivariable function is the subject of many modern studies. A method of unconstrained global optimization is presented in [ 5 ]. The method is iterative and guaranteed to coincide for polynomial functions. In [ 6 ] a simultaneous perturbation method is proposed, using which the solution of an optimization problem is reduced only to the analysis of two dimensions, irrespective of its dimensionality. This simplifies the implementation and speeds up the optimization process. In [ 7-10 ] optimization methods based on the golden ratio method were developed. The methods differ in the way of step selection and computational complexity. Optimization methods based on evolutionary technology are widespread [ 11-13 ]. The advantage of this class methods is the possibility to avoid the problem of getting into local minima. However, their use requires the participation of an expert analyst for setting basic parameters of the method per specific features of the target function. Neural network methods in the process of solving optimization problems are presented in [ 14-16 ].

Optimization problems and methods for their solution often arise in data mining tasks [ 17-19 ]. In them, to solve, for example, clustering problems, the target function to be optimized is constructed specially. Models and methods of equal and multi-criteria optimization are given in [ 20, 21 ].

A separate group of optimization methods consists of methods developed to solve narrowly applied problems. Manuscript [ 22 ] describes the analysis and target programming approaches for solving the defense budget optimization problem. In [ 23 ], a method for optimizing the trajectory of a robot has been developed. The method allows determining such an optimal trajectory in a room that minimizes energy consumption. In [ 24 ], the task of fiber orientation optimization in composite structures is solved. The developed method is based on the optimized choice of discrete angles, allowing to avoid the multiple local minima problem. In [ 25 ], numerical optimization of current converter efficiency was proposed. It is shown that the results obtained by the genetic algorithm are close to the experimental data. The mentioned methods differ in the method of software implementation, simplicity of use, speed of convergence, and computational complexity. Taking into account the consequences of the “No Free Lunch” (NFL) theorem [ 26 ], it can be argued that it is impossible to construct one best method for all optimization problems, so the development of special methods for solving applied optimization problems is actual.

2. Problem setting

Consider the two-dimensional case. The roads in the task of optimal location of the logistics hub will be represented by straight lines. Then the task will consist in finding the point that would be closer to the most distant of the roads.

Perform the mathematical formulation in this formulation as follows: let the set of lines be given L  {L i | i  1, n} , each is defined by two points of the plane L i  {(x1i , y1i ), (x2i , y2i )} , i 1, n , thereby i {1, 2,..., n} (x1i , y1i )  (x2i , y2i ) . It is necessary to find such a point of the plane

A*(x*, y*) , (x, y)  R2 , the distance from which to the farthest line would be minimal.

Introduce the distance function di (x, y)  d (Li , A) , that is equal to the euclidean distance from the point A(x, y) to the line Li , i 1, n . Then the problem of placing the logistics hub will be to find a point A*(x*, y*) for which the condition was satisfied:

A*  Arg min max d(Li , A)

A(x,y)R2 i1,n To solve the task, construct the equation of lines in the form:

Li : ai x  bi y  ci  0 , i 1, n .

When calculating the coefficients ai ,bi ,ci , use the equation of a line passing through two points: Li :      Then the equation will be: x  x1i , y  y1i ,  x  x1i   x2i  x1i y  y1i , if x1i  x2i and y1i  y2i ; y 2i  y1i if x1i  x2i ; if y1i  y2i .

, i 1, n .

x( y2i  y1i )  y(x1i  x2i )  x1i ( y1i  y2i )  y1i (x2i  x1i )  0 Therefore, ai  y2i  y1i , bi  x1i  x2i , ci  x1i ( y1i  y2i )  y1i (x2i  x1i ) .

To find the distance from a point A(x, y) to a line Li using the rule: d (Li , A)  ai x  bi y  ci

Thus, to solve the task of finding coordinates for the location of the logistics hub, it is necessary to find a solution to such a task: (1) (2) (3) (4) (5) f (x, y)  max ai x  bi y  ci  i1,n min (x, y)R2

3. Methods and algorithms for solving the optimization task 3.1.

The general idea of subordinate descent method

Task (6) is an optimization task for a function of many variables. The method of subordinate descent often used to solve it [ 27, 28 ], the algorithm of which described bbelow:

Step 1. Determine the initial approximation A0 (x0 , y0 ) .

Step 2. Substitute x0 in the function f and solve the task of minimizing a function of one variable: Let y1  Arg myiRn f (x0 , y) і A1 ( x0 , y1 ) .

Step 3. Substitute y1 into a function f . Let's solve the problem f (x0 , y)  max ai x0  bi y  ci  min

i1,n ai2  bi2 yR f (x, y1)  max ai x  bi y1  ci  min

i1,n ai2  bi2 yR Let x1  Arg min f (x, y1) and A2 ( x1, y1 ) . The process iteratively continues until f ( Ak )  f ( Ak 1) .

xR The criteria for stopping the algorithm can be: - Ak  Ak1   – the proximity of points generated in successive steps; - f ( Ak )  A(k1)   proximity of the values of the target function, obtained at successive steps; - exceeding the specified time for finding the optimal value, etc.

The question of convergence of the method remains open. 3.2. Development of an optimization method based on the Golden Ratio method

3.2.1. Two-dimensional case

Let's investigate how the target function (6) is represented in space. The distance function of an arbitrary point ( , ) to the i-th line will be a plane. And the target function will coincide then with one plane and then another that will intersect with the previous one. A typical view of the target function is shown in Figure 1. While recording the distance function from the point to the lines when one of the parameters x or y is fixed in the form of (7) or (8), it turns into a unimodal function. That is, (7) and (8) are continuous, and as the uncommitted parameter changes, they first decrease and then increase. This is shown schematically in Fig. 2. Therefore, let apply to find the minimum value of the target function an approach that uses the call of the golden ratio method in itself. Due to the specific features of functions (7) and (8), to find their minimum value let apply the golden ratio method for one-dimensional optimization. The method is applied alternately – first for (7), then for (8). Let propose an approach that will give a significant acceleration. For this purpose, let focus on the fact that the target function at each fixed value of variable x is unimodal. Therefore, the following modification will be quite effective: within each step for variable x, find the optimal value of the target function immediately and concerning variable y. This process is shown schematically in Fig. 3. This approach significantly accelerates the search for a solution. Because in this way the modified golden ratio method is run once and after its completion, the optimal solution is obtained at once. And the method of coordinate descent for obtaining such a result will require a considerable number of iterations. General schemes of methods for solving tasks are shown in Figs. 4-7. Here, the function (6) has been modified as follows to reduce the number of operations when calculating the function: f (x, y)  max

i1,n where ai 

ai .

 mi1a,nx aix  biy  ci  min (x,y)R2 (9) Algorithm for two-dimensional case: Step 1. Enter the number of lines N, and N pairs of points that will specify a straight line. Step 2. Set left (xl) and right (xr) the boundary of the interval to find the optimal value along Step 3. Divide the boundaries in relation to the golden ratio

Step 4. To fix value 1. Set left (yl) and right (yr) the boundary of the interval to find the the abscissa where = 1+√5.

2

then yr = 2, else yl = 1.

Step 5. Divide the boundaries in relation to the golden ratio where = 1+√5.

2

Step 6. If the value of the objective function ( 1, 1) < ( 1, 2), optimal value along the abscissa

Step 8. To fix the value of the objective function 1 = ( 1, ).

Step 9. To fix value 2. Set left (yl) and right (yr) the boundary of the interval to find the Step 10. To divide the boundaries along the y-axis with respect to the golden ratio 1 =

− − , 2 = + − ,

then yr = 2, else yl = 1. then xr = 2, else xl = 1. where = 1+√5.

2 Step 11. If the value of the objective function ( 2, 1) < ( 2, 2), Step 12. Repeat steps 10 - 11 until

Step 14. If the value of the objective function 1 < 2, Step 13. To fix the value of the objective function 2 = ( 2, ).

|

, ,

Step 16. The answer will be the value on the abscissa, which is equal ∗ = result will be a point ( ∗, ∗). on the y-axis ∗ is found by performing steps 4 - 7, fixing the value of ∗. Accordingly, the desired

3.2.2. The three-dimensional case

Consider the three-dimensional case when the lines are defined in space and it is needed to find the location of a point from which the distance to the lines would be as small as possible.

Step 15. Repeat steps 3 - 14 until where the parameters a1i , a2i ,bi1,b2i , c1i , c2i , d1i , d2i are calculated from the equations: Li :  a1i x  b1i y  c1i z  d1i  0 a2i x  b2i y  c2i z  d2i  0 x  x1i 

The ideas described above also apply to the three-dimensional case. That is, the implementation of the solution search would be as follows:

Repeat the first 5 steps, as in the two-dimensional case.

Step 6. To fix value 1. Set left (zl) and right (zr) the boundary of the interval to find the Step 7. To divide the boundaries along the y-axis with respect to the golden ratio the the set of lines are defined as L i  {(x1i , y1i , z1i ), (x2i , y2i , z2i )} , i 1, n , whereas i {1, 2,..., n} (x1i , y1i , z1i )  (x2i , y2i , z2i ) . Then define the line by a system of two equations of the form: optimal value along the abscissa

Step 10. To fix the value of the objective function 1 = ( 1, 1, ).

Step 11. To fix value 2. Set left (zl) and right (zr) the boundary of the interval to find the Step 12. To divide the boundaries along the y-axis with respect to the golden ratio , Step 9. Repeat steps 7 - 8 until

then zr = 2, else zl = 1. where = 1+√5.

2 Step 8. If the value of the objective function ( 1, 1, 1) < ( 1, 1, 2), then zr = 2, else zl = 1.

Step 14. Repeat steps 12 – 13 until 1+√5.

2 Step 13. If the value of the objective function ( 1, 2, 1) < ( 1, 2, 2), (10) (11) (12) where

3.2.3. Generalization of the method

Consider the m-dimensional case where the lines are given in m-dimensional space and it is needed to find the location of a point from which the distance to the lines would be as small as possible. The target function, in this case, will be as presented below: max d (Li , A)  i1,n

min A(x1,x2 ,...,xm )Rm (13) The ideas and implementation for the m-dimensional case will be similar to the above.

The advantage of the proposed approach becomes extremely significant. The time complexity of the proposed approach for the m-measure case will be ( · ), where C is a parameter depending on search range and accuracy. The solution by the method of coordinate descent will require such a number of iterations, which far exceeds the value of −1 . This indicates that the method of coordinate descent is significantly inferior to the proposed approach

4. Numerical Research and discussion

For the two-dimensional case, the time complexity of the proposed approach is ( · 2 ), where C is a parameter that depends on the search range and accuracy. The square of operations arises from the fact that one golden ratio method is used in another. Let also compare the golden ratio method with the ternary search method. The ternary search will be used the same way as it was proposed in the case of the golden ratio method. That is, it will internally call itself.

The ternary search method is easily derived from the golden ratio method by simply replacing the coefficients 0.38 by 1/3, and 0.62 by 2/3. Codeforces measured the solution time for both of these methods when the dimensionality of this problem is larger and will go from 10000 to 100000 in steps of 10000. As can be seen from Figure 9, there is a linear dependence of the execution time of the considered methods on the dimensionality of the problem. The ternary search method requires about 40% more time than the golden ratio method to find the solution to the problem in question. Another important indicator is that the number of iterations of the golden ratio method to determine the desired value of the variable x in the range [−109, 109] will be 74, and for the ternary search method – 87, if the accuracy of 10-6 is required.

5. Conclusions

The study is devoted to the method development for determining the point for the optimal location of the logistics hub. The mathematical formulation of the task for the two-dimensional, threedimensional and multidimensional cases in the form of the optimization task of the several variables function was carried out. A method for solving the task based on the golden ratio method has been developed. The peculiarity of the proposed method is the nesting of the golden ratio method "in itself" that allows reducing the considerably computational complexity of the algorithm.

A comparative analysis is carried out and the advantages of the developed method with the method of coordinate descent and search are shown. The considered problem can be a subtask for larger tasks, where it can be called repeatedly. Accordingly, its effective solution will lead to a significant acceleration of the search for the solution of larger tasks as well.

6. Acknowledgments

The authors are grateful to the colleagues at the Department of Information Technology, Uzhhorod National University for productive discussions of the topic and results of this work.

7. References

References

[1] Alptekin Ulutaş , Can Bülent Karakuş, Ayşe Topal. “ Location selection for logistics center with fuzzy Swara and CoCoSo methods . ” Journal of Intelligent & Fuzzy Systems , 38 .4, ( 2020 ) 4693 - 4709 .

[2] Jacek Brdulak , Bartosz Zakrzewski. “ Methods for calculating the efficiency of logistics centres . ” Archives of Transport , 27 .28, iss . 3- 4 , ( 2013 ) 25 - 43 .

[3] Pawel Zajac . Evaluation method of energy consumption in logistic warehouse systems . Switzerland: Springer International Publishing, 2015 .

[4] Shahrooz Shahparvari et al. “ A GIS-LP integrated approach for the logistics hub location problem . ” Computers & Industrial Engineering , 2020 , 146 : 106488 .

[5] Hans Bremermann . “A method of unconstrained global optimization . ” Mathematical Biosciences , 1970 , 9 : 1 - 15 .

[6] James C. Spall. “ An overview of the simultaneous perturbation method for efficient optimization . ” Johns Hopkins apl technical digest , 19 .4, ( 1998 ) 482 - 492 .

[7] Amin Foroughi Nematollahi , Abolfazl Rahiminejad, Behrooz Vahidi. “A novel meta-heuristic optimization method based on golden ratio in nature . ” Soft Computing , 24 .2, ( 2020 ) 1117 - 1151 .

[8] Yura Malitsky . “ Golden ratio algorithms for variational inequalities . ” Mathematical Programming , 184 .1, ( 2020 ) 383 - 410 .

[9] Dang Van Hieu , Yeol Je Cho , Yi‐Bin Xiao . “ Golden ratio algorithms with new stepsize rules for variational inequalities . ” Mathematical Methods in the Applied Sciences , 42 . 18 , ( 2019 ) 6067 - 6082 .

[10] Y. A. Pervak , A. Mitsa , I. Holovach , I. V. Fekeshgazi . “ Influence of transition film-substrate layers on optical properties of the multilayer structures . ” Selected Papers from the International Conference on Optoelectronic Information Technologies. International Society for Optics and Photonics , Vol. 4425 ( 2001 ) 321 - 325 .

[11] Jane-Jing Liang , Ponnuthurai Nagaratnam Suganthan, Kalyanmoy DEB. “ Novel composition test functions for numerical global optimization . ”Proceedings 2005 IEEE Swarm Intelligence Symposium , 2005 . SIS 2005 . IEEE, ( 2005 ) 68 - 75 .

[12] O. Mulesa , I. Povkhan, T. Radivilova , O. Baranovskyi. “ Devising a method for constructing the optimal model of time series forecasting based on the principles of competition .” EasternEuropean Journal of Enterprise Technologies , 5 ( 4 ( 113 ), ( 2021 ) 6 - 11 . https://doi.org/10.15587/ 1729 - 4061 . 2021 .240847

[13] Handing Wang et al. “ Offline data-driven evolutionary optimization using selective surrogate ensembles . ” IEEE Transactions on Evolutionary Computation , 23 .2, ( 2018 ) 203 - 216 .

[14] Matias Sessarego et al. “ Design optimization of a curved wind turbine blade using neural networks and an aero-elastic vortex method under turbulent inflow . ” Renewable Energy , 146 , ( 2020 ) 1524 - 1535 .

[15] Lina Deng , Bo Feng, Yue Zhang. “ An optimization method for multi-objective and multi-factor designing of a ceramic slurry: Combining orthogonal experimental design with artificial neural networks .” Ceramics International, 44 . 13 , ( 2018 ) 15918 - 15923 .

[16] Asti Herliana et al. “ Feature selection of diabetic retinopathy disease using particle swarm optimization and neural network.” 2018 6th International Conference on Cyber and IT Service Management (CITSM) . IEEE, ( 2018 ) 1 - 4 .

[17] O. Mulesa , V. Snytyuk , I. Myronyuk. “ Forming the clusters of labour migrants by the degree of risk of hiv infection . ” Eastern-European Journal of Enterprise Technologies . Vol. 3, N 4 ( 81 ), ( 2016 ) 50 - 55 . DOI : 10 .15587/ 1729 - 4061 . 2016 . 71203 .

[18] Alexander Kuchansky . “ Combined models for forecasting the air pollution level in infocommunication systems for the environment state monitoring .” 2018 IEEE 4th International Symposium on Wireless Systems within the International Conferences on Intelligent Data Acquisition and Advanced Computing Systems (IDAACS-SWS) . IEEE, ( 2018 ) 125 - 130 .

[19] I. Povkhan , M. Lupei , M. Kliap , V. Laver . “ The issue of efficient generation of generalized features in algorithmic classification tree methods . ” International Conference on Data Stream Mining and Processing: DSMP 2020 Data Stream Mining & Processing , Springer, Cham, ( 2020 ) 98 - 113 .

[20] H. Hnatiienko . ” Choice Manipulation in Multicriteria Optimization Problems.” Selected Papers of the XIX International Scientific and Practical Conference "Information Technologies and Security" (ITS 2019 ), ( 2019 ) 234 - 245 .

[21] H. Hnatiienko , N. Tmienova , A. Kruglov . ” Methods for Determining the Group Ranking of Alternatives for Incomplete Expert Rankings .” Shkarlet S. , Morozov A. , Palagin A . (eds) Mathematical Modeling and Simulation of Systems (MODS' 2020 ). MODS 2020. Advances in Intelligent Systems and Computing , vol 1265 . Springer, Cham, ( 2021 ) 217 - 226 . doi: 10 .1007/978-3- 030 -58124-4_ 21 .

[22] O. V. Barabash , P. V. Open'ko , O. V. Kopiika , H. V. Shevchenko , N. B. Dakhno . “ Target Programming with Multicriterial Restrictions Application to the Defense Budget Optimization.” Advances in Military Technology . Vol. 14 , No. 2 , ( 2019 ) 213 - 229 . Doi: 10 .3849/aimt.01291

[23] M. Bagheri , M. Krstić , P. Naseradinmousavi . “ Multivariable extremum seeking for joint-space trajectory optimization of a high-degrees-of-freedom robot . ” Journal of Dynamic Systems , Measurement, and Control , 2018 , 140 .11: 111017 .

[24] Y. Zhou , S. Zheng , G. Zhang. “ Artificial neural network based multivariable optimization of a hybrid system integrated with phase change materials, active cooling and hybrid ventilations . ” Energy Conversion and Management , 2019 , 197 : 111859 .

[25] M. Çelebi . “ Efficiency optimization of a conventional boost DC/DC converter .” Electrical Engineering, 100 .2, ( 2018 ) 803 - 809 .

[26] S. P. Adam et al. “ No free lunch theorem: A review.” Approximation and optimization , ( 2019 ) 57 - 82 .

[27] Zhe Wang , Y. LI , J. LU. “ Coordinate descent full configuration interaction . ” Journal of chemical theory and computation , 15 .6, ( 2019 ) 3558 - 3569 .

[28] K. Fountoulakis , R. Tappenden . “ A flexible coordinate descent method . ” Computational Optimization and Applications , 70 .2, ( 2018 ) 351 - 394 .