ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

Поддержка клиентов в настоящее время занимает высокие позиции среди целей корпораций, в том числе для привлечения новых клиентов. Современные технологии позволяют повысить эффективность решения данной задачи. В настоящее время есть возможность общения с клиентами по средствам не только телефонии, но и видео-телефонии (Skype, Google Talk, QIP и др.). Несмотря на это, существуют проблемы, решить которые возможно только выездом сотрудника организации к клиенту. Примером обслуживающей организации будет служить корпорация «Парус-Донецк».

Корпорация Парус основана в 1990 году. Обладая хорошей репутацией, завидным опытом работы, мощными трудовыми ресурсами и явно прослеживающейся динамикой развития, эта компания всегда выступает в роли надежной фирмы-партнера, способной решить не только задачи автоматизации управления предприятием, но и в дальнейшем оперативно осуществлять сопровождение своих программных продуктов. Основной вид деятельности компании: разработка, продвижение и внедрение программного обеспечения (ПО) для автоматизации управления предприятием. Парус-Донецк – это представительство корпорации Парус в Донбассе. Клиентами «Парус-Донецк» являются свыше 400 организаций в Донецке и более 1100 в области. Штат предприятия насчитывает всего 46 сотрудников. Чтобы обеспечивать поддержку организациям, количество которых превышает 1500, сотрудникам «Парус-Донецк» необходимо оптимально распределять свое время и выбирать наилучший маршрут для продуктивной работы.

1. Описание объекта

1.1 Описание объекта исследований

Объектом исследований в данной работе является обслуживание. Поддержка клиентов может быть осуществлена двумя способами:

Способ решения вопроса клиента зависит не только от сложности вопроса, но и от знаний самого клиента в компьютерной области. Например, около 70% клиентов не справляются с такими простейшими задачами, как обновление ПО или форм. С системой в основном работают бухгалтера. Обновление проводится в 3 этапа:

  1. файл установки (*.exe или *.zip) отправляется клиенту на e-mail;
  2. сотрудник (бухгалтер) организации-клиента загружает себе на компьютер установочный файл;
  3. бухгалтер запускает инсталлятор на своем ПК.

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

Парус-Донецк предоставляет несколько вариантов обновлений. Если сотрудник фирмы-заказчика самостоятельно не справляется с обновлением, он всегда может получить поддержку от сотрудника Паруса по горячей линии. Если даже это не поможет решить проблему, то запрос клиента о помощи на месте является 100% гарантией решения вопроса. Но для сотрудника Парус-Донецк, такой клиент не единственный. Со временем, количество запросов на помощь увеличивается до такого объема, что каждому сотруднику необходимо заранее спланировать свой маршрут, чтобы обслужить всех клиентов за отведенный срок. Учитывая то, что каждый месяц выходит новый инсталлятор для каждого программного продукта, то можно сделать вывод о необходимости наличия специальной системы для автоматического распределения сотрудников по организациям-клиентам, так как проблему оптимального распределения рабочего времени приходится решать ежедневно каждому сотруднику в отдельности.

Для автоматизации стратегий взаимодействия с заказчиками необходимо использовать CRM системы. Система управления взаимоотношениями с клиентами (CRM, CRM-система, сокращение от англ. Customer Relationship Management) – прикладное программное обеспечение для организаций, предназначенное для автоматизации стратегий взаимодействия с заказчиками, в частности, для повышения уровня продаж, оптимизации маркетинга и улучшения обслуживания клиентов путём сохранения информации о клиентах и истории взаимоотношений с ними, установления и улучшения бизнес-процедур и последующего анализа результатов.

В «арсенале» ООО «Парус-Донецк» есть такое средство. Такая система называется «ПАРУС-Менеджмент и Маркетинг».

Проектируемая подсистема, позволяющая автоматизировать распределение сотрудников на обслуживание клиентов, может служить дополнением к существующей CRM системе.

1.1 Обоснование актуальности задачи

Штат корпорации «Парус-Донецк» насчитывает 46 сотрудников, включая директора, бухгалтера и офис-менеджера. Если учитывать только сотрудников, занимающихся обслуживанием организаций-клиентов, то их 43.

В списке клиентов «Парус-Донецк» находится 434 организации, расположенных в Донецке и 1136 в пределах области. Всего их 1570.

Каждый месяц выходит обновленный инсталлятор. Для обновления ПО в идеале клиент не нуждается в помощи сотрудника Паруса, но на деле получаем такую статистику: примерно 70% организаций-клиентов не в силе провести обновление самостоятельно и обращаются за помощью в Парус. 70% от 1570 организаций – это около 1100 единиц фирм. Учитывая штат представительства в Донецке, получаем отношение «организаций на сотрудника»: 1100/43≈26. Каждый сотрудник Паруса на одну организацию в среднем затрачивает примерно 2–3 часа (без учета времени на дорогу). Если говорить об организациях, находящихся в черте города, то на дорогу уходит времени примерно в 2 раза меньше. Если же в поддержке нуждается клиент, находящийся за пределами Донецка, то на дорогу сотрудник затрачивает времени столько же сколько на само обслуживание.

Кроме ежемесячных обновлений, существует обновления квартальные. Каждые 3 месяца в обновлении нуждается программный продукт «Парус-Консолидация». Процесс обновления этой системы не должен длиться больше недели. Получается, что 1100 организаций необходимо обновить 43 сотрудникам «Парус-Донецк» за 5 рабочих дней. Для более ясного представления, подсчитаем количество организаций, которые должен обслужить каждый сотрудник Паруса. Учитывая то, что на сотрудника приходится 26 организаций, получим: 26/5≈5 (организаций в день). Для обновления этого ПО времени необходимо меньше, но то же время затрачивается на дорогу. Т.е. на одну организацию нужно в среднем 1 час, в то время как на дорогу все те же 2–3 часа (в области). Если рассчитать количество времени, затрачиваемое сотрудником Паруса на 1 организацию в области, получим: 1+3=4 (часа) максимум). В сумме: 4*5=20 (часов) на 5 организаций – норма для сотрудника Парус-Донецк). Учитывая, что рабочий день составляет 8 часов, сталкиваемся с проблемой нехватки времени, а точнее – сотрудник не успеет обслужить половину организаций при максимальной нагрузке.

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

2. Анализ методов распределения в условиях поставленной задачи

2.1 Алгоритм поиска А*

Поиск A* – алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).

Порядок обхода вершин определяется эвристической функцией «расстояние+стоимость» (обычно обозначаемой как f(x)) [1]. Эта функция – сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).

Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.

Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Это по сути было расширение алгоритма Эдсгера Дейкстры, созданного в 1959 году. Он достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как «алгоритм A» [2]. Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.

Обобщением для него является двунаправленный эвристический алгоритм поиска. Он состоит из следующих пунктов [3]:

2.2 Алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда – алгоритм поиска кратчайшего пути во взвешенном графе [4]. Граф – включает множество вершин и множество рёбер, являющееся подмножеством декартова квадрата множества вершин. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает рёбра с отрицательным весом (Вес ребра – значение, поставленное в соответствие данному ребру взвешенного графа.). Предложен независимо Ричардом Беллманом и Лестером Фордом. Этот алгоритм также носит название RIP. Алгоритм маршрутизации RIP (алгоритм Беллмана-Форда) был впервые разработан в 1969 году, как основной для сети ARPANET.

Формулировка задачи: дан ориентированный или неориентированный граф G со взвешенными рёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа [5].

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

Способ решения задачи зависит от графа. Различают 2 вида графов:

  1. граф без отрицательных циклов;
  2. граф с отрицательными циклами.

2.3 Алгоритм Дейкстры

Алгоритм Дейкстры (Dijkstra`s algorithm) – алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году [6]. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

Формальное определение: дан взвешенный ориентированный граф G(V,E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

Неформальное объяснение: каждой вершине из V сопоставим метку – минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово – на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

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

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма [7].

2.4 Муравьиный алгоритм

Муравьиный алгоритм (алгоритм оптимизации подражанием муравьиной колонии) – один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра, а также аналогичных задач поиска маршрутов на графах. Суть подхода заключается в анализе и использовании модели поведения муравьёв, ищущих пути от колонии к источнику питания и представляет собой метаэвристическую оптимизацию[8]. Первая версия алгоритма, предложенная доктором наук Марко Дориго в 1992 году, была направлена на поиск оптимального пути в графе.

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

3. Выбор и обоснование метода

3.1 Обоснование выбранного метода

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

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

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

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

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

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

3.2 Подробный обзор выбранного метода

В основе алгоритма лежит поведение муравьиной колонии – маркировка более удачных путей большим количеством феромона [10]. Работа начинается с размещения муравьёв в вершинах графа (городах), затем начинается движение муравьёв – направление определяется вероятностным методом, на основании формулы вида:

Формула вероятности

(3.1)

где: Pi вероятность перехода по пути i, li величина, обратная весу (длине) i-ого перехода, ƒi количество феромона на i-ом переходе, q величина, определяющая «жадность» алгоритма, p величина, определяющая «стадность» алгоритма и q+p=1.

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

В литературе было предложено несколько метаэвристических моделей ACO (ant colony optimization). Среди них три наиболее успешные:

  1. ant system (Dorigo 1992, Dorigo et al. 1991, 1996);
  2. ant colony system (ACS) (Dorigo & Gambardella 1997);
  3. MAX-MIN ant system (MMAS) (Stutzle & Hoos 2000).

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

На рис. 3.1 изображен алгоритм:

  1. Первый муравей находит источник пищи (F) любым способом, а затем возвращается к гнезду (N), оставив за собой тропу из феромонов.
  2. Затем муравьи выбирают один из четырёх возможных путей, затем укрепляют его и делают привлекательным.
  3. Муравьи выбирают кратчайший маршрут, так как у более длинных феромоны сильнее испарились.
Поведение муравьев

Рисунок 3.1 – Поведение муравьев
(анимация: 7 кадров, 8 циклов повторения, 26 килобайт)

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

Муравьи используют окружающую среду как средство общения. Они обмениваются информацией косвенным путём, через феромоны, в ходе их «работы». Обмен информации имеет локальный характер, только те муравьи, которые находятся в непосредственной близости, где остались феромоны – могут узнать о них. Такая система называется «Stigmergy» и справедлива для многих социальных животных (был изучен в случае строительства столбов в гнёздах термитов). Данный механизм решения проблемы очень сложен и является хорошим примером самоорганизации системы. Такая система базируется на положительной (другие муравьи укрепляют феромонную тропу) и отрицательной (испарение феромонной тропы) обратной связи. Теоретически, если количество феромонов будет оставаться неизменным с течением времени по всем маршрутам, то невозможно будет выбрать путь. Однако из-за обратной связи, небольшие колебания приведут к усилению одного из маршрутов и система стабилизируется к кратчайшему пути [11].

3.3 Обзор модификаций классического алгоритма

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

  1. Elitist Ant System

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

    Эксперименты показывают, что, до определенного уровня, увеличение числа элитных муравьев является достаточно эффективным, позволяя значительно сократить число итераций алгоритма. Однако, если число элитных муравьев слишком велико, то алгоритм достаточно быстро находит субоптимальные решение и застревает в нем. Как и другие изменяемые параметры, оптимальное число элитных муравьев следует определять опытным путем [12].

  2. Ant-Q

    Лука Гамбарделла и Марко Дориго опубликовали в 1995 году работу, в которой они представили муравьиный алгоритм, получивший свое название по аналогии с методом машинного обучения Q-learning. В основе алгоритма лежит идея о том, что муравьиную систему можно интерпретировать как систему обучения с подкреплением. Ant-Q усиливает эту аналогию, заимствуя многие идеи из Q-обучения.

    Алгоритм хранит Q-таблицу, сопоставляющую каждому из ребер величину, определяющую «полезность» перехода по этому ребру. Эта таблица изменяется в процессе работы алгоритма – то есть обучения системы. Значение полезности перехода по ребру вычисляется исходя из значений полезностей перехода по следующим ребрам в результате предварительного определения возможных следующих состояний. После каждой итерации полезности обновляются исходя из длин путей, в состав которых были включены соответствующие ребра [13].

  3. Ant Colony System

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

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

  4. Max-min Ant System

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

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

  5. ASrank

    Бернд Бульнхаймер, Рихард Хартл и Кристине Штраусс разработали модификацию классического муравьиного алгоритма, в котором в конце каждой итерации муравьи ранжируются в соответствие с длинами пройденных ими путей. Количество феромонов, оставляемого муравьем на ребрах, таким образом, назначается пропорционально его позиции [16]. Кроме того, для более тщательного исследования окрестностей уже найденных удачных решений, алгоритм использует элитных муравьев.

4. Математическая модель поставленной задачи

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

Основная целевая функция:

Основная целевая функция

(4.1)

где Si – сумма стоимости проезда по Ofi организациям, Tfi – суммарное количество времени на Ofi организаций.

Ограничение по объектам:

Ограничение по объектам

(4.2)

где Ofi – фактическое количество организаций на i-го сотрудника, Opi – плановое количество организаций на i-го сотрудника.

Ограничения по времени:

Ограничения по времени

(4.3)

где Tp – рабочее время сотрудника за день, равное норме (8 часов).

Затраты на проезд

(4.4)

где s1 – затраты на проезд от офиса к первой организации, sj – затраты на проезд от (j-1)-ой к j-ой организации i-му сотруднику, Ofi – количество организаций, которые должен посетить i-ый сотрудник за день

Затраты по времени

(4.5)

где tw1 – время на дорогу от офиса к первой организации, trj – время на дорогу от (j-1)-ой к j-ой организации для i-го сотрудника, twj – время на обслуживающие работы j-ой организации для i-го сотрудника

Обслужено организаций

(4.6)

где O – общее число организаций, V – общее число сотрудников, τ – период обновления.

Формула (4.1) является основной целевой функцией при ограничениях (4.2) и (4.3), а формулы (4.4) – (4.6) описывают каждый параметр. Гранулярность целевой функции объясняется тем, что рассматриваемая задача состоит из нескольких подзадач и имеет определенные ограничения для каждой из них. Так, например, (4.4) ограничена количеством возможных путей следования и дальностью поездки, а (4.5) зависит от количества контрольных точек (организаций). Число организаций по плану для каждого сотрудника (4.6) является переменным и зависит от периода обновления ПО и количеством клиентов, которых необходимо обслужить.

Решать данную задачу можно теми же методами, что и задачу коммивояжера, но при этом необходимо учитывать не только время в дорогу (trj), но и время обслуживания (twj). К таким методам относятся:

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

Для адаптации классической задачи к нашей теме введем следующие обозначения:

Моделирование движения сотрудника связано с распределением рейтинга на пути маршрута. При этом вероятность (4.7) включения пути в маршрут отдельного сотрудника пропорциональна количеству рейтинга на этом пути, а количество инкрементируемого рейтинга пропорционально длине маршрута. Чем короче маршрут, тем больше рейтинга будет инкрементировано на его пути (4.8), следовательно, большее количество сотрудников будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости – большинство сотрудников движется по локально оптимальному маршруту. Избежать этого можно, моделируя отрицательную обратную связь в виде декрементации рейтинга. При этом если рейтинг декрементирует быстро, то это приводит к «потере памяти» сотрудников и забыванию хороших решений, с другой стороны, большое время декрементации может привести к получению устойчивого локального оптимального решения.

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

(4.7)

где wij(t) – уровень рейтинга, dij – эвристическое расстояние, а β, α – константные параметры. При α=0 выбор ближайшего клиента наиболее вероятен, то есть алгоритм становится жадным. При β=0 выбор происходит только на основании рейтинга, что приводит к субоптимальным решениям.

Уровень рейтинга

(4.8)

где ρ – интенсивность декрементации, Lk(t) – цена текущего решения для k-ого сотрудника, а Q – параметр, имеющий значение порядка цены оптимального решения, то есть  – рейтинг, инкрементируемый k-ым сотрудником, использующим ребро (i,j).

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

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

(4.9)

где К – количество пересадок между транспортом, М – расстояние между точками.

Выводы

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

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2012 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

  1. Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка. – М.: Мир, 1991. – С. 238–244.
  2. Рассел С. Дж., Норвиг, П. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach / Пер. с англ. и ред. К. А. Птицына. – 2-е изд. – М.: Вильямс, 2006. – С. 157–162.
  3. Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. – Addison-Wesley, 1984.
  4. R. Bellman: On a Routing Problem // Quarterly of Applied Mathematics. 1958. Vol 16, No. 1. C. 87–90, 1958.
  5. L. R. Ford, Jr., D. R. Fulkerson. Flows in Networks, Princeton University Press, 1962.
  6. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. – 2-е изд. – М.: «Вильямс», 2006. – С. 1296.
  7. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. – М.: «Вильямс», 2006. – С. 189–195.
  8. M. Dorigo & T. Stutzle, 2004. Ant Colony Optimization, MIT Press.
  9. M. Dorigo, G. Di Caro & L. M. Gambardella, 1999. "Ant Algorithms for Discrete Optimization". Artificial Life, 5 (2): 137–172.
  10. M. Dorigo, V. Maniezzo & A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26 (1): 29–41.
  11. C. Blum, 2005 "Ant colony optimization: Introduction and recent trends". Physics of Life Reviews, 2: 353–373.
  12. T. Stutzle et H.H. Hoos, MAX-MIN Ant System, Future Generation Computer Systems, volume 16, pages 889–914, 2000.
  13. L. M. Gambardella, M. Dorigo, "Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem" // Twelfth International Conference on Machine Learning, Morgan Kaufmann, p. 252–260, 1995.
  14. M. Dorigo, L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation Vol. 1, 1, p. 53–66, 1997.
  15. T. Stutzle, H. Hoos, "MAX-MIN Ant System and local search for the traveling salesman problem" // IEEE International Conference on Evolutionary Computation, p. 309–314, 1997.
  16. Bernd Bullnheimer, Richard F. Hartl, Christine Strau?, "A new rank based version of the Ant System. A computational study" // Adaptive Information Systems and Modelling in Economics and Management Science, 1, 1997.