ЦИКЛІЧНІ ПЕРЕСТАНОВКИ В МЕТОДАХ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ НА ОСНОВІ ЦИКЛІЧНИХ ТРАНСФЕРІВ
DOI:
https://doi.org/10.30837/bi.2019.2(93).05Ключові слова:
КОМБІНАТОРНА ОПТИМІЗАЦІЯ, ЦИКЛІЧНІ ПЕРЕСТАНОВКИ, ЦИКЛІЧНІТРАНСФЕРИ, ЗАДАЧА МАРШРУТИЗАЦІЇ, КЛАСТЕРИЗАЦІЇАнотація
Дана стаття присвячена стратегії розв’язання задач комбінаторної оптимізації, основаній на циклічних трансферах та властивостях множини циклічних перестановок. Циклічні трансфери – це один із відомих методів пошуку в околі, що дозволяє отримувати наближене рішення задач комбінаторної оптимізації. Існує загальний метод для пошуку в околі за допомогою циклічних трансферів. Він заснований на пошуку циклічного трансфера у допоміжному графі. Але особливості задачі, що розв’язується, деколи не дозволяють побудувати допоміжний граф та скористатися вже існуючими методами пошуку. У такому випадку ми пропонуємо використовувати множину циклічних перестановок та її властивості для побудови циклічних трансферів. Для демонстрації застосування, описаної у статті стратегії розв’язку задач комбінаторної оптимізації, було розв’язано задачу маршрутизації транспорту. Обчислювальні експерименти та їх результати наведені у статті.Посилання
Сергієнко І. В. Математичні моделі і методи розв’язання задач дискретної оптимізації // К.: Наук. думка, 1988. – С. 472.
Стоян Ю.Г., Яковлев С.В. Математичні моделі і оптимізаційні методи геометричного проектування // К.: Наук. думка, 1986. – С. 268.
Sergienko I. V., Hulianytskyi L. F., Sirenko S.I. Classification of applied methods of combinatorial optimization // Cybernetics and Systems Analysis. – 2009. – № 5(45). – P. 732–741.
Papadimitriou C.H., Steiglitz K. Combinatorial Optimization: Algorithms and Complexity // Prentice-Hall, englewood Cliffs, NJ, 1982 – Р. 528.
Стоян Ю Г., Ємець О. О. теорія і методи евклідової комбінаторної оптимізації // Київ.: ін-т систем. досліджень освіти, 1993. – С. 188.
Сергієнко І.В., Шило В.П. Сучасні підходи до розв’язання складних задач дискретної оптимізації // Проблеми управління і інформатики. – 2016. – № 1. – С. 32-40.
Ahuja R.K., Ergun Ö., Orlin J.B., Punnen A.P. A survey of very large-scale neighborhood search techniques // Discrete Applied Mathematics. – 2002. – № 1–3(123). – P.75–102.
Thompson P.M., Orlin J.B. The theory of cyclic transfers: working paper // Massachusetts Institute of Technology, Operations Research Center, 1989 – Р. 37.
Thompson P.M., Psaraftis H.N. Cyclic transfer algorithms for multivehicle routing and scheduling problems // Operations Research. – 1993. – № 5(41). – P. 935-946.
Yagiura M., Ibaraki Т., Glover F.W. An ejection chain approach for the generalized assignment problem // INFORMS Journal on Computing. – 2004. – № 2(16). – Р. 133-151.
Rego C., James T.L., Glover F.W. An ejection chain algorithm for the quadratic assignment problem // Networks. – 2010. – № 3(56). – P. 188-206.
Ahuja R.K., Orlin J.B., Sharma D. Multi-exchange neighborhood structures for the capacitated minimum spanning tree // Mathematical Programming. – 2001. – № 1(91). – Р. 71–97.
Post G., Ahmadi S., Geertsema F. Cyclic transfers in school timetabling // OR Spectrum. – 2012. – № 1(34). – P. 133–154.
Grebennik I.V., Chorna O.S. Influence of Certain Transpositions on the Cyclic Structure of Permutations // Cybernetics and Systems Analysis. – 2015. – № 6(51). – Р. 947–955.
Гребеннік І.В., Чорна О.С. Спеціальні транспозиції елементів перестановок і властивості композиції // Кібернетика і системний аналіз. – 2017. – № 1(53). – С.79–90.
Гребеннік І. В., Литвиненко А. С., Тітова О. С. Оптимізація лінійної функції на множині циклічних перестановок // біоніка інтелекту. – 2012.– № 2 (67). – С. 8–12.
Grebennik I., Baranov A., Chorna O., Gorbacheva E. Optimization of linear functions on a cyclic permutation based on the random search // An International Quarterly Journal on economics of Technology and Modelling Processes . – 2016. – № 3(5). – Р. 211–216.
Kumar S., Panneerselvam R. A survey on the vehicle routing problem and its variants // Intelligent Information Management. – 2012.– № 3(4). – Р. 66–74.
Pillac V., Gendreau M., Guéret C., Medaglia A. L. A review of dynamic vehicle routing problems / // european Journal of Operational Research. – 2013. – № 1(225). – Р. 1–11.
Toth P., Vigo D. Vehicle routing: problems, methods, and applications // Society for Industrial and Applied Mathematics, 2001 – Р. 481.
Панішев А. В. Моделі і методи оптимізації замкнутих маршрутів на транспортній мережі: монографія // ЖГтУ, Житомир, 2014 – С. 316.
Cordeau J., Laporte G., Ropke S. Recent models and algorithms for one-to-one pickup and delivery problems // The vehicle routing problem: latest advances and new challenges. – 2008. – № 43. – Р. 327–357.
Gendreau M., Laporte G., Potvin J. Metaheuristics for the capacitated VRP // The vehicle routing problem. Society for Industrial and Applied Mathematics. – 2001. – Р. 129–154.
Belhaiza S., M’Hallah R., Brahim G.B. A new Hybrid genetic Variable Neighborhood search heuristic for the Vehicle Routing Problem with Multiple Time Windows // 2017 Ieee Congress on evolutionary Computation (CeC). – 2017. – Р. 1319–1326.
Yao B., Hu P., Zhang M., Wang S. Artificial bee colony algorithm with scanning strategy for the periodic vehicle routing problem // SIMulATION: Transactions of The Society for Modeling and Simulation International. – 2013. – № 6(89). – Р. 762–770.
Gendreau M., Jabali O., Rei W. Stochastic vehicle routing problems // Vehicle routing: problems, methods, and applications. – 2014. – Р. 213–239.
Grebennik I. V., Pankratov A. V., Chugay A. M., Baranov A. V. Packing n-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an n-dimensional parallelepiped // Cybernetics and Systems Analysis. – 2010. – № 5(46). – Р. 793–802.
Stoyan Y. G., Gil N. I., Scheithauer G., Pankratov A., Magdalina I. Packing of convex polytopes into a parallelepiped // Optimization. – 2005. – № 2(54). – Р. 215–235.
Dupas R., Grebennik I., Lytvynenko O., Baranov O. An Heuristic Approach to Solving the one-to-one Pickup and Delivery Problem with Three-dimensional loading Constraints // International Journal of Information Technology and Computer Science Information Technology and Computer Science(IJITCS). – 2017. – № 10(9). – Р. 1–12.
Fabregas A. C., Gerardo B. D., Tanguilig III B. T. enhanced Initial Centroids for K-means Algorithm // International Journal of Information Technology and Computer Science(IJITCS). – 2017. – № 1(9). – Р. 26–33.
