Савкін Владислав Юрійович

Факультет комп'ютерних наук та технологій (ФКНТ)

Кафедра автоматизованих систем управління (АСУ)

Спеціальність Інформаційні системи і технології в техніці та бізнесі

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

Науковий керівник: к.т.н., доц. Світлична Вікторія Антонівна

Резюме Біографія Реферат

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

Зміст

• Вступ
• 1. Актуальність теми
• 2. Мета і задачі дослідження
• 3. Огляд існуючих систем
• 4. Аналітична постановка задачі
• 4.1 Критерії оптимізації маршруту
• 4.2 Обмеження, що впливають на побудову маршруту
• 4.3 Математичний апарат
• 5. Огляд методів, моделей, алгоритмів
• 5.1 Точні алгоритми
• 5.2 Евристичні алгоритми
• 5.3 Пошукові алгоритми
• Висновки
• Перелік посилань

Вступ

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

1. Облік товарів на складі.
2. Облік і обробка заявок на поставку товару.
3. Розрахунок завантаження транспортних засобів.
4. Задача кластеризації.
5. Задача комівояжера.
6. Задача про рюкзак [1].

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

1. Актуальність теми

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

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

2. Мета і задачі дослідження

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

• скорочення тривалості маршрутів – найбільш вигідний маршрут, як правило, є оптимальним або близьким до оптимального по тимчасових витратах;
• зменшення кількості витраченного палива – найбільш вигідний маршрут дозволить витрачати меншу кількість палива за рахунок меншої відстані, яку треба подолати;
• зменшення пробігу автомобілів – найбільш вигідний маршрут дозволить зменшити фізичний знос автомобілів за рахунок меншої відстані, яку необхідно подолати.

Крім того, дана інформаційна система покликана полегшити і прискорити час роботи відділу логістики.

Описана мета може бути досягнута за допомогою вирішення наступних задач:

• облік приходу/витрати лікарських засобів;
• формування та обробка заявок на доставку лікарських засобів;
• розробка моделі поставок лікарських засобів в пункти роздрібної торгівлі;
• облік складених маршрутів, формування маршрутних листів [1].

3. Огляд існуючих систем

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

1. Мурашина логістика. Онлайн сервіс для розрахунку оптимальних маршрутів доставки. Сервіс надається для безкоштовного використання на пробний період, після чого вимагає покупки ліцензії для використання, при цьому кількість точок в маршруті може бути обмежена в залежності від типу ліцензії, а кількість маршрутів в день обмежена незалежно від типу ліцензії. [3].
2. ABM Rinkai TMS. Спеціалізується на побудові оптимальних маршрутів доставки товару. Система ABM Rinkai TMS є платною і не надає демо-версії для ознайомлення. Формування маршрутів в ABM Rinkai TMS передбачає 3 різних способи оптимізації, в кожному з яких закладена своя логіка процесу побудови маршрутів. Враховує всі ключові параметри, необхідні для побудови оптимальних маршрутів [4].
3. Zig-Zag. Сервіс управління транспортною логістикою для компаній, чий бізнес пов'язаний з доставкою вантажів. Сервіс дозволяє створювати оптимальні маршрути і ефективно планувати завантаження водіїв і кур'єрів. Сервіс є безкоштовним тільки для некомерційного використання. Містить в собі такі особливості, як робота в команді, оперативні зміни та аналіз виконання. Крім того, присутня мобільна версія [5].
4. Maxoptra. Веб-орієнтована система управління логістикою. Автоматично розподіляє роботу між виконавцями і планує оптимальні маршрути для доставки точно в строк і з мінімальними витратами. З її допомогою користувач має можливість контролювати і при необхідності коректувати рух співробітників в режимі реального часу. Maxoptra надає пробний період для використання, поле чого вимагає покупки ліцензії [6].

4. Аналітична постановка задачі

Задача комівояжера представляє собою завдання пошуку найкоротшого Гамільтонового шляху в повному кінцевому графі з N вершинами. Комівояжер, що виходить з якогось пункту, бажає відвідати N-1 інших пунктів і повернутися до вихідного пункту. Відомі відстані між усіма цими пунктами. Потрібно встановити, в якому порядку він повинен відвідувати міста, щоб загальна пройдена відстань була мінімальною [7].

Для вирішення поставленої задачі необхідним є додаткова умова збалансованості маршрутів, зокрема, за кількістю пунктів, що входять до маршрутів. Таке задача, звана узагальненою задачею комівояжера, належить до класу NP-важких задач. Для k комівояжерів на безлічі з n + 1 пунктів будується k замкнутих маршрутів за такими правилами:

• один з пунктів, званий базою, входить в усі маршрути;
• кожен з пунктів (виключаючи базу) входить рівно в один з маршрутів;
• сумарна довжина всіх маршрутів мінімальна.

4.1 Критерії оптимізації маршруту

Маршрут можна вважати оптимальним виходячи з наступних критеріїв:

• найменш витратний маршрут з точки зору часу і відстані;
• найменш витратний маршрут з точки зору фінансової складової;
• найменш витратний маршрут з точки зору часу, відстані, і фінансової складової, тобто сукупний критерій.

Варто відзначити, що найкоротший маршрут не завжди є найменш витратним, тому ці два критерії варто розглядати як окремі.

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

4.2 Обмеження, що впливають на побудову маршруту

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

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

4.3 Математичний апарат

Задачу комівояжера можна описати таким способом. Є n пунктів, вартість між якими задана матрицею C. комівояжер повинен побувати в кожному пункті один раз і повернутися в початковий пункт маршруту, витративши при цьому мінімум коштів [8]. Математично це може бути представлено наступною формулою, яка також представляє собою цільову функцію:

де n – кількість пунктів на карті;

c_ij – матриця вартості між пунктами;

x_ij – матриця переходів з компонентами:

    x_ij = 1, кщо маршрут включає переїзд з точки i безпосередньо в точку j;

    x_ij = 0, в іншому випадку.

Постановку задачі можна сформулювати наступним чином: знайти мінімум функції Z при виконанні обмежень і невід'ємності значень матриці X [9]. Систему обмежень можна представити таким чином:

де n – кількість пунктів на карті;

x_ij – матриця переходів з компонентами:

u_i, u_j – довільні цілі невід'ємні числа.

При цьому кожне з обмежень висловлює такі умови:

• обмеження №1 висловлює умову, що комівояжер виїжджає з кожного пункту один раз;
• обмеження №2 висловлює умову, що комівояжер в'їжджає один раз в кожен пункт;
• обмеження №3 висловлює умову, що маршрут не буде містити в собі замкнуті маршрути (умова незамкнутості), крім одного, що включає всі пункти, а також те, що маршрут не повинен містити петель.

Для реалізації вищенаведених рівностей досить ввести штрафні функції, поклавши:

де k = p;

c_ijmax – максимальне значення для всіх c_ij.

5. Огляд методів, моделей, алгоритмів

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

5.1 Точні алгоритми

Серед точних алгоритмів найбільш популярними для вирішення завдання комівояжера є:

• метод послідовної сепарації [8];
• алгоритм повного перебору [10];
• метод гілок і меж [11].

Алгоритм повного перебору здійснює пошук в просторі N! рішень за допомогою перебору всіх варіантів. Результатом роботи алгоритму є точне рішення. Недоліком алгоритму є його тимчасова складність – простір пошуку зростає експоненціально, тому, коли N не є значно меншим, використовують евристичні і пошукові алгоритми. Часова складність алгоритму повного перебору показана на рис. 1 з логарифмічною шкалою.

Експериментально складність даного алгоритму була оцінена як t = 0,0056 × e^{(1,3789 × N)}.

До переваг даного алгоритму можна віднести можливість розпаралелювання і точне рішення задачі.

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

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

Експериментально складність даного алгоритму була оцінена як t = 0,0745 × e^{(0,8485 × N)}. У разі використання в якості мінімального початкового рішення використовується рішення, отримане жадібним методом. Складність алгоритму складе t = 0,3164 × e^{(0,7469 × N)}. До переваг даного алгоритму можна віднести можливість розпаралелювання і точне рішення задачі. Часова складність методу гілок і меж і його розвиток показані на рис. 1 з логарифмічною шкалою [10].

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

Алгоритм рішення можна описати таким чином. Вирішується задача про призначення. Отримане рішення:

1. або представляє замкнутий маршрут, що включає всі міста;
2. або представляє сукупність декількох замкнутих локальних маршрутів.

Перший випадок являє собою і рішення задачі комівояжера, тобто рішення задачі про призначення дає одночасно рішення задачі комівояжера. Для отримання необхідного рішення з другого випадку слід розірвати замкнуті гілки і з'єднати їх в один замкнутий маршрут найменшої вартості. Нехай рішення задачі про призначення представимо у вигляді двох замкнутих маршрутів: ABC і DEF (рис. 2). Слід з'єднати ці маршрути в один так, щоб збільшення цільової функції було мінімальним.

Слід передбачити неможливість організації приватних замкнутих маршрутів.

Тому слід зробити заборони на перехід в варіантах:

• від точки кінця ланцюга σ до точки s;
• від точки p до точки початку ланцюга α;
• від точки p до точки s [8].

5.2 Евристичні алгоритми

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

• нейронні мережі [7];
• BV-метод [10];
• метод включення дальнього [10];
• метод імітації відпалу [12];
• метод найближчого сусіда;
• алгоритм розрізання загального маршруту;
• алгоритм розподілу по куту;
• метод дихотомічного поділу на групи;

Більш детально будуть розглянуті два методи: BV-метод і метод включення дальнього.

Ідея методу включення дальнього полягає в наступному: пункти, максимально віддалені один від одного, ніколи не будуть суміжними в ланцюзі. Ці два пункти і будуть базовими для подальшого вирішення. Потім знову знаходиться вершина, максимально віддалена від вершин, вже укладених в ланцюг. Знаходиться мінімальна сума довжин ребер між знайденої вершиною і парою суміжних вершин в ланцюзі, що задає місце в ланцюзі знайденої вершині [10].

Даний алгоритм має лінійну складність, дає приблизне рішення задачі і не може бути розпаралелєний. Його часова складність була оцінена як t = 28,0600 + (–1,6069 × N) + (0,0227 × N²)

BV-метод заснований на аналізі наявного еталонного маршруту і його оптимізації. Алгоритм умовно складається з трьох етапів:

1. отримання початкового еталонного рішення;
2. побудова BV матриці;
3. оптимізація поточного рішення.

Початкове рішення являє собою краще рішення з усіх рішень отриманих на основі жадібного методу. Для його реалізації будується N маршрутів, за кількістю пунктів доставки. У кожному з цих N маршрутів, початковий пункт дорівнює номеру маршруту, а всі наступні пункти вибираються за принципом жадібного алгоритму (вибирається найближчий пункт).

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

Другий етап алгоритму – побудова BV-матриці. Для цього будується матриця оцінок розміром NхN, спочатку заповнена нулями. Далі переглядаючи N побудованих жадібних маршрутів, для кожної пари сусідніх пунктів p і q, відповідний елемент матриці оцінок a [p, q] збільшується на одиницю.

Третій етап алгоритму полягає в перетворенні еталонного маршруту за допомогою послідовного застосування BV-модифікаторів до кожної пари пунктів, яким відповідає ненульовий елемент матриці оцінок. Якщо перетворений маршрут має меншу довжину шляху, то він стає еталонним і в матриці оцінок відповідний елемент замінюється на 0. Прохід по BV-матриці повторюється до тих пір, поки модифікований маршрут має перевагу над еталоном. Відсутність переваги модифікованого маршруту над еталоном, говорить про те, що отримане рішення є кінцевим для даного методу рішення.

BV-модифікатори можуть бути наступних видів:

• модифікатор Згладжування;
• модифікатор Перенесення;
• модифікатор Інверсний перехід;
• модифікатор Інверсне перенесення [10].

Даний алгоритм має квадратичну складність, дає приблизне рішення і може бути розпаралелєний на 2-му етапі. Його часова складність була оцінена як t = –169,40 + (15,5786 × N) + (–0,4104 × N²) + (0,0040 × N³).

5.3 Пошукові алгоритми

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

генетичні алгоритми – це процедури пошуку, засновані на механізмах природного добору і успадкування. У них використовується еволюційний принцип виживання найбільш пристосованих особин. Вони відрізняються від традиційних методів оптимізації декількома базовими елементами. Зокрема, генетичні алгоритми мають ряд відмітних властивостей:

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

Генетичні алгоритми є найбільш оптимальними серед пошукових в плані співвідношення час/якість і можуть бути розпаралелєні. Експериментально часова складність генетичного алгоритму була оцінена як t = 683 + (–42,467 × N) + (1,0696 × N²).

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

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

Мурашині алгоритми добре піддаються розпараллелюванню. Їх часова складність була оцінена як t = 4437,6 + (–293 × N) + (4,6779 × N²).

Висновки

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

З урахуванням проведеного дослідження [13, 14, 15], можна зробити висновок, що для вирішення задачі комівояжера найбільш доцільно використовувати мурашині алгоритми, які були розроблені спеціально для вирішення даної задачі і є найбільш ефективними в цій галузі. Однак, крім самого алгоритму, не можна забувати про критерій оптимізації, який вказує, в якому напрямку має працювати алгоритм. Це важливо з тієї точки зору, що один і той же алгоритм може давати різні результати для різних критеріїв оптимізації при вирішенні однієї і тієї ж задачі. Крім того, варто брати до уваги обмеження, які будуть впливати на роботу алгоритму і кінцевий результат. Ці обмеження можуть бути представлені в якості вхідних даних [1].

Примітки

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

Перелік посилань

1. Савкин В.Ю. Анализ методов решения задачи коммивояжёра / В.Ю. Савкин, В.А. Светличная, Радзывыло К.Г. // Материалы IX Международной научно-технической конференции. – Донецк: ДонНТУ, 2018. – с.6–10.
2. Семенов Ю.Н. Автоматизация построения маршрутов перевозок крупнопартионных грузов / Ю.Н. Семенов, О.С. Семенова // Вестник Кузбасского государственного технического университета. – Кемерово: КузГТУ, 2015. – с.131–134.
3. Автоматизация транспортной логистики – онлайн сервис для планирования оптимальных маршрутов доставки [Электронный ресурс] – Режим доступа: [Ссылка]
4. Управление транспортом, транспортная логистика, TMS система – ABM Rinkai [Электронный ресурс] – Режим доступа: [Ссылка]
5. Zig-Zag: Оптимизация транспортной логистики [Электронный ресурс] – Режим доступа: [Ссылка]
6. Maxoptra: Система управления логистикой, программа для логистики транспорта, система логистики предприятия [Электронный ресурс] – Режим доступа: [Ссылка]
7. Товстик, Т.М. Алгоритм приближённого решения задачи коммивояжёра / Т.М. Товстик, Е.В. Жукова // Вестник СПбГУ. – 2013. – №1. – с. 101-109.
8. Петрунин, С.В. Использование метода последовательной сепарации (ПС) для решения задачи коммивояжёра // Научный вестник МГТУ ГА. – 2009. – №143. – с. 87-90.
9. Задача коммивояжёра. [Электронный ресурс] – Режим доступа: [Ссылка]
10. Борознов, В.О. Исследование решения задачи коммивояжёра // Вестник АГТУ. Сер: Управление, вычислительная техника и информатика. – 2009. – №2. – с.147-151.
11. Костюк, Ю.Л. Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ // Прикладная дискретная математика: Научный журнал – Томск : Национальный исследовательский Томский государственный университет – 2013 – №2. – с.78-90.
12. Гараба, И.В. Сравнительный анализ методов решения задачи коммивояжёра для выбора маршрута прокладки кабеля кольцевой сети кольцевой архитектуры // Молодёжный научно-технический вестник. – 2013. – №1. – с.173-188.
13. Мурзин, Б.П. Использование алгоритма муравьиной колонии для определения оптимального маршрута доставки грузов / Б.П. Мурзин, В.А. Светличная // Інформаційні управляючі системи та комп'ютерний моніторинг (ІУС КМ-2011) / Збірка матеріалів IІ всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених – 11-13 квітня 2011 р., Донецьк, ДонНТУ – 2011, с. 183-186.
14. Курейчик, В.М. О некоторых модификациях муравьиного алгоритма / В.М. Курейчик, А.А. Кажаров // Известия ЮФУ. Технические науки. – 2009. – №1. – с.7-12.
15. Семенкина, О.Е. Effectiveness Comparison of Ant Colony and Genetic algorithms for solving combinatorial optimization problems // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. – 2012. – №1. – с.96-97.