|
DOI: 10.14489/vkit.2015.03.pp.022-027
Чеканин В. А., Чеканин А. В.
МОДЕЛЬ ПОТЕНЦИАЛЬНЫХ КОНТЕЙНЕРОВ ДЛЯ КОНСТРУИРОВАНИЯ ОРТОГОНАЛЬНОЙ УПАКОВКИ
(с. 22-27)
Аннотация. Рассмотрена оптимизационная задача многомерной ортогональной упаковки объектов. Предложена новая модель представления объектов, описывающая все существующие свободные области контейнеров для конструирования ортогональной упаковки. Показана эффективность применения предложенной модели потенциальных контейнеров на тестовых задачах трехмерной ортогональной упаковки объектов.
Ключевые слова: упаковка; задача ортогональной упаковки; модель представления объектов; модель потенци-альных контейнеров; оптимизация; контейнерная упаковка; задача трехмерной упаковки.
Chekanin V. A., Chekanin A. V.
MODEL OF POTENTIAL CONTAINERS FOR CREATION OF ORTHOGONAL PACKAGES
(pp. 22-27)
Abstract. The actual in industry orthogonal packing problem is considered in the article. This problem is NP-hard in strong sense. To solve this problem are usually used heuristic algorithms of discrete optimization. In this case a decision of a packing problem is represented as a string contains a sequence of objects to be packed into free containers that is optimized with the heuristic algorithms. The efficiency of decoding of this string is dependent on used packing representation model. In the paper is proposed a new packing representation model named as model of potential containers. This model describes all orthogonal spaces are existing in containers. The efficiency of the proposed model was investigated on standard three-dimensional orthogonal bin packing problems. The model of potential containers is applicable for solving any dimensional orthogonal packing problems.
Keywords: Packing; Orthogonal packing problem; Packing representation model; Model of potential containers; Optimization; Bin packing; Three-dimensional orthogonal packing problem.
В. А. Чеканин, А. В. Чеканин (Московский государственный технологический университет «Станкин») E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
V. A. Chekanin, A. V. Chekanin (Moscow State University of Technology “Stankin”) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Wascher G., Haubner H., Schumann H. An Improved Typology of Cutting and Packing Problems // European Journal of Operational Research. 2007. V. 183, N. 3. P. 1109 – 1130.
2. Чеканин В. А., Ковшов Е. Е. Моделирование и оптимизация технологических операций в промышлен-ном производстве на основе эволюционных алгоритмов // Технология машиностроения. 2010. № 3. С. 53 – 57.
3. Оптимизационные проблемы транспортной ло-гистики: оперативное размещение контейнеров при транспортировке грузов / Э. А. Мухачева и др. // Инфор-мационные технологии. 2008. № 7. С. 17 – 22.
4. Garey M., Johnson D. Computers Intractability: a Guide to the Theory of NP-completeness. San Francisco: W. H. Freeman, 1979. 338 p.
5. Валеева А. Ф. Применение метаэвристики муравьиной колонии к задачам двумерной упаковки // Информационные технологии. 2005. № 10. С. 36 – 43.
6. Валиахметова Ю. И., Филиппова А. С. Муль-тиметодный генетический алгоритм для решения задач ортогональной упаковки // Информационные техноло-гии. 2007. № 12. С. 50 – 56.
7. Чеканин В. А., Чеканин А. В. Алгоритм реше-ния задач ортогональной упаковки объектов на основе мультиметодной технологии // Информационные техно-логии. 2013. № 7. С. 17 – 21.
8. Чеканин В. А., Чеканин А. В. Исследование генетических методов оптимизации распределения пря-моугольных ресурсов // Материалы 2-й междунар. на-уч.-практ. конф. «Современное машиностроение. Наука и образование». СПб.: Изд-во Политехн. ун-та, 2012. С. 798 – 804.
9. Филиппова А. С. Моделирование эволюцион-ных алгоритмов решения задач прямоугольной упаковки на базе технологии блочных структур // Информацион-ные технологии. 2006. № 6. Приложение. 32 с.
10. Чеканин В. А., Ковшов Е. Е. Систематизация и анализ структур данных при автоматизации управления складом на основе генетических алгоритмов // Проблемы полиграфии и издательского дела. 2008. № 5. С. 42 – 51.
11. Картак В. М. Матричный алгоритм поиска оп-тимального решения для решения задачи упаковки пря-моугольников в полубесконечную полосу // Информаци-онные технологии. 2008. № 2. С. 24 – 30.
12. Crainic T. G., Perboli G., Tadei R. Extreme Point-based Heuristics for Three-dimensional Bin Packing // INFORMS, Journal on Computing. 2008. V. 20, N. 3. P. 368 – 384.
13. Чеканин В. А., Чеканин А. В. Эффективные модели представления ортогональных ресурсов при ре-шении задачи упаковки // Информационно-управляющие системы. 2012. № 5. С. 29 – 32.
14. Чеканин В. А. Эффективное решение задачи двухмерной контейнерной упаковки прямоугольных объектов // Вестник компьютерных и информационных технологий. 2011. № 6. С. 35 – 39.
15. Чеканин А. В., Чеканин В. А. Алгоритмы эф-фективного решения задачи ортогональной упаковки объектов // Журнал вычислительной математики и мате-матической физики. 2013. Т. 53, № 10. С. 1639 – 1648.
16. Bortfeldt A., Wascher G. Constraints in Container Loading – A State-of-the-art Review // European Journal of Operational Research. 2013. V. 229, N. 1. P. 1 – 20.
17. Чеканин В. А., Чеканин А. В. Оптимизация решения задачи ортогональной упаковки объектов // Прикладная информатика. 2012. № 4(40). С. 55 – 62.
18. Martello S., Pisinger D., Vigo D. The Three-dimensional Bin Packing Problem // Operations Research. 2000. V. 48, N 2. P. 256 – 267.
19. Faroe O., Pisinger D., Zachariasen M. Guided Local Search for the Three-dimensional Bin Packing Problem // INFORMS Journal on Computing. 2003. V. 15, N. 3. P. 267 – 283.
20. Lodi A., Martello S., Vigo D. Heuristic Algorithms for the Three-dimensional Bin Packing Problem // European Journal of Operational Research. 2002. V. 141, N. 2. P. 410 – 420.
21. Boschetti M. A. New Lower Bounds for the Finite Three-dimensional Bin Packing Problem // Discrete Applied Mathematics. 2004. V. 140. P. 241 – 258.
1. Wascher G., Haubner H., Schumann H. (2007). An improved typology of cutting and packing prob-lems. European Journal of Operational Research, 183(3), pp. 1109-1130. doi: 10.1016/j.ejor.2005.12.047
2. Chekanin V. A., Kovshov E. E. (2010). Evolution-ary-algorithm-based modelling and optimization of the pro-cessing steps in industrial production. Tekhnologiia mashinostroeniia, (3), pp. 53-57.
3. Mukhacheva E. A., Bukharbaeva L. Ia., Filippov D. V., Karipov U. A. (2008). Optimization problems of transport logistics: Operating bin stowage for cargo transporta-tion. Informatsionnye tekhnologii, (7), pp. 17-22.
4. Garey M., Johnson D. (1979). Computers intracta-bility: a guide to the theory of np-completeness. San Francisco: W. H. Freeman.
5. Valeeva A. F. (2005). Ant colony algorithm for the 2-d bin-packing problems. Informatsionnye tekhnologii, 10, pp. 36-43.
6. Valiakhmetova Iu. I., Filippova A. S. (2007). Multi-method genetic algorithm for the decision of problems of orthogonal packing. Informatsionnye tekhnologii, (12), pp. 50-56.
7. Chekanin V. A., Chekanin A. V. (2013). Based on a multimethod technology algorithm for solving the orthogonal packing problems. Informatsionnye tekhnologii, 7, pp. 17-21.
8. Radkevich M. M., Yevgrafov A. N. (Eds.), Chekanin V. A., Chekanin A. V. (2012). Researching of genetic methods to optimize the allocation of tectangular resources. Modern Engineering: Science and Education: Pro-ceedings of the 2nd International scientific conference. St. Petersburg: Izdatel’stvo Politekhnicheskogo universiteta, pp. 798-804.
9. Filippova A. S. (2006). Modeling of evolution algo-rithms for rectangular packing problems based on block structure technology. Informatsionnye tekhnologii, (6).
10. Chekanin V. A., Kovshov E. E. (2008). Systemati-zation and analysis of data structures for automation the warehouse management based on genetic algo-rithms. Problemy poligrafii i izdatel'skogo dela, (5), pp. 42-51.
11. Kartak V. M. (2008). A matrix algorithm for exact solution of two-dimensional strip packing prob-lem. Informatsionnye tekhnologii, (2), pp. 24-30.
12. Crainic T. G., Perboli G., Tadei R. (2008). Extreme point-based heuristics for three-dimensional bin pack-ing. INFORMS, Journal on Computing, 20(3), pp. 368-384.
13. Chekanin V. A., Chekanin A. V. (2012). Effective models of representations of orthogonal resources in solving the packing problem. Informatsionno-upravliaiushchie sistemy, (5), pp. 29-32.
14. Chekanin V. A. (2011). The effective solving of the two-dimensional packing task of rectangular objects. Vestnik komp'iuternykh i informatsionnykh tekhnologii, (6), pp. 35-39.
15. Chekanin A. V., Chekanin V. A. (2013). Algorithms for efficiently solving the problem of the orthogonal packing of objects. Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki, 53(10), pp. 1639-1648.
16. Bortfeldt A., Wascher G. (2013). Constraints in con-tainer loading – a state-of-the-art review. European Journal of Operational Research, 229(1), pp. 1-20. doi: 10.1016/j.ejor.2012.12.006.
17. Chekanin V. A., Chekanin A. V. (2012). Optimiza-tion of the solution of the orthogonal packing prob-lem. Prikladnaia informatika, 40(4), pp. 55-62.
18. Martello S., Pisinger D., Vigo D. (2000). The three-dimensional bin packing problem. Operations Re-search, 48(2), pp. 256-267.
19. Faroe O., Pisinger D., Zachariasen M. (2003). Guid-ed local search for the three-dimensional bin packing prob-lem. INFORMS Journal on Computing, 15(3), pp. 267-283. doi: 10.1287/ijoc.15.3.267.16080
20. Lodi A., Martello S., Vigo D. (2002). Heuristic al-gorithms for the three-dimensional bin packing problem. European Journal of Operational Research, 141(2), 410-420. doi: 10.1016/S0377-2217(02)00134-0.
21. Boschetti M. A. (2004). New lower bounds for the finite three-dimensional bin packing problem. Discrete Applied Mathematics, 140, pp. 241-258. doi: 10.1016/j.dam.2003.08.004
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 250 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа статьи заполните форму:
{jform=1,doi=10.14489/vkit.2015.03.pp.022-027}
.
This article is available in electronic format (PDF).
The cost of a single article is 250 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please fill out the form below:
{jform=2,doi=10.14489/vkit.2015.03.pp.022-027}
.
.
|
Архив номеров
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»