Автоматизована система управління транспортними перевезеннями
Розроблено автоматизовану систему оптимізації вантажних перевезень на транспортній мережі, яку реалізовано у вигляді програмного комп’ютерного комплексу із застосуванням середовища візуального проектування Borland C++ Builder. Програмний комплекс складається з головної форми, з якої завантажуються д...
Saved in:
| Published in: | Системні дослідження та інформаційні технології |
|---|---|
| Date: | 2014 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2014
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/85495 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Автоматизована система управління транспортними перевезеннями / С.С. Забара, M.Т. Дехтярук // Системні дослідження та інформаційні технології. — 2014. — № 2. — С. 18-28. — Бібліогр.: 16 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859643416324866048 |
|---|---|
| author | Забара, С.С. Дехтярук, M.Т. |
| author_facet | Забара, С.С. Дехтярук, M.Т. |
| citation_txt | Автоматизована система управління транспортними перевезеннями / С.С. Забара, M.Т. Дехтярук // Системні дослідження та інформаційні технології. — 2014. — № 2. — С. 18-28. — Бібліогр.: 16 назв. — укр. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Розроблено автоматизовану систему оптимізації вантажних перевезень на транспортній мережі, яку реалізовано у вигляді програмного комп’ютерного комплексу із застосуванням середовища візуального проектування Borland C++ Builder. Програмний комплекс складається з головної форми, з якої завантажуються дві підпрограми. Використовуючи підпрограму «Оптимізація маршрутизації перевезень» проведено пошук оптимальних маршрутів при транспортних перевезеннях вантажів на заданій транспортній мережі за різними схемами (від однієї вершини (постачальника) до всіх інших вершин (споживачів), по черзі від кожної вершини до всіх інших вершин, від двох (або декількох) заданих вершин до всіх інших вершин). За допомогою підпрограми «Оптимізація транспортних перевезень вантажів» виконується оптимізація перевезень вантажів між пунктами постачання та пунктами споживання, з урахуванням обмежень на об’єми вантажів у пунктах відправлення та призначення.
Разработана автоматизированная система оптимизации грузовых перевозок на транспортной сети, которая реализована в виде программного компьютерного комплекса с применением среды визуального проектирования Borland C++ Builder. Программный комплекс состоит из главной формы, из которой загружаются две подпрограммы. Используя подпрограмму «Оптимизация маршрутизации перевозок» проведен поиск оптимальных маршрутов при транспортных перевозках грузов на заданной транспортной сети по разным схемам (от одной вершины (поставщика) ко всем остальным вершинам (потребителям), поочередно от каждой вершины ко всем остальным вершинам, от двух (или нескольких) заданных вершин ко всем остальным вершинам). С помощью подпрограммы «Оптимизация транспортных перевозок грузов» выполняется оптимизация перевозок грузов между пунктами снабжения и пунктами потребления, с учетом ограничений на объемы грузов в пунктах отправления и назначения.
The automated system of optimization of freight traffic on a transport network is developed which is implemented in the form of the software system using the Borland C ++ Builder visual design environment. The software system consists of the main form from which two subroutines are loaded. Using the subroutine “Optimization of routing of transportations” the optimum routes for transporting the cargo are searched on the given transport network using different schemes (from one vertex (the supplier) to all other vertices (the consumers), successively from each vertex to all other vertices, from two (or several) specified vertices to all other vertices). The subroutine “Optimization of transport transportations of cargoes” performs the optimization of transportations of cargoes between the points of supply and consumption, taking into account restrictions on volumes of cargoes in departure and destination points.
|
| first_indexed | 2025-12-07T13:25:02Z |
| format | Article |
| fulltext |
С.С. Забара, М.Т. Дехтярук, 2014
18 ISSN 1681–6048 System Research & Information Technologies, 2014, № 2
TIДC
ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ,
ВИСОКОПРОДУКТИВНІ КОМП’ЮТЕРНІ
СИСТЕМИ
УДК 004.94(045)
АВТОМАТИЗОВАНА СИСТЕМА УПРАВЛІННЯ
ТРАНСПОРТНИМИ ПЕРЕВЕЗЕННЯМИ
С.С. ЗАБАРА, М.Т. ДЕХТЯРУК
Розроблено автоматизовану систему оптимізації вантажних перевезень на
транспортній мережі, яку реалізовано у вигляді програмного комп’ютерного
комплексу із застосуванням середовища візуального проектування Borland
C++ Builder. Програмний комплекс складається з головної форми, з якої заван-
тажуються дві підпрограми. Використовуючи підпрограму «Оптимізація марш-
рутизації перевезень» проведено пошук оптимальних маршрутів при транспорт-
них перевезеннях вантажів на заданій транспортній мережі за різними схемами
(від однієї вершини (постачальника) до всіх інших вершин (споживачів), по чер-
зі від кожної вершини до всіх інших вершин, від двох (або декількох) заданих
вершин до всіх інших вершин). За допомогою підпрограми «Оптимізація
транспортних перевезень вантажів» виконується оптимізація перевезень ван-
тажів між пунктами постачання та пунктами споживання, з урахуванням об-
межень на об’єми вантажів у пунктах відправлення та призначення.
ВСТУП
Транспорт є однією з найважливіших галузей економіки України. Від стабіль-
ної й ефективної роботи транспорту значною мірою залежить добробут на-
селення, розвиток національної економіки та безпека держави. Транспорт
належить до галузі виробництва матеріальних послуг. З урахуванням провід-
ної ролі транспорту в ринковій економіці, управління транспортом виділя-
ється в окремий блок, який має назву транспортна логістика [1, 2].
Транспортна логістика включає в себе низку елементів, основними
з яких є: вантаж; пункти зосередження вантажу; транспортна мережа; рухо-
мий склад; навантажувально-розвантажувальні засоби; учасники логістич-
них процесів; тара та пакування. Основні резерви вдосконалення транспорт-
ного логістичного процесу знаходяться в раціональній організації взаємодії
учасників ланцюга доставки, у погодженні їх інтересів та пошуку взаємови-
гідних та придатних рішень [2, 3].
Для аналізу й проектування логістичних транспортних систем застосо-
вують методологічні принципи, основними з яких є [3]:
Системний підхід — всі елементи логістичної системи розглядають-
ся як взаємопов’язані та взаємодіючі для досягнення єдиної цілі управління.
Отже, застосування системного підходу передбачає оптимізацію функціону-
вання не окремих елементів, а логістичної системи в цілому.
Автоматизована система управління транспортними перевезеннями
Системні дослідження та інформаційні технології, 2014, № 2 19
Принцип глобальної оптимізації — оптимізація структури логістич-
ної системи потребує узгодженості локальних цілей функціонування елемен-
тів (ланок) системи з метою досягнення глобального оптимуму.
Принцип моделювання та інформаційно-комп'ютерної підтримки —
використання різних моделей: математичних, економіко-математичних,
графічних, фізичних, імітаційних тощо.
Аналіз останніх наукових публікацій показує, що проблемам оптиміза-
ції транспортних логістичних систем приділяється значна увага, як в нашій,
вітчизняній, так і в зарубіжній науковій літературі [4–11]. Так, в роботах
[4–8] розглядаються проблеми оптимізації маршрутизації та переміщення
вантажопотоків аналітичними методами; в роботі [9] — моделювання
транспортно-складської системи на основі теорії масового обслуговування;
в роботі [10] використовуються методи моделювання логістичних транспорт-
них систем на основі нечіткої логіки; в роботі [11] — на основі генетичних
алгоритмів.
В цих роботах використовуються різні аналітичні методи оптимізації
режимів роботи транспортних логістичних систем на основі теорії масового
обслуговування, нечіткої логіки та генетичних алгоритмів, або аналітичні
методи носять узагальнюючий характер.
Прогрес інформаційних технологій та інформаційних систем дав змогу
значно підвищити ефективність транспортної логістики, а інформаційно-
комп’ютерна підтримка посіла належне місце серед ключових логістичних
функцій.
ПОСТАНОВКА ЗАВДАННЯ
Ефективним способом проектування та дослідження транспортних логістич-
них процесів є комп’ютерне моделювання [12]. Комп’ютерні моделі явля-
ють собою програму, яка крок за кроком відтворює події, що відбуваються
в реальній системі. Перевагою таких моделей є можливість підміни процесу
зміни подій у досліджуваній системі в реальному масштабі часу на приско-
рений процес зміни подій у темпі роботи програми. У результаті за кілька
хвилин можна відтворити роботу системи протягом певного часу (декількох
днів, тижнів, місяців), що дає можливість оцінити роботу системи, яка до-
сліджується в широкому діапазоні змінюваних параметрів.
Для створення комп’ютерних моделей використовуються як універсальні
системи програмування — Visual C++, Borland C++ Builder, Delphi, так і спе-
ціалізовані системи, розроблені спеціально для побудови алгоритмів моде-
лювання: GPSS, SIMSCRIPT, SIMULA, SIMPLE++ тощо [12]. У цих систе-
мах передбачаються засоби автоматичного керування послідовністю змін
(подій) у моделі, динамічного розподілу даних у пам’яті, необхідного для
побудови складних моделей, стандартні програми статистичної обробки
результатів моделювання (накопичення і виводу гістограм, середніх значень
випадкових величин, їхніх дисперсій тощо).
Мета роботи — використання сучасних комп’ютерних інформаційних
технологій для моделювання й оптимізації режимів роботи транспортних
логістичних систем. За допомогою системи візуального проектування
Borland C++ Builder розроблено автоматизовану систему оптимізації вантаж-
них перевезень на транспортній мережі, яка здійснює процедуру пошуку
С.С. Забара, М.Т. Дехтярук
ISSN 1681–6048 System Research & Information Technologies, 2014, № 2 20
найкоротших відстаней та визначення оптимальних обсягів перевезень на
заданій транспортній мережі.
МАТЕМАТИЧНА МОДЕЛЬ ЗАДАЧІ ТРАНСПОРТНИХ ПЕРЕВЕЗЕНЬ
Для знаходження самого економічного плану перевезення вантажів у транс-
портній логістиці застосовуються спеціалізовані методи, ефективніші, ніж
методи, призначені для розв’язання загальних задач лінійного програмуван-
ня. Серед цих методів ключове місце займає маршрутизація транспортних
перевезень (транспортна задача (ТЗ)), яка належить до класу задач лінійного
програмування
Класичне формулювання ТЗ виглядає так: у m пунктах відправлення
(виробництва чи видобування) (ПВ) ),,,( 21 mAAA знаходиться, відповід-
но, maaa ,,, 21 одиниць однорідного (або взаємозамінного) вантажу (ре-
сурсу), який потрібно доставити в n пунктів призначення (споживання)
(ПП) ),,,( 21 nBBB в необхідній кількості nbbb ,,, 21 одиниць. Позначимо
через ia — запаси вантажу в i-му пункті відправлення ПВ ,iA через jb —
потреби у вантажі в j-му пункті призначення ПП ,jB через ijx — кількість
одиниць вантажу, який перевозиться з пункту iA у пункт ,jB а ijc — тари-
фи (вартість) перевезень одиниці вантажу з і-го пункту відправлення в j-й
пункт призначення [13, 14]. Математична модель транспортної задачі запи-
сується в такий спосіб.
Визначити значення функції мети:
min
1 1
ij
n
j
m
i
ij xcZ (1)
за умов-обмежень:
).,1(
);,1(
1
1
njbx
miax
j
m
i
ij
i
n
j
ij
(2)
При цьому необхідно, щоб перевезення були невід’ємними:
).,1;,1(0 njmixij (3)
Функція мети Z є загальною вартістю всіх перевезень. Її записано у вигля-
ді подвійної суми. Внутрішня сума відповідає пунктам виробництва, а зов-
нішня — пунктам споживання.
Перевезти вантаж потрібно таким чином, щоб задовольнити всі замов-
лення, при цьому критерієм оптимальності є мінімальна вартість, або міні-
мальний час його доставки.
ТЗ можуть бути двох типів:
закритого типу (коли сумарний обсяг вантажу в усіх ПВ дорівнює
сумарному обсягу споживання в усіх ПП):
Автоматизована система управління транспортними перевезеннями
Системні дослідження та інформаційні технології, 2014, № 2 21
.
1 1
m
i
n
j
ji ba (4)
відкритого типу (коли сумарний обсяг вантажу в усіх ПВ не дорів-
нює сумарному обсягу споживання в усіх ПП):
m
i
n
j
ji ba
1 1
або
m
i
n
j
ji ba
1 1
. (5)
Під час розв’язання ТЗ, як правило, задачі відкритого типу зводяться до
ТЗ закритого типу. Існують два найбільш відомі методи зведення відкритих
ТЗ до збалансованого виду:
введення додаткового (фіктивного) ПВ або ПП вантажу;
зменшення обсягу попиту (пропозиції) на величину невідповідності
в одному з ПП (ПВ).
Далі задачі розв’язуються методами, розробленими для закритих
транспортних задач.
Транспортна задача, як відомо, є комбінаторною, або NP-повною зада-
чею, точне рішення якої через факторіальний ріст числа необхідних опера-
цій у багатьох випадках вимагає підключення надпотужних комп’ютерних
засобів. Тому існують десятки наближених методів рішення задачі обмеже-
ної розмірності ( m та n — кілька десятків об’єктів).
На практиці, як правило, реальні транспортно-логістичні структури
формуються за територіально-виробничими принципами і обмежуються де-
кількома суміжними районами або областями, на території яких розміщу-
ються виробники та споживачі певної продукції або ресурсів, як правило це
декілька десятків об’єктів. Тому, запропоновану автоматизовану систему
оптимізації вантажних перевезень на транспортній мережі розраховано на
розв’язування саме таких транспортних задач середньої складності.
ОПТИМІЗАЦІЯ МАРШРУТИЗАЦІЇ ТРАНСПОРТНИХ ПЕРЕВЕЗЕНЬ
Особливої уваги заслуговує така транспортна задача, в якій необхідно міні-
мізувати час виконання заданих обсягів робіт. Критерієм розв’язування та-
ких ТЗ може бути час, оскільки у певних життєвих ситуаціях, таких як прак-
тичне планування перевезень, необхідно звести до мінімуму загальний час
перевезень, а не транспортні витрати на перевезення. Цей критерій часто
використовується під час виконання сільськогосподарських робіт, переве-
зенні сировини та продукції, яка швидко псується тощо.
Оптимальним планом для такої ТЗ буде план, згідно з яким весь вантаж
від ПВ до ПП буде доставлено якнайшвидше. Тобто потрібно розподілити
поставки (перевезення) таким чином, щоб час найдовшого перевезення був
мінімальним. За умови, що всі перевезення розпочнуться одночасно (з неве-
ликою похибкою), то план перевезень буде виконано за час, який дорівнює
найдовшому перевезенню.
Задачі про найкоротші шляхи належать до фундаментальних задач
комбінаторної оптимізації тому, що багато з них можна звести до пошуку
найкоротшого шляху на мережі [14, 15]. Існують різні типи задач про най-
коротший шлях:
між двома заданими вершинами;
С.С. Забара, М.Т. Дехтярук
ISSN 1681–6048 System Research & Information Technologies, 2014, № 2 22
між даною вершиною і всіма іншими;
між кожною парою вершин у мережі;
між двома заданими вершинами для шляхів, що проходять через од-
ну або кілька зазначених вершин;
перший, другий, третій тощо, найкоротші шляхи в мережі.
На сьогодні алгоритмів пошуку оптимального рішення ТЗ розроблено
досить багато, але практично на увагу заслуговують лише кілька з них, зок-
рема відомі алгоритми Дейкстри та Флойда [16].
Метод Дейкстри шукає найкоротший шлях від заданої вершини (дже-
рела) до всіх інших вершин на графі. Метод Флойда шукає найкоротший
шлях по черзі від кожної вершини до всіх інших і цим же він відрізняється
від Дейкстри. Матричний метод дуже схожий з методом Флойда, він дозво-
ляє знайти матрицю D, елементи якої будуть рівні мінімальним величинам
маршрутів, а також знайти відстань з кожної вершин в саму себе.
Транспортна задача значно ускладнюється у виробничо-транспортних
економічних системах, які виробляють сировину і продукцію в широкому
асортименті на декількох незалежних ПВi, а для перевезення їх використо-
вуються різні види транспорту. При цьому слід зауважити, що на практиці
перевезення можуть здійснюватися як безпосередньо від постачальників до
споживачів, так і через декілька проміжних пунктів, створюючи складні
транспортні комунікації.
ТЗ у такому трактуванні належать до класу мережевих задач. Інтерпре-
тація ТЗ у мережевій формі дає можливість врахувати пропускну спромож-
ність окремих ділянок транспортної мережі. У мережевій формі легше врахо-
вувати навантаження та розвантаження на проміжних станціях, кожна з яких
розглядається як вузол.
Слід також зауважити, що розв’язання мережевих ТЗ безпосередньо на
топології транспортної мережі не дозволяє здійснювати алгоритмізацію та
подальшу автоматизацію пошуку оптимального плану перевезень на базі
сучасної комп’ютерної техніки.
При цьому доцільніше подавати мережеву ТЗ у матричному вигляді,
що дозволяє здійснити алгоритмізацію пошуку оптимального рішення.
У роботі запропоновано метод мінімізації матричної форми мережевих ТЗ,
що значно спрощує процедуру розв’язання мережевих ТЗ великої розмірно-
сті і зменшує обсяги необхідних обчислювальних операцій.
Для розв’язання цієї задачі розглянуті алгоритми не можуть бути засто-
совані, оскільки алгоритм Дейкстри недостатній (за ним знаходимо лише
один рядок із матриці найкоротших відстаней), а алгоритм Флойда надлишко-
вий (генерує матрицю найкоротших відстаней між будь-якими ПВi та ППj).
Запропоновано більш економний та ефективний метод розв’язання ме-
режевих ТЗ великої розмірності, які поєднують методи рішення класичної
ТЗ у матричній формі з модифікацією відомого методу Дейкстри для знахо-
дження найкоротших відстаней у мережі сполучень між ПВі та ППj , заданій
у вигляді графу. Саме це поєднання дозволяє здійснити чітко визначену ал-
горитмізацію мережевої ТЗ і застосувати для її розв’язання сучасні
комп’ютерні технології.
Модифікація алгоритму Дейкстри полягає у включенні до нього впоряд-
кованої системи перебору вершин-постачальників ,)(m з одного боку, та
Автоматизована система управління транспортними перевезеннями
Системні дослідження та інформаційні технології, 2014, № 2 23
вершин-користувачів ,)(n з другого. Тобто ми додаємо два вкладені цикли:
перебір усіх постачальників, як вершину mV та усіх користувачів, як верши-
ну .nV Завдяки цьому можна знайти найкоротші шляхи від кожного поста-
чальника до кожного користувача і визначити вартісні характеристики пере-
везень безпосередньо від ПВi до ППj, враховуючи проміжні вузли.
ОПТИМІЗАЦІЯ ТРАНСПОРТНИХ ПЕРЕВЕЗЕНЬ ВАНТАЖІВ
Оптимізація транспортних перевезень вантажів починається з побудови
опорного (базисного) плану, який у подальшому покращується з метою одер-
жання оптимального плану перевезень, застосовуючи один зі стандартних
методів знаходження оптимальних планів перевезень.
Серед багатьох методів побудови опорних планів уваги заслуговують
три з них — це методи північно-західного кута (через свою простоту), най-
меншого елемента в усій транспортній таблиці (через свою економічність)
і апроксимації Фогеля (через свою результативність) [13, 14].
Побудову опорного плану за методом північно-західного кута почина-
ють із заповнення лівої верхньої клітинки таблиці ,)( nx в яку записують
менше з двох чисел 1a та .1b Далі переходять до наступної клітинки в рядку
або у стовпчику і заповнюють її тощо. Закінчують заповнювати таблицю у пра-
вій нижній клітинці.
Ідея методу мінімальної вартості полягає в тому, що на кожному кроці
заповнюють клітинку таблиці, яка має найменшу вартість перевезення оди-
ниці продукції. Такі дії повторюють доти, доки не буде розподілено всю
продукцію між постачальниками та споживачами.
Метод апроксимації Фогеля. За цим методом на кожному кроці визна-
чають різницю між двома найменшими вартостями в кожному рядку і стовп-
чику транспортної таблиці. Ці різниці записують у спеціально відведених
місцях таблиці. Серед усіх різниць вибирають найбільшу, і у відповідному
рядку або стовпчику заповнюють клітинку з найменшою вартістю. Якщо
ж однакових найбільших різниць кілька, то вибирають будь-який відповід-
ний рядок або стовпчик. Коли залишається незаповненим лише один рядок
або стовпчик, то обчислення різниць припиняють, а таблицю продовжують
заповнювати за методом мінімальної вартості.
Отриманий опорний план транспортної задачі необхідно привести до
оптимального плану перевезень. Існує кілька методів оптимізації ТЗ, а точ-
ніше приведення до оптимального плану перевезень складеного раніше
опорного плану. Всі вони дають одинакові результати. Застосувавши до
отриманого опорного плану один із стандартних методів знаходження оп-
тимальних планів перевезень (симплексний, розподільний, метод потенціа-
лів, метод диференціальних рент), можна одержати оптимальний план пере-
везень [13, 14].
Процес роботи більшості методів оптимізації ТЗ базується на побудові
замкнутих контурів для перерозподілу вантажопотоків. Найпоширенішим
методом для оптимального розв’язування ТЗ є метод потенціалів, так як він
не вимагає складання збільшеної кількості додаткових таблиць з оцінками
комірок, а помилка у попередніх розрахунках виправляється на наступних
С.С. Забара, М.Т. Дехтярук
ISSN 1681–6048 System Research & Information Technologies, 2014, № 2 24
кроках. Метод потенціалів дозволяє, виходячи з деякого опорного плану,
побудувати за кінцеве число ітерацій оптимальний план перевезень.
Кількість ітерацій, необхідних для розв’язання ТЗ методом потенціалів,
суттєво залежить від первинного плану. Вдалий вибір методу побудови опор-
ного плану може значно зменшити кількість ітерацій і тим самим прискори-
ти процес рішення задачі. Тому дуже важливо мати досить простий метод,
який найчастіше дозволяє будувати план близький до оптимального.
СТРУКТУРА ПРОГРАМНОГО КОМПЛЕКСУ
Алгоритми оптимізації маршрутизації, які розглянуто, та вантажних переве-
зень на транспортній мережі реалізовано у вигляді програмного комп’ютерного
комплексу, який дає змогу автоматизувати процедуру пошуку найкоротших
відстаней між заданими множинами вершин у мережі та визначення опти-
мальних обсягів перевезень на заданій транспортній мережі.
Комплекс розроблено із застосуванням середовища візуального проек-
тування Borland C++ Builder — графічної автоматизованої оболонки над
об’єктно-орієнтованою мовою програмування C++. Середовище проекту-
вання Borland C++ Builder містить у собі повний набір візуальних інструмен-
тів для швидкісної розробки додатків, що підтримує розробку інтерфейсу
користувача і підключення до корпоративних баз даних.
Програмний комплекс складається з головної форми, з якої завантажу-
ються дві підпрограми.
Оптимізація маршрутизації перевезень. На рис. 1 показано орієнто-
ваний граф транспортної мережі, на якій виконується пошук оптимальних
маршрутів під час транспортних перевезень вантажів за різними схемами
(від однієї вершини (постачальника) до всіх
інших вершин (споживачів), по черзі від ко-
жної вершини до всіх інших вершин, від
двох (або декількох) заданих вершин до всіх
інших вершин). При цьому перевезення ван-
тажів можуть здійснюватися як безпосеред-
ньо від постачальників до споживачів, так
і через один або декілька проміжних пунктів.
Вершинами на графі позначено пункти
відправлення та призначення. З’єднані дуга-
ми вершини відповідають пунктам, які ма-
ють транспортне сполучення. Числа, що зна-
ходяться біля кожної дуги, відповідають
відстаням між даними пунктам (у. о.).
Вікно підпрограми для визначення оп-
тимальних маршрутів транспортних перевезеннях вантажів за різними схе-
мами показано на рис. 2. Оптимізація маршрутизації перевезень виконується
наступним чином. Спочатку вводиться кількість існуючих вершин графа.
Потім у «Таблицю відстаней» (рис. 2) заносяться початкові дані, тобто від-
стані, у вигляді матриці, між пунктами, що мають сполучення між собою.
Слід зауважити, що введення початкових даних можливе безпосередньо
у матрицю або програмним способом, шляхом попереднього внесення даних
Рис. 1. Граф транспортної ме-
режі для визначення оптималь-
них маршрутів
Автоматизована система управління транспортними перевезеннями
Системні дослідження та інформаційні технології, 2014, № 2 25
у програму і занесенні їх у матрицю перевезень, натискаючи на кнопку
«Початкові дані».
Пошук найкорот-
ших маршрутів, за від-
повідними алгоритма-
ми [16], відбувається,
натискаючи на кнопки
«Дейкстра», «Флойд»,
«Мод. Дейкстра», «Мат-
ричний». Якщо розраху-
нки виконуються мето-
дом «Мод. Дейкстра»,
пункти 1, 2 приймають-
ся як пункти відправ-
лення, а пункти 3, 4, 5,
6 — як пункти призна-
чення. Виведення кін-
цевих результатів роз-
рахунків виконується у
таблицю «Найкоротші
маршрути».
Натискаючи на
кнопку «Очистити» відбувається очищення даних, занесених у таблицю
«Найкоротші маршрути». Форма з графом маршрутів перевезень (рис. 1)
виводиться при натисканні на кнопку «Граф». Кнопка «Вихід» завершує
роботу цієї підпрограми.
Результати розрахунку найкоротших маршрутів, виконано за різними
алгоритмами (див. табл.).
Т а б л и ц я . Методи розрахунку найкоротших маршрутів
Методи розрахунку
Дейкстри Флойда Модифікований
Дейкстри
1021
3031
70431
605631
40631
1021
1021
70431
60521
40631
46012
8032
120432
5052
90632
46013
46023
4043
30563
1063
46014
46024
46034
80564
6064
46015
46025
46035
7045
130645
46016
46026
46036
90456
2056
3031
70431
60521
40631
8032
120432
5052
90632
Рис. 2. Вікно підпрограми для визначення оптимальних
маршрутів
С.С. Забара, М.Т. Дехтярук
ISSN 1681–6048 System Research & Information Technologies, 2014, № 2 26
З таблиці видно, що результати розрахунку найкоротших маршрутів
між відповідними вершинами, які одержано різними методами, співпадають.
Так, розрахунок оптимальних маршрутів між вершиною 1 та всіма іншими
вершинами, одержано різними методами, дають одинакові результати. Ре-
зультати розрахунку найкоротших маршрутів між вершинами 1, 2 та всіма
іншими вершинами, одержані методом Флойда та модифікованим методом
Дейкстри, також співпадають.
Оптимізація транспортних перевезень вантажів. На рис. 3 показано
неорієнтований граф транспортної мережі, на якій виконується оптимізація
перевезень вантажів між пунктами відправлення та пунктами призначення,
з урахуванням обмежень на об’єми вантажів у пунктах відправлення та
призначення.
Граф на рис. 3 відображає
шляхи сполучення між пункта-
ми відправлення та призначен-
ня. Всю множину його вершин
розбито на дві підмножини. До
першої підмножини вершин
відносяться пункти відправлення
,)( iA а до другої підмножини
— пункти призначення .)( jB
Вершини, з’єднані ребрами,
відповідають пунктам, між яки-
ми існують шляхи сполучення.
Вартості транспортування між
відповідними пунктами проста-
влено біля кожного ребра (у.о.). Об’єми постачання проставлено у вершинах
пунктів відправлення, а об’єми споживання — у вершинах пунктів призна-
чення (у.о.).
Необхідно відшукати найкоротші маршрути транспортування між пунк-
тами відправлення і призначення, включаючи рух через проміжні пункти
(ними можуть бути як пункти відправлення, так і пункти призначення). Роз-
рахунки проводяться з використанням математичної моделі транспортної
задачі (1)–(4). Критерієм оптимальності є мінімальна вартість перевезень.
На рис. 4 показано результати розрахунку оптимізації перевезень ван-
тажів між пунктами відправлення та пунктами призначення на транспортній
мережі зображено на рис. 3.
Оптимізація транспортних перевезень вантажів виконується наступним
чином. Натискаючи на кнопку «Початкові дані» заповнюються таблиці «Вар-
тості перевезень C», тобто вартості перевезень між пунктами, що мають
сполучення між собою, дані про постачальників «Постачальники A» —
об’єми вантажів у пунктах постачання, та споживачів «Споживачі B» — по-
треби у вантажах у пунктах споживання. При цьому також можливе введення
початкових даних безпосередньо у матрицю, або програмним способом,
шляхом попереднього внесення даних у програму і занесенні їх у матрицю
перевезень при натисканні на кнопку «Початкові дані».
Далі необхідно натиснути кнопку «Найкоротші маршрути» для визна-
чення найкоротших маршрутів між пунктами постачання та споживання, які
виконуються за модифікованим методом Дейкстри та заносяться в «Транс-
портну таблицю».
Рис. 3. Граф транспортної мережі, на якій
виконується оптимізація перевезень вантажів
Автоматизована система управління транспортними перевезеннями
Системні дослідження та інформаційні технології, 2014, № 2 27
Побудова опорного плану виконується методом найменшого (мінімаль-
ного) елемента таблиці, натискаючи на кнопку «Опорний план». Внаслідок
чого дані виводяться у «Таблицю перевезень», а в поле таблиці «Найкорот-
ші маршрути» виводяться найкоротші маршрути, які одержано модифікова-
ним методом Дейкстри.
Оптимізація одержаного опорного плану перевезень виконується мето-
дом потенціалів, на-
тискаючи на кнопку
«Оптимізація». Резуль-
тати оптимізації виво-
дяться у «Таблицю пе-
ревезень» (рис. 4).
Компоненти Label
служать для виводу
цільової функції на
кожній ітерації та для
інформування користу-
вача про знаходження
оптимального плану
перевезень відповідно.
Кнопки «Очисти-
ти», «Граф» та «Ви-
хід», які розміщено на
цій формі, мають ана-
логічне призначення.
ВИСНОВКИ
В роботі розроблено автоматизовану систему оптимізації вантажних переве-
зень на транспортній мережі у вигляді програмного комп’ютерного комплек-
су із застосуванням середовища візуального проектування Borland C++
Builder — графічної автоматизованої оболонки над об’єктно-орієнтованою
мовою програмування C++. Програмний комплекс складається з головної
форми, з якої завантажуються дві підпрограми.
Використовуючи підпрограму Оптимізація маршрутизації переве-
зень проведено пошук оптимальних маршрутів транспортних перевезень
вантажів на заданій транспортній мережі за різними схемами (від однієї вер-
шини (постачальника) до всіх інших вершин (споживачів), по черзі від кож-
ної вершини до всіх інших вершин, від двох (або декількох) заданих вершин
до всіх інших вершин). При цьому перевезення вантажів можуть здійснюва-
тися як безпосередньо від постачальників до споживачів, так і через один
або декілька проміжних пунктів.
За допомогою підпрограми Оптимізація транспортних перевезень
вантажів виконується оптимізація перевезень вантажів між пунктами по-
стачання та пунктами споживання, з урахуванням обмежень на об’єми ван-
Рис. 4. Вікно підпрограми для оптимізації транспортних
перевезень вантажів
С.С. Забара, М.Т. Дехтярук
ISSN 1681–6048 System Research & Information Technologies, 2014, № 2 28
тажів у пунктах відправлення та призначення. Критерієм оптимальності є міні-
мальна вартість перевезень.
ЛІТЕРАТУРА
1. Бакаєв О.О., Кутах О.П., Пономаренко Л.А. Теоретичні засади логістики:
Підручник. У 2-х т. — К.: Фенікс, 2005. — 951 с.
2. Логистика автомобильного транспорта: Учеб. пособие / В.С. Лукинский,
В.И. Бережной, Е.В. Бережная и др. — М.: Финансы и статистика, 2004. — 368 с.
3. Смирнов І.Г., Косарева Т.В. Транспортна логістика: Навч. посібник. — К.:
Центр учбової літератури, 2008. — 224 с.
4. Eksioglu B., Vural A.V., Reisman A. The vehicle routing problem: A taxonomic review
// Computers & Industrial Engineering. — 2009. — 57, № 4. — P. 1472–1483.
5. Dabia S., Ropke S., Van Woensel T. Branch and cut and price for the time dependent
vehicle routing problem with time windows // Transportation Science. — 2010. —
361, № 11. — P. 56–62.
6. Холоденко А.М., Горб О.С. Рівноваги виробничо-транспортної системи зі
зворотним завантаженням контейнерів // Методи та засоби управління
розвитком транспортних систем: Зб. наук. праць. — Одеса: ОНМУ. —
2011. — Вип.17. — С. 183–199.
7. Ляшенко Н.И. Создание временных шлюзов 2-го порядка в логистической цепи
поставок // Методи та засоби управління розвитком транспортних систем:
Зб. наук. праць. — Одеса: ОНМУ. — 2009. — Вип.15. — С. 54–69.
8. Kholodenko A., Gorb O. Supply chain equilibriums under non-linear cost functions
of participants // Montenegrin journal of economics. — 2010. — № 6. — P. 5–8.
9. Кічкіна О.І. Моделювання поведінки транспортно-складської системи // Вісник
Східноукраїнського національного університету ім. В. Даля. — Луганськ:
СУНУ. — 2012. — № 6 (177). — Ч. 1. — С. 312–314.
10. Дудукалов Ю.В. Применение методов нечеткого моделирования для оптимизации
транспортных систем // Вісник СевНТУ: Серія: Машиноприладобудування та
транспорт. — Севастополь. — 2011. — Вип. 122/2011. — С. 61–64.
11. Hosny M.I., Mumford C.L. Investigating genetic algorithms for solving the multiple
vehicle pickup and delivery problem with time windows // Metaheuristic Interna-
tional Conference, MIC-2009. — 2009. — P. 36–39.
12. Томашевский В.Н. Моделювання систем. — К.: Видавнича група BHV, 2007. — 352 с.
13. Зайченко Ю.П. Дослідження операцій. Підручник, вид. 8. — К.: Вид. дім «Сло-
во», 2010. — 816 с.
14. Ржевський С.В., Александрова В.М. Дослідження операцій: Підручник. — К.:
Академвидав, 2006. — 560 с.
15. Пападимитриу С., Стайглиц К. Комбинаторная оптимизация. Алгоритмы
и сложность: Пер. с англ. — М.: Мир, 1985. — 325 с.
16. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы.: Пер. с англ. —
М.: Изд. дом «Вильямс», 2001. — 384 с.
Надійшла 26.06.2013
|
| id | nasplib_isofts_kiev_ua-123456789-85495 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Ukrainian |
| last_indexed | 2025-12-07T13:25:02Z |
| publishDate | 2014 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Забара, С.С. Дехтярук, M.Т. 2015-08-06T19:26:39Z 2015-08-06T19:26:39Z 2014 Автоматизована система управління транспортними перевезеннями / С.С. Забара, M.Т. Дехтярук // Системні дослідження та інформаційні технології. — 2014. — № 2. — С. 18-28. — Бібліогр.: 16 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/85495 004.94(045) Розроблено автоматизовану систему оптимізації вантажних перевезень на транспортній мережі, яку реалізовано у вигляді програмного комп’ютерного комплексу із застосуванням середовища візуального проектування Borland C++ Builder. Програмний комплекс складається з головної форми, з якої завантажуються дві підпрограми. Використовуючи підпрограму «Оптимізація маршрутизації перевезень» проведено пошук оптимальних маршрутів при транспортних перевезеннях вантажів на заданій транспортній мережі за різними схемами (від однієї вершини (постачальника) до всіх інших вершин (споживачів), по черзі від кожної вершини до всіх інших вершин, від двох (або декількох) заданих вершин до всіх інших вершин). За допомогою підпрограми «Оптимізація транспортних перевезень вантажів» виконується оптимізація перевезень вантажів між пунктами постачання та пунктами споживання, з урахуванням обмежень на об’єми вантажів у пунктах відправлення та призначення. Разработана автоматизированная система оптимизации грузовых перевозок на транспортной сети, которая реализована в виде программного компьютерного комплекса с применением среды визуального проектирования Borland C++ Builder. Программный комплекс состоит из главной формы, из которой загружаются две подпрограммы. Используя подпрограмму «Оптимизация маршрутизации перевозок» проведен поиск оптимальных маршрутов при транспортных перевозках грузов на заданной транспортной сети по разным схемам (от одной вершины (поставщика) ко всем остальным вершинам (потребителям), поочередно от каждой вершины ко всем остальным вершинам, от двух (или нескольких) заданных вершин ко всем остальным вершинам). С помощью подпрограммы «Оптимизация транспортных перевозок грузов» выполняется оптимизация перевозок грузов между пунктами снабжения и пунктами потребления, с учетом ограничений на объемы грузов в пунктах отправления и назначения. The automated system of optimization of freight traffic on a transport network is developed which is implemented in the form of the software system using the Borland C ++ Builder visual design environment. The software system consists of the main form from which two subroutines are loaded. Using the subroutine “Optimization of routing of transportations” the optimum routes for transporting the cargo are searched on the given transport network using different schemes (from one vertex (the supplier) to all other vertices (the consumers), successively from each vertex to all other vertices, from two (or several) specified vertices to all other vertices). The subroutine “Optimization of transport transportations of cargoes” performs the optimization of transportations of cargoes between the points of supply and consumption, taking into account restrictions on volumes of cargoes in departure and destination points. uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Автоматизована система управління транспортними перевезеннями Автоматизированная система управления транспортными перевозками The automated control system of freight traffic Article published earlier |
| spellingShingle | Автоматизована система управління транспортними перевезеннями Забара, С.С. Дехтярук, M.Т. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| title | Автоматизована система управління транспортними перевезеннями |
| title_alt | Автоматизированная система управления транспортными перевозками The automated control system of freight traffic |
| title_full | Автоматизована система управління транспортними перевезеннями |
| title_fullStr | Автоматизована система управління транспортними перевезеннями |
| title_full_unstemmed | Автоматизована система управління транспортними перевезеннями |
| title_short | Автоматизована система управління транспортними перевезеннями |
| title_sort | автоматизована система управління транспортними перевезеннями |
| topic | Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| topic_facet | Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85495 |
| work_keys_str_mv | AT zabarass avtomatizovanasistemaupravlínnâtransportnimiperevezennâmi AT dehtârukmt avtomatizovanasistemaupravlínnâtransportnimiperevezennâmi AT zabarass avtomatizirovannaâsistemaupravleniâtransportnymiperevozkami AT dehtârukmt avtomatizirovannaâsistemaupravleniâtransportnymiperevozkami AT zabarass theautomatedcontrolsystemoffreighttraffic AT dehtârukmt theautomatedcontrolsystemoffreighttraffic |