Реферат на тему «Розробка комп'ютеризованої системи оптимального розподілу та доставки лікарських засобів»

  1. Ціль і завдання даного дослідження
  2. Актуальність теми
  3. Передбачувана наукова новизна
  4. Передбачувана практична цінність
  5. Огляд досліджень і розробок за темою
  6. Постановка задачі дослідження
  7. Математична модель завдання
  8. Мурашиний алгоритм
  9. Висновок
  10. Список літератури

Ціль і завдання дослідження

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

У рамках даної роботи були поставлені наступні завдання:

· Охарактеризувати об'єкт та оцінити вимоги до розроблюваної системи

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

· Провести вибір і обґрунтування методу для виконання поставленої мети

· Розробити й програмно реалізувати алгоритм для оптимальної побудови маршрутів доставки лікарських засобів

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

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

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

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

Передбачувана наукова новизна

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

Передбачувана практична цінність

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

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

Система Arclogistics

Продукт компанії ESRI(США), однієї зі світових лідерів у розробці, створенні й просуванні геоінформаційних систем. Arclogistics – це інструмент диспетчера, який щодня планує роботу парку транспортних засобів, чия робота містить у собі розрахунки оптимальних маршрутів, створення маршрутних карт, побудову звітів, аналіз пробігу й оцінку ефективності роботи. Arclogistics призначений для користувачів, що не є фахівцями в області ГІС. Інтерфейс програми простий у використанні.

Основні переваги Arclogistics:

· Оптимальне використання парку транспортних засобів.

· Наявність карт доріг за усією територію Європи (включаючи Росію).

· Сумісність із іншими програмними продуктами й форматами даних ESRI.

· Гнучкі налаштування характеристик транспортних засобів.

· Можливість інтеграції із зовнішніми інформаційними системами.

· Інструменти створення звітів і маршрутних карт.

· Використання зон відповідальності водіїв і оперативне внесення змін (бар'єрів).

Можливості:

Побудова оптимальних маршрутів дозволяє знизити пробіг автомобілів і вартість експлуатації автопарку, а також поліпшити якість обслуговування клієнтів компанії. У Arclogistics враховуються різні властивості автомобілів, такі як вантажопідйомність, максимальна кількість замовлень, маса, вартість години роботи або кілометра пробігу. Залежно від завдань, можна обирати режим максимальної економії та режим пріоритету своєчасної доставки замовлення. Однієї з найважливіших логістичних завдань є геокодування, тобто пошук на карті точок або відрізка, відповідного до текстової адреси, зазначеної у замовленні. Arclogistics дозволяє максимально автоматизувати цей процес, знизити навантаження на оператора й зменшити час обробки замовлень. Є можливість прив'язки автомобілів до певних зон обслуговування, обліку перешкод на дорогах. Складання маршрутних карт і звітів реалізоване за допомогою програми Crystal Reports, яка дозволяє генерувати звіти на основі запитів до найпоширеніших типів баз даних, у тому числі до баз даних Arcgis. За допомогою стандартних інструментів Crystal Reports користувач може зробити власні шаблони звітів, які потім будуть використовуватися в повсякденній роботі. Arclogistics є самостійним додатком, що не потребує інших програмних продуктів Arcgis.

Система Mapxplus

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

Завдання, що вирішуються системою Mapxplus:

· Планування маршрутів доставки товару з одного або декількох складів на безліч торгівельних точок з мінімальними витратами.

· Робота як централізовано, так і з декількома центрами планування доставок.

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

· Планування роботи як свого автопарку, так і залучених (найманих) транспортних засобів з розрахунками витрат за заданими тарифами.

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

· Підтримка форматів роботи Van-salling та Pre-salling.

· Виявлення торгівельних точок, доставка вантажу в які є невигідною.

Система «Ділова карта»

Ділова карта – система розроблена компанією ІНГИТ.

Можливості системи «Ділова карта»:

Ведення бази даних клієнтів, яка автоматично наноситься на карту за адресами, автоматично сортується за адміністративно-територіальним розподілом й заготовленими довільними зонами (дилерськими кварталами, зонами обслуговування). Технологія прив'язки за адресами забезпечує автоматичний добір адрес, виявлення помилок і видачу рекомендацій.

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

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

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

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

Постановка задачі дослідження

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

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

Таким чином, відстані між об'єктами задаються квадратною матрицею відстаней C = [i, j], розмір якої становить n x n, де C[i, j] – відстань від пункту i до пункту j. Необхідно відзначити, що, у загальному випадку, матриця відстаней не є симетричною (однобічний рух, складні транспортні розв'язки і т.д.)[3].

Постановка завдання виглядає так:

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

· маршрут повинен бути замкненим, тобто автомобіль повинен повернутися на склад;

· у кожній із точок автомобіль повинен побувати точно один раз, тобто треба обов'язково обійти всі точки, при цьому не побувавши в жодній точці двічі.

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

Математична модель завдання

N – кількість точок.

Cij, i, j = 1…N – матриця витрат, де Cij – витрати на перехід з i-ої точки до j-ої.

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

Xij = 1, якщо автомобіль робить перехід з i-ої точки до j-ої,

Xij = 0, якщо не робить переходу,

де i, j = 1…N та i<>j.

Критерій:

, (1)

де Сij – матриця вартості переходів,

Xij – матриця переходів, де xij = 0, якщо перехід був та xij = 1 якщо ні.

Обмеження:

, i = 1...N (2)

, j = 1...N (3)

Ui - Uj + N * Xij <= N-1, i, j = 1...N, i<>j. (4)

Умова (2) означає, що автомобіль із кожної точки виїжджає тільки один раз; умова (3) – в'їжджає в кожну точку тільки один раз; умова (4) – забезпечує замкнутість маршруту, що містить N точок й не містить замкнених внутрішніх петель. На малюнку 1 чорним прямокутником зображено склад, кругами - аптеки по яких треба розвести лiки.

Малюнок 1 – Схема доставки лікарських засобів

Мурашиний алгоритм

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

Малюнок 2 – Схема роботи мурашиного алгоритму

Завдання формулюється як завдання пошуку мінімального за вартістю замкненого маршруту за усіма вершинами без повторень на повному зваженому графові з n вершинами. Змістовно вершини графа – це точки, які повинен відвідати автомобіль, а ваги ребер відображають відстані проїзду. Це завдання є Np-важким, і точний переборний алгоритм її вирішення має факторіальну складність[8].

З урахуванням поставленого завдання правила вибору шляху мурахою описуються наступним способом:

1. Мурахи мають власну «пам'ять». Оскільки кожне місто може бути відвідане лише один раз, то в кожної мурахи є список вже відвіданих міст – список заборон. Позначимо через Jik список міст, які необхідно відвідати мурасі k, що перебуває в місті i.

2. Мурахи мають «зір» – видимість є евристичним бажанням відвідати місто j, якщо мураха перебуває в місті i. Будемо вважати, що видимість обернено пропорційна відстані між містами ηij=1/Dij.

3. Мурахи мають «нюх» – вони можуть вловлювати слід феромона, що підтверджує бажання відвідати місто j з міста i на підставі досвіду інших мурах. Кількість феромона на ребрі (i,j) у момент часу t позначимо через τij(t) .

4. На цій підставі ми можемо сформулювати ймовірнісно-пропорційне правило, що визначає ймовірність переходу k-ої мурахи з міста i до міста j:

, (5)

Де α,β – параметри, що задають ваги сліду феромона. Якщо α = 0 – алгоритм вироджується до жадібного алгоритму (буде обрано найближче місто). Зазначимо, що вибір міста є імовірнісним, правило (5) лише визначає ширину зони міста j; у загальну зону всіх міст Jik кидається випадкове число, яке й визначає вибір мурахи. Правило (5) не змінюється під час роботи алгоритму, але у двох різних мурах значення ймовірності переходу будуть відрізнятися, тому що вони мають різний список дозволених міст.

5. Пройшовши ребро (i,j), мураха відкладає на ньому деяку кількість феромона, яка повинна бути пов'язана з оптимальністю зробленого вибору. Нехай Tk(t)­ – маршрут, що пройшла мураха k до моменту часу t; Lk(t) – довжина цього маршруту, а Q – параметр, що має значення порядку довжини оптимального шляху. Тоді кількість феромона, що відкладається може бути задана у вигляді

, (6)


Правила зовнішнього середовища визначають, у першу чергу, випар феромона. Нехай p = [0,1] – коефіцієнт випару, тоді правило випару має вигляд

,(7)

де m – кількість мурах у колонії.

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

Висновок

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

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

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

1. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. // Высшая школа, М. – 1980, 300 с.

2. Е. П. Липатов. Теория графов и её применения // Знание, М. – 1986, 32 с.

3. Новиков Ф.А. Дискретная математика для программистов // Питер, Санкт-Петербург – 2001, 304 с.

4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ // МЦНМО, М. – 2000, 960 с.

5. Dorigo M., Gambardella L. M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation – 1997, pp. 53-66.

6. Dorigo M., G. Di Caro, Gambardella L. M. Ant Algorithms for Discrete Optimization // Artificial Life – 1999, pp. 137-172.

7. Джонс М.Т. Программирование искусственного интеллекта // ДМК Пресс, М. – 2004, 312 с.

8. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях – 2003, №4, сс.70-75.

9. Чураков Михаил. Муравьиные алгоритмы [электронный ресурс]. – Режим доступа: http://rain.ifmo.ru/cat/data/theory/unsorted/ant-algo-2006/article.pdf

10. Алгоритмы муравьиной колонии [электронный ресурс]. – Режим доступа: http://ru.science.wikia.com/wiki/Алгоритмы_муравьиной_колонии