Введение 3
1. Классические задачи теории расписаний и построения маршрутов в графах 5
1.1. Методы составления расписаний 5
1.2. Методы построения оптимальных маршрутов 11
1.3. Биоинспирированные методы 14
2. Практическое применение биоинспирированных методов
2.1. Биоинспирированные методы решения задачи составления
расписания 21
2.2. Применение муравьиных алгоритмов для составления
оптимальных маршрутов 26
2.3. Описание программы и полученных результатов 30
Заключение 34
Список литературы 35
Приложение
Задача составления расписания зачастую возникает во многих сферах деятельности: транспортной, энергетической, коммунальной, промышленной и так далее. Компаниям необходимо сформировывать различного рода расписания, например: график отпусков рабочих, расписание обработки документации и другие. Чем крупнее компания, тем сложнее организовать для нее оптимальное расписание выполнения тех или иных задач.
Наряду с задачей о составлении расписания также стоит проблема построения оптимального маршрута. Сделать такой маршрут между тремя или четырьмя точками не составляет проблем. Однако, чем больше компания, тем больше точек необходимо посетить и тем сложнее построить хороший маршрут.
Каждое предприятие решает проблемы составления расписания и оптимизации маршрута по-разному, но чаще всего это происходит вручную. При таком подходе к составлению расписания и маршрута маловероятно, что получившийся результат будет оптимальным. В связи с вышеизложенным возникает необходимость в построении автоматизированных систем составления расписания и маршрута.
Цель и задачи исследования.
Целью выпускной квалификационной работы является построение математической модели составления расписания для торгового представителя оптовой компании на неделю и получение оптимального маршрута передвижения.
Для решения данной проблемы необходимо решить ряд задач.
1. Рассмотреть некоторые классические методы решения задач теории расписаний.
2. Рассмотреть метод создания расписания, основанный на применении генетического алгоритма.
3. Рассмотреть метод муравьиного алгоритма для решения задачи составления оптимального маршрута.
Выпускная квалификационная работа объемом 37 листов состоит из введения двух частей, заключения и списка литературы, включающего 23 источника. Работа содержит 10 рисунков, 4 таблицы и приложение.
В настоящей работе была сформулирована задача о составлении расписания для торговых компаний. Для ее решения были рассмотрены два классических метода теории расписаний. После тщательного анализа было установлено, что их применение на практике оказывается достаточно труднореализуемым в случае, когда необходимо учесть все факторы, имеющиеся в поставленной задаче. Это потребовало применения альтернативных способов поиска решения.
Также в работе были рассмотрены некоторые классические алгоритмы решения задачи поиска оптимального маршрута в графе. Точное решение такой задачи возможно только при помощи полного перебора возможных решений, что практически реализуемо лишь только при малых значениях числа пунктов посещения. Существуют алгоритмы неполного перебора. В качестве такового в исследовании был рассмотрен еще один биоинспирированный метод - муравьиный алгоритм.
Как показало исследование, биоинспирированные методы оказались очень гибкими алгоритмами для решения подобных задач. Генетический алгоритм может учесть множество различных факторов. Требуется только правильно представить особь и реализовать эволюционные операторы. Он был использован в качестве метода, для составления расписания. Муравьиный алгоритм может быть использован для построения оптимального маршрута с дополнительными условиями, которые отсутствуют в классических постановках задач.
Для того, чтобы сформировать расписание и найти оптимальный маршрут, на языке программирования C# была создана программа с графическим интерфейсом пользователя.
На данный момент в приложении реализована только часть, выполняющая составление расписания на неделю для торгового представителя по заданным исходным данным. В дальнейшем планируется усовершенствовать и расширить приложения за счет добавления распараллеливания вычислений, а также включения муравьиного алгоритма для построения оптимального маршрута.
