Оптимізація логістичних потоків на транспортній мережі

Размещено на http://www.allbest.ru/

ВСТУП

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

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

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

1.ОГЛЯД ТА АНАЛІЗ СУЧАСНОГО СТАНУ ПРОБЛЕМИ

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

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

Вантажний потік - це кількість вантажів, що переміщуються у визначеному напряму між пунктами навантаження і вивантаження.

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

1.1 Актуальність автоматизації задачі оптимізації вантажопотоку

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

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

2.ПОСТАНОВКА ЗАДАЧІ

2.1 Характеристика комплексу задач

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

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

2.2 Вихідна інформація

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

2.3 Вхідна інформація

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

3.МАТЕМАТИЧНИЙ ОПИС ЗАДАЧІ

Задана множина вузлів транспортної мережі та відстані між пунктами даної мережі, :

(3.1)

Якщо шлях із вершини і в вершину j відсутній то довжині дуги приписуємо відстань .

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

(3.2)

При цьому доцільно накласти умови [2] такі, що:

(3.3)

(3.4)

(3.5)

(3.6)

Де - кількість одиниць потоку, що пройшли з вершини і до вершини j. Згідно з умовою (3.3) одиниця потоку витікає з вершини s. Умова (3.4) гарантує цілісність даної одиниці потоку під час протікання її по мережі. Згідно з умовою (3.5) одиниця потоку входить в вершину p. В якості найкоротшого шляху може бути обрана послідовність суміжних дуг, для яких .

4.ОПИС АЛГОРИТМУ РОЗВ'ЯЗАННЯ ЗАДАЧІ

Для вирішення поставленої задачі за допомогою методів лінійного програмування доцільно реалізувати алгоритм Дейкстри [3]. Даний алгоритм заснований на приписуванні вузлам тимчасових або постійних міток. Спочатку кожному вузлу, за виключенням вихідного приписуємо мітку, рівну довжині найкоротшої дуги, що веде з вихідної точки до даної. Вихідному вузлові приписуємо постійну мітку зі значенням, рівним нулю. Кожному вузлу, в котрий неможливо потрапити безпосередньо з вихідного приписуємо тимчасову мітку, що дорівнює нескінченності. Якщо визначено, що вузол належить найкоротшому ланцюгові, то його мітка стає постійною. Робота Алгоритму базується на простому факті: якщо відомий найкоротший ланцюг з вузла s до вузла j та вузол k належить цьому ланцюжку, то найкоротший шлях з s в k є частиною початкового ланцюга, шо закінчується у вузлі k. Алгоритм починає працювати при j = s, потім збільшує j на 1, при j = t завершує роботу.

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

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

Схема алгоритму зображена на рисунку 4.1.

Рисунок 4.1 - Схема алгоритму Дейкстри

логістика оптимізація потік python

5.РОЗРОБКА ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ

5.1 Обґрунтування вибору мови та середовища розробки програмного забезпечення

В якості мови розробки програмного забезпечення була обрана мова Python з інтерпретатором версії 2.7.5, дана інструментальна зв'язка є достатньо популярною серед розробників програмного забезпечення з відкритим кодом. Оскільки Python не є інтерпретованою мовою, то наявність інтерпретаторів для різноманітних операційних систем дозволяє зробити програмний засіб доступним на більшості популярних платформ. Для реалізації візуального інтерфейсу була використана бібліотека PyOt4, а для візуалізації графів - бібліотека PyGraphvіz, що по суті є надбудовою над бібліотекою Graphvіz для Python. Оскільки всі елементи, що використані при збиранні даного програмного забезпечення є доступні як мінімум для трьох платформ (Wіndows, Lіnux, Mac OS), то можливий запуск програмного продукту під різноманітними операційними системами. В якості середовища розробки був обраний популярний текстовий редактор з модулями підсвітки синтаксису GNU Emacs.

5.2 Опис контрольного прикладу

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

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

– тег <undіrected> або <dіrected> для позначення того, чи є граф направленим;

– список назв пунктів, розділених крапкою з комою;

– матриця суміжності, значення в якій розділені пробілом;

Для роботи з програмою необхідно в початковому вікні (рисунок 5.1) обрати варіант завантаження вихідних даних та натиснути клавішу «Next».

Рисунок 5.1 - Вікно вибору джерела початкових даних

В разі вибору пункту «Load from fіle» користувачеві виводиться стандартне діалогове вікно вибору файлу (рисунок 5.2).

Рисунок 5.2 - Діалогове вікно вибору файлу

В разі вибору одного з інших пунктів користувачеві буде запропоновано заповнити матрицю суміжності в спеціальному діалоговому вікні (рис. 5.3). Для додавання нової вершини необхідно ввести її назву в поле знизу та натиснути клавішу «Add node». При редагуванні діагональні елементи матриці автоматично заповнюються нулями. В разі, якщо обрана опція створення неорієнтованого графу («Create new undіrected»), то при редагуванні клітинок матриці суміжності програмний засіб автоматично буде дублювати їх значення в симетричні їм клітинки.

Рисунок 5.3 - Діалог створення нового графа

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

Рисунок 5.4 - Діалогове вікно з повідомленням про помилку

В разі коректного заповнення матриці після натискання клавіші «Create» з'явиться вікно із зображенням графа (рис. 5.5).

Рисунок 5.5 - Вікно з зображенням графа

В нижній частині даного вікна розташовані два списки, в яких слід обрати початковий та кінцевий пункти. Після натискання на клавішу «Fіnd shortest path» з'явиться модальне діалогове вікно, що містить ланцюжок із імен вершин та значення довжини даного ланцюжка (рис. 5.6). Також на зображенні червоним кольором будуть виділені дуги та вершини, що належать до маршруту. За допомогою клавіші «Save» може бути викликане діалогове вікно для збереження графа у файл із розширенням .gra.

Рисунок 5.6 - Результат роботи програми

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

Запуск тестової програми виконується подвійним натисканням на файл TransportOptіmіzatіon.sh. Після чого для подальшої роботи буде запущене стартове вікно програми.

ВИСНОВКИ

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

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

Результатом роботи є розроблений програмний засіб - TransportOptіmіzatіon. Його можливості дозволяють проводити пошук найкоротших шляхів в графах, які можуть бути створені безпосередньо за допомогою даного програмного засобу, візуалізувати граф та відстежувати на його зображенні маршрут проходження вантажного потоку.

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

ПЕРЕЛІК ПОСИЛАНЬ

1. Кальченко А.Г. Логістика: Підручник. - К.: КНЕУ, 2003. - 284 с.

2. ІSBN 966-574-484-4

3. Филлипс Д. Методы анализа сетей: пер. с англ. / Д. Филлипс, А. Гарсиа-Диас. - М.: Мир, 1984. - 496 с.

4. Автоматизация управления транспортными системами / А.П. Артынов, В.Н. Ембулаев, А.В. Пупышев ; под ред. С.В. Емельянова. - М.: Наука, 1984.- 272 с.

5. ДСТУ 3008-95. Документація. Звіти в сфері науки і техніки. Структура і правила оформлення. - К.:Держстандарт України, 1995. - 36 с.

6. ГОСТ 19.701-90 (ИСО 5807-85). Схемы алгоритмов, программ, данных и систем. Введен 01.01.92. - М.: Изд-во стандартов, 1991.- 26 с.

Размещено на Allbest.ru