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

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

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

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

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

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

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

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

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

Тема

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

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

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

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

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

Москва - 2017

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

.4 Тестирование и отладка программного комплекса

.5 Инструкция пользователю

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

Глава 3. Оценка технико-экономических показателей разработанного программного комплекса построения оптимального маршрута обхода пациентов

3.1 Испытания программного комплекса

.2 Оценка качественных показателей разработанного программного комплекса

.3 Оценка экономической эффективности

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

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1.1

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

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

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

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. Кидая жребий на интервале  пусть выпало число 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 протоколу. Это программное средство, в свою очередь, располагается на сервере. На сегодняшний день, любые медицинские учреждения (поликлиники, больницы) уже имеют в своем распоряжении сервера для хранения баз данных сотрудников, привязанных к учреждению клиентов и различной бухгалтерской информации.