Mатематические модели и алгоритмы решения задач размещения логистических объектов на основе кратных покрытий и упаковок тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Ле Куанг Мынг

• Ле Куанг Мынг
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Ле Куанг Мынг

Введение

Глава 1 Обзор применения математических моделей и численных методов в области оптимального размещения логистических объектов

1.1 Обзор исследований задачи размещения логистических объектов

1.2 Численные методы в исследовании проблемы размещения логистических объектов

1.3 Задачи оптимальных покрытий и упаковок и методы их решения

1.3.1 Задача о покрытии кругами на плоскости

1.3.2 Задача об упаковке кругов на плоскости

1.3.3 Диаграмма Вороного-Дирихле

1.4 Оптико-геометрический подход

Глава 2 Математические модели задач размещения логистических объектов и численные алгоритмы для их решения

2.1 Построение математических моделей

2.1.1 Методика исследования логистических систем

2.1.2 О построении математических моделей

2.2 Численные методы

2.2.1 Базовые алгоритмы

2.2.2 Многократное покрытие замкнутого множества равными кругами

2.2.3 Покрытие замкнутого множества кругами разного радиуса

2.2.4 Многократная упаковка равных кругов в ограниченное множество

2.2.5 Упаковка кругов разного радиуса в ограниченное множество

2.2.6 Упаковка кругов двух типов в ограниченное множество

Глава 3 Программный комплекс «КУПОЛ-М»

3.1 Описание программного комплекса

3.1.1 Общая характеристика

3.1.2 Модуль «Среда»

3.1.3 Модуль «Упаковка»

3.1.4 Модуль «Покрытие»

3.1.5 Модуль «Параметры»

3.2 Решение тестовых задач

3.2.1 Многократное покрытие замкнутого множества равными кругами

3.2.2 Покрытие замкнутого множества кругами разного радиуса

3.2.3 Многократная упаковка равных кругов в ограниченное множество

3.2.4 Упаковка кругов разного радиуса в ограниченное множество

3.2.5 Упаковка кругов двух типов в ограниченное множество

Глава 4 Решение модельных и прикладных задач

4.1 Решение модельных задач

4.2 Решение прикладных задач

4.2.1 Покрытие территории страны Вьетнам заданным числом одинаковых радиолокационных стаций с наименьшей суммарной мощностью

4.2.2 Расположение заданного количества базовых приёмопередающих станций в городе Дананг-Вьетнам

4.2.3 Размещение автобусных остановок в городе Дананге с минимальным

временем достижения центрального автовокзала

Заключение

Список литературы

Приложение А Свидетельство о государственной регистрации программы для ЭВМ

Приложение В Акт о внедрении программного продукта

140

4

Введение диссертации (часть автореферата) на тему «Mатематические модели и алгоритмы решения задач размещения логистических объектов на основе кратных покрытий и упаковок»

Введение

Актуальность исследования. Состояние экономики каждой страны в мире напрямую зависит от развития ее логистических систем, поэтому проблема их оптимизации для достижения определенного экономического эффекта является актуальной. Известно, что проведение практических экспериментов с логистическими системами невозможно или чрезвычайно рискованно, поэтому необходимо применять методы математического моделирования для их исследования, т.е. необходимо строить и исследовать математические модели как всей исследуемой системы, так и ее отдельных частей. При исследовании логистических систем рассматривается ряд основных проблем, одной из которых является задача выбора оптимального местоположения одного или нескольких логистических центров на полигоне обслуживания.

При изучении данной задачи традиционно используются следующие подходы: «центра тяжести» для размещения одного центра (А.М. Гаджинский [23], В.С. Лукинский [70], P.R. Murphy [169], Zh. Xueying [189]), метод кластеризации «k-средних» в случае нескольких центров (И.Д. Мандель [72], K.J. Anil [98], A. Coates [117], J. MacQueen [163]). Кроме этого, для исследования данной проблемы также применяются методы теории графов (Д.Т. Лотарев [68], Э. Майника [71], В.К. Попков [80]) или различных модификаций задач линейного и дискретного программирования (А.Б. Аникин [4], И.Л. Васильев [21], В.С. Лукинский [70], О.В. Свеженцева [85], И.В Расина [83], О.В Хамисов [90], P. Avella [100]).

Можно видеть, что в большинстве известных источников задача оптимального размещения инфраструктурных логистических объектов решена в предложении об отсутствии на исследуемой территории таких естественных ограничений, как особенности рельефа, других логистических центров, населённых пунктов и т.д. При этом время перемещения между этими объектами зависит только от расстояния между ними. Последнее предположение

существенно снижает общность рассмотрения, поскольку для логистических систем, зачастую, время доставки груза играет существенно большую роль, чем пройдённое при этом расстояние. Таким образом, выбор минимального времени перемещения между объектами в качестве меры их удалённости друг от друга, с одной стороны, позволяет учитывать факторы, влияющие на скорость перемещения (перепады высот, дорожное покрытие, непроходимые области, наличие пробок и узких мест), а, с другой стороны, приводит к необходимости решать задачу минимизации интегрального функционала специального вида. Для этого в данной диссертационной работе предлагается использовать оптико-геометрический подход, базирующийся на аналогии между распространением световых волн в оптически неоднородной среде и нахождением минимума интегрального функционала [46-48,57-61,88,150].

Объект и предмет исследования. Объектом диссертационного исследования являются логистические системы, в которых требуется определить оптимальное местоположение объектов логистической инфраструктуры (системы логистической инфраструктуры - СЛИ). Предметом диссертационного исследования являются математические модели СЛИ с одним или несколькими логистическими обслуживающими объектами при непрерывном распределении потребителей и численные методы их исследования.

Цель и задачи исследования. Целью диссертационной работы является разработка математических моделей СЛИ на основе задач о кратных покрытиях и упаковках, создание эффективных алгоритмов исследования предложенных моделей, а также реализация этих алгоритмов в виде комплекса программ.

Для достижения поставленной цели необходимо решить следующие задачи: 1. Предложить методику изучения СЛИ, отвечающую общей парадигме математического моделирования «модель-алгоритм-программа», ключевым этапом которой является построение математических моделей в форме задач непрерывной оптимизации.

2. Построить математические модели СЛИ в форме: а) задач о многократных покрытиях и упаковках равных кругов; б) задач об однократных покрытиях и упаковках кругов разного радиуса.

3. Разработать вычислительные алгоритмы решения задач из п. 2 в случае неевклидового пространства на основе оптико-геометрического подхода с использованием диаграммы Вороного-Дирихле.

4. Реализовать предложенные алгоритмы в виде комплекса программ, провести вычислительный эксперимент по решению тестовых задач, проверить работоспособность предложенного подхода и корректность вычислений.

5. Провести решение модельных и прикладных задач, сделать выводы с точки зрения предметной области (логистики).

Методы исследования. При выполнении диссертационного исследования применяются следующие методы: математического моделирования, геометрической оптики, вычислительной геометрии и непрерывной оптимизации. Для реализации программной системы используется среда разработки Visual Studio 2013 (язык программирования С#) с дополнительной библиотекой SVG для представления результатов в виде векторных изображений.

Научная новизна. Научная новизна исследования состоит в следующем:

1. Предложена оригинальная методика математического моделирования СЛИ на основе использования специальных модификаций задач об оптимальных покрытиях и упаковках кругов, при этом в качестве критерия оптимальности выступает время перемещения между центрами кругов, входящих в покрытия и упаковки, что приводит к необходимости введения неевклидовых метрик. Данные математические модели впервые применяются в исследовании задач логистики, ранее использовались только модели на основе однократных покрытий и упаковок равных кругов.

2. Разработаны численные алгоритмы решения задач о многократных оптимальных покрытиях и упаковках равных кругов в ограниченное множество на основе оптико-геометрического подхода и многократных диаграмм Вороного-

Дирихле, которые обобщают известные алгоритмы для решения задач об однократных покрытиях и упаковках равных кругов с неевклидовыми метриками.

3. Разработаны новые алгоритмы решения задач об однократных оптимальных покрытиях и упаковках кругов разного радиуса в двухмерном пространстве на основе оптико-геометрического подхода и нового метода построения обобщённых диаграмм Вороного-Дирихле, отличающиеся от известных возможностью использования неевклидовых метрик.

4. Предложенные численные алгоритмы реализованы в виде комплекса программ «КУПОЛ-М: кратные упаковки и покрытия, оптимизация, логистика», с помощью которого выполнены тестовые и модельные расчёты и решены прикладные задачи инфраструктурной логистики, актуальные для Социалистической Республики Вьетнам.

Достоверность и обоснованность. Достоверность и обоснованность результатов исследования обеспечиваются корректностью применения задач о кратных покрытиях и упаковках для исследования, корректностью исходных данных для проведения вычисленного эксперимента, согласованностью теоретических и экспериментальных данных.

Теоретическая значимость исследования состоит в следующем:

1. Предложенная методика построения математических моделей СЛИ в форме специальных модификаций задач о покрытиях и упаковках кругов вносит вклад в развитие теории математического моделирования.

2. Разработанные на основе оптико-геометрического подхода и диаграммы Вороного-Дирихле вычислительные алгоритмы вносят вклад в развитие методов решения классических задач об упаковке и покрытии.

Практическая значимость исследования заключается в следующем:

1. Предложенная методика построения математических моделей применена для исследования задач логистики с единичным или многократным обслуживанием потребителей.

2. Разработанный программный комплекс «КУПОЛ-М» позволяет строить решения задач размещения логистических центров, математическое описание которых приводит к задачам покрытий и упаковок кругов специального вида.

3. Предложенные численные алгоритмы могут быть использованы для решения других классов прикладных задач, включая задачи управления движением, обеспечения безопасности, организации средств коммуникаций, круговой резки, загрузки контейнера, размещения электрической приборной панели и т.д.

Апробация результатов исследования. Работа выполнялась на кафедре автоматизированных систем ФГБОУ ВО ИРНИТУ. Основные результаты диссертационного исследования докладывались и обсуждались на следующих научных конференциях, семинарах и симпозиумах: XVII и XVIII Всероссийские конференции молодых учёных по математическому моделированию и информационным технологиям (г. Новосибирск, 2016; г. Иркутск, 2017); Международная школа-конференция «Соболевские чтения» (г. Новосибирск, 2016); Научно-практическая конференция молодых учёных «Проблемы информационного и математического моделирования сложных систем» (г. Иркутск, 2017); VI Международная конференция по анализу изображений, социальных сетей и текстов (г. Москва, 2017); Всероссийская молодёжная научно-практическая конференция «Винеровские чтения» (г. Иркутск, 2018); 17th IFAC Workshop on control applications of optimization CAO 2018 (г. Екатеринбург, 2018); VIII Международная конференция «Cистемный анализ и информационные технологии» (г. Иркутск, 2019); XVIII Международная конференция «Теория математической оптимизации и исследование операций» (г. Екатеринбург, 2019); Международный симпозиум «Динамические системы, оптимальное управление и математическое моделирование» (г. Иркутск, 2019).

Результаты диссертационного исследования неоднократно докладывались на научных семинарах кафедры автоматизированных систем ФГБОУ ВО ИРНИТУ.

Результаты диссертационного исследования опубликованы в 13 научных работах, из них 1 статья опубликована в журнале, индексируемом в базе данных Web of Science, 2 статьи в изданиях, индексируемых в базе данных Scopus и 2 статьи в журналах, входящих в Перечень ВАК. Получено 1 свидетельство о государственной регистрации программ для ЭВМ.

Основные результаты исследования опубликованы в следующих работах.

Издания, индексируемые в базе данных WoS:

1. Le Q.M. Multiple covering of a closed set on a plane with non-Euclidean metrics / A.A. Lempert, Q.M. Le // IFAC-PapersOnLine. - 2018. - Vol. 51, No. 32. -P. 850-854.

Издания, индексируемые в базе данных Scopus:

2. Le Q.M. An algorithm for packing circles of two types in a fixed size container with Non-Euclidean metric / A.L. Kazakov, A.A. Lempert, Q.M. Le // CEUR-Workshop Proceedings. - 2017. - Vol. 1975. - P. 281-292.

3. Le Q.M. On reserve and double covering problems for the sets with non-Euclidean metrics / A.A. Lempert, A.L. Kazakov, Q.M. Le // Yugoslav Journal Operation Research. - 2019. - Vol. 29, No. 1. - P. 69-79.

Издания, входящие в Перечень ВАК РФ:

4. Ле К.М. Алгоритм размещения логистических центров в заданной области при точечном и непрерывном распределении потребителей / А.А. Лемперт, Н.Г. Лием, К.М. Ле // Известия Байкальского государственного университета. - 2016. - № 26 (6). - С. 1031-1038.

5. Ле К.М. О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве / А.А. Лемперт, А.Л. Казаков, К.М. Ле // Управление большими системами. - 2019. - Вып. 81. - С.6-25.

Свидетельства о государственной регистрации программы для ЭВМ:

6. Ле К.М. «КУПОЛ-М»: кратные упаковки и покрытия, оптимизация, логистика / А.Л. Казаков, А.А. Лемперт, К.М. Ле // Свидетельство о гос. регистрации программы для ЭВМ. № 2018666830 от 21 ноября 2018 г. Москва: Федеральная служба по интеллектуальной собственности. 2018.

Прочие издания:

7. Ле К.М. Размещение логистических центров в области при точечном и непрерывном распределениях потребителей / А.А. Лемперт, К.М. Ле // Материалы XVII всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям. Новосибирск: ИВТ СО РАН, 2016. - С. 49.

8. Ле К.М. О задаче упаковки равных кругов в неодносвязное множество / А.А. Лемперт, К.М. Ле // Сборник тезисов докладов международной школы-конференции «Соболевские чтения». Новосибирск: ИМ СО РАН и НГУ, 2016. -С. 112.

9. Ле К.М. Задача построения оптимального покрытия разными кругами двух типов / К.М. Ле // Материалы XVIII всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям. Новосибирск: ИВТ СО РАН, 2017. - С. 42.

10. Ле К.М. Покрытие замкнутого множества разными кругами с неевклидовой метрикой на плоскости/ К.М. Ле // Материалы всероссийской молодёжной научно-практической конференции «Винеровские чтения 2018». Иркутск: ИРНИТУ, 2018. - С. 57-58.

11. Ле К.М. Об алгоритме упаковки кругов разного радиуса в ограниченное множество в неевклидовом метрическом пространстве / А.Л. Казаков, А.А. Лемперт, К.М. Ле // Труды VIII международной конференции «Cистемный анализ и информационные технологии - САИТ 2019». Иркутск: ФИЦ ИУ РАН, 2019. -С. 72-79.

12. Le Q.M. On the thinnest covering of fixed size containers with Non-Euclidean metric by incongruent circles / A.A. Lempert, A.L. Kazakov, Q.M. Le // Сборник тезисов международной конференции «Теория математической оптимизации и исследование операций - MOTOR 2019». Екатеринбург: ИММ УрО РАН, 2019. -C. 113.

13. Ле К.М. О задаче многократной упаковки кругов в ограниченное множество / А.А. Лемперт, А.Л. Казаков, К.М. Ле // Материалы международного

симпозиума «Динамические системы, оптимальное управление и математическое моделирование». Иркутск: ИГУ, 2019. - C. 397-399.

Тематика работы соответствует следующим пунктам паспорта специальности 05.13.18:

1) пункт 1. «Разработка новых математических методов моделирования объектов и явлений» - в части разработки методики построения математических моделей логистических систем на основе задач о кратных покрытиях и упаковках;

2) пункт 4. «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента» - в части разработки и реализации численных алгоритмов в виде комплекса программ «КУПОЛ-М»;

3) пункт 5 «Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента» - в части решения модельных и прикладных задач выбора местоположения логистических центров.

Личный вклад. Все выносимые на защиту результаты исследования, включая новые математические модели и разработанные численные методы, получены лично автором. Методика построения математических моделей разработана совместно с д.ф.-м.н. А.Л. Казаковым. Постановки задач о кратных покрытиях и упаковках кругов выполнены совместно с к.ф.-м.н. А.А. Лемперт. Программный комплекс «КУПОЛ-М: кратные упаковки и покрытия, оптимизация, логистика» создан в неделимом соавторстве с д.ф.-м.н. А.Л. Казаковым и к.ф.-м.н. А.А. Лемперт, при этом программная реализация выполнена автором диссертации.

Структура и объем работы. Диссертационная работа состоит из введения, четырёх глав, заключения и списка литературы из 191 наименований. Объем данной работы составляет 141 страниц текста, иллюстрированного 48 рисунками и 23 таблицами.

Кратко изложим содержание основных разделов диссертационной работы:

В главе 1 представлен обзор математических моделей и численных методов, применяемых при изучении проблемы оптимального размещения логистических объектов. Показано, что в ряде случаев могут быть уместны модели в форме задач об оптимальных покрытиях и упаковках. Проведён обзор применения задач о покрытиях и упаковках кругов на плоскости в различных сферах человеческой деятельности, включая логистику. Проведён анализ известных методов изучения задач о покрытии и упаковке, который позволил установить, что они относятся к классу №-полных, а основным элементом большинства известных алгоритмов, применяемых для их решения, является построение диаграммы Вороного-Дирихле. Поскольку ранее в научной школе А.Л. Казакова при рассмотрении более простых аналогичных постановок использовался оптико-геометрический подход, в заключительном разделе главы 1 приведены принципы, на которых он основан, и обсуждена возможность его применения при изучении задач оптимизации в двухмерном пространстве с неевклидовой метрикой.

В главе 2 предложена методика исследования СЛИ, соответствующая общей парадигме математического моделирования «модель-алгоритм-программа» и включающая: построение математических моделей исследуемых логистических систем в форме специальных задач об оптимальных покрытиях и упаковках кругов; разработку численных алгоритмов на основе оптико-геометрического подхода и диаграммы Вороного-Дирихле; создание на их основе программного комплекса; проведение вычислительного эксперимента и решение прикладных задач. Согласно предложенной методике исследования, в разделе 2.1 разработаны математические модели СЛИ в виде задач о многократных покрытиях и упаковках равных кругов и задач об однократных покрытиях и упаковках кругов разного радиуса в ограниченное множество с неевклидовыми метриками. Для решения этих задач в разделе 2.2 разработаны оригинальные численные алгоритмы на основе оптико-геометрического подхода и модификаций

(многократной и обобщённой однократной) диаграммы Вороного-Дирихле с неевклидовой метрикой.

В главе 3 представлено описание программного комплекса «КУПОЛ-М», в котором реализованы предложенные во второй главе алгоритмы. Данный комплекс программ реализован на языке программирования С# в среде разработки Visual Studio 2013, имеет четыре главных модуля и дополнительные функции для ввода данных, изменения параметров при выполнении алгоритмов, сохранения полученных результатов. В данной главе также проведено тестирование точности и скорости работы предложенных алгоритмов и работоспособности созданного программного комплекса. При тестировании применялись как евклидовая, так и различные неевклидовые метрики.

В главе 4 представлены решения некоторых модельных задач с использованием программного комплекса «КУПОЛ-М» при комбинированном (точечном и непрерывном) распределении потребителей. Также представлены решения следующих прикладных задач: покрытие территории страны Вьетнам заданным числом одинаковых радиолокационных стаций с наименьшей суммарной мощностью; расположение заданного количества базовых приёмопередающих станций в городе Дананг (Вьетнам); размещение автобусных остановок в городе Дананг с целью минимизировать суммарное время достижения жителями города центрального автовокзала.

В заключении представлены основные научные результаты, полученные в ходе выполнения данной диссертационной работы.

Глава 1 Обзор применения математических моделей и численных методов в области оптимального размещения логистических объектов

1.1 Обзор исследований задачи размещения логистических объектов

Логистика - область науки и практической деятельности, которая занимается вопросами планирования, движения и контроля материальных потоков: сырья, материалов, комплектующих, готовой продукции, сервиса и связанной информации от точки зарождения до точки потребления (включая импорт, экспорт, внутренние и внешние перемещения) с целью полного удовлетворения требований потребителей. В ее рамках изучаются: закупочная или снабженческая логистика, логистика производственных процессов, сбытовая или распределительная логистика, информационная логистика, транспортная логистика и др. [4, 29].

Основная задача транспортной логистики - выбор вида и типа транспорта, определение маршрутов доставки груза и размещение логистических обслуживающих объектов оптимальным образом (в том или ином смысле) [74]. Решение данных проблем позволяет снизить затраты на доставку грузов и, как следствие, повысить эффективность снабжения сырьём и продукцией конечных потребителей. К наиболее известным оптимизационным задачам транспортной логистики, сохраняющим актуальность до настоящего времени, относятся задача об оптимальном маршруте, задача идентификации и сегментации логистических зон, задача организации средств коммуникаций и задача об оптимальном размещении логистических объектов [75]. Последняя из задач занимает особое место в ряду содержательных проблем транспортной логистики [51]. Данный класс задач имеет широкое практическое применение, поскольку включает в себя задачи по размещению вокзалов, учебных заведений, больниц, пунктов экстренной помощи, пожарных частей, коммуникационных стаций, производственных цехов, магазинов, складов, пунктов захоронения токсичных и радиоактивных отходов и др.

На рисунке 1.1 представлены местоположения магазинов компании спортивных товаров «Морис» в США в 2018 году и зоны обслуживания каждого магазина.

•_» If /

6 Я £ Л *{\t

К A SK Л •

у n

STATES

ITJv 4ж • li VJjj К

r' I

DCV',:;;

pit

0 Rochester . BulMlob,,, ,vу j

Clt. clond'

С OtUlllt'UD

о •

Olll

о Boston о ProviderK

Ptttsbutgnj

¿fct Louis

fff.\ m> ss« kT ••

■CmIV7.''-'

'l".v York

DC 2

c'miadelphla

mqf

'^rtinjtwi

RltWWld Norfolk

DC6 " DC з

.« l"*. ' еш.мШ

v. r llf «1.Л .

i '

ОС 5

Tlew Orleans

DC7 f

-•As" i*

a Jacksonville

Рисунок 1.1 - Размещение магазинов компании спортивных товаров «Морис» в

США

Существуют различные способы постановки задачи размещения объектов в зависимости от накладываемых ограничений: размещение производства однородной или неоднородной продукции; размещение объектов с ограничением на мощность их производства; минимизация затрат строительства и суммарного расстояния до потребителей; расположение логистических объектов на полигоне обслуживания в заданных возможных местах размещения [71].

Проблема об оптимальном размещении объектов, рассматриваемая как геометрическая задача нахождения минимума, была представлена итальянским физиком и математиком В. Вивиани в 1665 году следующим образом: пусть имеются три точки на плоскости. Требуется найти четвёртую точку так, чтобы сумма расстояний от неё до трёх заданных точек была минимальной [82].

В логистической науке проблема о размещении объектов, по-видимому, была впервые изучена немецким экономистом В. Лаунхардтом. Он поставил задачу следующим образом: пусть имеется один вид продукции, существует один рынок сбыта, источник сырья и источник материалов. Производственные затраты постоянны для всех точек заданной области. Необходимо найти такой пункт размещения промышленного предприятия, чтобы транспортные издержки на единицу продукции, которые пропорциональны расстоянию, были

минимальными возможными. Для решения этой задачи он разработал теорию с использованием метода «локационного треугольника» (весового треугольника), суть которой состоит в том, что на каждой из сторон «локационного треугольника» строится треугольник, подобный весовому. Затем вокруг построенных таким образом треугольников описываются окружности, точка пересечения которых и является точкой минимума транспортных издержек [67].

Позднее А. Вебер продолжил исследовать «проблему трёх точек» в работе [22], где сначала он сводит весь набор факторов, влияющих на расположение производства, к трём: транспортные издержки; затраты на рабочую силу; агломерационные / дегломерационные силы. Далее он последовательно изучает их раздельное и совместное влияние на геометрию промышленности и её динамику. Это важный шаг по сравнению с исследованиями В. Лаунхардта, в которых внимание фокусировалось только на транспортных издержках. Недостатком теории Вебера является отсутствие учёта конкуренции, поскольку в его модели предприятия не конкурируют друг с другом за ресурсы или рынки сбыта.

На основе результатов В. Лаунхардта и А. Вебера, немецкий географ В. Кристаллер создал теорию центральных мест, обосновывающую количество, размер и местоположение населённых пунктов. В соответствие с ней города представляют собой центральные места, обслуживающие прилегающие территории [ 115].

Позднее появилось большое количество работ, посвящённых проблеме оптимального размещения объектов, в которых применялись различные математические модели. Кроме того, с развитием и усложнением структуры логистических систем появилась необходимость разработки численных методов для исследования предложенных математических моделей [2,4,23,33,85].

В настоящее время для решения прикладных задач оптимального размещения логистических центров наиболее часто применяются следующие методы: метод «центра тяжести» [4,23], метод ^-средних [23,72,98], метод FOREL

[3,35,158], основанные на определения положения некоторой центральной точки для групп потребителей, попавших в соответствующую зону обслуживания.

В работе [4] рассматривается задача определения месторасположения распределительного склада в заданном регионе. Критерием оптимизации является минимизация транспортных затрат. Месторасположение склада определяется как «центр равновесной системы транспортных затрат».

В работе [23] рассматривается задача об оптимальном размещении одного или нескольких складов в заданном регионе. Критерием оптимизации являются минимизация расстояния между поставщиками, потребителями и складом. Месторасположение одного склада определяется в виде координат центра тяжести грузовых потоков. Местоположение нескольких складов определяется на основе метода «К-средних».

В работе [3] предложена математическая модель задачи выделения объектов в бортовой системе, суть которой состоит в размещении двух датчиков изображений с минимально возможными спектральными диапазонами так, чтобы наблюдались все объекты бортовой системы. Алгоритм решения данной задачи разработан на основе модификации метода FOREL.

Проблема оптимального размещения объектов также возникает в задачах организации средств коммуникаций (электрических сетей, информационных каналов и др.), прокладка которых должна производиться с минимально возможными затратами. Эта проблема зачастую приводит к решению задачи Штейнера [66,92].

Список литературы диссертационного исследования кандидат наук Ле Куанг Мынг, 2020 год

Список литературы

1. Алдыноол, Т.А. Покрытие плоской области случайно распределенными сенсорами / Т.А. Алдыноол, А.И. Ерзин, В.В. Залюбовский // Вестник НГУ. -Серия Математика, механика, информатика. - 2010. - Т.10, № 4. - C. 7-25.

2. Алексеева, Е.В. Генетический локальный поиск для задачи о p-медиане с предпочтениями клиентов / Е.В. Алексеева, Ю.А. Кочетов // Дискретный анализ и исследование операций. - 1999. - № 1. - C. 12-32.

3. Алпатов, Б.А. Выделение движущихся объектов в условиях геометрических искажений изображения / Б.А. Алпатов, П.В. Бабаян // Цифровая обработка сигналов. - 2004. - № 4. - С. 9-14.

4. Аникин, А.Б. Логистика: Учебник для вузов / А.Б. Аникин. - Москва: ИНФРА-М, 2000. - 352 с.

5. Арнольд, В.И. Математические методы классической механики /

B.И. Арнольд. - Москва: Эдиториал УРСС, 2000. - 408 с.

6. Астраков, С.Н. Сенсорные сети и покрытие плоскости кругами /

C.Н. Астраков, А.И. Ерзин, В.В. Залюбовский // Дискретный анализ и исследование операций. - 2009. -Т.16, № 3. - C. 3-19.

7. Астраков, С.Н. Сенсорные сети и покрытие полосы эллипсами / С.Н. Астраков, А.И. Ерзин // Вычислительные технологии. - 2013. - Т.18, № 2. -C. 3-11.

8. Балюк, Л.В. Генетические алгоритмы решения задачи размещения элементов СБИС / Л.В. Балюк // Известия ТРТУ. - 2006. - № 8(63). - С. 65-71.

9. Башуров, В.В. Применение методов геометрической оптики для решения задач безопасности объекта / В.В. Башуров // Вычислительные технологии. -2006. - № 4. - С.23-28.

10. Бельц, Е.А. Оптимизация размещения предприятий с учетом минимально допустимых расстояний / Е.А. Бельц, А.А. Колоколов // Вестник Омского ун-та. - 2012. - № 4. - С.13-16.

11. Береснев, В.Л. Алгоритмы локального поиска для задачи конкурентного размещения предприятий / В.Л. Береснев // Автоматика и телемеханика. - 2012. -№ 3. - С. 12-27.

12. Береснев, В.Л. Математическая модель конкурентной борьбы на рынке / В.Л. Береснев, В.И. Суслов // Сибирский журнал индустриальной математики. -2009. - № 1. - С. 11-24.

13. Береснев, В.Л. Приближенные алгоритмы для задачи конкурентного размещения предприятий / В.Л. Береснев, А.А. Мельников // Дискретный анализ и исследование операций. - 2010. - № 6. - C. 3-19.

14. Блауг, М. Экономическая мысль в ретроспективе / М. Блауг. - Москва: Дело, 1994. - 627 с.

15. Боровских, А.В. Двумерное уравнение эйконала / А.В. Боровских // Сибирский математический журнал. - 2006. - Т.47, №. 5. - С. 993-1018.

16. Брусов, В.С. Вычислительный алгоритм оптимального покрытия областей плоскости / В.С. Брусов, С.А. Пиявский // Журнал вычислительной математики и математической физики. - 1971. - Т.11, № 2. - С. 304-313.

17. Брусов, В.С. Двигательная установка малой тяги, универсальная для двумерного диапазона / В.С. Брусов, С.А. Пиявский // Известия Академии наук СССР. Космические исследования. - 1970. - № 4. - С. 542-546.

18. Брусов, В.С. Применение теории оптимальных покрытий к задачам выбора мощности двигателя малой тяги / В.С. Брусов, С.А. Пиявский // Известия Академии наук СССР. Механика твердого тела. - 1968. - № 5. - С. 3-10.

19. Брусов, В.С. Применение теории оптимальных покрытий к задачам выбора мощности двигателя малой тяги / В.С. Брусов, С.А. Пиявский // Известия Академии наук СССР. Механика твердого тела. - 1969. - № 2. - С. 10-14.

20. Бухаров, Д.С. Программная система «ВИГОЛТ» для решения задач оптимизации, возникающих в транспортной логистике / Д.С. Бухаров, А.Л. Казаков // Вычислительные методы и программирование: новые вычислительные технологии. - 2012. - Т.13, № 2 (26). - С. 65-74.

21. Васильев, И.Л. Новые нижние оценки для задачи размещения с предпочтениями клиентов / И.Л. Васильев, К.Б. Климентова, Ю.А. Кочетов // Журнал вычислительной математики и математической физики. - 2009. - № 6. -С. 1055-1066.

22. Вебер, А. Теория размещения промышленности / А. Вебер. - Москва: Книга, 1926.

23. Гаджинский, А.М. Современный склад. Организация, технология, управление и логистика / А.М. Гаджинский. - Учеб. практическое пособие. Москва: ТК Велби, 2005. - 176 с.

24. Галиев, Ш.И. Многократные покрытия кругами равностороннего треугольника, квадрата и круга / Ш.И. Галиев, А.В. Хорьков // Дискретный анализ и исследование операций. - 2015. - Т. 22, № 6. - C. 5-28.

25. Галиев, Ш.И. Многократные упаковки и покрытия сферы / Ш.И. Галиев // Дискретная математика. - 1996. - Т. 8, Вып. 3. - C. 148-160.

26. Галиев, Ш.И. Нахождение глобального экстремума и субоптимальных решений для задач размещения станций скорой помощи / Ш.И. Галиев, Л.Ю. Емалетдинова, М.А. Разина // Весник КГТУ. - 2004. - № 3. - С. 40-45.

27. Галиев, Ш.И. Оптимизация многократного покрытия ограниченного множества кругами / Ш.И. Галиев, М.А. Карпова // Журнал вычислительной математики и математической физики. - 2010. -T. 50, № 4. - С -757-769.

28. Галиев, Ш.И. Численный метод оптимизации упаковок правильных выпуклых многоугольников / Ш.И. Галиев, М.С. Лисафина // Журнал вычислительной математики и математической физики. - 2016. - T. 56, № 8. - С. 1416-1427.

29. Гайдаенко, А.А. Логистика: учебник / А.А. Гайдаенко, О.В. Гайдаенко. -Москва: Кнорус, 2008. - 272 с.

30. Гигиенические требования к безопасности процессов испытаний, хранения, перевозки, реализации, применения, обезвреживания и утилизации пестицидов и агрохимикатов: СанПиН 1.2.2584-10 от 02.03.2010г.

31. Гигиенические требования к хранению, применению и транспортировке пестицидов и агрохимикатов: СанПиН 1.2.1077-01 от 08.10.2001г.

32. Жук, С.Н. Приближенные алгоритмы упаковки прямоугольников в несколько полос / С.Н. Жук // Дискретная математика - 2006. - Т. 18, № 1. - С. 91-105.

33. Забудский, Г.Г. Построение моделей и решение задач размещения на плоскости с запрещенными зонами / Г.Г. Забудский // Автоматика и телемеханика. - 2006. - № 12. - С. 136-141.

34. Забудский, Г.Г. Решение задачи размещения в евклидовом пространстве с запрещенной областью / Г.Г. Забудский, Нежинский И.В. // Вестник Омского университета. - 1999. - Вып. 2. - С. 17-19.

35. Загоруйко, Н.Г. Алгоритмы обнаружения эмпирических закономерностей Н.Г. Загоруйко, В.Н. Ёлкина, Г.С. Лбов. - Новосибирск: Наука, 1985. - 107 с.

36. Загоруйко, Н.Г. Прикладные методы анализа данных и знаний / Н.Г. Загоруйко. - Новосибирск: Изд-во Ин-та математики, 1999. - 270 с.

37. Исакин, М.А. Модификация метода к-средних с неизвестным числом классов / М.А. Исакин // Прикладная эконометрика. - 2006. - №. 4(4). - С. 62-73.

38. Казаков, А.Л. Алгоритм построения оптимальных покрытий равными кругами невыпуклых многоугольников с неевклидовой метрикой / А.Л. Казаков, А.А. Лемперт, Г.Л. Нгуен // Вестник ИрГТУ. - 2016. - № 5(112). - С. 45-55.

39. Казаков, А.Л. Вопросы сегментации логистических платформ в условиях становления региональной логистики / А.Л. Казаков, М.А. Журавская, А.А. Лемперт // Транспорт Урала. - 2010. - №. 4. - С. 17-20.

40. Казаков, А.Л. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей / А.Л. Казаков, А.А. Лемперт, Д.С. Бухаров // Автоматика и телемеханика. - 2013. - Т. 74, № 6. - С. 87-100.

41. Казаков, А.Л. «КУПОЛ-М»: кратные упаковки и покрытия, оптимизация, логистика / А.Л. Казаков, А.А. Лемперт, К.М. Ле // Свидетельство о

гос. регистрации программы для ЭВМ. № 2018666830 от 21 ноября 2018 г. Москва: Федеральная служба по интеллектуальной собственности, 2018.

42. Казаков, А.Л. Об алгоритме упаковки кругов разного радиуса в ограниченное множество в неевклидовом метрическом пространстве / А.Л. Казаков, А.А. Лемперт, К.М. Ле // Труды VIII Международной конференции «^стемный анализ и информационные технологии - САИТ 2019». Иркутск: ФИЦ ИУ РАН, 2019. - С. 72-79.

43. Казаков, А.Л. Об одном алгоритме построения упаковки конгруэнтных кругов в неодносвязное множество с неевклидовой метрикой / А.Л. Казаков, А.А. Лемперт, Г.Л. Нгуен // Вычислительные методы и программирование. -2016. - Т. 17, Вып. 2. - С. 177-188.

44. Казаков, А.Л. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике / А.Л. Казаков, А.А. Лемперт // Автоматика и телемеханика. - 2011. - № 7. - С. 50-57.

45. Казаков, А.Л. Оптимизация системы коммуникаций с учетом региональных особенностей: математическая модель и численный метод / А.Л. Казаков, А.А. Лемперт, Г.Л. Нгуен // Вестник ИрГТУ. - 2014. - № 12(95). - С. 17-22.

46. Казаков, А.Л. Программный модуль оптимального размещения логистических центров / А.Л. Казаков, Г.Л. Нгуен, А.А. Лемперт // Свидетельство о гос. регистрации программы для ЭВМ. № 2015616554 от 15 июня 2015 г. Москва: Федеральная служба по интеллектуальной собственности, 2015.

47. Казаков, А.Л. Программный модуль построения оптимальных покрытий и упаковок в оптически неоднородной среде / А.Л. Казаков, Г.Л. Нгуен, А.А. Лемперт // Свидетельство о гос. регистрации программы для ЭВМ. № 2016614997 от 13 мая 2016 г. М.: Федеральная служба по интеллектуальной собственности, 2016.

48. Казаков, А.Л. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости / А.Л. Казаков, П.Д. Лебедев //

Вычислительные методы и программирование. - 2015. - Т. 16, Вып. 2. - С. 307317.

49. Козюрин, Н.Н. Вероятностный анализ различных шельфовых алгоритмов упаковки прямоугольников в полосу / Н.Н. Козюрин, А.И. Поспелов // Математические методы и алгоритмы. Сборник трудов ИСП РАН. - 2006. - Т. 12. - С. 17-26.

50. Кристофидес, Н. Теория графов: алгоритмический подход / Н. Кристофидес. -Москва: Мир, 1978. - 432 с.

51. Курейчик, В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР: Учебник для вузов. / В.М. Курейчик. - Москва: Радио и связь, 1990. - 352 с.

52. Ланцош, К. Вариационные принципы механики / К. Ланцош. - Москва: Физматгиз, 1965. - 408 с.

53. Ле, К.М. Задача построения оптимального покрытия разными кругами двух типов / К.М. Ле // Материалы XVIII всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям. Новосибирск: ИВТ СО РАН, 2017. - С. 42.

54. Ле, К.М. Покрытие замкнутого множества разными кругами с неевклидовой метрикой на плоскости/ К.М. Ле // Материалы всероссийской молодёжной научно-практической конференции «Винеровские чтения 2018». Иркутск: ИРНИТУ, 2018. - С. 57-58.

55. Лебедев, П.Д. Алгоритмы наилучшей аппроксимации плоских множеств объединениями кругов / П.Д. Лебедев, А.А. Успенский, В.Н. Ушаков // Вестник Удмуртского ун-та. Математика. Механика. Компьютерные науки. - 2013. - Вып. 4. - С. 88-99.

56. Лебедев, П.Д. Аппроксимация многоугольников наилучшими наборами кругов / П.Д. Лебедев, Д.С. Бухаров // Известия Иркутского государственного унта. Математика. - 2013. - № 3. - С. 72-87.

57. Лебедев, П.Д. Геометрия и асимптотика волновых фронтов / П.Д. Лебедев, А.А. Успенский // Известия высших учебных заведений. Математика. - 2008. - № 3. - С. 27-37.

58. Лебедев, П.Д. Итерационные алгоритмы построения оптимальных упаковок в неоднородной метрике / П.Д. Лебедев, А.А. Лемпер // Труды Международной (48-й Всероссийской) молодежной школы-конференции, Екатеринбург, 2017. - С. 98-108.

59. Лебедев, П.Д. Построение минимаксного решения уравнения типа эйконал / П.Д. Лебедев, А.А. Успенский, В.Н. Ушаков // Труды института математики и механики. - 2008. - № 2. - С. 182-191.

60. Лемперт, А.А. Алгоритм размещения логистических центров в заданной области при точечном и непрерывном распределении потребителей / А.А. Лемперт, Н.Г. Лием, К.М. Ле // Известия Байкальского государственного университета. - 2016. - № 26 (6). - С. 1031-1038.

61. Лемперт, А.А. Математическая модель и программная система для решения задачи размещения логистических объектов / А.А. Лемперт, А.Л. Казаков, Д.С. Бухаров // Управление большими системами. - 2013. - №. 41. - С. 270-284.

62. Лемперт, А.А. О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве / А.А. Лемперт, А.Л. Казаков, К.М. Ле // Управление большими системами. - 2019. - Вып. 81. - С.6-25.

63. Лемперт, А.А. О задаче многократной упаковки кругов в ограниченное множество / А.А. Лемперт, А.Л. Казаков, К.М. Ле // Материалы международного симпозиума «Динамические системы, оптимальное управление и математическое моделирование». Иркутск: ИГУ, 2019. - C. 397-399.

64. Лемперт, А.А. О задаче упаковки равных кругов в неодносвязное множество / А.А. Лемперт, К.М. Ле // Сборник тезисов докладов международной школы-конференции «Соболевские чтения». Новосибирск: ИМ СО РАН и НГУ, 2016. - С. 112.

65. Лемперт, А.А. Размещение логистических центров в области при точечном и непрерывном распределениях потребителей / А.А. Лемперт, К.М. Ле // Материалы XVII всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям. Новосибирск: ИВТ СО РАН, 2016. - С. 49.

66. Лотарев, Д.Т. Преобразование задачи Штейнера на евклидовой плоскости к задаче Штейнера на графе / Д.Т. Лотарев, А.П. Уздемир // Автоматика и телемеханика. - 2005. - № 10. - С. 80-92.

67. Лимонов, Л.Э. Региональная экономика и пространственное развитие / Л.Э. Лимонов. - Москва: Юрайт, 2015. - 396 с.

68. Лотарев, Д.Т. Цифровая модель местности для задачи размещения коммуникаций / Д.Т. Лотарев // Автоматика и телемеханика. - 1999. - №. 12. - С. 41-49.

69. Лукинский, В.С. Логистика автомобильного транспорта: Учеб. Пособие / В.С. Лукинский, В.И. Бережной, Е.В. Бережная. - Москва: Финансы и статистика, 2004. - 368 с.

70. Лукинский, В.С. Модели и методы теории логистики / В.С. Лукинский, В.В. Лукинский, Ю.В. Малевич и др. - Санкт-Петербург: Изд-во Питер, 2007. - 448 с.

71. Майника, Э. Алгоритмы оптимизации на сетях и графах / Э. Майника. -Москва: Мир, 1981. - 324 с.

72. Мандель, И.Д. Кластерный анализ / И.Д. Мандель. - Москва: Финансы и статистика, 1988. - 176 с.

73. Матвийчук, А.Р. О построении разрешающих управлений в задачах управления с фазовыми ограничениями / А.Р. Матвийчук, В.Н. Ушаков // Известия РАН. Теория и системы управления. - 2006. - № 1. - С. 5-20.

74. Миротин, Л.Б. Транспортная логистика: Учебник для транспортных вузов / Л.Б. Миротин. - М.: Изд-во «Экзамен», 2003. - 512 с.

75. Миротин, Л.Б. Логистика, технология, проектирование складов, транспортных узлов и терминалов / Л.Б. Миротин, А.В. Бульба, В.А. Демин. -Ростов-на-Дону: Феникс, 2009. - 408 с.

76. Можаев, Г.В. Задача о непрерывном обзоре поверхности Земли и кинематически правильные спутниковые системы / Г.В. Можаев // Космические исследования - 1972. - Т.10, № 6. - С. 833-840.

77. Мухачева, А.С. Простые эвристики для решения двумерной задачи максимального покрытия: Принятие решений в условиях неопределенности /

А.С. Мухачева // Межвузовский научный сборник. - Ч. 1.- Уфа: УГАТУ. -2005. - Вып. 2 - С. 24-32.

78. Пиявский, С.А. Об оптимизации сетей / С.А. Пиявский // Известия Академии наук СССР. Техническая кибернетика. - 1968. - № 1. - С. 68-80.

79. Подлазова, A.B. Генетические алгоритмы на примерах решения задач раскроя / A.B. Подлазова // Проблемы управления. - 2008. - Вып. 2. - С. 57-63.

80. Попков, В.К. О моделировании городских транспортных систем гиперсетями / В.К. Попков // Автоматика и телемеханика. - 2011. - №. 6. - С. 179-189.

81. Препарата, Ф. Вычислительная геометрия. Введение / Ф. Препарата, М. Шеймос. - Москва: Мир, 1989. - 478 с.

82. Протасов, В.Ю. Максимумы и минимумы в геометрии / В.Ю. Протасов. -Москва: МЦНМО, 1999. - 56 с.

83. Расина, И.В. Итерационные алгоритмы оптимизации дискретно-непрерывных процессов / И.В. Расина // Автоматика и телемеханика // - 2012. -№. 10. - C. 3-17.

84. Самарский, А.А. Математическое моделирование. Методы описания и исследования сложный систем / А.А. Самарский, Н.Н. Моисеев, А.А. Петров. -Москва: Наука, 1989. - 271 с.

85. Свеженцева, О.В. Разработка и тестирование генетического алгоритма размещения источников питания в распределительной электрической сети / О.В. Свеженцева // Вестник ИрГТУ. - 2012. - №4. - С. 184-193.

86. Тараскина, А.С. Нечеткая кластеризация по модифицированному методу C-средних и её применение для обработки микрочиповых данных / А.С. Тараскина // Проблемы интеллектуализации и качества систем информатики. - 2006. - С. 217-228.

87. Телицкий, С.В. Комплексный подход к решению задачи покрытия области заготовками неопределенных размеров / С.В. Телицкий, А.С. Филиппова // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. - 2012. - № 2(145). - С. 61-67.

88. Ушаков, В.Н. Один метод решения задач управления протяженными объектами на конечном промежутке времени / В.Н. Ушаков, А.Р. Матвийчук // Труды IX Международной Четаевской конференции «Аналитическая механика, устойчивость и управление движением», Иркутск: ИДСТУ СО РАН, 2007. - Т. 3. -С. 253-261.

89. Филиппова, А.С. Задачи о минимальном покрытии ортогональных многоугольников с запретными участками / А.С. Филиппова, В.Ю. Кузнецов // Информационные технологии. - 2008. - № 9 (145). - С. 60-65.

90. Хамисов, О.В. Обоснование эффективности межгосударственных энергообъединений с разделением эффектов между участниками / О.В. Хамисов, В.А. Савельев, Л.Ю. Чудинова, С.В. Подковальников // Автоматика и телемеханика. - 2018. - № 10. - C.26-38.

91. Шишулин, С.С. Методология сравнительного статистического анализа промышленности России на основе кластерного анализа / С.С Шишулин // Статистика и экономика. - 2017. - №. 3. - С. 21-30.

92. Щербакова, В.А. Классы ориентированных градуированных графов с полиномиально разрешимой мощностной задачей Штейнера / В.А. Щербакова //Дискретная математика. - 1997. - Вып. 4. - С. 73-85.

93. Addis, B. An improved algorithm for the packing of unequal circles within a larger containing circle / B. Addis, H. Wang, W. Huang, Q. Zhang, D. Xu // European Journal of Operational Research. - 2002. - Vol. 141. - P. 440-453.

94. Addis, B. Efficiently packing unequal disks in a circle / B. Addis, M. Locatelli, F. Schoen // Operations Research Letters. - 2008. - Vol. 36, № 1. - P. 37-42.

95. Akeb, H. A beam search algorithm for the circular packing problem / H. Akeb, M. Hifi, R. M'Hallah // Computers & Operations Research. - 2009. -Vol. 36. - P. 1513-1528.

96. AlBdaiwi, B.F. A GPU-based genetic algorithm for the p-median problem / B.F. AlBdaiwi, H.M.F. AboElFotoh // Journal Of Supercomputing. - 2017. - Vol. 73, № 10. - P. 4221-4244.

97. Aldynool, T.A. The coverage of a planar region by randomly deployed sensors / T.A. Aldynool, A.I. Erzin, V.V. Zalyubovskiy // Journal of Mathematical Sciences. - 2010. - Vol. 10, № 4. - P. 7-25.

98. Anil, K.J. Algorithms for clustering data / K.J. Anil. - New Jersy: Prentice Hall, 1988. - 320 p.

99. Arthur, D. K-means++: The advantages of careful seeding / D. Arthur, S. Vassilvitskii // Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, United States. - P. 1027-1035.

100. Avella, P. An effective heuristic for largescale capacitated facility location problems / P. Avella, M. Boccia, A. Sforza, I. Vasil'ev // Journal of Heuristics. -2009. -Vol. 15, №. 6. - P. 597-615.

101. Banhelyi, B. Optimal circle covering problems and their applications / B. Banhelyi, E. Palatinus, B.L. Levai // Central European Journal of Operations Research. - 2015. - Vol. 23, No. 4. - P. 815-832.

102. Berg, M.D. Computational Geometry: Algorithms and Applications / M.D. Berg, M.V. Kreveld, M. Overmars. - Springer Verlag, Berlin, 2008. - 386 p.

103. Bezdek, J.C. FCM: The Fuzzy C-means clustering algorithm / J.C. Bezdek, R. Ehrlich, W. Full // Computers and Geosciences. - 1984. - Vol. 10, № 2-3. - P. 191203.

104. Bezdek, K. Improving Rogers' upper bound for the density of unit ball packings via estimating the surface area of Voronoi cells from below in Euclidean d-space for all d > 8 / K. Bezdek // Discrete and Computational Geometry. - 2002. - Vol. 28, № 1. - P. 75-106.

105. Birgin, E. Optimizing the packing of cylinders into a rectangular container: A nonlinear approach / E. Birgin, J. Martinez, D. Ronconi // European J. Oper. Res. -2005. - Vol. 160, № 1. - P. 19-33.

106. Blundon, W.J. Multiple covering of the plane by circles / W.J. Blundon // Mathematika. - 1957. - Vol. 4, № 1. - P. 7-16.

107. Boll, D.W. Improving dense packings of equal disks in a square [Electronic resource] / D.W. Boll, J. Donovan, R.L. Graham, B.D. Lubachevsky // The electronic

Journal of combinatorics. - 2000. - Vol. 7. - URL: http://www.combinatorics.org /oj s/index.php/elj c/article/view/v7i 1r46 (дата обращения: 23.11.2018).

108. Bortfeldt, A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces / A. Bortfeldt // Eur. J. Oper. Research. - 2006. - Vol. 172. - P. 814-837.

109. Cardei, M. Improving netwotk lifetime using sensors with adjustible sensing ranges / M. Cardei, J. Wu, M. Lu // Int. J. Sensor Networks. - 2006. - Vol. 1. - P. 4149.

110. Casazza, M. Mathematical programming algorithms for bin packing problems with item fragmentation / M. Casazza, A. Ceselli // Computers & Operations Research. - 2014. - Vol. 46. - P. 1-11.

111. Castilo, I. Solving circle packing problems by global optimization: Numerical results and industrial applications / I. Castilo, F. Kampas, J. Pinter // European Journal of Operational Research. - 2008. - Vol. 191, № 3. - P.786-802.

112. Ceselli, A. Two exact algorithms for the capacitated p-median problem / A. Ceselli // 4OR Quarterly Journal of the Belgian, French and Italian Operations Research Society. - 2003. - Vol. 1, № 4. - P. 319-340.

113. Ceria, S. A Lagrangian-based heuristic for large-scale set covering problems / S. Ceria, P. Nobili, A. Sassano // Mathematical Programming. - 1998. - Vol. 81, № 2. - P. 215-228.

114. Chvatal, V. A greedy heuristic for the set covering / V. Chvatal // Mathematics of Optimizations Reseach. - 1979. - Vol. 4, № 3. - P. 233-235.

115. Christaller, W. Central places in southern Germany / W. Christaller. - N.J.: Prentice-Hall, 1966. - 230 p.

116. Chan, Y. Location, transport and land-use: Modelling spatial-temporal information / Y. Chan. - Berlin: Springer, 2005. - 929 p.

117. Coates, A. Learning feature representations with k-means / A. Coates, A.Y. Ng // Neural Networks: Tricks of the Trade. Lecture Notes in Computer Science. - 2012. - Vol. 7700. - P. 561-580.

118. Das, G.K. Efficient algorithm for placing a given number of base station to cover a convex region / G.K. Das, S. Das, S.C. Nandy, B.S. Shina // J. Parallel Distrib. Comput. - 2006. - Vol. 66. - P.1353-1358.

119. Dorninger, D. Thinnest covering of the Euclidean plane with incongruent circles / D. Dorninger // Anal. Geom. Metr. Spaces. - 2017. - Vol. 5, № 1. - P. 40-46.

120. Drezner, Z. Facility location: A survey of applications and methods / Z. Drezner. - NY: Springer, 1995. - 571 p.

121. Erdogan, G. Exact and heuristic algorithms for the Hamiltonian p-median problem / G. Erdogan, G. Laporte, Chia A.R.M // European Journal of Operational Research. - 2016. - Vol. 253, № 2. - P. 280-289.

122. Farahani, R.Z. Facility location: Concepts, models, algorithms and case studies / R.Z. Farahani, M. Hekmatfar. - Berlin: Springer, 2009. - 549 p.

123. Few, L. Double covering with spheres / L. Few // Mathematika. - 1967. -Vol. 14. - P. 207-214.

124. Few, L. Double packing of spheres: A new upper bound / L. Few // Mathematika. - 1968. - Vol. 15. - P. 88-92.

125. Few, L. Multiple packing of spheres / L. Few // J. London Math. Soc. -1964. - Vol. 39. - P. 51-54.

126. Florian, A. Solid coverings of the Euclidean plane with incongruent circles / A. Florian, A. Heppes // Discrete Computational Geometry. - 2000. - Vol. 23. -P. 225-245.

127. Fodor, F. The densest packing of 12 congruent circles in a circle / F. Fodor // Contributions to Algebra and Geometry. - 2000. - Vol. 43. - P. 401-409.

128. Fodor, F. The densest packing of 13 congruent circles in a circle / F. Fodor // Contributions to Algebra and Geometry. - 2003. - Vol. 40, № 2. - P. 431-440.

129. Fodor, F. The densest packing of 19 congruent circles in a circle / F. Fodor // Contributions to Algebra and Geometry. - 1999. - Vol. 74, № 2. - P. 139-145.

130. Fraser, H.J. Integrated container loading software for pulp and paper industry / H.J. Fraser, J.A. George // European Journal of Operational Research. - 1994. - Vol. 77. - P. 466-474.

131. Friedman, E. Circles covering squares. [Electronic resource]. - URL: http: //www2. stetson. edu /~efriedma/circovsqu/.

132. Fujito, T. On combinatorial approximation of covering 0-1 integer programs and partial set cover / T. Fujito // Journal of Combinatorial Optimization. - 2004. -Vol. 8, No. 4. - P. 439-452.

133. George, J.A. Packing different-sized circles into a rectangular container / J.A. George, J.M. George, B.W. Lamer // European Journal of Operational Research. -1995. - Vol. 84. - P. 693-712.

134. Gilmore, P.C. A linear approach to the cutting-stock problem / P.C. Gilmore, R.E. Gomery // Operations Research. - 1961. - Vol. 9. - P. 849-859.

135. Graham, R.L. Dense packings of congruent circles in a circle / R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.R.J. Ostergard // Discrete Mathematics. - 1998. -Vol. 181. - P. 139-154.

136. Grosso, A. Solving the problem of packing equal and unequal circles in a circular container / A. Grosso, A.R. Jamali, M. Locatelli, F. Schoen // Journal of Global Optimization. - 2010. - Vol. 47, № 1. - P. 63-81.

137. Hales, T. A formulation of the Kepler conjecture / T. Hales, S. Ferguson // Discrete Comput. Geom. - 2006. - Vol. 36. - P. 21-69.

138. Hales, T. A formal proof of the Kepler conjecture / T. Hales, M. Adams, G. Bauer, T. Dang, J. Harrison, L. Hoang // Forum of Mathematics, Pi. - 2017. -Vol. 5, № 2. - URL: http://dx.doi.org//10.1017/fmp.2017.1 (дата обращения: 14.12.2018).

139. Hall, N. A fast approximation algorithm for the multicovering problem / N. Hall, D. Hochbaum // Discrete Appl. Math. - 1989. - Vol. 15. - P. 35-40.

140. He, K. An action-space-based global optimization algorithm for packing circles into a square container / K. He, M. Huang, C. Yang // Computers & Operations Research. - 2015. - Vol. 58. - P. 67-74.

141. Heppes, A. Covering a rectangle with equal circles / А. Heppes, J.B.M. Melissen // Period. Math. Hungar. - 1997. - Vol. 34, № 1-2. - P. 65-81.

142. Hermann, G. Parallel genetic algorithm for solving the container loading problem / A. Bortfeldt, G. Hermann // Internat. Trans. in Operat. Research. - 2002. - V. 9, № 4. - P. 497-511.

143. Hifi, M. Adaptive and restarting techniques-based algorithms for circular packing problems / M. Hifi, R. M'Hallah // Computational Optimization and Applications. - 2008. - Vol. 39. - P. 17-35.

144. Hifi, M. A simulated annealing approach for the circular cutting problem / M. Hifi, V.T. Paschos, V. Zissimopoulos // European Journal of Operational Research.

- 2004. - Vol. 159. - P. 430-448.

145. Huang, W. Greedy algorithms for packing unequal circles into a rectangular container / W. Huang, Y. Li, H. Akeb, C. Li // Journal of the Operational Research Society. - 2005. - Vol. 56. - P. 539-548.

146. Huang, W. New heuristics for packing unequal circles into a circular container / W. Huang, Y. Li, C. Li, R. Xu // Computers & Operations Research. - 2006.

- Vol. 33. - P. 2125-2142.

147. Huang, W. A new heuristic algorithm for rectangle packing / W. Huang, D. Chen, R. Xu // Computers & Operat. Research. - 2007. - V. 34. - P. 3270-3280.

148. Huang, W. Note on: An improved algorithm for the packing of unequal circles within a larger containing circle / W. Huang, M. Chen // Computers & Industrial Engineering. - 2006. - Vol. 50. - P. 338-344.

149. Johnson, D.S. Approximation algorithms for combinatorial problems / D.S. Johnson // Journal of Computer and System Sciences. - 1974. - Vol. 9, № 3. - P. 256-278.

150. Kazakov, A.L. An algorithm for packing circles of two types in a fixed size container with Non-Euclidean metric / A.L. Kazakov, A.A. Lempert, Q.M. Le // CEUR-Workshop Proceedings. - 2017. - Vol. 1975. - P. 281-292.

151. Kazakov, A.L. On mathematical models for optimization problem of logistics infrastructure / A.L. Kazakov, A.A. Lempert // International Journal of Artificial Intelligence. - 2015. - Vol. 13, № 1. - P. 200-210.

152. Karatas, M. An iterative solution approach to a multi-objective facility location problem / M. Karatas, E. Yakici // Applied Soft Computing. - 2018. - Vol. 62. - P. 272-287.

153. Kravitz, S. Packing cylinders into cylindrical containers / S. Kravitz // Mathematics Magazine. - 1967. - Vol. 40, № 2. - P. 65-71.

154. Lempert, A.A. Multiple covering of a closed set on a plane with non-Euclidean metrics / A.A. Lempert, Q.M. Le // IFAC-PapersOnLine. - 2018. - Vol. 51, № 32. - P. 850-854.

155. Lempert, A.A. On reserve and double covering problems for the sets with non-Euclidean metrics / A.A. Lempert, A.L. Kazakov, Q.M. Le // Yugoslav Journal Operation Research. - 2019. - Vol. 29, № 1. - P. 69-79.

156. Lempert, A.A. On the thinnest covering of fixed size containers with Non-Euclidean metric by incongruent circles / A.A. Lempert, A.L. Kazakov, Q.M. Le // Сборник тезисов международной конференции «Теория математической оптимизации и исследование операций - MOTOR 2019». Екатеринбург: ИММ УрО РАН, 2019. - C. 113.

157. Liu, J. Efficiently packing circles into a larger containing circle / J. Liu, Y. Wang, J. Pan / In High performance computing and applications: Lecture Notes in Computer Science. - Heidelberg, Germany: Springer, 2010. - Vol. 5938. P. 250-256.

158. Litinskii, L.B. Neural Network Clustering Based on Distances Between Objects / L.B. Litinskii, D.E. Romanov // Artificial Neural Networks - ICANN 2006: Lecture Notes in Computer Science. - Berlin: Springer Verlag, 2006. - Vol. 4132. - P. 438-443.

159. Locatelli, M. Packing equal circles in a square: a deterministic global optimization approach / M. Locatelli, U. Raber // Discrete Applied Mathematics. -2002. - Vol. 122. - P.139-166.

160. Lopez, C.O. A heuristic for the circle-packing problem with a variety of containers / C.O. Lopez, J.E. Beasley // European Journal of Operational Research. -2011. - V. 214. - P. 512-525.

161. Lopez, C.O. Packing unequal circles using formulation space search / C.O. Lopez, J.E. Beasley // Computers and Operations Research. - 2013. - Vol. 40. - P. 1276- 1288.

162. Lubachevsky, B.D. Curved hexagonal packings of equal disks in a circle / B.D. Lubachevsky, R.L. Graham // Discrete & Computational Geometry. - 1997. -Vol. 18. - P. 179-194.

163. MacQueen, J. Some methods for classification and analysis of multivariate observations / J. MacQueen // University of California, Los Angeles. - 1967. Vol. 1. -P. 281-297.

164. Markot, M.Cs. A new verified optimization technique for the «packing circles in a unit square» problems / M.Cs. Markot, T.A. Csendes // SIAM Journal on Optimization. - 2005. - V. 16. - P. 193-219.

165. Melissen, H. Densest packings of congruent circles in an equilateral triangle / H. Melissen // American Mathematical Monthly. - 1993. - Vol. 100. - P. 916-925.

166. Melissen, J.B.M. Densest packing of eleven congruent circles in a circle / J.B.M. Melissen // Geometriae Dedicata. - 1994. - Vol. 50. - P. 15-25.

167. Melissen. J.B.M. Loosest circle coverings of an equilateral triangle / J.B.M. Melissen // Math. Mag. - 1997. - Vol. 70. - P. 119-125.

168. Melissen, J.B.M. Optimal packings of eleven equal circles in an equilateral triangle / J.B.M. Melissen //Acta Mathematica Hungarica. - 1994. - Vol. 65. - P. 389393.

169. Murphy, P.R. Contemporary Logistics / P.R. Murphy, D.F. Wood. -Prentice-Hall, New York, 2008. - 415 p.

170. Nurmela, K.J. Covering a square with up to 30 equal circles [Электронный ресурс] / K.J. Nurmela, P.R.J. Ostergard. - Res. rept A62. Lab. Technol. Helsinki Univ. - 2000. - 20 p. - URL: http://www.ymmf.hu/sites/ talata. istvan.ymmf.hu/files/2015_osz/sikgeom_bemut 1 _segedanyagok/covering_a_squa re_with_circles.pdf (дата обращения: 04.12.2018).

171. Nurmela, K.J. Packing up to 50 equal circles in a square / K.J.Nurmela, P.R.J. Ostergard // Discrete and Computational Geometry. - 1997. - Vol. 18. - P. 111-120.

172. Poshyanonda P. Two dimensional nesting problem: artificial neural network and optimization approach Neurale Networks / P. Poshyanonda, A. Bahrami, C.H. Dagli // IJCNM., International Joint Conference. - 1992. - Vol. 4, № 4. - P. 572-577.

173. Shamos, M.I. Geometric intersection problems [Электронный ресурс] / M.I. Shmos, D. Hoey. - 17th Annual Symposium on Foundations of Computer Science (sfcs 1976), Houston, TX, USA, 1976. - P. 208-215. - URL: http://dx.doi.org/10.1109/SFCS.1976.16 (дата обращения: 26.01.2019).

174. Specht, E. A precise algorithm to detect voids in polydisperse circle packings [Электронные ресурс] / E. Specht // Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science, 2015. - Vol. 471, № 2182. - URL: http://dx.doi.org/10.1098/rspa.2015.0421 (дата обращения: 08.02.2019).

175. Specht, E. Packomania [Электронные ресурс]. - 2019. - URL: http://www.packomania.com (дата обращения: 03.02.2019).

176. Stoyan, Y.G. An optimization problem of packing identical circles into a multiply connected region / Y.G. Stoyan, A.M. Chugay // Journal of Mechanical Engineering. - 2011. - Vol. 14, № 1. - P. 44-51.

177. Stoyan, Y.G. Covering a compact polygonal set by identical circles / Y.G. Stoyan, V.M. Patsuk // Comput. Optim. Appl. - 2010. - Vol. 46. - P. 75-92.

178. Stoyan, Y.G. Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints / Y.G. Stoyan, G.N. Yaskov // International Transactions in Operational Research. -1998. - Vol. 5. - P. 45-57.

179. Szabo, P.G. New approaches to circle packing in square with program codes / P.G. Szabo, M.Cs. Markot , T. Csendes, E. Specht, L.G. Casado , I. Garcia. - N.Y.: Springer Verlag, 2007. - 390 p.

180. Tabirca, T. Smallest number of sensors for k-covering / T. Tabirca, L.T. Yang, S. Tabirca // Int. J. Comput. Commun. Control. - 2013. - Vol. 8, № 2. - P. 312-319.

181. Tarnai, T. Covering a square by equal circles / T. Tamai, Zs. Gaspar // Acta Technica Acad. Sci. Hung. - 1995. - Vol. 50. - P. 167-170.

182. Terminology in Logistics. Annex Dictonary / UK: Europian Logistics Association, 1994. - 367 р.

183. Toth, G.F. Covering the plane with two kinds of circles / G.F. Toth // Discrete Computational Geometry. -1995. -Vol. 13. -P. 445-457.

184. Toth, G.F. Packing and covering [Электронный ресурс] / G.F. Toth // Handbook of Discrete and Computational Geometry. - URL: https://pdfs. semanticscholar.org/affb/ce2b9b2260f72d65e21b9d22bf88a4a231e7.pdf (дата обращения: 20.02.2019).

185. Toth, G.F. Thinnest covering of a circle by eight, nine, or ten congruent circles / G.F. Toth // Combinatorial and Computational Geometry. - 2005. - Vol. 52. -P. 361-376.

186. Toth, L.F. Solid circle-packings and circle-coverings / L.F. Toth // Studia Sci. Math. Hungar. - 1968. - Vol. 3. - P. 401-409.

187. Toth, G.F. Multiple packing and covering of the plane with circles / G.F. Toth // Acta Mathematica Acaddemiae Scientiarum Hungarica. - 1976. -Vol. 27. - P. 135-140.

188. Wang, H. An improved algorithm for the packing of unequal circles within a larger containing circle / H. Wang, W. Huang, Q. Zhang , D. Xu // European Journal of Operational Research. - 2002. - Vol. 141. - P. 440-453.

189. Xueying, Zh. Based on Gravity Method of Logistics Distribution Center Location Strategy Research / Zh. Xueying // International Conference on Logistics Engineering, Management and Computer Science, 2014. - Vol. 101. - URL: https://doi.org/10.2991/lemcs-14.2014.134 (дата обращения: 15.12.2018).

190. Zahn Jr.C.T. Black box maximization of circular coverage / Jr.C.T. Zahn // Journal of Research of the National Bureau of Standards. - 1962. - Vol. 66, № 4. - P. 181-216.

191. Zhang, D. An effective hybrid algorithm for the problem of packing circles into a larger containing circle / D. Zhang, A. Deng // Computers & Operations Research. - 2005. - Vol. 32, № 8. - P. 1941-1951.

Свидетельство о государственной регистрации программы для ЭВМ

Приложение B

Акты о внедрении программного продукта

АКТ

о внедрении программного продукта «КУПОЛ-М (кратные упаковки и покрытии, оптимизация, логистика)» (авторы Казаков Л.Л.. Лемперт A.A., Ле K.M.)

11астоящии акт свидетельствует о том, чю программный продукт «КУПОЛ-М (кратные упаковки и покрытия, оптимизация, логистика)» (Свидетельство о государственной регистрации 2013666830 от 26 ноября 2018), авторами которою являются Казаков Александр Леонидович. Лемперт Анна Ананьевна, Ле КуангМынг, внедрён в учебный процесс и используется на кафедре «Автоматизирован пых систем» Федерального государственного бюджетного образовательного учреждения высшего образовании «Иркутский национальный исследовательский технический университет» (ФГБОУ ВО ИР1 МТУ) в учебных курсах «Системология».

Программный модуль «КУПОЛ-М (кратные упаковки и покрытия, оптимизация, логистика)» реализует численные методы решения ряда задач оптимального размещения логистических объектов в озраниченное множество на основе кратных упаковок и покрытий в двумерных метрических пространствах с неевклидовыми метриками. Он имеет простой, удобный и интуитивно понятный интерфейс. Исследователи, аспиранты и магистранты могут применять данный программный модуль дня исследования методов оптимизации, а студенты при изучении соответствующих дисциплин: программирование на высоком языке, теория управления и др,

ЗаведуЕОщнй кафедрой « Автоматизированных систем»

к.т.н, доцент —jg-^*' C.B. Бахвалов

Профессор кафедры «Автоматизированных систем»

к.т.н, профессор

military technical academy socialist republic of vietnam

INSTmriT Of^IMUlvVriCW TECHNOLOGY liKlqx-ntktKr - Freedom - Happjam

No: 97/GCN-CNMP Ha Noi, 25/10/2019

CERTIFICATE on software implementation MPCOL-M

Institute of Simulation Technology certifies that the software product «MPCOL-M (multiple packing and covering, optimization, logistic)», which is developed by Mr. Kazakov Alexandar Leonidovich, Ms. Lempert Anna Ananievna, Mr Nguyen Huy Liem, Mr. Le Quang Mung (Irkutsk National Research Technical University), is implemented in the educational process and used in the activities of the Institute of Simulation Technology, Military Technical Academy, Vietnam.

Using the computer program "MPCOL-M (multiple packing and covering, optimization, logistic)" (The certificate of state registration № 2018666830 dated November 26* 2018) allows us to solve the problems of optimal placement of logistics centers with non-F.uclidean metrics on the plane.

The software module has a simple, user-friendly and intuitive interface. The software module is intended for researchers, graduate students, who have the scientific interests in the field of optimization methods. In addition, it is useful for specialists to plan the development of transport and logistics infrastructure, as well as for students in the study of relevant disciplines./.^

Receiver:

- Mr. Liem (02b);

- Store: BM, VI. L04