Савкин Владислав Юрьевич

Факультет компьютерных наук и технологий (ФКНТ)

Кафедра автоматизированных систем управления (АСУ)

Специальность Информационные системы и технологии в технике и бизнесе

Информационная система формирования маршрутов доставки лекарственных средств в пределах аптечной сети

Научный руководитель: к.т.н., доц. Светличная Виктория Антоновна

Резюме Биография Реферат Библиотека Ссылки Отчёт о поиске Индивидуальный раздел

Реферат по теме выпускной работы

Содержание

• Введение
• 1. Актуальность темы
• 2. Цель и задачи исследования
• 3. Обзор существующих систем
• 4. Аналитическая постановка задачи
• 4.1 Критерии оптимизации маршрута
• 4.2 Ограничения, влияющие на построение маршрута
• 4.3 Математический аппарат
• 5. Обзор методов, моделей, алгоритмов
• 5.1 Точные алгоритмы
• 5.2 Эвристические алгоритмы
• 5.3 Поисковые алгоритмы
• Выводы
• Список источников

Введение

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

1. Учёт товаров на складе.
2. Учёт и обработка заявок на поставку товара.
3. Расчёт загрузки транспортных средств.
4. Задача кластеризации.
5. Задача коммивояжёра.
6. Задача о рюкзаке [1].

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

1. Актуальность темы

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

Учитывая такие факторы, как различная грузоподъёмность транспортных средств, наличие специальных приспособлений для погрузки/выгрузки, занятость автомобиля, наличие прицепа, условия подъезда к пунктам разгрузки, ежедневно меняющийся спрос, необходимость максимального использования собственных автомобилей, вполне целесообразно использовать автоматизацию построения маршрутных листов, а именно – автоматизированную систему формирования маршрутов доставки определённого вида товаров [2]. Кроме того, автоматизация построения маршрутов является важным аспектом для любого предприятия с экономической точки зрения. Внедрение такой системы минимизирует влияние человеческого фактора, ускоряет процесс работы логистического отдела, ведёт к сокращению простоя автомобилей под загрузкой и разгрузкой товара. Соответственно, ускорение процесса грузоперевозок ведёт к минимизации затрат, а соответственно – к увеличению прибыли.

2. Цель и задачи исследования

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

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

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

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

• учёт прихода/расхода лекарственных средств;
• формирование и обработка заявок на доставку лекарственных средств;
• разработка модели поставок лекарственных средств в пункты розничной торговли;
• учёт составленных маршрутов, формирование маршрутных листов [1].

3. Обзор существующих систем

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

1. Муравьиная логистика. Онлайн сервис для расчета оптимальных маршрутов доставки. Сервис предоставляется для бесплатного использования на пробный период, после чего требует покупки лицензии для использования, при этом количество точек в маршруте может быть ограничено в зависимости от типа лицензии, а количество маршрутов в день ограничено независимо от типа лицензии [3].
2. ABM Rinkai TMS. Специализируется на построении оптимальных маршрутов доставки товара. Система ABM Rinkai TMS является платной и не предоставляет демо-версии для ознакомления. Формирование маршрутов в ABM Rinkai TMS предусматривает 3 разных метода оптимизации, в каждом из которых заложена своя логика процесса построения маршрутов. Учитывает все ключевые параметры, необходимые для построения оптимальных маршрутов [4].
3. Zig-Zag. Сервис управления транспортной логистикой для компаний, чей бизнес связан с доставкой грузов. Сервис позволяет создавать оптимальные маршруты и эффективно планировать загрузку водителей и курьеров. Сервис является бесплатным только для некоммерческого использования. Содержит в себе такие особенности, как работа в команде, оперативные изменения и анализ исполнения. Кроме того, присутствует мобильная версия [5].
4. Maxoptra. Веб-ориентированная система управления логистикой. Автоматически распределяет работу между исполнителями и планирует оптимальные маршруты для доставки точно в срок и с минимальными затратами. С её помощью пользователь имеет возможность контролировать и при необходимости корректировать движение сотрудников в режиме реального времени. Maxoptra предоставляет пробный период для использования, поле чего требует покупки лицензии [6].

4. Аналитическая постановка задачи

Задача коммивояжёра представляет собой задачу поиска кратчайшего Гамильтонова пути в полном конечном графе с N вершинами. Коммивояжёр, выходящий из какого-нибудь пункта, желает посетить N-1 других пунктов и вернуться к исходному пункту. Известны расстояния между всеми этими пунктами. Требуется установить, в каком порядке он должен посещать города, чтобы общее пройденное расстояние было минимальным [7].

Для решения поставленной задачи необходимым является дополнительное условие сбалансированности маршрутов, в частности, по числу пунктов, входящих в маршруты. Такая задача, называемая обобщённой задачей коммивояжёра, принадлежит к классу NP-трудных задач. Для k коммивояжёров на множестве из n+1 пунктов строится k замкнутых маршрутов по следующим правилам:

• один из пунктов, называемый базой, входит во все маршруты;
• каждый из пунктов (исключая базу) входит ровно в один из маршрутов;
• суммарная длина всех маршрутов минимальна.

4.1 Критерии оптимизации маршрута

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

• наименее затратный маршрут с точки зрения времени и расстояния;
• наименее затратный маршрут с точки зрения финансовой составляющей;
• наименее затратный маршрут с точки зрения времени, расстояния, и финансовой составляющей, т.е. совокупный критерий.

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

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

4.2 Ограничения, влияющие на построение маршрута

На формирование оптимального маршрута может влиять ряд дополнительных факторов, которые принято называть ограничениями. Для задачи коммивояжёра ограничениями являются:

• карта города с отметками о местонахождении потребителей (аптек) и поставщиков (склад);
• количество автомобилей, выполняющих транспортировку лекарственных средств, равное количеству кластеров (геозон);
• список заявок на доставку медикаментов, сформированных по каждому пункту доставки.

4.3 Математический аппарат

Задачу коммивояжёра можно описать следующим способом. Имеется n пунктов, стоимость между которыми задана матрицей C. Коммивояжёр должен побывать в каждом пункте один раз и вернуться в исходный пункт маршрута, затратив при этом минимум средств [8]. Математически это может быть представлено следующей формулой, которая также представляет собой целевую функцию:

где n – количество пунктов на карте;

c_ij – матрица стоимости между пунктами;

x_ij – матрица переходов с компонентами:

    x_ij = 1, если маршрут включает переезд из точки i непосредственно в точку j;

    x_ij = 0, в противном случае.

Постановку задачи можно сформулировать следующим образом: найти минимум функции Z при выполнении ограничений и неотрицательности значений матрицы X [9]. Систему ограничений можно представить следующим образом:

где n – количество пунктов на карте;

x_ij – матрица переходов с компонентами:

u_i, u_j – произвольные целые неотрицательные числа.

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

• ограничение №1 выражает условие, что коммивояжёр выезжает из каждого пункта один раз;
• ограничение №2 выражает условие, что коммивояжёр въезжает один раз в каждый пункт;
• ограничение №3 выражает условие, что маршрут не будет содержать в себе замкнутые маршруты (условие незамкнутости), кроме одного, включающего все пункты, а также то, что маршрут не должен содержать петель.

Для реализации вышеприведённых равенств достаточно ввести штрафные функции, положив:

где k = p;

c_ijmax – максимальное значение для всех c_ij.

5. Обзор методов, моделей, алгоритмов

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

5.1 Точные алгоритмы

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

• метод последовательной сепарации [8];
• алгоритм полного перебора [10];
• метод ветвей и границ [11].

Алгоритм полного перебора осуществляет поиск в пространстве N! решений посредством перебора всех вариантов. Результатом работы алгоритма является точное решение. Недостатком алгоритма является его временная сложность – пространство поиска растёт экспоненциально, поэтому, когда N не является значительно малым, используют эвристические и поисковые алгоритмы. Временная сложность алгоритма полного перебора показана на рис. 1 с логарифмической шкалой.

Экспериментально сложность данного алгоритма была оценена как t = 0,0056 × e^{(1,3789 × N)}.

К преимуществам данного алгоритма можно отнести возможность распараллеливания и точное решение задачи.

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

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

Экспериментально сложность данного алгоритма была оценена как t = 0,0745 × e^{(0,8485 × N)}. В случае использования в качестве минимального начального решения используется решение, полученное жадным методом. Сложность алгоритма составит t = 0,3164 × e^{(0,7469 × N)}. К преимуществам данного алгоритма можно отнести возможность распараллеливания и точное решение задачи. Временная сложность метода ветвей и границ и его развитие показаны на рис. 1 с логарифмической шкалой [10].

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

Алгоритм решения можно описать следующим образом. Решается задача о назначениях. Полученное решение:

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

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

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

Поэтому следует сделать запреты на переход в вариантах:

• от точки конца цепи σ к точке s;
• от точки p к точке начала цепи α;
• от точки p к точке s [8].

5.2 Эвристические алгоритмы

Эвристические алгоритмы эффективны как при решении обобщённой задачи коммивояжёра, так и при решении простой задачи коммивояжёра. К ним можно отнести довольно большое количество методов:

• нейронные сети [7];
• BV-метод [10];
• метод включения дальнего [10];
• метод имитации отжига [12];
• метод ближайшего соседа;
• алгоритм разрезания общего маршрута;
• алгоритм разделения по углу;
• метод дихотомического разделения на группы;

Более подробно будут рассмотрены два метода: BV-метод и метод включения дальнего.

Идея метода включения дальнего заключается в следующем: пункты, максимально удаленные друг от друга, никогда не будут смежными в цепи. Эти два пункта и будут базовыми для дальнейшего решения. Затем опять находится вершина, максимально удаленная от вершин, уже заключенных в цепь. Находится минимальная сумма длин рёбер между найденной вершиной и парой смежных вершин в цепи, что задает место в цепи найденной вершине [10].

Данный алгоритм имеет линейную сложность, даёт приблизительное решение задачи и не может быть распараллелен. Его временная сложность была оценена как t = 28,0600 + (–1,6069 × N) + (0,0227 × N²)

BV-метод основан на анализе имеющегося эталонного маршрута и его оптимизации. Алгоритм условно состоит из трёх этапов:

1. получение начального эталонного решения;
2. построение BV матрицы;
3. оптимизация текущего решения.

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

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

Второй этап алгоритма – построение BV-матрицы. Для этого строится матрица оценок размером NхN, первоначально заполненная нулями. Далее просматривая N построенных жадных маршрутов, для каждой пары соседних пунктов p и q, соответствующий элемент матрицы оценок a [p, q] увеличивается на единицу.

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

BV-модификаторы могут быть следующих видов:

• модификатор Сглаживания;
• модификатор Перенос;
• модификатор Инверсный переход;
• модификатор Инверсный перенос [10].

Данный алгоритм имеет квадратичную сложность, даёт приблизительное решение и может быть распараллелен на 2-м этапе. Его временная сложность была оценена как t = –169,40 + (15,5786 × N) + (–0,4104 × N²) + (0,0040 × N³).

5.3 Поисковые алгоритмы

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

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

• кодирование параметров – генетические алгоритмы обрабатывают не значения параметров самой задачи, а их закодированную форму;
• операции на популяции – генетические алгоритмы осуществляют поиск решения исходя не из единственной точки (начальное приближение), а из некоторой популяции;
• использование минимума информации о функции – генетические алгоритмы используют только целевую функцию, а не производные либо иную дополнительную информацию;
• рандомизация операций – генетические алгоритмы применяют вероятностные, а не детерминированные правила выбора [12].

Генетические алгоритмы являются наиболее оптимальными среди поисковых в плане соотношения время/качество и могут быть распараллелены. Экспериментально временная сложность генетического алгоритма была оценена как t = 683 + (–42,467 × N) + (1,0696 × N²).

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

Если промоделировать процесс такого поведения на некотором графе, рёбра которого представляют собой возможные пути перемещения муравьёв в течение определённого времени, то наиболее обогащённый феромоном путь по рёбрам этого графа и будет являться решением задачи, полученным с помощью муравьиного алгоритма [13].

Муравьиные алгоритмы хорошо поддаются распараллеливанию. Их временная сложность была оценена как t = 4437,6 + (–293 × N) + (4,6779 × N²).

Выводы

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

С учётом проведённого исследования [13, 14, 15], можно сделать вывод, что для решения задачи коммивояжёра наиболее целесообразно использовать муравьиные алгоритмы, которые были разработаны специально для решения данной задачи и являются наиболее эффективными в этой области. Однако, помимо самого алгоритма, нельзя забывать о критерии оптимизации, который указывает, в каком направлении должен работать алгоритм. Это важно с той точки зрения, что один и тот же алгоритм может давать разные результаты для разных критериев оптимизации при решении одной и той же задачи. Кроме того, стоит брать во внимание ограничения, которые будут влиять на работу алгоритма и конечный результат. Эти ограничения могут быть представлены в качестве входных данных [1].

Примечания

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

Список источников

1. Савкин В.Ю. Анализ методов решения задачи коммивояжёра / В.Ю. Савкин, В.А. Светличная, Радзывыло К.Г. // Материалы IX Международной научно-технической конференции. – Донецк: ДонНТУ, 2018. – с.6–10.
2. Семенов Ю.Н. Автоматизация построения маршрутов перевозок крупнопартионных грузов / Ю.Н. Семенов, О.С. Семенова // Вестник Кузбасского государственного технического университета. – Кемерово: КузГТУ, 2015. – с.131–134.
3. Автоматизация транспортной логистики – онлайн сервис для планирования оптимальных маршрутов доставки [Электронный ресурс] – Режим доступа: [Ссылка]
4. Управление транспортом, транспортная логистика, TMS система – ABM Rinkai [Электронный ресурс] – Режим доступа: [Ссылка]
5. Zig-Zag: Оптимизация транспортной логистики [Электронный ресурс] – Режим доступа: [Ссылка]
6. Maxoptra: Система управления логистикой, программа для логистики транспорта, система логистики предприятия [Электронный ресурс] – Режим доступа: [Ссылка]
7. Товстик, Т.М. Алгоритм приближённого решения задачи коммивояжёра / Т.М. Товстик, Е.В. Жукова // Вестник СПбГУ. – 2013. – №1. – с. 101-109.
8. Петрунин, С.В. Использование метода последовательной сепарации (ПС) для решения задачи коммивояжёра // Научный вестник МГТУ ГА. – 2009. – №143. – с. 87-90.
9. Задача коммивояжёра. [Электронный ресурс] – Режим доступа: [Ссылка]
10. Борознов, В.О. Исследование решения задачи коммивояжёра // Вестник АГТУ. Сер: Управление, вычислительная техника и информатика. – 2009. – №2. – с.147-151.
11. Костюк, Ю.Л. Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ // Прикладная дискретная математика: Научный журнал – Томск : Национальный исследовательский Томский государственный университет – 2013 – №2. – с.78-90.
12. Гараба, И.В. Сравнительный анализ методов решения задачи коммивояжёра для выбора маршрута прокладки кабеля кольцевой сети кольцевой архитектуры // Молодёжный научно-технический вестник. – 2013. – №1. – с.173-188.
13. Мурзин, Б.П. Использование алгоритма муравьиной колонии для определения оптимального маршрута доставки грузов / Б.П. Мурзин, В.А. Светличная // Інформаційні управляючі системи та комп'ютерний моніторинг (ІУС КМ-2011) / Збірка матеріалів IІ всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених – 11-13 квітня 2011 р., Донецьк, ДонНТУ – 2011, с. 183-186.
14. Курейчик, В.М. О некоторых модификациях муравьиного алгоритма / В.М. Курейчик, А.А. Кажаров // Известия ЮФУ. Технические науки. – 2009. – №1. – с.7-12.
15. Семенкина, О.Е. Effectiveness Comparison of Ant Colony and Genetic algorithms for solving combinatorial optimization problems // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. – 2012. – №1. – с.96-97.