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

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

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

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

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

Путем численных экспериментов выполнено сравнение двух реализаций алгоритма Краскала, основанных на списочной (предложенный алгоритм) и древовидной (алгоритм Тарьяна) структуре данных и алгоритма Прима. Результаты сравнения позволяют утверждать, что для решения практических задач нахождение минимального или максимального остовного дерева (леса) алгоритмы со списочной структурой данных работают не хуже, а в большинстве случаев быстрее, чем алгоритмы с древовидной структурой. Показана практическая оценка сложности предложенного алгоритма, которая для связных графов составляет O(e), где e - число ребер графа. Экспериментально доказано, что время работы алгоритма на связных разреженных графах сравнимо со временем "карманной" сортировки ребер (bucket sort). Выявлено, что предложенный алгоритм работает быстрее алгоритма Прима для графов с числом ребер не больше, чем 0,27, 2v где v - число вершин графа. Экспериментальное исследование алгоритма на графах, содержащих от 499500 до 71994000 ребер, показало его высокую вычислительную эффективность, и он может быть рекомендован для решения практических задач на разреженных графах или сетях большой размерности.

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

Розглянуто задачу оптимізації упакувань елементів квадратної матриці, заданих цілими позитивними числами, у блоки фіксованого розміру. Запропоновано постановку задачі та досліджено трудомісткість повного перебору її розв'язків. Доведено, що задача є NP-повною. Це зроблено шляхом поліноміального зведення до неї NP-повної цілочислової задачі про багатопродуктовий потік мінімальної вартості.

Розглянуто алгоритми розв'язання задачі оптимізації пакування, що виникає під час сортування та пакування дрібнопартіонних вантажів у контейнери в магістральних транспортних мережах або об'єднання повідомлень у віртуальні контейнери в опорних мережах передачі даних. Запропоновано постановку задачі та обговорено її особливості та підходи до розв'язання. Проаналізовано збіжність і часову складність низки евристичних алгоритмів і на обчислювальних експериментах досліджено їхню порівняльну ефективність. Експериментально показано, що результати розв'язання задачі, одержані різними стратегіями оптимізації на мережах, що містять до 500 вузлів, відрізняються не більше, ніж на 2,65 %.

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

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

Приведены полезные сведения для разработчиков алгоритмов и программ об использовании кодов Грея для решения комбинаторных задач с псевдобулевыми функциями (полиномами от булевых переменных). В качестве примера эффективности применения этих кодов рассматривается решение 0 - 1 задачи о ранце с полным перебором вариантов решения. Представлены результаты экспериментального исследования, которые показывают, что коды Грея можно практически применять в схемах ветвления, например, в методе ветвей и границ, когда количество переменных в узлах ветвления решающего алгоритма не превышает 35.

Рассмотрена задача выбора пропускных способностей дуг из заданного набора, актуальная при распределении потоков в многопродуктовых коммуникационных сетях с ограничением на время задержки потоков. Доказано, что такая задача является NP-трудной. Приведены алгоритмы приближенного решения задачи и результаты их экспериментального сравнения с точным переборным алгоритмом на основе генерации последовательности двоично-отраженных кодов Грея. Отмечено, что получение точного решения возможно с использованием псевдополиномиальных алгоритмов для 0 - 1 задачи о ранце с мультивыбором.

Рассмотрена задача выбора пропускных способностей дуг из заданного набора, актуальная при распределении потоков в многопродуктовых коммуникационных сетях с ограничением на время задержки потоков. Доказано, что такая задача является NP-трудной. Приведены алгоритмы приближенного решения задачи и результаты их экспериментального сравнения с точным переборным алгоритмом на основе генерации последовательности двоично-отраженных кодов Грея. Отмечено, что получение точного решения возможно с использованием псевдополиномиальных алгоритмов для 0 - 1 задачи о ранце с мультивыбором.

Несмотря на многочисленность работ, связанных с проблемой нахождения кратчайших путей (КП), внимание к разработке эффективных по быстродействию алгоритмов построения КП не уменьшается. Это, в первую очередь, объясняется тем, что в подавляющем большинстве случаев такие алгоритмы часто используются для решения отдельных подзадач во многих приложениях в различных областях естествознания, и время решения общей оптимизационной задачи в значительной степени определяется временем построения КП. Рассмотрены 3 группы однокритериальных алгоритмов: сетевые комбинаторные алгоритмы; алгебраические или матричные алгоритмы; алгоритмы, базирующиеся на методах решения задач линейного программирования (LP). Приведены обзор, анализ и классификация методов и алгоритмов построения кратчайших путей на сетях и графах между заданными подмножествами узлов сети (Single Source Shortest Path - SSSP) и между всеми парами узлов (Shortest Path Tree - SPT или All Pairs Shortest Paths - APSP). Приведены оценки временной сложности наилучших известных алгоритмов для решения задач SSSP и APSP комбинаторными, матричными и LP-методами для сетей с неотрицательными длинами дуг и сетей с отрицательными длинами дуг и циклами отрицательной длины. Отмечается, что для решения отдельных SSSP-задач существуют "почти оптимальные" алгоритмы в теории и на практике, в то же время для решения более широкого класса задач, включая и APSP-проблему, имеются предпосылки для улучшения уже существующих алгоритмов. За последние годы эволюция методов решения задачи нахождения КП была связана с разработкой и дальнейшим усовершенствованием эффективных структур абстрактных типов данных для представления объектов задачи и созданием параллельных алгоритмов для многопроцессорного решения задачи. Определены основные направления дальнейших исследований по разработке эффективных методов и алгоритмов решения задач нахождения кратчайших путей.

Исследована задача оптимизации иерархической структуры многопродуктовой коммуникационной сети с дискретными потоками и параметрами при изменении ее плотности (отношение количества дуг сети к максимально возможному количеству дуг для заданного числа узлов в сети). В сети выделено три уровня иерархии - магистральный, зональный и внутренний, и 4 типа узлов - первого, второго и третьего типа, образующие магистральный и зональный уровни сети, и узлы четвертого типа, подчиненные каждому магистральному узлу и образующие внутренние уровни сети. Типы узлов отличаются функциональными возможностями. Основная задача исследования - установить, как изменяется структура магистральной сети (МС) (количество и расположение магистральных узлов первого, второго и третьего типа), схема обработки и распределения потоков и техникоэкономические показатели функционирования сети для различной степени ее плотности. Приведены принципы сортировки и распределения потоков в иерархической сети и ее математическая модель. Сформулирована математическая модель задачи оптимизации структуры МС, схемы сортировки и распределения потоков. Алгоритмы решения задачи основаны на предложенном ранее авторами дискретном аналоге метода локального спуска, когда окрестности метрического пространства возможных решений выбираются из эвристических соображений с учетом особенностей решаемой задачи. Проведено компьютерное моделирование задачи на однородной сети, содержащей 100 узлов при изменении степени узлов от 2 до 99. Моделирование проведено на примере автотранспортной сети перевозки грузов с помощью компьютерной программы, которая является частью инструментальных программных средств информационно-аналитической системы поддержки принятия решений (ИАС НИР), которая разрабатывается в Институте телекоммуникаций и глобального информационного пространства НАН Украины. Экспериментальное исследование решения задачи показало, что наилучшие технико-экономические и эксплуатационные показатели ее функционирования достигаются при степени узлов сети от 9 до 14, когда обеспечивается высокая связность сети и значительно сокращается среднее и максимальное время доставки грузов получателям. Предложенная компьютерная технология решения задачи при изменении плотности сети позволяет проектировщику в интерактивном режиме моделировать различные варианты сети, изменяя топологию, иерархическую структуру, потоки, параметры и ограничения модели; из семейства полученных результатов выбирать наилучший вариант с учетом выбранной функции цели и принятых ограничений; рассчитывать предварительные технико-экономические показатели функционирования сети; оценивать стоимость дополнительных ресурсов; для планирования величины потребных инвестиций на модернизацию и строительство ее структурных элементов, что в конечном итоге дает возможность повысить эффективность функционирования сети за счет оптимизации использования ее ресурсов и снижения эксплуатационных затрат на обработку и транспортировку потоков.

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