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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «РОССИЙСКИЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ Г.В. ПЛЕХАНОВА»

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

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

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

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

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

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



СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 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, программный комплекс «Логистика развоза» компании ООО «Программы для бизнеса», ОПТИМУС ГИС и ABMRinkaiTMS. Рассмотрим каждое программное средство более подробно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

.

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



.

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

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

Помимо обновления феромонов после каждой итерации, применяется дополнительное обновление, которое выполняется после прохода по ребру по формуле (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 основанной на движке ChromeV8. Еще одним преимуществом 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 библиотеки VirtualDOMможно добиться высокой производительности приложения. Reactвместо воздействия на DOMнапрямую, работает с ее виртуальной копией. Работа с DOM происходит в три этапа:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· 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)



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

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

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

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

Тогда матрица, полученная с помощью веб-службы «GoogleMapsDistanceMatrixAPI» имеет вид (таблица 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 на каждой итерации:



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

Уже на 24 итерации алгоритма был найденмаршрут{1, 7, 8, 6, 9, 10, 4, 5, 3, 2}, который остался оптимальным на всех последующих итерациях,и его время пути составляет65 минут. Время пути сокращается почти в два раза, в сравнении, если бы врач посещал адреса по порядку из входных данных (в сумме 128 минут). Также время выполнения запроса для 10 точек, за 100 итераций и 10 агентов, вместе с запросом к«GoogleMapsDistanceMatrixAPI» для получения матрицы, в среднем составляет 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 Authenticationerror». Данная ошибка может быть в двух случаях: когда токен неверный/отсутствует или закончилась сессия пользователя. Для последнего случая используется POST запрос /auth/check, который проверяет сессию и продлевает ее, если она не закрыта, а в ответе возвращает модель пользователя. Это решение полезно для SPAинтерфейса веб-сервиса. Перед отображением, компонент интерфейса посылает checkзапрос на сервер, после чего, на основании полученного ответа показывает соответствующий пользователю контент. муравьиный программный тестирование отладка

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