Мезенцев Юрий Анатольевич,
Эстрайх Игорь Викторович
Аннотация
Представлен новый подход к решению проблем составления оптимальных по быстродействию расписаний параллельно-последовательных систем с использованием двухэтапной схемы: кластеризации и последующего определения маршрутов. Частными случаями применения разработанного инструментария являются решения различных модификаций задач маршрутизации с минимаксным критерием. Приведены формальные постановки рассматриваемых подзадач кластеризации и составления маршрутов в виде NP-трудных задач дискретного программирования. Предложен приближенный алгоритм решения поставленной задачи, основанный на ее декомпозиции на подзадачу оптимального по равномерной нагрузке на приборы разбиения множества заявок на подмножества и ряд подзадач определения последовательностей их обслуживания приборами. Приведены иллюстративные примеры применения развиваемого подхода, вычислены эмпирические оценки точности и быстродействия его программной реализации. На сгенерированных тестовых примерах в широком диапазоне размерностей исследованы быстродействие и точность реализованных алгоритмов. Обозначены возможные практические применения при построении календарных графиков реализации крупных промышленных проектов и определены направления развития предложенного подхода.
Ключевые слова: параллельно-последовательная система, неопределенные маршруты обслуживания, оптимальность по быстродействию, маршрутизация, кластеризация, задача коммивояжера.
Авторы:
Мезенцев Юрий Анатольевич
родился в 1955 году, д-р техн. наук, доцент, профессор кафедры экономической информатики Новосибирского государственного технического университета. Область научных интересов: задачи и методы дискретного программирования. Опубликовано
55 научных работ. (Адрес: 630073, Россия, Новосибирск, проспект Карла
Маркса 20. Email: mezencev@corp.nstu.ru).
Эстрайх Игорь Викторович
родился в 1961 году, старший преподаватель кафедры экономической информатики Новосибирского государственного технического университета. Область научных интересов: задачи и методы дискретного программирования. (Адрес: 630073, Россия, Новосибирск, проспект Карла Маркса 20. Email: estrajx@corp.nstu.ru).
Список литературы
- An algorithm for the traveling salesman problem / J.D.C. Little, K.G. Murty, D.W. Sweeney, C. Karel // Operations Research. – 1963. – Vol. 11. – P. 972–989.
- Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. – 1964. – № 9. – С. 219–222.
- Miliotis P. Integer programming approaches to the travelling salesman problem // Mathematical Programming. – 1976. – Vol. 10, iss. 3. – P. 367–378.
- Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem // Symposium on New Directions and Recent Results in Algorithms and Complexity. – Orlando: Academic Press, 1976. – P. 441.
- Lin S., Kernighan B.W. An effective heuristic algorithm for the traveling salesman problem // Operations Research. – 1973. – Vol. 21, iss. 2. – P. 498–516.
- Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic // European Journal of Operational Research. – 2000. – Vol. 126, iss. 1. – P. 106–130.
- Golden B.L., Skiscim С.C. Using simulated annealing to solve routing and location problems // Naval Research Logistics Quarterly. – 1986. – Vol. 33, iss. 2. – P. 261–279.
- Haist T., Osten W. An optical solution for the traveling salesman problem // Optics Express. – 2007. – Vol. 15, iss. 16. – P. 10473–10482. – doi: 10.1364/OE.15.010473.
- Javadian N., Alikhani M.G., Tavakkoli-Moghaddam R. A discrete binary version of the electromagnetism-like heuristic for solving traveling salesman problem // Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence. – Berlin; Heidelberg: Springer, 2008. – P. 123–130. – doi: 10.1007/978-3-540-85984-0_16.
- Bouzidi M., Riffi M.E. Adaptation of the harmony search algorithm to solve the travelling salesman problem // Journal of Theoretical & Applied Information Technology. – 2014. – Vol. 62, N 1. – P. 154–160.
- Balachandar S.R., Kannan K. Randomized gravitational emulation search algorithm for symmetric traveling salesman problem // Applied Mathematics and Computation. – 2007. – Vol. 192, iss. 2. – P. 413–421. – doi: 10.1016/j.amc.2007.03.019.
- Fiechter C.N. A parallel tabu search algorithm for large traveling salesman problems // Discrete Applied Mathematics. – 1994. – Vol. 51, iss. 3. – P. 243–267. – doi: 10.1016/0166-218X(92)00033-I.
- Verma O.P., Jain R., Chhabra V. Solution of travelling salesman problem using bacterial foraging optimisation algorithm // International Journal of Swarm Intelligence. – 2014. – Vol. 1, N 2. – P. 179–192. – doi: 10.1504/IJSI.2014.060243
- Dorigo M., Gambardella L.M. Ant colonies for the travelling salesman problem // BioSystems. – 1997. – Vol. 43, iss. 2. – P. 73–81. – doi: 10.1016/S0303-2647(97)01708-5.
- Wong L.P., Low M.Y.H., Chong C.S. A bee colony optimization algorithm for traveling salesman problem // Second Asia International Conference on Modelling & Simulation, Kuala Lumpur, Malaysia, 13–15 May 2008. – Piscataway: IEEE, 2008. – P. 818–823. – doi: 10.1109/AMS.2008.27.
- Jati G.K. Evolutionary discrete firefly algorithm for travelling salesman problem. –Berlin; Heidelberg: Springer, 2011. – P. 393–403. – doi: 10.1007/978-3-642-23857-4_38.
- Feng X., Lau F.C.M., Yu H. A novel bio-inspired approach based on the behavior of mosquitoes // Information Sciences. – 2013. – Vol. 233. – P. 87–108. – doi: 10.1016/j. ins.2012.12.053.
- Xue-Hui L., Ye Y., Xia L. Solving TSP with shuffled frog-leaping algorithm // Eighth International Conference on Intelligent Systems Design and Applications, ISDA 2008. – Los Alamitos, 2008. – Vol. 3. – P. 228–232. – doi: 10.1109/ISDA.2008.346.
- An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems / Е. Osaba, X.-S. Yang, F. Diaz, П. Lopez-Garcia, R. Carballedo // Engineering Applications of Artificial Intelligence. – 2016. – Vol. 48. – P. 59–71. – doi: 10.1016/ j.engappai.2015.10.006.
- Mzili I., Riffi M.E. Discrete penguins search optimization algorithm to solve the traveling salesman problem // Journal of Theoretical & Applied Information Technology. – 2015. – Vol. 72, N 3. – P. 331–336.
- Bouzidi A., Riffi M.E. Discrete cat swarm optimization to resolve the traveling salesman problem // International Journal of Advanced Research in Computer Science and Software Engineering. – 2013. – Vol. 3, iss. 9. – P. 13–18. – doi: 10.1109/WCCCS.2014.7107914.
- Agharghor A., Riffi M.E. Hunting search algorithm to solve the traveling salesman problem // Journal of Theoretical & Applied Information Technology. – 2015. – Vol. 74, N 1. – P. 120–129.
- Producer-scrounger method to solve traveling salesman problem / M.A.H. Akhand, Pintu Chnadra Shill, Md. Forhad Hossain, A.B.M. Junaed, K. Murase // International Journal of Intelligent Systems and Applications. – 2015. – Vol. 7, N 3. – P. 29–36. – doi: 10.5815/ijisa.2015.03.04.
- Goldbarg E.F.G., Souza G.R. de, Goldbarg M.C. Particle swarm optimization algorithm for the traveling salesman problem [Electronic resource] // Traveling Salesman Problem. – 2008. – URL.: http://www.intechopen.com/books/traveling_salesman_problem/particle_ swarm_optimization_algorithm_for_the_traveling_salesman_problem (accessed: 07.04.2016).
- Potvin J.Y. Genetic algorithms for the traveling salesman problem // Annals of Operations Research. – 1996. – Vol. 63, iss. 3. – P. 337–370. – doi: 10.1007/BF02125403.
- Ouaarab A., Ahiod B., Yang X.S. Discrete cuckoo search algorithm for the travelling salesman problem // Neural Computing and Applications. – 2014. – Vol. 24, iss. 7/8. – P. 1659–1669. – doi: 10.1007/s00521-013-1402-2.
- Clarke G., Wright J.W. Scheduling of vehicles from a central depot to a number of delivery points // Operations Research. – 1964. – Vol. 12, N 4. – P. 568–581.
- Костюк Ю.Л., Пожидаев М.С. Приближенные алгоритмы решения сбалансированной задачи k коммивояжеров // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. – 2008. – № 1. – С. 106–112.
- Solution of a min-max vehicle routing problem / D. Applegate, W. Cook, S. Dash, A. Rohe // INFORMS Journal on Computing. – 2002. – Vol. 14, iss. 2. – P. 132–143. – doi: 10.1287/ijoc.14.2.132.118.
- Ren C. Solving min-max vehicle routing problem // Journal of Software. – 2011. – Vol. 6, N 9. – P. 1851–1856. – doi: 10.4304/jsw.6.9.1851-1856.
- Алексеев А.О. Минимаксная задача M коммивояжеров // Журнал вычислительной математики и математической физики. – 1991. – Т. 31, № 12. – С. 1899–1905.
- Svestka J.A., Huckfeldt V.E. Computational experience with an m-salesman traveling salesman algorithm // Management Science. – 1973. – Vol. 19, iss. 7. – P. 790–799.
- Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures // Omega. – 2006. – Vol. 34, iss. 3. – P. 209–219. – doi: 10.1016/j.omega. 2004.10.004.
- Мезенцев Ю.А. Оптимизация расписаний параллельных динамических систем в календарном планировании // Информационные технологии. – 2008. – № 2. – С. 16–23.
- Мезенцев Ю.А. Оптимизация расписаний параллельно-последовательных систем в календарном планировании // Информационные технологии. – 2009. – № 6. – С. 35–41.
- Мезенцев Ю.А. Эффективные вычислительные методы решения дискретных задач оптимизации управления производственными процессами. – Новосибирск: Изд-во НГТУ, 2015. – 275 с.
- Мезенцев Ю.А. Метод бинарных отсечений и ветвлений целочисленного программирования // Доклады Академии наук высшей школы Российской Федерации. – 2011. – № 1 (16). – С. 12–25.
- Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. – М.: Мир, 1984. – 496 с.
