КВАЛІФІКАЦІЙНА РОБОТА МАГІСТРА

Тема : Методи і алгоритми пошуку оптимального шляху переміщення агентів з територіально-розподіленим торговим точкам

Зміст

Цілі і задачі

На сьогоднішній день можна виділити два види систем оптимізації руху - настільні і орієнтовані на доступ через глобальну мережу. Основним і визначальним різницею в даних типах систем є джерело інформації для складання маршруту. Настільні системи беруть інформацію з баз даних, розташованих на власних серверах, або, отримуючи дані по локальній мережі. З переваг варто відзначити контроль над доступом до інформації, крім того швидкість роботи додатків, побудованих за настільної клієнт - серверній архітектурі у багато разів може перевищувати швидкість роботи web – орієнтованої підсистеми. Недоліком даних систем є необхідність постійного оновлення даних, і їх додатки новими, що робить такі системи залежними від частоти оновлення. Це позначається на актуальності відомостей, необхідних для виконання кінцевої задачі - знаходження оптимального маршруту слідування. Основною метою даної підсистеми є складання оптимального маршруту проходження агента, складеного на підставі різних критеріїв: відстань між торговими точками; час, витрачений на поїздку; тип місцевості; витрата палива; напрямок руху по дорогах (односпрямованої, двонаправлене).

Основними завданнями є:

  • візуалізація даних за маршрутами на карті;
  • перегляд знаходження окремо інтерсующіх маршрутних точок;
  • відображення детальної інформації по торгових точках (її показники).

Також буде організована видача інформації за результатами обробки користувачеві підсистеми і показники, які вплинули на результат.

Актуальність роботи

Сьогодні ринок пропонує рішення на будь-який смак і колір, для будь-якого бюджету, намагаючись покрити всі проізводственнние потреби. І вже завтра потреби і вимоги будуть, безсумнівно, масштабніше і суворіше. Цей факт ставить перед розробниками питання про пошук нових шляхів вирішення поставлених завдань, з урахуванням необхідності постійного оновлення своїх продуктів. Це безпосередньо відноситься до теми мого дослідження, так як карти з часом застарівають, з'являються нові будівлі, маршрути проїзду. Таким чином з'являється необхідність у надійному джерелі картографічних даних, за допомогою якого можна було б отримувати актуальні географічні дані і системі, яка б на підставі цих даних, допомагала вибирати найбільш короткий і дешевий маршрут для пересування.

Наукова новизна

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

Плановані практичні результати

За допомогою даної системи передбачається отримати засіб для:

  • аналізу ефективності переміщення торгових агентів;
  • географічної візуалізації маршрутів пересування;
  • регулювання пересування агентів по торгових точках.
Підвищення ефективності відвідин торгових точок буде отримано за рахунок: контролю переміщення агентів; тимчасової оптимізації - більше відвіданих торгових точок за той же робочий час.

Повышение эффективности посещения торговых точек будет получено за счет:

  • контроля перемещения агентов;
  • временной оптимизации - больше посещенных торговых точек за то же рабочее время.

Огляд досліджень і розробок по темі:

Виділяють два види систем оптимізації руху - настільні і орієнтовані на доступ через глобальну мережу. Основним і визначальним різницею в даних типах систем є джерело інформації для складання маршруту. Настільні системи беруть інформацію з баз даних, розташованих на власних серверах. отримуючи дані по локальній мережі. З переваг варто відзначити контроль над доступом до інформації, крім того швидкість роботи додатків, побудованих за клієнт - серверній архітектурі у багато разів може перевищувати швидкість роботи web - орієнтованої підсистеми. Недоліком даних систем є необхідність постійного оновлення даних, і їх додатки новими, що робить такі системи залежними від частоти оновлення, що відбивається на актуальності відомостей, необхідних для виконання кінцевої задачі - знаходження оптимального маршруту слідування. Web - базовані системи є, на мою думку, більш ефективним засобом розв'язання задачі. Незважаючи на меншу швидкість доступу до даних, вони забезпечують максимальну актуальність, велику гнучкість і розширюваність, можливість доступу до необхідної інформації з будь-якої точки, а при відповідному забезпеченні - мобільний доступ з допомогою КПК або телефону.

Структурно такі системи являють собою набір з двох частин - база даних і клієнтська частина. База даних містить географічні дані, що дозволяють за координатами, адресою, набору вулиць, доріг і будинків визначити місце розташування, прокласти маршрут, знайти на карті будь-який об'єкт.

Основним специфічним відзнакою розповсюджуваних систем є присутність своєї бази даних, націленої на контролювання рухів транспорту або агентів, і неможливість інтегрування корпоративних даних до даних карти. Згідно специфіці завдання, було б неможливо відобразити на карті дані по торгових точках і інформацію про них.

Клієнтська частина складається з двох частин - логіка і інтерфейс користувача. Логіка програми передбачає наявність коштів для зв'язку з сервером, який містить дані картки; сервера з корпоративними даними; класів, що реалізовують методи оптимізації знаходження найкоротшого маршруту для проходження за маршрутними листами; коштів для виведення результатів роботи користувачеві.

Математичні методи розв'язання задачі

В якості вихідних даних згідно завдання є розклад відвідування агентами торговельних точок - маршрутний лист, адреси торгових точок, в деяких випадках їх точні географічні координати (широта, довгота). Необхідно отримати маршрут збудований згідно з різними критеріями: відстань між торговими точками; час, витрачений на поїздку; витрата палива; тип місцевості.

Після отримання маршруту необхідно нанести його на карту місцевості, із зазначенням відвідуваних торгових точок як пунктів зупинки агента. Для вирішення поставленої задачі необхідно отримати географічні координати шляхів між торговими точками, тобто координати магістралей, вулиць, будинків, які агент зобов'язаний відвідати. Після отримання таких даних можна підключати алгоритми пошуку оптимальних маршрутів за наявними координатах. Математично місто можна представити як граф, тобто впорядкована пара G: = (V, E), для якої виконані наступні умови: V це безліч вершин або вузлів, E це множина пар (у разі неорієнтованого графа - невпорядкованих) вершин, званих ребрами.

Насправді вершини V являють собою перехрестя, перетину доріг, ребра E - об'єднують їх ділянки доріг. Ця схема застосовується не тільки в масштабі міста, але і по суті мережі доріг країни. Таким чином, для вирішення завдання слід використовувати алгоритми на графах, що дозволяють знайти оптимальний шлях через набір вершин.

На малюнку приведений схемний вид неорієнтованого графа з шістьма вершинами, у якості яких виступають перехрестя і сім'ю ребрами, у якості яких виступають дороги, що з'єднують перехрестя (рисунок 1).


Рисунок 1. Неорієнтовані граф з шістьма вершинами та дев'ятьма ребрами.

Робота системи має на увазі наявність постачальника географічної інформації, такого як Google Maps, який забезпечить систему інформацією про дороги, перехрестях, альтернативні варіанти під'їзду до місця призначення. Система, на підставі цієї інформації, зіставляючи її з інформацією про розклад відвідування торговельних точок, створить маршрут відвідування торговельних точок, обчислить показники, що характеризують вибір маршруту слідування. Доступ до аналітичної інформації буде надано аналітикам, перегляд маршрутів на карті з точним описом маршруту проїзду - агентам.

Схема функціонування системи (інакше кажучи, архітектура) представлена на малюнку 2.

Схема функционирования системы (иначе говоря, архитектура) представлена на рисунке 2.

Иллюстрация работы подсистемы
Рисунок 2. Процес функціонування підсистеми, що ілюструє отримання та обробку інформації. Анімація складається з 4 кадрів із затримкою в 50мс між кадрами; затримка для повторного відтворення становить 250мс; кількість циклів відтворення не обмежена; обсяг 87кБ.

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

  • алгоритм пошуку A *;
  • алгоритм Дейкстри;
  • пошуку найкоротших шляхів алгоритм Флойда;
  • генетичний алгоритм;
  • мурашиний алгоритм;
  • нейронні мережі моделі Хопфілда.

Висновок

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

Список літератури

  • Лорьер Ж.-Л. Системи штучного інтелекту / Пер. з фр. і ред. В. Л. Стефанюка. - М.: Світ, 1991. - С. 238-244. - 20 000 екз. екз. - ISBN 5-03-001408-X
  • Рассел С. Дж., Норвіг, П. Штучний інтелект: сучасний підхід = Artificial Intelligence: A Modern Approach / Пер. з англ. і ред. К. А. Птіцина. - 2-е изд .. - М.: Вільямс, 2006. - С. 157-162. - 3000 екз. екз. - ISBN 5-8459-0887-6
  • Нільсон М. Штучний інтелект: методи пошуку рішень = Problem-solving Methods in Artificial Intelligence / Пер. з англ. В. Л. Стефанюка; під ред. С. В. Фоміна. - М.: Світ, 1973. - С. 70 - 80.
  • Dechter, R., Pearl, J. Generalized best-first search strategies and the optimality of A * / / Journal of the ACM. - 1985. - Т. 32. - № 3. - С. 505 - 536.
  • Hart P. E., Nilsson, N. J., Raphael, B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths / / IEEE Transactions on Systems Science and Cybernetics SSC4. - 1968. - № 2. - С. 100 - 107.
  • Hart P. E., Nilsson, N. J., Raphael, B. Correction to «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» / / SIGART Newsletter. - 1972. - Т. 37. - С. 28 - 29.
  • Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. - Addison-Wesley, 1984. - ISBN 0-201-05594-5
  • Ананій В. Левітін Глава 3. Метод грубої сили: Завдання комівояжера / / Алгоритми: введення в розробку й аналіз = Introduction to The Design and Analysis of Algorithms. - М.: «Вільямс», 2006. - С. 159-160. - ISBN 0-201-74395-7
  • Томас Х. Кормен, Чарльз І. Лейзерсон, Рональд Л. Рівестом, Кліффорд Штайн Алгоритми: побудова й аналіз = Introduction to Algorithms. - 2-е вид. - М.: «Вільямс», 2006. - С. 1296. - ISBN 0-07-013151-1 В.І.
  • Мудров Задача про комівояжера. - М.: «Знання», 1969. - С. 62.

При написанні даного автореферату магістерська робота ще не завершена. Дата остаточного завершення роботи: 1 грудня 2010 Повний текст роботи та матеріали по темі можуть бути отримані у автора або його наукового керівника після зазначеної дати.