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

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

Зміст

Введення

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

1. Постановка проблеми

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

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

2. Аналіз літератури

Необхідність такої системи обумовлена спадом обсягів перевезень залізничним транспортом з причини збільшення частки автомобільного транспорту. Раніше розроблені алгоритми Юсіповим Р.А. в дисертації «Прогнозування показників в оперативних планах поїзної і вантажної роботи», Шапкіним І.М. «Організація залізничних перевезень на основі інформаційних технологій», Макаровим В.М. «Розробка та застосування математичної моделі оперативного прогнозування поїзної роботи» і іншими є не ефективними, тому що в них не враховується якість перевізного процесу.[5]

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

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

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

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

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

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

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

Для досягнення зазначених результатів треба вирішити такі задачі:

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

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

ПМайже у кожному місті України існує склад, який використовує деяку кількість транспортних засобів поставки з ідентичною вантажопідйомністю Q. На N станціях є вантаж вагою Р , i . Потрібно скласти маршрути доставки вантажів з одних станцій на інші, при чому вивантаження і дозавантаження можуть здійснюватися на складах по шляху проходження транспортного засобу [8]


Рисунок 4.1 – Приклад рішення задачі оптимального планування маршрутів вантажних перевезень
(анімація: об'єм – 133 КБ, розмір – 600x368, кількість кадрів – 30, затримка між кадрами – 30 мс; затримка між останнім і першим кадрами – 100 мс; кількість циклів повторення – 7)

Дан повний зважений граф з N вершин. Вершинам графа зіставимо станції, на яких є вантаж, ребрам - шляхи, що ведуть від станції до станції, і припишемо їм вартість шляху . Рішення для задачі маршрутизації транспорту може бути представлено у вигляді перевезень всього наявного на всіх станціях вантажу K маршрутами , К --> min [17].

5. Застосування задачі комівояжера

Задача комівояжера (ЗК) - досить стара, вона була сформульована ще в 1759 році (під іншим ім'ям). Термін «Задача комівояжера» був використаний у 1932 р. у німецькій книзі «The traveling salesman, how and what he should to get commissions and be successful in his business», написаної старим комівояжером.

ЗК формулюється як задача пошуку мінімального за вартістю замкнутого маршруту по всіх вершинах без повторень на повному зваженому графі з n вершинами. Змістовно вершини графа є містами, які має відвідати комівояжер, а ваги ребер відображають відстані (довжини) або вартості проїзду. Ця задача є NP-складною, і точний переборний алгоритм її вирішення має факторіальну складність [16].

ЗК є широко відомою задачею оптимізації комбінаторного типу. Вона формулюється наступним образом: дано повний зважений граф G(X, V) порядку n, де X={x ,...,x } – множина вершин; V=X*X- множина ребер, в ньому необхідно знайти цикл Гамильтона, що має найменшу сумарну вагу ребер, що входять до нього [18].

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

Вочевидь, рішенням задачі є перестановка з n вершин, кількість можливих перестановок дорівнює n!, проте кількість різних рішень задачі з урахуванням напрямку обходу та зсуву початкової вершини буде (n-1)!\2 .

ЗЗадача не має алгоритму, що дозволяє знайти рішення за прийнятний час, і вирішується в основному евристичними методами.

6. Застосування мурашиного алгоритму для пошуку оптимального маршруту

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

Опишемо локальні правила поведінки мурах при виборі шляху [16].

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

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

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

Мурахи розміщуються у випадково вибрані міста без збігів. Кожна мураха починає рух зі свого вузла і проходить нові вузли до тих пір, поки всі вузли графа не будуть відвідані. Перебуваючи у вузлі і, мураха ймовірнісно вибирає наступний вузол j з набору допустимих вузлів за правилом, що визначає вірогідність переходу k-ого мурахи з міста i в місто j [16]:

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

Пройшовши ребро (i, j), мураха відкладає на ньому деяку кількість феромону, яка повинна бути пов'язана з оптимальністю зробленого вибору. Нехай Tij(t) є маршрут, пройдений мурахою k до моменту часу t, - довжина цього маршруту, а Q - параметр, що має значення порядку довжини оптимального шляху. Тоді кількість феромону, що відкладається, може бути задана у вигляді [20]:

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

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

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

Додаткова модифікація алгоритму полягає у введенні так званих «елітних» мурах, які посилюють ребра найкращого маршруту, знайденого з початку роботи алгоритму. Позначимо через T* найкращий поточний маршрут, через L* - його довжину. Тоді, якщо в колонії є e елітних мурах, то ребра маршруту отримають додаткову кількість феромону [19]:

7. Застосування генетичного алгоритму для локального пошуку

Генетичні алгоритми використовують принципи й термінологію, запозичені у біологічної науки - генетики. У ГА кожна особина представляє потенційне рішення деякої проблеми. Множина особин, потенційних рішень, становить популяцію. Пошук (суб)оптимального вирішення проблеми виконується в процесі еволюції популяції - послідовного перетворення однієї кінцевої множини рішень в іншу за допомогою генетичних операторів репродукції, кросинговера і мутації. Еволюційні обчислення використовують такі механізми природної еволюції [14]:

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

У генетичному алгоритмі основною проблемою являється вибір способу кодировки рішення оптимізаційної задачі. Прімемо, ОСІБ у популяції являє собою набор генів, номер шкірного Із якіх у рядку відповідає номеру вантажу в портфелі замовлень, а хромосома кодує маршрути обходу станцій. Тоді чисельне значення гена відповідає станції, якій даний вантаж призначається на обслуговування (транспортування). Довжина гена в хромосомі вибирається виходячи з необхідності кодування всіх станцій, а число генів відповідає числу замовлень у портфелі. Так, якщо в системі всього два потяги, то для їх кодування достатньо одного біта: 0 означає перший потяг, а 1 - другий поїзд, і в цьому випадку довжина бінарної рядка-хромосоми дорівнює числу вантажів в портфелі замовлень.

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

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

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

1. Маршрути з обраних особин поєднуємо в одне рішення. Дане рішення назвемо об'єднаним рішенням;

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

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

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

1. обмін: у хромосомі вибирають двох клієнтів і міняють їх. Обрані вузли можуть належати одному і тому ж або різних маршрутах. Якщо новостворене рішення є неприпустимим, то застосовуємо оператор коректування;

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

3. переміщення: вибирають подмаршрут і вставляють його в інше місце. Цей оператор може виконати внутрішнє або зовнішнє переміщення;

4. вторинна вставка маршрутів: з рішення віддаляються маршрути цілком, потім клієнти з віддалених маршрутів заново вставляються в рішення;

5. вторинна вставка клієнтів: з рішення віддаляються окремі клієнти, і потім заново вставляються в маршрут;

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

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

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

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

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

8. Переваги і недоліки мурашиних алгоритмів

Переваги

  1. Для TSP (Traveling Salesman Problem) порівняно ефективні
  2. Для невеликої кількості вузлів TSP може бути вирішена повним перебором
  3. Для великої кількості вузлів TSP обчислювально складна (NP-важка) - експоненціальний час збіжності
  4. Працюють краще, ніж інші глобальні оптимізації для TSP (нейронні мережі, генетичні алгоритми)
  5. Порівняння з GAs (Genetic Algorithms):Спираються на пам'ять про всю колонії замість пам'яті тільки про попередньому поколінні
  6. Менше схильні неоптимальним початковим рішенням (за випадкового вибору шляху і пам'яті колонії)
  7. Можуть використовуватися в динамічних додатках (адаптуються до змін, скажімо, відстаней)
  8. Застосовувалися до безлічі різних завдань

Недоліки:

  1. Теоретичний аналіз утруднений: в результаті послідовності випадкових (не незалежні) рішень, розподіл ймовірностей змінюється при ітераціях
  2. Зазвичай необхідно застосування додаткових методів таких, як локальний пошук
  3. Сильно залежать від настроювальних параметрів, які підбираються тільки виходячи з експериментів[13]

Висновок

У ході роботи була розглянута система здійснення маршрутизації залізничним транспортом.

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

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

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

Список источников

  1. Современные системы планирования и управления транспортом // Склад и Техника. – 2008.
  2. GPS GPRS Слежение. Определение местоположение через спутник.
  3. Васильева Наталья Курьерская почта UPS: быстро и надежно // Бизнес & Балтия. – 2004. – № 222.
  4. Транспортная логистика :: Оптимизация грузоперевозок.
  5. SystemGroup Логистика.
  6. Решение "IT-Box: Грузоперевозки, Логистика, Склад".
  7. Транспортная логистика.
  8. Метод ветвей и границ.
  9. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. — 476 c.
  10. Пушкарёва Г.В. Исследование и применение бионических методов и моделей для автоматизированного проектирования маршрутов обхода геометрических объектов. Компьютерная графика и представление GraphiCon 2005: науч.-техн. конф., 20-24 июня 2005г. : - 2005.
  11. Генетический алгоритм.
  12. Бейсенбек Б.М. Обобщённая задача коммивояжёра для определения рациональных маршрутов поставки.
  13. Glover F. Tabu Search Journal of the Operational Research Society. – 1999. – Vol.50, № 1. – pp. 106–107.
  14. Сухарев А.Г. Курс методов оптимизации: Учебное пособие. - [2-е изд]. – М.: ФИЗМАТЛИТ, 2005. – 368 с.
  15. Муравьиный алгоритм.
  16. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях. - 2003. – № 4. – С. 70-75
  17. Семенюта E.В., Привалов М.В. Применение муравьиных алгоритмов для поиска оптимальных маршрутов грузоперевозок. // Інформаційні управляючі системи та комп'ютерний моніторинг (ІУС та КМ - 2011) / Матеріали II науково-технічної конференції студентів, аспірантів та молодих вчених. — Донецьк, ДонНТУ — 2011. – с. 199-203
  18. Методичні вказівки до виконання лабораторних робіт за курсом “Еволюційні обчислення у технічних задачах” (для студентів спеціальності 7.091503 “Спеціалізовані комп’ютерні системи” (СКС)) / Укл. Ю.О. Скобцов, С.В. Хмільовий, Т. О. Васяєва – Донецьк, 2008. – 91 с.
  19. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации. Учебно-методический материал по программе повышения квалификации «Информационные технологии и компьютерное моделирование в прикладной математике». – Нижний Новгород, 2007. – 85 с.
  20. Семенюта Е.В., Привалов М. В. Применение муравьиных и генетических алгоритмов для решения задачи коммивояжера с ограничениями на направленность маршрута. // Інформатика та комп’ютерні технології / Збірка праць VII міжнародної науково-технічної конференції студентів, аспірантів та молодих науковців – 22-23 листопада 2011 р., Донецьк, ДонНТУ. – 2011. У 2-х томах, Т. 1 – с. 159-163
  21. Gambardella L.M., Dorigo M. HAS-SOP Hybrid Ant System for the Sequential Ordering Problem Technical Report IDSIA 11-97.
  22. Ascheuer N., Escudero L. F., Grotschel M. and Stoer M., 1993, A Cutting Plane Approach to the Sequential Ordering Problem SIAM Journal on Optimization 3, 25–42. – 355 pp.

Зауваження

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