Размещено на http://www.Allbest.ru/

Размещено на http://www.Allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования

Российский экономический университет имени Г.В. Плеханова

Факультет математической экономики, статистики и информатики

Кафедра управления информационными системами и программирования

Направление 02.03.03 «Математическое обеспечение и администрирование информационных систем»

Профиль «Системное программирование»

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Тема

Разработка программного комплекса построения оптимального маршрута обхода пациентов

Выполнил Тишкин Дмитрий

студент группы ДКО-131б

Научный руководитель

ст. преп. Иванов Е.А.

Москва - 2017



СОДЕРЖАНИЕ

• ВВЕДЕНИЕ
• Глава 1. Задача разработки программного комплекса построения оптимального маршрута обхода пациентов
• 1.1 Обзор алгоритмов построения оптимального маршрута
• 1.2 Обзор программных продуктов для решения задачи построения оптимального маршрута
• 1.3 Постановка задачи на разработку программного комплекса построения оптимального маршрута обхода пациентов
• 1.4 Математическая модель муравьиного алгоритма с модификацией муравьиной колонии
• Выводы по первой главе
• Глава 2. Разработка программного комплекса построения оптимального маршрута обхода пациентов
• 2.1 Выбор аппаратных и программных средств для разработки программного комплекса
• 2.2 Реализация муравьиного алгоритма
• 2.3 Состав и структура программного комплекса
• 2.4 Тестирование и отладка программного комплекса
• 2.5 Инструкция пользователю
• Выводы по второй главе
• Глава 3. Оценка технико-экономических показателей разработанного программного комплекса построения оптимального маршрута обхода пациентов
• 3.1 Испытания программного комплекса
• 3.2 Оценка качественных показателей разработанного программного комплекса
• 3.3 Оценка экономической эффективности
• Выводы по третьей главе
• ЗАКЛЮЧЕНИЕ
• СПИСОК ЛИТЕРАТУРЫ
• ПРИЛОЖЕНИЕ


ВВЕДЕНИЕ

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

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

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

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

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

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



Глава 1. Задача разработки программного комплекса построения оптимального маршрута обхода пациентов

1.1 Обзор алгоритмов построения оптимального маршрута

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

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

К точным алгоритмам относятся метод ветвей и границ и алгоритм полного перебора. Решение, полученное с помощью приведенных алгоритмов, имеет 100%-ю точность, однако это компенсируется большими вычислительными и временными затратами. Например, сложность алгоритма полного перебора с ростом вершин (пунктов) напрямую зависит от всех возможных решений задачи. Другими словами для пунктов необходимо рассмотреть вариантов маршрута. Откуда, при очень большом алгоритм может дать результат спустя несколько часов работы. Метод ветвей и границ отчасти решает эту проблему, если расстояния между пунктами различаются, в противном случае, при небольшом разбросе данных нахождение оптимального пути происходить очень медленно. Метод основывается на частичном переборе возможных решений с исключением подмножеств, которые не содержат оптимальных решений. Метод опирается на следующие построения:

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

· постепенное разбиение множества на подмножества (ветвления);

· пересчет оценок при постепенном разбиении множеств;

· нахождение конкретных вариантов решения;

· проверка вариантов на оптимальность;

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

Рисунок 1.1 График сравнения методов

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

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

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

· Задается число итераций (температура) и случайное начальное решение;

· Случайным образом меняются местами две точки;

· Сравниваются длины старого и нового путей. Во время сравнения учитывается разница нового пути и текущего с учетом количества итераций. Чем меньше число итераций, тем больше вероятность принять текущий путь для сравнения его с последующим на новой итерации;

· Пройдя все итерации, последний найденный путь считается наилучшим;

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

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

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

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

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

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

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

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

Муравьиный алгоритм имеет несколько вариантов модификации, которые увеличивают шанс нахождения оптимального маршрута быстрее или позволяют найти куда более короткие маршруты за N повторений. Среди таких алгоритмов: Элитарная муравьиная система, Система муравьиной колонии (ACS), Max-Min муравьиная система (MMAS), Выпрямление.

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

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

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

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

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

Рисунок 1.2 Сравнение сходимости MMAS с ACS

Сначала на оптимизированном маршруте случайно выбирается участок небольшой длины, затем к этому участку применяется метод ветвей и границ. В результате, возникает эффект выпрямления на отобранном участке. Применение данного алгоритма можно наглядно увидеть на рисунке 1.3, где граф под буквой «А» до выпрямления, «Б» после. Жирным цветом выделен участок, выбранный для выпрямления.

Рисунок 1.3 Результат применения модификации выпрямления

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

Начальное расположение колонии. Существуют несколько вариантов расположения муравьиной колонии:

· Расположение всей колонии в одной точке

· Случайное расположение всей колонии в одной точке на каждой итерации

· Равномерное распределение колонии по точкам

· Случайное распределение колонии по точкам (где-то больше, где-то меньше)

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

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

Таблица 1.1

Сравнение муравьиного и генетического алгоритмов

Число заказчиков	Муравьиный алгоритм	Генетический алгоритм
	Длина маршрута для лучшего решения	Время решения, мин	Длина маршрута для лучшего решения	Время решения, мин
200	6460,98	7,13	6460,98	1,04
255	586,87	139,27	596,89	14,32
300	1007,07	32,55	1018,74	39,33
399	927,27	158,93	933,74	78,5
420	1834,79	239,47	1946,55	210,42

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

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

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

· Оптимизация маршрутов патрульной службы

· Оптимизация маршрута службы доставки

· Планирование строительства нефтегазовой магистрали

· Построение маршрутизации в сетях

· Обслуживание объектов военного назначения

Решение данных задач позволяет ускорить выполнение поставленных целей организации и приносит экономию в финансовом секторе. Таким образом, например, компьютерная сеть Национального фонда науки США внедрила муравьиные алгоритмы для построения оптимальной маршрутизации в телекоммуникационных сетях в 1994 году, что увеличило пропускную способность с 300Кбит/с до 44,736 Мбит/с и увеличило суммарный объем пакетов данных с 1 трлн. до 10 трлн. байт. Сеть выдерживала 4000 организаций и около 50000 сетей.

Среди известных программных средств на рынке, решающих задачу поиска оптимального маршрута, на сегодняшний день можно выделить: веб приложение построение оптимального маршрута Poncy-ru, программный комплекс «Логистика развоза» компании ООО «Программы для бизнеса», ОПТИМУС ГИС и ABM Rinkai TMS. Рассмотрим каждое программное средство более подробно.

Логистика развоза. Программный комплекс «Логистика развоза» компании - ООО «Программы для бизнеса» также использует методы для решения транспортной задачи [21]. А именно, распределяет заказы таким образом, чтобы максимально загрузить весь текущий транспорт и построить для каждой машины оптимальный маршрут проезда с учетом дорожной ситуации. Данный программный комплекс позволяет рассчитать доставку с учетом нескольких дней, расписания транспортных средств и их привязки к зонам погрузки и разгрузки. В программе есть возможность диспетчеризации водителей с использованием мобильных устройств на базе оперативной системы Android. Программный комплекс является конфигурацией для 1С и интегрирован с программой GWX и электронными картами «Ингит». В области логистики можно выделить преимущества рассматриваемой программы:

· Быстрый поиск оптимального маршрута

· Контроль отклонения фактического маршрута водителя от оптимального

· Возможность изменения построенного маршрута в случае изменившейся дорожной ситуации

По заявлениям компании программа позволяет снизить затраты на перевозку до 30%.

Оптимум ГИС. Оптимум ГИС - система GPS-мониторинга транспорта, оптимизация транспортной логистики и планирования маршрута выездного персонала [22]. Решение системы снижает расходы компании за счет уменьшения транспортных издержек, которые позволяют сократить общий километраж в среднем на 15-20% и количество используемого автотранспорта. Система так же включает в себя модули «Мониторинг и «Доставка», которые предназначены для автоматизации процессов транспортной логистики и наблюдения за перемещением авто.

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

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

На карте (рисунок 1.4) можно увидеть пример рассчитанный системой ОПТИМУМ ГИС, где красным цветом отмечен оптимальный маршрут, синим - маршрут пройденный водителем. На основании чего можно сделать вывод, что транспортное средство использовалось в личных целях, и представленный рейс потерпел издержки.

Рисунок 1.4 Карта оптимального и фактического маршрутов

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

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

Рисунок 1.5 Статистика доставок

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

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

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



1.3 Постановка задачи на разработку программного комплекса построения оптимального маршрута обхода пациентов

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

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

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

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



1.4 Математическая модель муравьиного алгоритма с модификацией муравьиной колонии

Пусть k-ый агент находится на i-ом пункте, а его список посещенных пунктов - еще не до конца заполненный массив . Тогда переход в пункт осуществляется при условии, что , где - случайное число, - порог псевдослучайного пропорционального выбора. Иначе вероятность перехода в пункт определяется следующей формулой (1.1):

(1.1)

где и - параметры управления относительной важности между феромонной информацией и эвристической информацией

Если k-й агент посетил все пункты, то он возвращается в стартовый, по пройденному пути

При возвращении в стартовый пункт агент оставляет на каждом пути феромоны. Концентрат феромона на ребре пересчитывается по формуле (1.2):

(1.2)

где - коэффициент испарения феромона, - количество феромона оставляемое на ребре k-ым агентом:

(1.3)

- длина пути k-го агента, Q - регулируемый параметр.

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

Помимо обновления феромонов после каждой итерации, применяется дополнительное обновление, которое выполняется после прохода по ребру по формуле (1.4):

(1.4)

где - параметр ослабления феромона, а - начальное значение феромона

Пример

Для примера использования приведенной математической модели, рассмотрим решение задачи поиска оптимального маршрута на графе (рисунок 1.6):

Рисунок 1.6 Граф для примера задачи

В таблице 1.2 представлены время пути для каждого ребра и концентрация феромонов на них:

Таблица 1.2

Входные данные

Ребро	1-2	1-3	1-4	2-3	2-4	3-4
Время пути (мин) d	10	21	25	13	22	11
Концентрация феромонов	3	1	2	3	2	3



Пусть заданы параметры: , и пусть агент стартует с вершины 1. Кидая жребий на интервале пусть выпало число 0,1. Тогда вершиной для дальнейшего перехода могут быть 2, 3 или 4. Рассчитаем вероятности для каждой из возможных вершин по формуле (1.1):

Можно проверить, что сумма всех найденных вероятностей равна 1, следовательно, расчеты верны. Составим интервал полученных вероятностей:

Затем кинув жребий от 0 до 1, пусть выпало число 0,87, тогда переход агента произойдет по ребру 1-4 в вершину 4. Рассчитаем локальное обновление феромонов на пройденном ребре:

Пусть снова кидая жребий для перехода в ребро с максимальным уровнем феромона, выпадает q больше . Тогда из вершины 4 можно перейти в вершину 2 и 3. В вершину 1 переход невозможен, так как она попала в список посещенных вершин - . Найдем вероятности и :



на интервале от 0 до 1: . Пусть жребий показал число 0.3, тогда переход произойдет в вершину 3, по ребру :. Рассчитаем локальное обновление феромонов на ребре :

Среди оставшихся не посещённых вершин остается одна - вершина 2. Логично, что вероятность перехода в данную вершину равна 100% . Локальное обновление ребра :

Следовательно, найденный путь 1,4,3,2, время прохождения которого, составляет 49 минут. Возвращаясь в стартовую вершину, рассчитаем глобальное обновление феромонов на пройденных ребрах:

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

Выводы по первой главе

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



Глава 2. Разработка программного комплекса построения оптимального маршрута обхода пациентов

2.1 Выбор аппаратных и программных средств для разработки программного комплекса

Исходя из поставленной задачи разработки веб-комплекса, его внедрение подразумевает использование веб-сервера. Веб-сервером выступает программное средство позволяющее принимать запросы и отправлять ответы по HTTP протоколу. Это программное средство, в свою очередь, располагается на сервере. На сегодняшний день, любые медицинские учреждения (поликлиники, больницы) уже имеют в своем распоряжении сервера для хранения баз данных сотрудников, привязанных к учреждению клиентов и различной бухгалтерской информации. Размещение веб-сервера, а точнее программного средства, как правило, не мешает работе других программных продуктов, если соблюдаются рекомендуемые системные требования. Для полноценной работы веб-комплекса рекомендуется 2Гб оперативной памяти, 5-20Гб свободного дискового пространства (зависит от количества сотрудников и клиентов), и процессор 3,2ГГц.

Среди существующих веб-серверов преимущественным выбором является Node, так как данная программная платформа выполняет задачу веб сервера и одновременно представляет среду для выполнения кода на JavaScript основанной на движке Chrome V8. Еще одним преимуществом Node в отличие от остальных средств, таких как, например PHP или .NET это событийно-ориентированный подход к программированию, который позволяет осуществить неблокирующий ввод/вывод. Другими словами, во время ожидания выполнения какой-либо операции сервер не блокируется и позволяет работать с другими запросами, тем самым увеличивая возможность одновременных подключений и скорость ответов на запросы пользователей. Тогда как синхронный подход подразумевает обработку запросов последовательно, то есть, выполнение следующего запроса начнется после выполнения предыдущего. Это оказывает неэффективное распределение вычислительных ресурсов и большую часть времени сервер попросту простаивает. Основной недостаток Node заключается в сложности проектирования серверной части программного средства. Необходимо позаботиться об очистке памяти после обработки каждого запроса, в противном случае произойдет утечка и потребуется перезагрузка сервера.

На текущий момент программная платформа Node активно развивается, для нее разработана масса библиотек и фреймворков, которые позволяют не только избавиться от недостатков, но и предоставляют дополнительные возможности в разработке. Node поддерживает язык программирования - CoffeeScript. Данный язык представляет собой обертку языка JavaScript (JS). CoffeeScript имеет упрощенный синтаксис, что улучшает читаемость кода, уменьшает его размеры и заменяет сложные в реализации задачи на чистом JS на простые. Поэтому использование этого языка отлично подойдет для реализации серверной части приложения.

В состав Node входит установщик пакетов NPM. Пакет в Node это набор JavaScript файлов, которые организуют различные инструменты для разработки программного средства. Одним из таких инструментов является фреймворк Express. Его использование дает такие возможности как удобство работы с запросами, структурированная маршрутизация, ориентированность на высокую производительность и диспетчер задач, который способен перезапустить веб-сервер в случае его отказа [7].

Фреймворк Express в своей архитектуре использует шаблон Модель-Вид-Контроллер (MVC). Подход MVC подразумевает разделение структуры программного средства на три компонента: модель данных, управляющая логика и пользовательский интерфейс. Модель данных это сами данные и правила для работы над ними. Контроллер занимается обработкой HTTP запросов и работает с соответствующей моделью. Представление обеспечивает отображение данных полученных из модели. Однако формирование представления на серверной части веб приложения, сказывается отрицательным образом на его производительности и отзывчивости интерфейса. Поэтому роль интерфейса (Frontend) возьмет на себя технология «Приложение одной страницы» (SPA). Архитектура SPA заключается в работе веб приложения на одной странице. При заходе на сайт происходит загрузка всего интерфейса, всех разделов и модулей в виде JavaScript и CSS файлов. Тем самым результаты запросов исключают генерацию и передачу с сервера целых HTML документов, а все последующие запросы выполняются с использованием веб-службы REST, которая доставляет данные в формате JSON. Еще одним преимуществом использование SPA это возможность кеширование JavaScript файлов в большинстве браузеров, за счет чего при повторной загрузке веб-приложения браузер загружает только новые файлы и использует уже загруженные, что ускоряет загрузку страницы и уменьшает нагрузку на сервер.

Существует множество JavaScript фреймворков для реализации пользовательского SPA интерфейса, среди которых наиболее популярны: React, Angular и Backbone. Последние два используют MVC архитектуру, тогда как React отвечает только за визуализацию и применяет компонентную концепцию в разработке. Суть этой концепции заключается в разделении интерфейса на самодостаточные компоненты (модальные окна, кнопки, поля и другие). Такие компоненты можно делать шаблонными, тем самым уменьшая дублирование программного кода. С помощью встроенной в React библиотеки Virtual DOM можно добиться высокой производительности приложения. React вместо воздействия на DOM напрямую, работает с ее виртуальной копией. Работа с DOM происходит в три этапа:

1. Внесение определенных изменений в виртуальную копию DOM

2. Сравнение виртуального DOM-дерева с настоящим и определение разницы

3. В случае выявления разницы, происходит перерисовка измененных компонентов

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

У компонентного подхода в React есть существенный недостаток. Передача данных происходит от компонента родителя к потомку. При этом если два компонента не связаны отношением родитель-потомок, и разработчик пытается установить взаимодействие между ними, это приводит к ошибкам и считается антипаттерном. Решением этой проблемы является архитектура Flux. К React представлению добавляются еще две дополнительные части: диспетчер (dispatch) и хранилище данных (store). Диспетчер в этой архитектуре выступает как ядро, которое управляет потоками данных, а хранилище содержит состояние приложения и его логику (функции, методы). Механизм работы Flux представлен на рисунке 2.1

Рисунок 2.1 Схема работы Flux

Глобальное хранилище регистрирует в диспетчере функции для изменения состояния и когда диспетчер получает событие действия, он вызывает метод внутри хранилища. После того как хранилище изменится, генерируется событие, которое сообщает подписанным на него представлениям что произошло обновление, а они в свою очередь перерисовывают компонент. Данный подход реализует библиотека Redux, которая помогает организовать хранилище и предоставляет инструменты для работы с ним. Данная библиотека разрабатывалась специально для React, не смотря на то, что ее можно использовать и в других фреймворках. С Redux все компоненты могут хранить свое состояние в глобальном хранилище. А действия, которые вызывают компоненты, так же отправляются в хранилище. Таким образом, компонент только инициирует изменение и не задумывается о компонентах, которые должны получить его. Разница взаимодействия компонентов на чистом React и на React c Redux хорошо отражена на рисунке 2.2.

Рисунок 2.2 Разница c использованием Redux

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

Еще одна важная часть полноценного веб-комплекса это база данных (БД). Так как планируется использовать Node для серверной части приложения, то MongoDB будет отличным выбором в роли СУБД. Это обусловлено тем, что в Node есть инструменты направленные особенным образом именно на взаимодействие с этой СУБД. MongoDB это документно-ориентированная система управления базами данных, которая отличается от привычных реляционных БД. Хранение данных осуществляется в бинарном формате JSON (BSON) что ускоряет работу с данными, быстрее выполняются обработка и поиск. Инструменты Node позволяют с легкостью десериализовать данные БД из BSON формата в привычный для JavaScript формат JSON. Помимо этого MongoDB не требует синхронизации схемы БД, и имеет динамические базы и коллекции. Поэтому в приложении нет необходимости знать структуру базы, что дает возможность ее легкой масштабируемости.

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

3 MongoDB как СУБД программного средства

4 Серверная часть приложения на базе Node на языке CoffeScript c фреймворком Express в роле архитектуры REST

5 Интерфейс приложения - React Redux

2.2 Реализация муравьиного алгоритма

В качестве входных данных алгоритма используется объект, в который входят двумерный массив (матрица) расстояний, полученный с помощью веб-службы Google Maps Distance Matrix API и адреса проживания пациентов, чтобы в дальнейшем можно было сопоставить полученный результат. Каждый элемент матрицы включает расстояние и время (так как в постановке задачи необходимо учитывать рабочее время врача, то в качестве стоимости перехода из одной точки в другую будет выступать время в минутах). Далее в полученной матрице начальные значения феромонов инициализируются единицами для каждого ребра. Затем матрица передается в конструктор при создании экземпляра класса AntAlgorithm, структура которого представлена на рисунке 2.3

Рисунок 2.3 Класс AntAlgorithm

Свойства класса представляют следующие параметры алгоритма:

· alfa и beta - параметры влияющие на жадность алгоритма

· p - коэффициент испарения феромонов

· q - параметр, имеющий значения порядка цены оптимального решения

· t - начальное значение феромонов на ребрах

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

Метод pijkt реализует формулу (1.1) муравьиного алгоритма. Программная реализация данного метода представлена на рисунке 2.4:

Рисунок 2.4 Реализация формулы (1.1)

Метод вычисляет вероятность перехода в конкретную точку, принимая на вход три аргумента: количество феромонов на ребре, время перехода по ребру и возможные вершины для перехода. Затем возвращает значение вероятности от 0 до 1. Единственное отличие от формулы заключается в том, что на вход методу уже приходят отсеянные вершины, то есть исключаются вершины, в которых побывал текущий муравей.

Метод randomizer принимает массив вероятностей с идентификаторами вершин. На основании полученного массива строит отрезки на интервале, соответствующие вероятностям. И затем возвращает идентификатор той вершины, на отрезок которой выпало случайное число.

Метод локального обновления, реализующий формулу (1.2) устроен следующим образом: на вход методу поступает объект ребра, затем из него по свойству feromon происходит расчет нового количества феромонов с помощью формулы (1.2). Программный код этого метода представлен на рисунке 2.5

Рисунок 2.5 Метод локального обновления

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

Рисунок 2.6 Метод глобального обновления

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

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

Рисунок 2.7 Блок-схема алгоритма

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

1. ул. Богданова, 48к1, Москва, Россия, 119620 (Стартовый адрес)

2. ул. Богданова, 10, Москва, Россия, 119618

3. ул. Главмосстроя, 7, Москва, Россия, 119618

4. Солнцевский пр., 13, Москва, Россия, 119620

5. Солнцевский пр., 34, Москва, Россия, 119620

6. ул. Щорса, 8к1, Москва, Россия, 119620

7. Авиаторов ул., 6, Москва, Россия, 119619

8. Авиаторов ул., 14, Москва, Россия, 119620

9. Авиаторов ул., 30, Москва, Россия, 119620

10. Волынская ул., 4, Москва, Россия, 11962

Тогда матрица, полученная с помощью веб-службы «Google Maps Distance Matrix API» имеет вид (таблица 2.1):

Таблица 2.1

Матрица стоимостей

	1	2	3	4	5	6	7	8	9	10
1		18	16	18	12	11	4	11	20	18
2	18		7	19	16	22	21	28	28	22
3	16	7		12	8	14	19	20	20	15
4	18	19	12		6	11	18	17	14	7
5	12	16	8	6		6	12	13	12	10
6	11	22	14	11	6		12	7	10	11
7	4	21	19	18	12	12		7	18	19
8	11	28	20	17	13	7	7		11	17
9	20	28	20	14	13	10	18	11		8
10	18	22	15	7	10	11	19	17	8

Проинициализировав, каждый элемент матрицы начальным значением феромонов и применяя к ней реализованный алгоритм, процесс решения можно представить в виде графика (рисунок 2.8), на котором заметно, как происходила оптимизация маршрута из точки 1 на каждой итерации:

Уже на 24 итерации алгоритма был найден маршрут {1, 7, 8, 6, 9, 10, 4, 5, 3, 2}, который остался оптимальным на всех последующих итерациях, и его время пути составляет 65 минут. Время пути сокращается почти в два раза, в сравнении, если бы врач посещал адреса по порядку из входных данных (в сумме 128 минут).

Рисунок 2.8 График итераций

Также время выполнения запроса для 10 точек, за 100 итераций и 10 агентов, вместе с запросом к «Google Maps Distance Matrix API» для получения матрицы, в среднем составляет 150мс

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

2.3 Состав и структура программного комплекса

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

Базы данных. Так как MongoDB имеет подход NoSQL, то таблицы базы данных будут называться коллекциями, а строки таблиц - документами. Реализация коллекций также происходит на серверной части веб-комплекса. База данных состоит из трех коллекций:

1. User - коллекция пользователей. Структура документа имеет следующие обязательные поля:

a. email - почта, уникальное значение

b. password - хэш пароля

c. address - строка адреса

d. latLng - географические координаты адреса (широта и долгота)

e. login - ФИО

f. phone - телефон

g. role - роль, перечисляемый тип из трех значений: пациент, врач, администратор. Дефолтное значение «пациент», выставляется при регистрации

2. Worker - коллекция рабочих графиков врачей

a. id_user - идентификатор пользователя «врач»

b. estimated_time - затрачиваемое время на обход пациентов

c. patients - массив документов коллекции record (подробнее в описании коллекции). Порядок документов массива задает путь обхода пациентов.

d. start - время начала рабочего дня

e. end - время конца рабочего дня

3. Record - коллекция записей пациентов

a. id_user - идентификатор документа коллекции user

b. id_worker - идентификатор документа коллекции worker

c. time_create - время создания записи

d. time_target - целевое время посещения пациента врачом. Применяется для планирования обхода. Назначается после расчета или перерасчета пути алгоритмом

e. comment - примечание, краткое описание причины вызова врача

Серверная сторона. Серверная сторона программного средства представляет независимый от интерфейса веб-сервис, использующий архитектуру REST. Взаимодействие с ним происходит по HTTP-протоколу (с помощью команд GET, POST, PUT, DELETE), а обмен данными осуществляется в формате JSON. Структура API веб-сервиса представлена в виде схемы на рисунке 2.9

Рисунок 2.9 API серверной части

Запросы производные от «auth» к API, не проходят проверку сессии по токену JWT. Остальные запросы - проходят проверку сессии. Токен может быть получен только после авторизации (запрос /auth/authenticate). В случае успешной проверки вызывается соответствующий запросу метод. Если токен неверный или отсутствует в заголовке запроса, то приходит ошибка «401 Authentication error». Данная ошибка может быть в двух случаях: когда токен неверный/отсутствует или закончилась сессия пользователя. Для последнего случая используется POST запрос /auth/check, который проверяет сессию и продлевает ее, если она не закрыта, а в ответе возвращает модель пользователя. Это решение полезно для SPA интерфейса веб-сервиса. Перед отображением, компонент интерфейса посылает check запрос на сервер, после чего, на основании полученного ответа показывает соответствующий пользователю контент.

Запросы к API вызывают соответствующие методы контроллера, которые взаимодействуют с базой данных и выполняют определенные действия. Запросы, проходящие проверку сессии, разделены на четыре вида: для врачей, пациентов, администратора или любой роли. Проверка ролей пользователя осуществляется аналогичным образом, как и проверка авторизации. При поступлении запроса, перед вызовом метода контроллера, происходит соответствующая проверка доступа, и в случае ее успеха вызывается уже сам метод. Описание методов обрабатывающих запросы, как представлено на рисунке 2.9 делятся на 4 группы: worker, user, record, auth. В таблице 2.2 представлено подробное описание каждого метода.