Разработка алгоритма поиска наилучших партнеров в логистической сети

В этой главе будет рассмотрен алгоритм поиска партнеров для взаимовыгодного сотрудничества в логистической сети. Исходными данными при этом являются модели, реализованные с помощью онтологии FEO. Основная задача данного алгоритма: выбрать среди всех участников логистической сети исполнителей транзакций таким образом, чтобы получить наиболее выгодную конфигурацию с точки зрения взаимодействия.

Сведение к задаче о поиске кратчайшего пути в нагруженном графе

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

По аналогии с проектом iCargo для того, чтобы стать участником логистической сети каждая компания должна предоставить данные о себе в формате OWL файла, содержащего информацию о взаимосвязях между бизнес-концептами организации в виде метамодели, полученной нами ранее в ходе интерпретации BMM с помощью онтологий UFO-C и FEO.

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

В итоге, среди полученных цепочек транзакций должна быть выбрана наиболее подходящая цепочка, оптимальная в смысле некоторой целевой функции, и для каждой транзакции выбранной цепочки должны быть назначены исполнители из числа компаний-участников сети. В рамках данной работы ставится задача максимизации целевой функции, при этом в качестве целевой функции выступает сумма так называемых степеней выгодности сотрудничества (степени связанности — cv (A_i, B_i)) пар компаний вида (Инициатор, Исполнитель) для всех транзакций из выбранной цепочки:

Smax = ?cv (Initiator_i, Executor_i)>max, i:1.n, (1).

где n — количество транзакций в выбранной цепочке.

Данную задачу можно сформулировать иначе: для нахождения наиболее выгодной конфигурации сети необходимо минимизировать целевую функцию, в качестве которой выступает сумма разностей некоторого максимального числа и степеней выгодности сотрудничества пар компаний вида «Инициатор, Исполнитель» для всех транзакций из выбранной цепочки:

Smin = ?(max — cv (Initiator_i, Executor_i))>max, i:1.n, (2).

где n — количество транзакций в выбранной цепочке;

max — максимальная степень выгодности для выбранной цепочки.

Рассмотрим второй вариант формулировки задачи более подробно. Эту задачу можно представить в виде ориентированного графа (рис. 15), где вес вершины — это компании, предоставляющие соответствующие услуги, т. е. выполняющие конкретные транзакции.

Например, если рассматривать логистическую сеть и процесс доставки груза, {A₁, A₂, ., A_n} - компании, которые могут выполнять транзакцию «Упаковка груза», а компании {Z₁, Z₂, ., Z_n} - транзакцию «Оплата груза».

Рис. 15. Задача поиска наилучших партнеров в сети.

Если определенным образом добавить веса, то данную задачу можно свести к задаче о нахождении кратчайшего пути в нагруженном графе, решением которой и будет наилучшая комбинация компаний (A_i, B_j, …, Z_k) для данного клиента.

Обозначим вес ребра между двумя вершинами vi и vj через w (vi, vj). Необходимо выбрать веса таким образом, чтобы минимальное суммарное значение веса, равное сумме весов w (A_i, B_j), w (B_j, C_l), и т. д. соответствовало наиболее взаимовыгодной конфигурации компаний-участников сети.

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

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

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

В стандарте SCOR выделяется ряд показателей KPI, характеризующих качество выполнения транзакций, сгруппированных по категориям: Reliability, Responsiveness, Costs и др. [23]. Для вычисления степени выгодности сотрудничества двух компаний, или степени связанности, в рамках указанной транзакции будем использовать следующий алгоритм:

• 1) Просуммировать количество показателей KPI по каждой категории (вес категории) для данной транзакции. Повторить для каждой компании.
• 2) Рассчитать степень связанности двух компаний как сумму совпадающих весов категорий по всем категориям.

Таким образом, первый шаг к определению весов на ребрах графа это вычисление так называемой степени связанности (connectivity degree). Например, рассмотрим логистическую сеть, ребро (A_i, B_j). Данное ребро соответствует следующему утверждению: «Инициатором транзакции типа B выступает компания A₁, исполнителем — компания B₂». Мы с помощью SPARQL запросов к моделям бизнес-знаний обеих компаний, описанных в формате OWL, можем получить информацию о показателях, которые компании A₁ и B₂ используют, для оценки качества выполняемых действий. Далее, используя описанный ранее алгоритм, мы вычисляем степень выгодности сотрудничества этих компаний в рамках транзакции B и записываем его в показатель степени связанности (connectivity degree), обозначенный нами ранее в виде cv (A_i, B_j). Важно отметить, что ребрам, направленным к вершине Fin, мы присваиваем нулевое значение.

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

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

• 1) Найти ребро с максимальным весом и записать его значение в max.
• 2) Чтобы избежать операций с нулем, увеличиваем значение max на единицу.
• 3) Присваиваем ненулевым ребрам новые веса, равные разнице между максимальным значением и исходным значением веса.

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

Рис. 16. Задача о минимальном пути в нагруженном графе