Программные продукты и системы

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

Для решения каждой из этих задач используются различные методы и подходы. Не- смотря на широкий спектр методов и алгорит- мов разбиения территории на зоны обслуживания, наиболее востребованными являются методы, основанные на построении диаграмм Вороного [1, 2]. Однако эти методы сложны и затратны с вычислительной точки зрения. Кроме того, они не ориентированы на учет особенностей территориальных объектов, а также на геопространственные особенности их размещения (наличие дорог, водных преград, административное деление) при зональном разбиении территорий.

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

Для распределения заказов и назначения логистических средств для их выполнения традиционно используется метод Г. Куна [5–8]. Однако его ограничением является недостаточная гибкость определения степени соответствия логистических средств и заказов. Поэтому в условиях необходимости учета разнокачественных характеристик транспортных средств (в том числе нормы заказов, пройденного без заказов расстояния, расчетного времени подъезда к заказам, расстояния до заказов, стоимости и назначения заказов), а также различных стратегий их поведения требуется реализация возможности каскадного формирования не- четкой оценки соответствия логистических средств и заказов.

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

Описание метода интеллектуальной поддержки принятия логистических решений

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

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

Этап 1. Нахождение центров территориальных зон на основе кластеризации территориальных объектов.

Этап 2. Генетическая кластеризация территориальных объектов относительно центров зон и формирование выпуклых оболочек этих зон с учетом особенностей территориальных объектов, а также геопространственных осо- бенностей их размещения.

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

Этап 4. Распределение заказов по зонам с учетом выбранной стратегии логистических средств.

Этап 5. Назначение логистических средств для выполнения заказов в каждой территориальной зоне.

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

Для реализации этапов 1 и 2 метода разработан способ зонального разбиения территории на основе генетической кластеризации.

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

Для выполнения этапов 4 и 5 разработаны каскадная нечеткая продукционная модель (и алгоритм ее структурно-параметрической настройки) для оценки и распределения заказов, а также способ распределения заказов по зонам и назначения логистических средств для выполнения заказов на основе модифицированного метода Г. Куна.

Способ зонального разбиения территории на основе генетической кластеризации

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

Для генетической кластеризации территориальных объектов сначала задается целевая функция оценки приспособленности особей (территориальных объектов) в популяции. Критерием для целевой функции является уменьшение времени подъезда логистических средств к заказу.

Способ зонального разбиения территории включает в себя следующие шаги.

Шаг 1. Задание целевой функции (приспособленности) для особей популяции.

Шаг 2. Создание начальной популяции (с использованием алгоритма кластеризации k-средних определяется число кластеров – территориальных зон).

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

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

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

Шаг 6. Формирование нового поколения (селекция территориальных зон с наилучшими значениями целевой функции).

Шаг 7. Если условие останова не выполняется, осуществляется возврат к шагу 3.

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

Отличительными особенностями предлагаемого способа зонального разбиения территорий являются следующие:

-     большая гибкость изменения границ зон и значений целевой функции благодаря обмену территориальными объектами между зонами;

-     уменьшение вычислительной сложности по сравнению с другими алгоритмами, например, k-средних;

-     незначительное влияние увеличения размерности задачи на сложность ее решения;

-     сочетание достоинств алгоритмов кластеризации и генетических алгоритмов [9, 10].

Результаты использования предлагаемого способа зонального разбиения территории представлены на рисунке 1.

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

Определение требуемого количества логистических средств при распределении заказов по зонам на основе скользящего временного окна

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

Сравнительная оценка среднего времени подъезда логистических средств к заказам

Comparative assessment of average time logistics facilities approach orders

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

Шаг 1. Определяется список заказов за анализируемый период времени (например, за 1 час суток).

Шаг 2. Создается «пустой» список объектов, предназначенный для хранения информации за анализируемый час для каждой территориальной зоны.

Шаг 3. Для каждого заказа из списка проверяется, в какой зоне начался заказ и в какой завершился.

Шаг 4. Для зон, в которых заказ и начался, и завершился, выбираются соответствующие территориальные объекты с информацией о них.

Шаг 5. К территориальному объекту с информацией о зоне, в которой начался заказ, добавляется информация об анализируемом заказе.

Шаг 6. Выполняется расчет максимального и суммарного времени подъезда транспортного средства к заказу, а также максимального и суммарного времени выполнения заказа.

Шаг 7. В списке заказов проверяется наличие непроанализированных заказов: если все заказы проанализированы, процедура продолжается с шага 8; если не все заказы проанализированы, выбирается следующий заказ и процедура продолжается с шага 3.

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

Шаг 1. На основе суммирования среднего времени выполнения заказов и среднего времени подъезда транспортных средств к заказам высчитывается среднее время выполнения одного заказа с момента его взятия до момента завершения.

Шаг 2. Исходя из среднего времени выполнения одного заказа задается скользящее временное окно.

Шаг 3. Сдвигая это окно с заданным шагом (например, в 1 минуту) по всему диапазону анализируемого временного периода подсчитывается количество заказов, поступивших за этот промежуток времени.

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

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

Модель и способ зонального распределения заказов и назначения логистических средств для их выполнения на основе модифицированного метода Г. Куна

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

В соответствии с модифицированным в работе методом Г. Куна при распределении заказов из всего множества возможных сочетаний пар «заказ–логистическое средство» требуется выбрать такую их совокупность, которая в наилучшей степени удовлетворяла бы заданному критерию качества логистических решений, характеризующемуся интегральной оценкой степени соответствия логистических средств и заказов.

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

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

-     стратегия максимизации доходов логистических средств, при распределении заказов в зоне учитывающая и логистические средства, которые, выполняя заказ, направляются в данную зону при условии, что данный заказ «вернет» логистическое средство в зону, из которой оно вышло; таким образом достигается относительный паритет логистических средств в зонах;

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

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

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

-     нечеткие продукционные модели первого каскада «заказ–назначение» и «средство–заказ», основанные на фиксированном и изменяемом (для задания различных стратегий распределения заказов) наборах нечетких переменных соответственно;

-     нечеткую продукционную модель второго каскада «средство–заказ–назначение», входными переменными которой являются нечеткие выходные переменные моделей первого каскада, а выходной переменной – нечеткое значение соответствия логистического средства и заказа.

Модель первого каскада «средство–заказ» предназначена для оценки целесообразности назначения логистического средства на заказ в зависимости от удаленности и стоимости заказа. Пример нечетких продукционных правил этой модели: IF Distance is Low AND Price is Low, THEN Result is Middle, где Distance – расстояние логистического средства до заказа; Price – стоимость заказа; Result – степень целесообразности назначения логистического средства на заказ; {Low, Middle, High} – терм-множества нечетких переменных модели.

Другая модель первого каскада «заказ–на­значение» предназначена для определения логистического средства, на текущий момент в наибольшей степени подходящего для выполнения заказа. Пример нечетких продукционных правил этой модели: IF DailyRate is Low AND ArrivalTime is Low AND DistanceTo­Order is Low, THEN Result is High, где Daily­Rate – степень выполнения логистическим средством дневной нормы заказов; ArrivalTime – расчетное время подъезда логистического средства к заказу; DistanceToOrder – расстояние, пройденное логистическим средством в состоянии простоя; Result – степень предпочтительности назначения логистического средства на заказ.

В отличие от модели «средство–заказ» модель «заказ–назначение» обучается отдельно для каждой из стратегий распределения заказов.

Модель второго каскада «средство–заказ–назначение» предназначена для интегральной оценки степени соответствия логистических средств и заказов. Пример нечетких продукционных правил этой модели: IF Control is Low AND Common is Low, THEN Result is Low, где Control – значение выходной нечеткой переменной модели «заказ–назначение»; Common – значение выходной нечеткой переменной модели «средство–заказ»; Result – степень соответствия логистического средства и заказа.

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

Шаг 1. Выбор стратегии распределения заказов.

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

Шаг 3. Определение соответствия логистического средства и заказа на основе разрабо- танной каскадной нечеткой продукционной модели с учетом выбранной стратегии.

Шаг 4. Составление матрицы назначений для каждой из зон и ее решение на основе модифицированного метода Г. Куна.

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

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

Оценка качества принимаемых логистических решений с использованием разработанных метода и программных средств

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

Оценка качества логистических решений проводилась по следующей методике.

Во-первых, для всех временных интервалов (с часовой периодичностью) строилось зональное разбиение территории.

Во-вторых, выбиралась стратегия распределения заказов.

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

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

В-пятых, проводилось сравнение стратегий по учитываемым характеристикам.

Оценка качества логистических решений выполнялась для стратегий

-     максимизации доходов логистических средств на основе среднего дохода этих средств в зоне;

-     минимизации пробега логистических средств без заказов на основе среднего рассто- яния, пройденного логистическими средствами в состоянии простоя для каждой зоны;

-     равномерного распределения доходов логистических средств на основе дисперсии дохода логистических средств в зоне.

При использовании стратегии максимизации доходов качество принимаемых логистических решений удалось повысить в среднем на 10,6 %, а при минимизации пробега и равномерного распределения доходов – в среднем на 8,3 % и 7,6 % соответственно.

Заключение

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

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

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

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

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

Исследование выполнено при финансовой поддержке РФФИ, проект № 18-29-03088_мк.

Литература

1.    Миркин Б.Г. Методы кластер-анализа для поддержки принятия решений: обзор. М.: Изд-во НИУ ВШЭ, 2011. 88 с.

2.    Дюран Б., Оделл П. Кластерный анализ. М., 2012. 128 с.

3.    Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: Физматлит, 2010. 368 с.

4.    Кордюков Р.Ю., Допира Р.В., Иванова А.В., Абу-Абед Ф.Н., Мартынов Д.В. Модель и алгоритмизация оптимизационной задачи о назначениях в условиях дополнительных ограничений // Программные продукты и системы. 2016. № 2. С. 16–22. DOI: 10.15827/0236-235X.114.016-022.

5.    Аверченков В.И., Казаков П.В. Эволюционное моделирование и его применение. М., 2011. 200 с.

6.    Воеводин В.В. Вычислительная математика и структура алгоритмов. М.: Изд-во МГУ, 2010. 134 с.

7.    Стивенс Р. Алгоритмы. Теория и практическое применение. М.: ЭКСМО, 2017. 544 с.

8.    Кормен Т., Лейзерсон Ч., Ривест Р., Штайн Л. Алгоритмы. Построение и анализ. М.: Вильямс, 2019. 1328 с.

9.    Рязанов А.В. Способ распределения логистических заказов на основе генетического алгоритма и нечеткого оценивания // Нейрокомпьютеры: разработка, применение. 2017. № 7. С. 32–38.

10. Рязанов А.В., Борисов В.В. Интеллектуальный способ зонального разбиения территории для поддержки логистических решений // Нейрокомпьютеры: разработка, применение. 2018. № 4. С. 11–17.

References

1. Mirkin B.G. Cluster Analysis Methods for Decision Support. Moscow, NRU HSE Publ., 2011, 88 p. (in Russ.).
2. Duran B.D., Odell P.L. Cluster Analysis. A Survey. Springer, 1974. Russ. ed.: Moscow, 2012, 128 p.
3. Gladkov L.A., Kureychik V.V., Kureychik V.M. Genetic Algorithms. Moscow, 2010, 368 p.
4. Kordyukov R.Yu., Dopira R.V., Ivanova A.V., Abu-Abed F.N., Martynov D.V. Model and algorithmization of the optimization assignment problem under additional constraints. Programmnye Produkty i Sistemy [Software and Systems]. 2016, no. 2, pp. 16–22 (in Russ.). DOI: 10.15827/0236-235X.114.016-022.
5. Averchenkov V.I., Kazakov P.V. Evolutionary Modeling and its Application. Moscow, 2011, 200 p. (in Russ.).
6. Voevodin V.V. Computational Mathematics and Structure of Algorithms. Moscow, MSU Publ., 2010, 134 p. (in Russ.).
7. Stephens R. Essential Algorithms. A Practical Approach to Computer Algorithms. Wiley, 2013. Russ. ed.: Moscow, 2017, 544 p.
8. Cormen T.H., Leiserson Ch.E., Rivest R.L., Shtein C. Introduction to Algorithms. Mit Press, 2009. Russ. ed.: Moscow, 2019, 1328 p.
9. Ryazanov A.V. The method of distribution of logistics orders based on the genetic algorithm and fuzzy estimation. Neurocomputers. 2017, no. 7, pp. 32–38 (in Russ.).
10. Ryazanov A.V., Borisov V.V. Intelligent zonal partitioning method to support logistics solutions. Neurocomputers. 2018, no. 4, pp. 11–17 (in Russ.).