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

Реферат за темою випускної роботи

Зміст

Вступ

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

Корпорація „Парус“ заснована в 1990 році. Володіючи хорошою репутацією, завидним досвідом роботи, потужними трудовими ресурсами і динамікою розвитку, що явно простежується, ця компанія завжди виступає в ролі надійної фірми-партнера, здатної вирішити не тільки задачі автоматизації управління підприємством, але й надалі оперативно здійснювати супровід своїх програмних продуктів. Основний вид діяльності компанії: розробка, просування і впровадження програмного забезпечення (ПЗ) для автоматизації управління підприємством. „Парус-Донецьк“ – це представництво корпорації „Парус“ в Донбасі. Клієнтами „Парус-Донецьк“ є понад 400 організацій в Донецьку і більше 1100 в області. Штат підприємства нараховує лише 46 співробітників. Щоб забезпечувати підтримку організаціям, кількість яких перевищує 1500, співробітникам „Парус-Донецьк“ необхідно оптимально розподіляти свій час і вибирати найкращий маршрут для продуктивної роботи.

1. Опис об’єкту

1.1 Опис об’єкту досліджень

Об’єктом досліджень у даній роботі є обслуговування. Підтримка клієнтів може бути здійснена двома способами:

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

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

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

„Парус-Донецьк“ надає кілька варіантів оновлення. Якщо співробітник фірми-замовника самостійно не справляється з оновленням, він завжди може отримати підтримку від співробітника Паруса по гарячій лінії. Якщо навіть це не допоможе вирішити проблему, тоді запит клієнта про допомогу на місці є 100% гарантією вирішення питання. Але для співробітника Парус-Донецьк, такий клієнт не єдиний. З часом, кількість запитів на допомогу збільшується до такого об’єму, що кожному співробітнику необхідно заздалегідь спланувати свій маршрут, щоб обслужити всіх клієнтів за відведений термін. Враховуючи те, що кожного місяця виходить новий інсталятор для кожного програмного продукту, то можна зробити висновок про необхідність наявності спеціальної системи для автоматичного розподілу співробітників по організаціям-клієнтам, так як проблему оптимального розподілу робочого часу доводиться вирішувати щодня кожному співробітникові окремо.

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

В „арсеналі“ ТОВ „Парус-Донецьк“ є такий засіб. Така система називається „Парус-Менеджмент і Маркетинг“.

Підсистема, що проектується дозволяє автоматизувати розподіл співробітників на обслуговування клієнтів, може служити доповненням до існуючої 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.