Математическая модель и численные методы решения задачи синтеза расписаний работы комплексов лесозаготовительных машин
Автор: Шабаев Антон И., Соколов Антон П., Урбан Александр Р., Пятин Дмитрий С.
Журнал: Resources and Technology @rt-petrsu
Статья в выпуске: 1 т.15, 2018 года.
Бесплатный доступ
В статье приведена постановка задачи синтеза расписаний работы комплексов лесозаготовительных машин, включающая распределение комплексов по делянкам, запланированным к освоению в расчётном периоде, с учётом графиков поставок каждого конкретного вида продукции конечным потребителям, а также с учётом различных технических и технологических ограничений. Разработана математическая модель описываемой задачи и предложен численный метод решения, основанный на применении метаэвристического метода имитации отжига и «жадных» алгоритмов. Проведено сравнение нескольких вариантов алгоритма решения поставленной задачи, в результате которого лучшим признан метод с применением территориальной кластеризации делянок. Результаты апробации алгоритма на реальных данных подтверждают возможность снижения затрат на перебазирование комплексов лесозаготовительных машин с выполнением всех необходимых технологических ограничений. Научные результаты, представленные в статье, использованы при разработке программной системы планирования и управления лесозаготовительным предприятием «Opti-Wood» компании Opti-Soft.
Лесозаготовки, оптимизация, теория расписаний, обобщение задачи коммивояжёра, алгоритм имитации отжига
Короткий адрес: https://sciup.org/147225641
IDR: 147225641
Mathematical model and numerical methods of the wood harvesting machines scheduling
The article contains formulation of the task of wood harvesting machines scheduling, including distribution of machines over the sites, scheduled for harvesting during the planning period, taking into account delivery schedules for each type of products, as well as various technical and technological constraints. A mathematical model of the problem is developed and a numerical solution method is proposed. The method is based on application of the meta-heuristic algorithm of simulated annealing and "greedy" algorithms. Comparison of several variants of the algorithm for solving this problem was made. The method applying spatial clustering of harvesting sites has been recognized as the most effective one. Approbation of the algorithm using real data has confirmed the possibility of reducing the costs of forest machines relocation while meeting all technological requirements. The scientific results presented in the article were used in the software system Opti-Wood for wood harvesting planning and management, developed by Opti-Soft company.
Список литературы Математическая модель и численные методы решения задачи синтеза расписаний работы комплексов лесозаготовительных машин
- Соколов, А. П. Система лесозаготовительной логистики для сортиментной технологии с учётом возможности заготовки топливной древесины / А. П. Соколов, Ю. Ю. Герасимов // Вестник МГУЛ - Лесной вестник. - 2013. - № 1 (93). - С. 145-149.
- Лапцевич, М. Автоматизация в лесной промышленности / М. Лапцевич // Лесная индустрия. - 2014. - № 12 (80). - С. 13-17.
- Оптимизация логистики лесозаготовок / А. П. Соколов, В. С. Сюнёв, Ю. Ю. Герасимов, Т. Карьялайнен // Resources and Technology. - Петрозаводск: Петрозаводский государственный университет. - 2012. - № 9 (2). - С. 117-128.
- Соколов, А. П. Методика принятия решений по оптимизации лесозаготовительных планов / А. П. Соколов, Ю. Ю. Герасимов // Научный журнал КубГАУ. - 2011. - № 69 (05). - С. 174-188.
- Yamada, T. A genetic algorithm with multi-step crossover for job-Shop scheduling problems / T. Yamada, R. Nakano // First IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications (GALESIA '95). - Sheffield, UK, 1995.
- Ertl, G. Shortest path calculation in large road networks / G. Ertl // Operations-Research-Spektrum. - 1998. - Vol. 20, Issue 1. - P. 15-20.
- Воронов, Р. В. Математические модели и методы автоматизированных систем планирования производства бумаги: автореф. дис. … канд. техн. наук: 05.13.18 / Воронов Роман Владимирович. - Петрозаводск, 2004.
- Лопатин, А. С. Метод отжига / А. С. Лопатин // Стохастическая оптимизация в информатике. - 2005. - Т. 1, № 1-1. - С. 133-149.
- Kirkpatrick, S. Optimization by Simulated Annealing / S. Kirkpatrick, Jr. C. D. Gelatt, M. P. Vecchi // Science. - 1983. - No 220. - P. 671-680.
- Yao, X. Call Routing by Simulated Annealing / X.Yao // International Journal of Electronics. - 1995. - Vol. 79, Issue 4. - P. 379-387.
- Equation of State Calculations by Fast Computer Machines / N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller // J. Chemical Physics. - 1953. - Vol. 21. - P. 1087-1092.
- Ingber, L. Simulated Annealing: Practice versus theory / L. Ingber // Mathematical and Computer Modelling. - 1993. - Vol. 18 (11). - P. 29-57.
- Ingber, L. Genetic Algorithms and Very Fast Simulated Reannealing: A Comparison / L. Ingber, B. Rosen // Mathematical and Computer Modelling. - 1992. - Vol. 16 (11). - P. 87-100.
- Optimization of Non-Linear Multiple Traveling Salesman Problem Using K-Means Clustering, Shrink Wrap Algorithm and Meta-Heuristics / R. Nallusamy, K. Duraiswamy, R. Dhanalaksmi, P. Parthiban // International Journal of Nonlinear Science. - 2010. - Vol. 9. - P. 171-177.
- Sokolov, A. P. The system of wood harvesting logistics for cut-to-length taking into account the possibility of fuelwood harvesting / A. P. Sokolov, Yu. Yu. Gerasimov // Forestry Bulletin. - 2013. - No 1 (93). - P. 145-149.
- Laptsevich, M. Automation in the Forest industry / M. Laptsevich // Forest industry. - 2014. - No 12 (80). - P. 13-17.
- Optimization of wood harvesting logistics / A. P. Sokolov, V. S. Syunev, Yu. Yu. Gerasimov, T. Karyalainen // Resources and Technology. - Petrozavodsk: Petrozavodskiy gosudarstvennyy universitet. - 2012. - No 9 (2). - P. 117-128.
- Sokolov, A. P. Methodology of decision-making for wood harvesting optimization / A. P. Sokolov, Yu. Yu. Gerasimov // Scientific Journal of KubSAU. - 2011. - No 69 (05). - P. 174-188.
- Yamada, T. A genetic algorithm with multi-step crossover for job-Shop scheduling problems / T. Yamada, R. Nakano // First IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications (GALESIA '95). - Sheffield, UK, 1995.
- Ertl, G. Shortest path calculation in large road networks / G. Ertl // Operations-Research-Spektrum. - 1998. - Vol. 20, Issue 1. - P. 15-20.
- Voronov, R. V. 2004. Mathematical models and methods of the automated paper production planning systems: abstract of the PhD thesis: 05.13.18 / Voronov Roman Vladimirovich. - Petrozavodsk, 2004. - 16 p.
- Lopatin, A. S. Simulated annealing method / A. S. Lopatin // Stochastic optimization in informatics. - 2005. - T. 1, No 1-1. - P. 133-149.
- Kirkpatrick, S. Optimization by Simulated Annealing / S. Kirkpatrick, Jr. C. D. Gelatt, M. P. Vecchi // Science. - 1983. - No 220. - P. 671-680.
- Yao, X. Call Routing by Simulated Annealing / X.Yao // International Journal of Electronics. - 1995. - Vol. 79, Issue 4. - P. 379-387.
- Equation of State Calculations by Fast Computer Machines / N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller // J. Chemical Physics. - 1953. - Vol. 21. - P. 1087-1092.
- Ingber, L. Simulated Annealing: Practice versus theory / L. Ingber // Mathematical and Computer Modelling. - 1993. - Vol. 18 (11). - P. 29-57.
- Ingber, L. Genetic Algorithms and Very Fast Simulated Reannealing: A Comparison / L. Ingber, B. Rosen // Mathematical and Computer Modelling. - 1992. - Vol. 16 (11). - P. 87-100.
- Optimization of Non-Linear Multiple Traveling Salesman Problem Using K-Means Clustering, Shrink Wrap Algorithm and Meta-Heuristics / R. Nallusamy, K. Duraiswamy, R. Dhanalaksmi, P. Parthiban // International Journal of Nonlinear Science. - 2010. - Vol. 9. - P. 171-177.
