Синтез структуры сети доставки

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

Заданы множество X = { x_i }, клиентов СД, которыми являются в данном случае ЛПС, матрица ||Λ|| интенсивностей потоков сообщений λ _ij, передаваемых в СД между x_i и x_j ПС, требование к среднему времени доставки продовольственных заказов Т₂, которое должно быть обеспечено при доставке заказов между любыми двумя узлами АСДП или ЛСП и клиентом.

Требование к показателям надежности задается в виде параметра связности ν ≥ 2. Это означает, что число независимых путей от ЦС до клиента, пролегающих через различные ПС, должно быть от двух и более. Независимыми будем считать пути, не содержащие общих ПСв, штата вовлечённых сотрудников и автопарка. Помимо этого, заданными считаются расстояния l_ij,  между всеми клиентами и их ЛПС, а так же характеристики КС, на базе которых создается СД аналогично тому, как это имело место в п. 4.3.

При решении задачи синтеза оптимальной топологической структуры СД используются те же допущения относительно характера передаваемых потоков доставляемых заказов и способа получения заказа (самовывоз с ПС (ЦС) или доставка на дом), что и при решении аналогичной задачи для КС.

При введенных допущениях, ограничениях и выбранном критерии оценки эффективности различных вариантов топологических структур СД задача оптимизации ставится следующим образом:

,

где ; ,

 

 = 1, если поток заказов  находится в процессе доставки от ЛПС, обозначаемый как  до клиента, обозначаемого как .

, , ;

F 1: z → ν, ν ≥ 2;

= 1, если в структуре СД есть ПС между заданным ЦС, обозначаемым, как  и ЛПС, обозначаемом как .

Выражение, определяющее С _ij, устанавливает соответствие между пропускной способностью СД, параметрами передаваемого по нему потока заказов и требованием к среднему времени доставки с учетом топологической структуры СД и выбранной формы доставки. Функция F ' устанавливает однозначное соответствие между числом транзитных участков в путях передачи потоков заказов, в которые входит маршрут между ПС x_i и ПС (клиентом) x_j, и параметром β _ij. Функция F 1 устанавливает однозначное соответствие между числом транзитных участков для всех пар ЛПС-клиент в СД заданной структуры и параметром ν, определяющим число независимых путей между ЛПС и клиентом.

Поставленная задача относится к комбинаторным задачам большой размерности, следовательно, ее точное решение невозможно. Для решения подобных задач применяются различного рода эвристические процедуры, компьютерное моделирование, повторяющее основные этапы построения СД с использованием значительных вычислительных мощностей  для точного просчета получаемых вариантов и запоминания больших массивов промежуточных результатов [16, 517, 12, 6]. Суть использования эвристических процедур сводится к выбору на основе эвристических соображений, реализованных в определенном алгоритме, топологических структур СД и определению приемлемости полученных структур в соответствии с заданными требованиями.

Процедура определения приемлемости полученных структур СД приводит к необходимости решения следующих задач:

1)Проверка выполнения требований, предъявляемых к надежности СД;

2)Нахождение маршрутов доставки потоков заказов, задаваемых матрицей тяготений;

3) Определение потоков заказов, передаваемых по каждому пути выбранной структуры СД, и определение требований к среднему времени их транспортировки на каждом этапе процесса;

4) Выбор пропускных способностей служб расфасовки и доставки, а так же расчет показателя эффективности выбранного варианта структуры СД;

5) вычисление задержек в доставке заказов для всех ЛПС и проверка их по допустимому времени задержки.

 

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

Требования к надежности СД задаются в виде показателя связности ν, что позволяет легко выполнить вычисления по проверке допустимости ν для заданной структуры СД.

Решение задач 2 и 3 обязательно должно учитывать принятый в СД метод (алгоритм) доставки заказа до клиента (развозки). Для этого необходимо иметь полную статистическую информацию о передаваемых потоках заказов, что возможно только после определённого этапа эксплуатации реальной СД с учетом множества реальных факторов. Однако на рассматриваемом этапе проектирования АСДП, может быть использован приближенный метод нахождения маршрутов доставки потоков заказов, а так же определения требований к среднему времени доставки по каждому этапу следования заказа внутри СД заданной структуры.

Будем считать, что весь поток заказов на каждом этапе доставки внутри СД передается по фиксированному пути с минимальным числом транзитных участков. Это предположение соответствует случаю использования статического метода управления распределением информационных потоков в вычислительных сетях. Введение указанного положения может быть обосновано следующими аргументами. Введение предположения позволяет математически определить «нижнюю» границу эффективности функционирования СД, соответствующую случаю полной её загрузки, когда выбор обходных направлений приводит к перегрузке служб, занятых в СД (автопарк).

Использование динамического управления могло бы позволить существенно улучшить показатели эффективности функционирования СД в случае возникновения локальных перегрузок (пробки, нехватка занятого в работе автотранспорта и пр.).

Задачи 4 и 5 при введенных предположениях относительно характера поведения потоков заказов, доставляемых по средствам СД, могут быть решены с использованием моделей теории массового обслуживания.

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

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

Рис. 4.8

Существуют различного рода эвристические алгоритмы генерации начальных структур магистральных вычислительных сетей [18, 5]. Можно попробовать использовать их в решении задачи построения оптимальной СД, т.к. принципиальные задачи двух данных процессов схожи.

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

Дальнейшим этапом построения начальной топологической структуры СД является дополнение остова избыточными ПС с целью обеспечения требований к надежности [1, 5]. Такое наращивание остова путей в зависимости от класса доставляемой продукции и возможности формализации условий, предъявляемых к СД, проводится с помощью математических моделей. При введении в СД каждой новой ветви осуществляется решение задач 2 и 4, т. е. определение кратчайшего пути в СД между всеми парами узлов АСДП и характеристик служб, занятых в СД, т. е. оптимальное распределение пропускных способностей автопарка. При дополнении КСП другими ПС, представляется целесообразным включать в избыточную структуру не более 50 % и не менее 30 % общего числа дуг полного графа.

Помимо этого, для решения поставленной задачи может быть использован другой метод. В качестве исходной, в этом случае, выбирается радиально-узловая структура соединения ПС по принципу «каждый с каждым». Строится максимальное связывающее дерево, которое называется также деревом доминирующих требований [20, 21, 18, 2, 19]. Далее производится синтез структуры СД по алгоритму, предложенному Гомори и Ху [1, 19], суть которого состоит в синтезе равномерных поддеревьев. Построенная таким образом минимальная сеть обеспечивает доставку заказа в каждый момент развозки только между двумя любыми оконечными пунктами, но не гарантирует одновременной передачи всех потоков заказов [16, 18]. Данная система является исходной. Надо проверить, обеспечит ли она одновременную передачу всех заданных потоков заказов и требования к заданным показателям надежности. Это может потребовать изменения структуры сети с помощью эвристических алгоритмов.

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

Выбирается пара узлов в СД, между которой нет еще ПСв, и по введенному критерию эффективности определяется целесообразность развёртки нового ПС. При введении нового ПС в работу АСДП, происходит определение его параметров. Если ПСв не вводится, то осуществляется перерасчет нагрузок, в уже существующих ПС на величину потока заказов между выбранной парой ЛПС. Процедура поиска сводится к поиску кратчайшего пути в графе, ветви которого имеют заданные веса [18, 5]. При использовании этого метода в первую очередь распределяется максимальная нагрузка между узлами, находящимися на минимальных расстояниях; все ПС делятся на несколько групп так, чтобы ПС высших групп являлись виртуальными ЦС для ПС низших групп (если считать за высший уровень – реальный ЦС, а за нижний – клиентскую метасистему). В первую очередь в при использовании данного метода происходит распределение нагрузки в пределах этих групп, начиная с низших. Затем распределяется нагрузка между группами.

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

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

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

Вначале случайным образом нумеруются узлы СД, затем происходит добавление линий по одной на каждом шаге. Связность определяется матрицей || M 1 (S ^*, Т ^*)||, которая задает минимальное число линий, соединяющихся с каждым узлом S ^*, т. е. наибольшее целое M 1 (S ^*, Т ^*) по всем пунктам Т ^*. По мере добавления линий на каждом узле регистрируется дефицит числа линий. Дефицит числа линий используется для управления процессом введения ветвей. Правила введения ветви между i и узлами состоят в следующем.

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

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

Конфигурации, полученные с помощью таких изменений существующей СД, постепенно приводят к оптимальным структурам путей следования заказа. Значение критерия эффективности этих путей доставки лишь на несколько процентов отличается от исходного, поэтому решение задачи улучшения начальной топологической структуры СД может быть оправдано и может привести к выигрышу в экономичности лишь при построении сложной многоуровневой АСДП [22].

Для упрощения решения задачи на начальном этапе синтеза структуры СД можно разбить на региональные (локальные) сети, синтезировать эти сети, а затем объединять полученные фрагменты в единую сеть. Число и размеры локальных сетей определяются путем решения дополнительной задачи разбиения всего множества ПС на основе данных об их реальном расположении, взаимодействии и взаимосвязи. При этом возможен просмотр нескольких вариантов разбиений.

Алгоритм синтеза структуры СД, по аналогии с алгоритмами синтеза информационных каналов связи, реализован в виде независимых алгоритмов (рис. 4.9), последовательное выполнение которых приводит к решению поставленной задачи. Фрагменты алгоритмов, требующие многократного повторения, оформлены в виде процедур.

Алгоритм синтеза начальных топологических структур СД основан на идеях, составляющих сущность третьего подхода к решению указанной задачи, т. е. последовательного построения топологической структуры СД. При использовании такого метода решения задачи на каждом шаге выбирается строка i в матрице тяготений ||Λ _М ||.

Клиенты , для которых в выделенной строке λ _ij ≠ 0, составляют множество, применительно к которому решается задача организации новых ПСв в структуре АСДП. Последняя задача полностью тождественна задаче, решенной в п. 3.3. В результате ее решения формируется множество клиентов , для которых значение переменных z_ji = 1, , . Таким образом, на i -м шаге решения в матрицу инциденций || MS ||, задающую топологическую структуру СД, вводятся новые элементы MS_ij = MS_ji = 1, соответствующие организации новых ПСв между ПС с номером i и ПС, составляющими множество , .

Описанная процедура последовательно повторяется для каждой строки матрицы тяготений. В результате формируется матрица инциденций || MS ||, задающая начальную топологическую структуру СД.

Процедура локальной оптимизации (блок 6 на рис. 4.8) заключается в изменении начальной топологической структуры СД за счет удаления ПСв. Схема алгоритма процедуры локальной оптимизации приведена на рис. 4.10.

Из начальной топологической структуры СД предусматривается удаление КСв, если при этом не нарушаются принятые условия связности и улучшается значение критерия Ф.

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

 

 

Рис. 4.9 Алгоритм локальной оптимизации