Development the methods of optimum placement undirected planar objects with piecewise non-linear boundaries in the multiply area

• Autorzy: Chaplya Yu. , Sobol O.
• Języki publikacji: EN

Abstrakty

EN

In this paper the statement of the problem is formulated and the mathematical model of optimization the placement of the undirected planar geometrical objects with piecewise non-linear boundaries in the multiply area is developed. It is shown the geometrical interpretation and derived the estimate of the number of restrictions in the model. On the basis of a mathematical model for finding the global extremum of the objective function was proposed modified method of branches and boundaries. It is also shown the solutions tree that takes into account the problems of optimal placement of undirected planar geometrical object with piecewise nonlinear boundaries in the multiply area, and received the complexity of this method. For locally optimal solutions of the problem modified simulated annealing method has been developed. Thus the analytical expressions for the function of energy system were received, the function, that describes the decrease of temperature over time, function that forms a new state of system. The method of formation the new state of the system was investigated in more detail, which is based on a random permutation of numbers the pair of the objects, it is also based on a consistent placement of objects according to reshuffle their numbers and determining the probability of transition to a new state. It is shown the example of determining permissible points of placement the local coordinate system of the specific geometrical object. The conclusion is that to solve practical optimization problems of placement of the undirected planar geometrical objects with piecewise non-linear boundaries in the multiply area should be used the modified simulated annealing method.

Słowa kluczowe

EN

optimal placement; object with piecewise linear boundary; multiply area; mathematical model; branch and bound method; method of simulated annealing

• Wydawca: Polish Academy of Sciences, Branch in Lublin
• Czasopismo: ECONTECHMOD : An International Quarterly Journal on Economics of Technology and Modelling Processes
• Rocznik: 2016
• Tom: Vol. 5, No 2
• Strony: 39--44
• Opis fizyczny: Bibliogr. 28 poz., wykr., wz.

Twórcy

autor

Chaplya Yu.

• National University of Civil Protection of Ukraine

autor

Sobol O.

• National University of Civil Protection of Ukraine

Bibliografia

• 1. Rvachev V.L. 1982. Theory of R-functions and Some Applications. Kiev: Naukova Dumka, p.551.(In Russian).
• 2. Rvachev V.L., Sheiko T.I. 1995. R-functions boundary value problems in mechanics, Appl. Mech. Rev, 48, N4, p.151-188.
• 3. Shapiro V. 2007. Semi-analytic geometry with RFunctions, Acta Numerica, Cambridge University Press, 16, p.239-303.
• 4. Stoyan Yu.G., Yakovlev S.V. 1986. Mathematical models and optimization methods of geometric design. Kiev: Naukova Dumka, 268. (In Russian).
• 5. Komyak V.M. 1980. Optimization of placement planar geometric objects in areas with complex form. Kharkiv, p.24. (In Russian).
• 6. Panishev A., Levchenko A., Matsiy O. 2010. Optimization of Closed Routes for Transport Network // Artificial intellect. №1, Рp.43-49.
• 7. Komyak V.M., Muntyan V., Sobol A.,Komyak V.V. 2013. Mathematical model and algorithm of defining optimal routes in the problem of compose rational evacuation plans. Moscow: RUDN, Рp. 220-225. (In Russian).
• 8. Sobol O.M., Sobina V.O., Tur O.M. 2010. Construction of ω-function in the problems of covering given area by geometric objects with variable metric characteristics // Applied Geometry and Engineering Graphics. 86, Рp.118-122. (In Ukrainian).
• 9. Sobina V.O. 2011. Modeling the rational covering of railway objects by departure areas of firefighting subdivisions // Kharkiv University of Air Forces, 1(27), Рp.240-242. (In Ukrainian).
• 10. Sobol O.M. 2008. Method of rational splitting multiply sets by polygons with variable metric characteristics // Scientific Notes, 22(1), Рp.324-328. (In Ukrainian).
• 11. Sadkovyi V., Komyak V., Sobol O. 2008. Efficient splitting sets at regional planning in the field of civil protection. Gorlivka: Lihtar, p.174. (In Ukrainian).
• 12. Zhiltsov A., Kondratenko I., and Sorokin D. 2012. Mathematical modelling of nonstationary electromechanical processes in Coaxial-Linear Engine // ECONTECHMOD. An international quarterly journal, Vol. 1, No. 2, Рp. 69-74.
• 13. Batluk V., Basov M., Klymets’ V. 2013. Mathematical model for motion of weighted parts in curled flow // ECONTECHMOD. An international quarterly journal, Vol. 2, No. 3, Рp.17-24.
• 14. Popov V., Chub I., Novozhylova M. 2015. The optimal structure for territorial technogenic safety system // ECONTECHMOD. An international quarterly journal, Vol.4, No.3, Рp.79-84.
• 15. Dowsland K., Gilbert M., Kendall G. 2007. A local search approach to a circle cutting problem arising in the motor cycle industry. Journal of the Operational Research Society, N.58, Рp.429-438.
• 16. Milenkovic V.J. 2002. Densest translational lattice packing of non-convex polygons. Computational Geometry, N.22, Рp.205-222.
• 17. Gomes A.M., Oliveira J.F. 2006. Solving irregular strip packing problems by hybridizing simulated annealing and linear programming. European Journal of Operational Research, N.171, Рp.811-829.
• 18. Birgin E., Gentil J.M. 2010. New and improved results for packing identical unitary radius circles within triangles, rectangles and strips. Computers & Operations Research, N.37, Рp. 1318-1327.
• 19. Bortfeldt A. 2006. A genetic algorithm for the twodimensional strip packing problem with rectangular pieces. European Journal of Operational Research, N.172, Рp.814-837.
• 20. Imahori S., Yagiura M. 2010. The best-fit heuristic for the rectangular strip packing problem: an efficient implementation and the worst-case approximation ratio. Computers & Operations Research, N.37, Рp.325-333.
• 21. Zlotnik M. 2007. Mathematical model and method of solution a problem of placement undirected polygons and circles. Kharkiv, 19. (In Ukrainian).
• 22. Pankratov A., Stoyan Yu., Romanova T. Zlotnik M. 2011. Automatic system of phi-function generation for arbitrary 2D-objects Proc. 8nd ESICUP Meeting. Copenhagen, 20.
• 23. Popova A.V. 2014. Model and method of optimum placement planar directed geometric objects with piecewise non-linear boundaries // Modern Problems of Modeling, N.2, Рp.88-93. (In Ukrainian).
• 24. Chaplya Yu., Popova A., Sobol O. 2014. Geometric information in the problems of optimum placement planar geometric objects with piecewise non-linear boundaries. Kyiv: DIYA, Vol.3, Рp.214-219. (In Ukrainian).
• 25. Komyak V., Sobol O., Chaplya Yu. 2014. Mathematical model of optimum placement planar undirected geometric objects with piecewise nonlinear boundaries // Bulletin of Kherson National Technical University, 3(50), p. 300-305. (In Ukrainian).
• 26. Sobol O., Chaplya Yu. 2014. Method of construction 0-level of Φ-function for planar undirected geometric objects with piecewise nonlinear boundaries // Modern Problems of Modeling, N.3, Рp.119-125. (In Ukrainian).
• 27. Kirkpatrick S., Gelatt C., Vecchi M. 1983. Optimization by simulated annealing. Science, Vol. 220, Рp.671-680.
• 28. Savin A., Timofeeva N. 2012. Application of optimization algorithm simulated annealing method on parallel and distributed computing systems. News of Saratov University, 1 (12), Рp.110-116. (In Russian).

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę