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

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

Вступ

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

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

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

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

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

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

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

Основні завдання дослідження:

  1. Провести аналіз існуючих алгоритмів, методів і технологій вирішення транспортної задачі;
  2. Розробити математичну модель перевезення вантажів транспортними засобами з урахуванням обмежень на безліч різних пунктів вантаження і різну вантажопідйомність транспортних засобів;
  3. Розробити модифікований алгоритм вирішення транспортної задачі з урахуванням перерахованих вище обмежень;
  4. Експериментально перевірити ефективність роботи алгоритму.

3. Огляд досліджень і розробок

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

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

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

  1. алгоритм повного перебору;
  2. метод гілок і меж;
  3. метод послідовної сепарації.

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

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

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

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

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

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

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

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

  1. BV – метод;
  2. метод включення дальнього;
  3. метод імітації відпалу;
  4. метод найближчого сусіда;
  5. нейронні мережі.

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

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

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

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

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

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

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

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

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

  1. модифікатор Згладжування;
  2. модифікатор Передача;
  3. модифікатор Інверсний перехід;
  4. модифікатор Інверсний перенесення.

3.3 Алгоритми пошуку

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

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

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

Генетичні алгоритми є найбільш оптимальними серед пошукових в плані співвідношення час / якість і можуть бути распараллеліть [8].

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

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

3.4 Узагальнені результати

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

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

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

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

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

  1. Мурашина логістика

    2. Мурашина логістика – онлайн сервіс для розрахунку оптимальних маршрутів доставки. Сервіс надається для безкоштовного використання на пробний період, після чого вимагає покупки ліцензії для використання, при цьому кількість точок в маршруті може бути обмежена в залежності від типу ліцензії, а кількість маршрутів в день обмежена незалежно від типу ліцензії [9].

  2. ePROMIS Transportation & Logistics

    3. Transportation & Logitics є продуктом компанії ePROMIS, яка спеціалізується на розробці і впровадженні хмарних програмних рішень для автоматизації управління всіма ділянками ланцюжка поставок: запасами, транспортом. Програма Transportation & Logitics спеціалізується на побудові оптимальних маршрутів доставки товару [10].

    Система Transportation & Logitics є платною і не надає демо – версії для ознайомлення.

  3. Gensoft Logistics ERP

    4. Gensoft Logistics – це сервіс управління транспортною логістикою для компаній, чий бізнес пов’язаний з доставкою вантажів. Сервіс дозволяє створювати оптимальні маршрути і ефективно планувати завантаження водіїв і кур’єрів. Сервіс є безкоштовним тільки для некомерційного використання. В іншому випадку вартість використання обговорюється при складанні договору [11].

  4. Interlogis ILS – Online

    5. ILS – Online – це веб – орієнтована система управління логістикою. Вона автоматично розподіляє роботу між виконавцями і планує оптимальні маршрути для доставки точно в строк і з мінімальними витратами. З її допомогою користувач має можливість контролювати і при необхідності коректувати рух співробітників в режимі реального часу [12].

5. Опис завдання оптимізації шляху

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

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

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

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

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

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

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

6. Математична постановка задачі

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

Цільова функція для всієї системи визначається за формулою 1.

Формула (1) (1)

де Ci – вартість перевезення вантажу i – м автомобілем на одиницю відстані, Li – сумарна довжина маршруту, по якому їде i – ї автомобіль.

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

Формула (2) (2)

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

Також необхідно врахувати наступні додаткові обмеження:

  1. вантажопідйомність автомобілів різна
  2. пунктів відправки автомобілів кілька
  3. кожен вантаж може бути перевезений тільки одним автомобілем
  4. пункти вивантаження різні для кожного вантажу

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

Висновки

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

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

Було виконано опис роботи транспортної компанії, представлене у вигляді схеми інформаційно – матеріальних потоків.

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

Зауваження

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

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

  1. Гарнов, А. П. Инструментарий логистики: учебник / А. П. Гарнов, Н. С. Киреева – М.:Креативная экономика, 2009. – 310 с.
  2. Товстик Т.М. Алгоритм приближенного решения задачи коммивояжера / Т.М. Товстик, Е.В. Жукова // Вестник СПбГУ. Серия 1. Математика. Механика. Астрономия. – СПБ:СПбГУ, 2013. – с. 101-106.
  3. Курейчик В.М. Генетический алгоритм решения логистической задачи / В.М. Курейчик, А.А. Рокотянский // Известия ЮФУ. Технические науки. – Таганрог:ТРТУ, 2012. – №136 –c. 245-251.
  4. Александрова О.А. Оптимизация грузовых перевозок с использованием генетических алгоритмов / О.А. Александрова, А.И. Секирин // Информатика и компьютерные технологии – 2009 №5, – Донецк: ДонНТУ, с. 237–244.
  5. Борознов В.О. Исследование эвристического метода решения задачи коммивояжера / В.О. Борознов // Электронный научный журнал ИССЛЕДОВАНО В РОССИИ. – Москва:МФТИ, 2008. – с. 322-328.
  6. Haroun S.A. A Performance Comparison of GA and ACO Applied to TSP / S.A. Haroun, B. Jamal, E.H. Hicham // International Journal of Computer Applications. – 2015. – vol.117 – pp. 28–35.
  7. Савкин В.Ю. Анализ методов решения задачи коммивояжера / В.Ю. Савкин, В.А. Светличная, Радзывыло К.Г. // Материалы IX Международной научно-технической конференции. – Донецк: ДонНТУ, 2018. – с.183–188.
  8. Скобцов Ю.А. Основы эволюционных вычислений. Донецк: ДонНТУ, 2008. – 326 с.
  9. Автоматизация транспортной логистики – онлайн сервис для планирования оптимальных маршрутов доставки [Электронный ресурс] – Режим доступа: https://ant-logistics.com/
  10. Transportation management software – ePROMIS ERP [Электронный ресурс] – Режим доступа: https://www.epromis.net/industries/transportation-logistics
  11. Gensoft – Logistics Software Provider [Электронный ресурс] – Режим доступа: http://www.gensoft.lk/
  12. Interlogis – Logistics Solutions for Business [Электронный ресурс] – Режим доступа: https://interlogix.com/
  13. Семенкина, О.Е. Effectiveness Comparison of Ant Colony and Genetic algorithms for solving combinatorial optimization problems // Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева. – 2012. – №1. – С.96-97.