Пристрій для моделювання та оптимізації трас

Корисна модель належить до засобів електронного моделювання та спеціалізованої аналого-цифрової обчислювальної техніки. Пристрій призначено для пошуку оптимального за декількома критеріями маршруту (траси) на графі, який відображає топологічні та геодезичні характеристики мережі доріг, телекомунікацій, комунікацій загального призначення тощо, та має початкову і кінцеву точки руху по трасі. Кожне ребро графа має нелінійні фізичні і геометричні характеристики за довжиною і характеризується багатьма критеріями. Причому, одні характеристики траси бажано звести до мінімуму (вартість землі під будівництво траси, довжина траси, витрати палива, амортизація техніки при русі по траси), а інші до максимуму (швидкість руху, пріоритетність по додатковому бізнесу та розвитку схеми доріг). Останнє вимагає, як правило, зведення загального критерію до одного виміру, наприклад, коштовності, або енергетичних витрат. Відома цифрова електронна модель графа, яка базується на елементах І, причому кожний елемент І відображає ребро графу, а вершини графу відображаються контактними площадками, з'єднаними у відповідності з заданою топологією графу та з визначеними входами елементів І. [Авт.св. СССР №1086434. Устройство для разбиения графа / В.М. Глушань, В.М. Курейчик, Л.И. Щербаков. Опубл. 1968, Бюл.№7]. Недоліком цього пристрою є те, що по-перше для кожного нового графу необхідно синтезувати відповідну цифрову електронну модель графу, а по-друге електронна модель графа не дозволяє здійснити оптимізацію траси за декількома критеріями, які мають різний фізичний та геометричний сенс і супротивні за метою. Найбільш близьким до пропонованого за сукупністю ознак є пристрій для оптимізації маршруту при техногенній катастрофі, який містить струмовводи, регульовані джерела електрорушійної сили, діоди, джерело струму, суматори, блок завдання граничних умов, R-сітку, перша група входів якої підключена до групи виходів блоку струмовводів, друга група входів R-сітки підключена до блоку завдання граничних умов, групи входів кожного суматора з'єднано з вузловими точками R-сітки, через які проходить відповідне ребро графу, вихід кожного суматора підключено до перших входів відповідних кожному ребру послідовно з'єднаних й зустрічно направлених регульованих джерел електрорушійної сили, які з'єднано з відповідними діодами, виходи яких підключено до вузлових точок графу, а до початкової та кінцевої точок маршруту, що відповідають вершинам графу, підключається джерело струму одиничної величини [Патент Україна №47961 А. Пристрій для оптимізації маршруту при техногенній катастрофі / В.П. Путятін, К.М. Коба (Україна). Опубл. 15.07.2002. Бюл. №7]. Недоліком цього пристрою є те, що він не дозволяє здійснити оптимізацію траси за декількома критеріями, які мають різний фізичний та геометричний сенс і супротивні за метою. В основу корисної моделі поставлено задачу створення пристрою з розширеними функціональними можливостями для багатокритеріального моделювання та оптимізації графу, кожне ребро якого характеризується декількома ваговими значеннями. Крім того, необхідно урахувати той факт, що ребра графу мають нелінійні фізичні характеристики за довжиною та за геометричною формою. Такого технічного результату можна досягнути, якщо у пристрій для оптимізації маршруту при техногенній катастрофі, який містить діоди, джерело струму, регульовані джерела електрорушійної сили, причому, кожне ребро графу моделюється чарунками, які являють собою два паралельних й зустрічно направлених ланцюжка, кожний з яких містить послідовно з'єднані між собою джерело електрорушійної сили та зустрічно направлений діод, виходи відповідних моделей ребер підключено до вузлови х точок графу, а до початкової та кінцевої точок графу, що відповідають його вершинам, підключається джерело струму одиничної величини, згідно з корисною моделлю введені блок введення інформації, перша група блоків обчислення, друга група блоків обчислення, цифро-аналогові перетворювачі, дешифратор, блок розрахунку функції мети, блок реєстрації, перший вхід якого підключено до першого виходу деши фратора, а другий вхід блоку реєстрації з'єднано з виходом блоку розрахунку функції мети, перший вхід якого є другим виходом дешифратора, другий вхід блоку розрахунку функції мети є першим виходом блоку введення інформації, перший вихід якого також підключено до першого входу дешифратора, кожний вхід другої гр упа входів дешифратора підключено до відповідних виходів чарунок ребер графу, кожний вихід цифро-аналогових перетворювачів підключено до відповідних кожному ребру регульованих джерел електрорушійної сили, входи кожного цифро-аналогового перетворювача підключені до кожного входу другої гр упи блоків обчислення, входи другої гр упи блоків обчислення з'єднані з виходами першої групи блоків обчислення, групи входів яких є ви ходами блоку введення інформації. Позитивним технічним результатом є те, що використання у пристрої, блоків, які виконують нормування та перехід до однакових одиниць виміру коефіцієнтів ваги кожного ребра графу, а також здійснюють згортання коефіцієнтів ваги ребер графа до одного, дає змогу одержати узагальнену вагу ребра графа та перейти до завдання необхідних параметрів для аналогової моделі відповідного графу. Все це дозволяє здійснити пошук оптимальної траси на графі. При пошукові в патентній та науково-технічній літературі не виявлені об'єкти з ознаками, подібними до характерних ознак технічного рішення за даним винаходом, на підставі чого можна зробити висновок про відповідність його критерію "суттєві відмінності". На Фіг.1 приведено зображення графа, у якому вершинами є точки А та В між якими здійснюється пошук оптимальної траси. На Фіг.2 приведено пристрій, який складається з наступних стандартних блоків: блок 1 введення інформації; однотипні блоки 2 обчислення; однотипні блоки 3 обчислення; цифро-аналогові перетворювачі 4; регульовані джерела 5 електрорушійної сили; діоди 6; джерело 7 струму; деши фратор 8; блок 9 розрахунку функції мети; блок 10 реєстрації. Блоки 2 та 3 обчислення реалізують стандартну процедуру приведення до єдиної шкали виміру коефіцієнтів ваги кожного ребра, їх нормування та згортання до одного загального значення ваги кожного ребра [Нагірний П.Ю. Обгр унтування інженерних рішень. - К.: Урожай, 1994. - 216с]. Пояснимо роботу пристрою. Ставиться за мету, наприклад, пошук оптимальної траси, яка з'єднає точки А та В (Фіг.1). У якості загального критерію пошуку такої траси з множини можливих, є, наприклад, мінімізація витрат на побудову або експлуатацію траси, яка з'єднає точки А та В (Фіг.1). Кожне ребро i, j (Фіг.1) графу характеризується кортежем коефіцієнтів ваги ребра. Причому, коефіцієнти мають різну фізичну природу, наприклад, довжина ребра, вартість землі під будівництво траси, вартість прокладки траси, швидкість та витрати палива при русі по ребру траси, амортизація техніки при русі по ребру траси, пріоритетність по додатковому бізнесу та розвитку схеми доріг, тощо. Ця інформація вводиться блоком 1 введення інформації до блоків 2 обчислення, які виконують перехід до однакових одиниць виміру та нормування коефіцієнтів ваги кожного ребра графу. Далі інформація поступає до блоків 3 обчислення, які здійснюють згортання коефіцієнтів ваги ребер графа до одного. Після цього цифро - аналогові перетворювачі 4 ставлять у відповідність узагальненим вагам ребер графу - аналогові величини, які надходить до аналогової моделі графу, а саме до відповідних регульованих джерел 5 електрорушійної сили. Завдяки регульованим джерелам 5 електрорушійної сили, діодам 6 та джерелу 7 струму, одержуємо перерозподіл електричних величин у моделі графу. При цьому стр ум пройде по тим ребрам графу, сума значень напруги джерел 5 електрорушійної сили яких буде мінімальна. За додатковою інформацією з блоку 1 введення інформації про загальну структур у графу, деши фратор 8 встановлює ці оптимальні ребра та відповідну трасу. Після чого блоком 9 розрахунку функції мети розраховується оптимальне значення функції мети, яке реєструється блоком 10 реєстрації та з дешифратора 8 реєструється відповідна оптимальна траса. За рахунок запропонованої апаратурної реалізації алгоритму розв'язання задач пошуку оптимальної траси, витрати часу, у порівнянні з витратами часу на ПЕОМ, скорочуються у зв'язку з відсутністю етапу створення відповідного програмного забезпечення. Скорочення часу розв'язання задач оптимізації на пристрої також забезпечується паралельним виконанням окремих етапів алгоритму, наприклад, нормування та перехід до однакових одиниць виміру коефіцієнтів ваги кожного ребра графу (блок 2) та згортання коефіцієнтів ваги ребер графа до одного (блок 3) виконується паралельно для кожного ребра графу. Загальний час розв'язання задач оптимізації, у порівнянні з ПЕОМ, скорочується за рахунок застосування аналогових блоків, де моделювання процесів у графі здійснюється практично миттєво, а витрати пам'яті в основному залежать від кількості ребер графу та кількості компонент у кортежі, що характеризує вагу ребра. Точність розв'язання задач оптимізації за допомогою пристрою залежить від точності аналогових блоків, точності вихідних даних та точності виконання обчислювальних операцій цифровими блоками 2 та 3.