РАЗРАБОТКА АЛГОРИТМА РАСЧЕТА ОПТИМАЛЬНОГО МАРШРУТА С УЧЕТОМ РАЗЛИЧНЫХ ПОКАЗАТЕЛЕЙ

Введение

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

Все мы понимаем, что большое количество платежей совершается именно в терминалах самообслуживания (далее ТСО) банков и от непрерывного их функционирования напрямую зависит прибыль банка. Так же надо понимать, что некоторые неисправности более критичны, хотя их устранение может наоборот занимать меньше времени. Например, неисправность карточного модуля или окончание чековой ленты. Без чековой ленты в терминале невозможно принимать платежи, и такую неисправность необходимо устранять как можно быстрее, к тому же это не занимает много времени. Другой пример - неисправность карточного модуля. Подобная неисправность не так критична, потому что сохраняется один из каналов приема денег (прием денег наличными). Так же стоит отметить, что денежный оборот ТСО также играет важную роль при принятии решения о приоритетности выбора ТСО. Логичнее сначала устранить неисправность на ТСО, у которого денежный оборот в день 200000 рублей, а затем поехать в тот ТСО, у которого денежный оборот составляет 20000 рублей.

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

Анализ существующих сервисов построения оптимального маршрута

1.  Сервисы построения оптимального маршрута в составе картографических поисково-информационных служб Яндекс.Карты, Карты Google, Bing Maps и др.

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

2.  Отраслевые решения типа продуктов компаний ТелеКонсалт и ООО Навигационные системы

Судить об их плюсах и минусах можно только по информации предоставляемых на их сайтах. Среди плюсов стоит отметить, что их продукты могут строить оптимальный маршрут посещения набора точек, интеграция с системами навигации GPS и ГЛОНАСС. Из минусов также остается то, что оптимальность маршрутов строится на основе расстояний, времени и затрат на горюче-смазочные материалы (далее ГСМ), ну и к тому же это платные продукты.

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

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

Разработка алгоритма

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

К примеру, имеется полносвязный граф (рис.1), где 0 – это офис, из которого выезжает специалист, а 1,2,3,4 – терминалы самообслуживания.

Рисунок 1.  Граф терминалов самообслуживания

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

Таблица №1

Пример матрицы расстояний для полносвязного графа

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

Таблица №2

Пример матрицы приоритетов устранения поломок

Для нахождения оптимального маршрута нам надо получить одну результирующую матрицу. Здесь мы сталкиваемся с другой проблемой, никакие математические действия с матрицами расстояний и приоритета мы делать не должны, потому что у нас в них хранятся разнородные данные: в матрице расстояний расстояния в км, в матрице приоритетов коэффициент приоритета. Необходимо как-то унифицировать эти данные. Для этого для каждой матрицы введем коэффициент унификации k. При назначении коэффициентов унификации экспертами решалась задача, какому количеству километров равняется одна условная единица приоритета. Поскольку расстояния между ТСО довольно большие, а также маршруты проходят преимущественно через дороги с высоким трафиком, то было принято решение, что 1 условная единица приоритета = 10 км. Исходя из этого, получаем k = 10 для матрицы расстояний, k = 1 для матрицы приоритетов, с возможностью их корректировок в процессе использования алгоритма.  Каждую матрицу мы разделим на этот коэффициент (1,2). Результат нам покажет отношения показателей внутри матрицы, и с этими матрицами уже можно будет проводить математические действия.

                                                                                 (1)

                                                                                 (2)

Где и – коэффициенты унификации, A – матрица расстояний, B – матрица приоритетов,  – элемент матрицы расстояний, – элемент матрицы приоритетов.

Далее мы складываем эти матрицы

                                                                                      (3)

                                                                                    (4)

Где  C – результирующая матрица, A и B– матрицы расстояний и приоритетов,  – элемент результирующей матрицы,  – элемент матрицы расстояний, – элемент матрицы приоритетов

Таблица №5

Результирующая матрица

Используя данные результирующей матрицы можно построить оптимальный маршрут. Блок-схема алгоритма создания результирующей матрицы изображена на рис.2.

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

Рисунок 2 – Блок-схема алгоритма расчета оптимального маршрута с учетом нескольких показателей оптимальности

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

Заключение

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

Список литературы:

1. Беллман Р. Введение в теорию матриц. Наука, 1969. - 368 с.
2. Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985. - 352 с.
3. Лукинский В.С Модели и методы теории логистики. - 2-е изд. Питер, 2008. - 448 с.
4. Мельников О.И. Теория графов в занимательных задачах. Либроком, 2009. - 233 с.
5. Миротин Л. Б., Покровский А. К. Основы логистики. Академия, 2013. - 192 с.