1 Засади удосконалення пасажирських перевезень
Невпинно зростаюча мобільність населення України, переформатування управлінських зв’язків між різними галузями суспільного виробництва
пред’являють пiдвищенi вимоги щодо побудови маршрутних систем, та до якостi планування і управлiння ними. В цих умовах, як показує вiтчизняний та
зарубiжний досвiд, найважливiшим напрямком ефективностi функцiонування систем пасажирського транспорту є науково-технічне обґрунтування їх
оптимальної побудови. Комплексно розглянемо та охарактеризуємо перелік проблем раціональної побудови маршрутних систем, а саме: методи збору i
обробки iнформацiї про пасажиропотоки, моделювання системи пасажирського транспорту мiст, а також методи, моделi i програмне забезпечення
маршрутизацiї перевезень пасажирiв.
Практика останнiх рокiв довела необхiднiсть одночасного розгляду транспортної системи ззовнi, як єдиного цiлого з вивченням тiльки входiв i
виходiв системи, як взаємозалежностi (макропiдхiд) i її внутрiшньої структури з вивченням її елементiв i зв'язку мiж ними (мiкропiдхiд). Сьогодні математичне
моделювання розвиває новий пiдхiд – iмiтацiйне моделювання, яке орiєнтоване на вивчення складних систем. Галузь використання цього методу – дослiдження систем, складених iз великогої кількості взаємодiючих об'єктiв.
Передбачається, що дослiдник здатний скласти алгоритм функцiонування кожного об’єкту. Цей алгоритм i набiр змiнних, що характеризують стан об'єкту, є математичною моделлю об’єкту. Вона реалiзується у виглядi програми i структури даних в пам'ятi ЕОМ.
Імiтацiйне моделювання – це вiдтворення на ЕОМ складного динамiчного процесу з наступним аналiзом чисельностi варiантiв його ходу, і в загальному
випадку воно містить наступні основнi етапи :
- постановка задачi i визначення мети експерименту. При цьому встановлюється характер маршрутної системи, основнi обмеження, показники
ефективностi тощо;
- вивчення системи. Виявлення основних джерел можливої iнформацiї щодо структури системи та її внутрiшнiх зв’язків. Hа цьому етапi також
визначаються вимоги до структури iнформацiйного забезпечення та засоби доступу до неї;
- формування математичної моделі. При цьому виділяються головнi i виключаються з розгляду другоряднi фактори та ознаки;
- планування програмно-машинного експерименту. Модель адаптується до виду, зручного для програмування. Вона будується у виглядi графiкiв,
рiвнянь, схем; формуються вимоги до структури програмного забезпечення.
- машинний експеримент, який на сукупностi реальних даних перевiряє адекватнiсть математичної моделi реальнiй системi. Формуються висновки по
результатах експерименту, уточнюється або змiнюється модель системи.
Iмiтацiйне моделювання зводить задачу дослiдження системи до програмної реалiзацiї варiантiв на ЕОМ. Це дозволяє значно скоротити витрати
щодо дослідження системи, систематизувати вивчення. Застосування методу iмiтацiї для вирiшення широкого класу формалiзованих задач практично не має
обмежень i при наявностi технiчних засобiв стримується тiльки труднощами реалiзацiї машинної програми.
Дослiдження транспортної системи мiста базується на iнформацiї про структуру та iнтенсивнiсть пасажиропотокiв : рухомiсть населення;
кореспонденцiї пасажиропотокiв за трудовими та культурно-побутовими цілями мiж транспортними районами; розмiри пасажиропотокiв за перiодами
доби, часу початку i закiнчення перiоду пiк; накопичення пасажирiв на зупинках i в пересадочних вузлах.
Для вирiшення задач побудови маршрутних систем мiст потрiбнi звiтнi данi технiко-експлуатацiйних та економічних показників роботи міського та
приміського пасажирського транспорту: транспортне районування мiста; схема транспортної i маршрутної мережi мiста; схема мiських магiстралей i вулично-
дорожної мережi; парк транспортних засобів (ТЗ) перевізника i показники, які характеризують регулярнiсть руху ТЗ.
Так як відбувається динамічна змiна структури пасажироперевезень, важливе мiсце займає отримання достовiрної iнформацiї для моделювання МПТ
при вирiшеннi задач побудови маршрутних систем. В зв’язку з цим виникає необхiднiсть у розробцi розрахункового методу обробки iнформацiї про
пасажиропотоки.
Розглянемо аналiз методiв збору та обробки iнформацiї про пасажиропотоки. Успiшне вирiшення питань, пов’язаних з рацiональною
побудовою маршрутних систем в мiстах, ускладнено тим, що сьогодні майже не проводиться систематичне вивчення пасажиропотокiв. Пасажиропотоки
змiнюються за своєю структурою в часi та в просторi, за спрямуванням та інтенсивністю зростання, утворюючи відповідні стiйкi пiкові спади за годинами
доби, днями тижня та сезонами року. Тому одним з найважливiших питань органiзацiї перевезень пасажирським транспортом в мiстах є моделювання
пасажиропотокiв, з метою коригування дiючих мереж маршрутiв і бiльш повного задоволення попиту населення на перевезення, ефективного
використання транспорту, що і складає основу побудови маршрутних систем міст.
Як показує досвiд, єдиним джерелом iнформацiї, що досить повно характеризує параметри транспортного попиту i умови його задоволення в
рамках дiючої системи, є рiзнi методи транспортних обстежень населення.
Тiльки обробка матерiалiв цих обстежень дозволяє отримати комплекс таких показникiв, як розмiр i спрямування пасажиропотокiв, величина витрат часу на
транспортнi перемiщення в цiлому i за складовими (пiшохiдний пiдхiд до зупинки, відхід від зупинки, очікування транспорту), кiлькiсть перевезень тощо.
Аналiз таких показникiв дозволяє об’єктивно оцiнити характер функцiонування iснуючої системи транспортного обслуговування i виявити її недолiки. Hа основi цього можуть бути розробленi конкретнi заходи з поліпшення обслуговування населення за рахунок iнформацiйного забезпечення таких транспортно-експлуатацiйних задач, як коригування роботи транспортних засобів мiж маршрутами, регулювання їх випуску на маршрути тощо.
Hаукова систематизацiя методiв транспортних обстежень населення мiст за найбiльш фундаментальними ознакам (об’єм i структура початкової i
кiнцевої iнформацiї, методи її отримання i обробки, а також характер практичного використання), які є цiльовим призначенням обстежень, дозволяє
класифiкувати їх на два великих класи: обстеження транспортних потреб населення i обстеження транспортного обслуговування населення. В
запропонованiй класифiкацiї звертає на себе увагу розподiл всіх видiв обстежень на два великих класи в залежностi вiд цiлей, які переважають при
використанні їх результатiв. До першого вiднесенi тi види, якi пов’язанi з обстеженням транспортних потреб населення, до другого – ті, якi пов’язанi з
обстеженням дiючої системи його транспортного обслуговування, тобто, що проводяться безпосередньо на маршрутах пасажирського транспорту.
Обстеження транспортних потреб населення дають свiдчення про закономiрностi i особливостi формування та прояву транспортного попиту. В
даний клас входять обстеження: розселення; рухомостi; вiдвiдування закладiв обслуговування; причини змiна мiсця роботи або проживання; бюджету часу та
інше.
Обстеження транспортного обслуговування населення надають iнформацiю про рiвень задоволення транспортного попиту населення на
маршрутній системi, що функцiонує.
Щодо отримання iнформацiї про пасажиропотоки на маршрутах в мiстах iснують рiзнi методи проведення їх обстежень. Звiтно-статистичний (квитковий) метод полягає в обробцi даних про кiлькiсть проданих квиткiв i дає уявлення про змiну обсягiв добових перевезень пасажирiв за маршрутами.
Вiзуальний (окомiрний) метод полягає в приблизному визначеннi наповнення транспортних засобiв на перегонах. Оцiнка наповнення ТЗ проводиться кондукторами, водiями або спецiальними облiковцями. В основi даного методу оцiнки наповнень транспортних засобiв лежить, як правило, бальна система, тобто встановлюється визначена шкала наповнень i у вiдповiдностi до неї реєструється приблизна кiлькiсть пасажирiв в транспортних засобах, що обстежуються.Можливi й iншi варiанти органiзацiї вiзуальних обстежень, зокрема
силуетний метод.
Табличний метод (облiк пасажирiв, якi входять i виходять на зупинках). При даному методі обстеження пасажиропотокiв в подальшiй обробцi матерiалiв обстеження отримують точну i значну iнформацiю про характеристику пасажиропотокiв, але при цьому вiдсутнi вiдомостi про кореспонденцiї пасажирiв між зупинками.
Як показує практика, при вдосконаленні органiзацiї пасажирських, а також при побудові маршрутних систем, табличний метод є найбiльш ефективним.
Талонний метод обстеження пасажиропотокiв базується на реєстрацiї облiковцями зупинок посадки i висадки кожного пасажира. Для цього всiм
пасажирам видаються спецiальнi талони з пронумерованими зупинками посадки, а потiм цi талони збираються при виходi пасажирiв з пронумерованими зупинками виходу. Таким чином, талонний метод дозволяє визначити кiлькiсть пасажирiв, що проїхали між зупинками, а отже, виявити розподiл перевезених пасажирiв за довжиною поїздки на маршрутах.
Анкетний метод передбачає опитування пасажирiв шляхом заповнення анкет про мету i характер перемiщення. Він призначений в основному для
вирiшення питань, якi торкаються реконструкцiї iснуючих або проектування нових транспортних мереж.
На сьогодні накопичений великий досвiд маршрутних обстежень, який дозволяє оцiнити позитивнi i негативнi аспекти кожного з використаних методiв. В оцiнцi цих методiв враховується: все бiльш широке використання інформаційних технологій при обробцi результатiв обстеження, можливiсть оптимiзувати сам процес проведення обстеження, розробку математичних моделей, якi дозволяють з достатньою точнiстю отримати розрахунковим шляхом характеристики пасажиропотокiв на маршрутах.
А тому, найбiльш перспективним вважається табличний метод обстеження пасажиропотокiв. Технологiя проведення табличного обстеження в порiвняннi з талонним має наступні переваги: вiдсутнiй прямий контакт обліковця з пасажирами, що зменшує кiлькiсть помилок i втрат iнформацiї; є можливiсть залучати до дослiдження обліковців з мiнiмальною попередньою пiдготовкою; спрощена попередня обробка i систематизацiя початкової iнформацiї перед введенням в ЕОМ i скорочено час, потрiбний на її обробку; зменшено кiлькiсть бланкiв, необхiдних для збору початкової iнформацiї тощо.
Основним недолiком табличного методу в порiвняннi з талонним вважається неможливiсть отримання матрицi кореспонденцiй поїздок пасажирiв на маршруті. В даний час є розробки [13, 79], якi показують можливiсть в результатi обробки матерiалiв табличного методу обстеження розрахунковим методом одержувати елементи матрицi кореспонденцiй пасажирiв на маршруті.
Протягом багатьох рокiв у вiтчизнянiй та зарубiжнiй практицi ведуться роботи з автоматизацiї обстеження пасажиропотокiв. Аналiз iснуючих методiв
оцiнки завантаження транспортних засобiв за допомогою автоматизованих засобів збору вихідної інформації можна роздiлити на дискретний i iнтегральний.
Дискретний метод передбачає пiдрахунок кожного пасажира в салонi ТЗ i є натуральною замiною ручного рахунку.
Iнтегральний метод заснований на зважуваннi ТЗ разом з пасажирами i переводу всiєї маси пасажирiв в їх кількості.
Зараз опрацьовано деякі методи автоматизованого обстеження, за якими технiчнi засоби дозволяють фiксувати iнформацiю щодо кількості пасажирiв,
якi входять i виходять на кожнiй зупинцi.
Автоматизованi методи вивчення пасажиропотокiв дозволяють розробити такi АСУ МПТ, за допомогою яких автоматизується метод збору вихідних
даних та проводиться фiксування їх на промiжний інформаційний носiй або безпосередньо на магнiтну стрiчку, що дозволяє прискорити збір та обробку
iнформацiї про пасажиропотоки. При необхiдностi інформація про вхiд та вихiд пасажирiв може бути передана в реальному масштабi часу безпосередньо в
диспетчерський центр для обробки на ЕОМ i використання в системi оперативного управлiння. Цей метод цiлковито вiдповiдає умовам використання в АСУ МПТ. Аналогічні системи використовуються за кордоном (Стокгольм, Роттердам, Цюрiх, Гамбург, Париж, Чiкаго тощо).
В Україні набуває широкого впровадження застосування спрощеної системи обліку пасажирів з метою виявлення недоотримання перевізником грошових надходжень від перевезень. Як приклад, можна навести систему «Відео-Кондуктор» завдяки якій об’єктивно можна обраховути кількості
пасажирів, що сплачують за проїзд в транспортних засобах. На рисунку представлена функціональна схема системи обліку та оплати проїзду на маршрутах транспорту загального користування, до якої входять: відеореєстратор – пристрій для відеоспостереження та моніторингу оплати проїзду; DVR – високошвидкісний процесор, що вбудований в Linux платформу, яка дозволяє використовувати сучасну технологію стиснення відео H.264; запис на SD-карту 4-х канального відео і аудіо в форматах СІФ, HD1 і d1; «чорний ящик», що захищений від вібрації автомобіля та впливу зовнішнього навколишнього середовища.
Рисунок 1.21 – Функціональна схема системи обліку та оплати проїзду на
маршрутах транспорту загального користування «Відео-Кондуктор»
Перспективним збором початкової iнформацiї є облiк пасажирiв, якi заходять та виходять, на першому етапi з використанням облiковцiв, а в наступному – з застосуванням технiчних засобiв. Подальшi дослiдження побудови маршрутних систем міст повиннi бути спрямованi на розробку нових методiв, алгоритмiв i програм для обробки початкової iнформацiї про пасажиропотоки за допомогою ЕОМ з отриманням матрицi кореспонденцiй пасажирiв, результатiв аналiзу роботи всього маршруту i т.п.
Для вирiшення транспортно-експлуатацiйних задач (таких як вибiр звичайних, експресних, маршрутно-таксомоторних режимів руху, побудови графiків руху ТЗ) важливою вихiдною iнформацiєю є матриця кореспонденцiй пасажирiв мiж зупинками.
Традицiйним джерелом такої iнформацiї слугують матерiали обстежень пасажиропотокiв на маршрутi талонним методом.
На основi iнформацiї про матрицю кореспонденцiй пасажирiв мiж зупинками на маршрутi отримують наступні характеристики про пасажиропотоки: пасажирооборот зупинок; щiльнiсть пасажиропотокiв на перегонах; кiлькiсть перевезених пасажирiв по маршруту; кiлькiсть виконаних пасажиро-кiлометрiв; середня дальнiсть поїздки пасажирiв на маршрутi; коефiцiєнт нерiвномiрностi пасажиропотоку за довжиною маршруту; коефiцiєнт нерiвномiрностi пасажирських перевезень в часi; коефiцiєнт змiнностi пасажирiв на маршрутi i низка iнших.
В результатi обробки матерiалiв обстеження пасажиропотокiв визначається кiлькiсть пасажирiв, що зайшли та вийшли на кожнiй зупинцi маршруту в заданому годинному iнтервалi.
Обробка матерiалiв обстеження пасажиропотокiв табличним методом дає можливiсть отримати iнформацiю про пасажиропотоки, яка необхiдна для
коригування розкладу руху ТЗ на маршрутi: щiльнiсть пасажиропотоку на перегонах маршруту; параметр, що характеризує роботу зупинок (пасажирооборот зупинок); рiзнi коефiцiєнти нерiвномiрностi пасажиропотоку (за довжиною маршруту, в часi i т.д.); коефiцiєнт використання мiсткостi ТЗ та iнші.
Як було показано вище, практичну цiннiсть має визначення матрицi кореспонденцiй пасажирiв мiж зупинками i розрахованi на її основi рiзнi показники (кiлькiсть виконаних пасажиро-кiлометрiв на маршрутi, середня дальнiсть поїздки пасажирiв на маршрутi i т.д.), що не дає можливостi визначити в результатi обробки матерiалiв табличного методу обстеження. В цьому випадку з’являється наступна задача: за вiдомими даними про кiлькiсть пасажирiв, що зайшли та вийшли на кожнiй зупинцi маршруту в заданому годинному iнтервалi, визначити структуру матрицi кореспонденцiй пасажирiв.
Iнформацiя про пасажирськi кореспонденцiї i потоки в транспортнiй мережi головним чином в даний час отримують iз спостережень. Як показує практика, отримання експериментальних даних про кореспонденцiї є занадто трудомiсткою, а часто i задачею, що не вирішується. В даний час вiдомо декiлька методiв визначення матрицi мiжрайонних кореспонденцiй, але жоден з них не дозволяє здiйснювати визначення з достатньою оперативнiстю i точнiстю.
Практично єдиними важливими засобами розрахунку кореспонденцiй є гравiтацiйнi i ентропiйнi моделi.
Моделi гравiтацiйного типу отримали розповсюдження ще в XVIII столітті i сьогодні широко використовуються для визначення кореспонденцiй в мiстах.
Вiдомо досить багато формальних пiдходiв до опису процесу формування кореспонденцiй: вибiр жителями районiв роботи, обмiн житлом,
реалiзацiя пропонованих при розселеннi можливостей i т.д. Перерахованi пiдходи є частковими випадками достатньо загальної закономiрностi масової
поведiнки клiєнтiв транспортної системи.
В основу ентропiйних моделей покладений принцип, згiдно якого ентропiя замкненої системи не зменшується. В роботi показано, як використовувати метод множникiв Лангранжа, для вирiшення цiєї задачi. Таким чином, отримується гравiтацiйний запис формули. Це є важливим аргументом на користь моделей гравiтацiйного типу. Але пасажирська маршрутна система не є замкнутою. Мiсто не iзольоване, iснують мiграцiї мiського населення iз мiста в мiсто, iз села в мiсто, існує відвідування мiста громадянами iнших мiст та областей. Маршрут також можна приставити замкненою системою – люди зміняють місце проживання i роботи, виявляються вiдвiдування приїзджих з рiзних мiських закладiв, одноразовi поїздки в магазини тощо. Для незамкненої системи не можна з упевнiстю стверджувати, що її ентропiя не зменшується.
Таким чином, ентропiя системи – функцiя вiд незамкненостi системи i iнерцiї (часу, який витрачається системою для досягнення максимуму ентропiї у випадку, коли система стала замкненою). Відзначимо, що сьогодні розрахунковi методи визначення мiжрайонних пасажирських кореспонденцiй в мiстах гравiтацiйними i ентропiйними методами значно вiдрiзняються вiд результатiв натурних обстежень – похибка коливається в дiапазонi 30-320%. Це пояснюється не тільки надзвичайною складнiстю задачi, викликаною неврахуванням окремих факторiв (містобудiвництва, соцiальних, психологiчних, фiзичних тощо), але i тим, що розглянутi системи не виявляються замкненими.
Моделі, що описують маршрутну систему з множиною видів міського пасажирського транспорту більш універсальні при дослідженні пасажирських перевезень, ніж моделі, що враховують один вид транспорту Складність їх створення окуповується точністю моделювання процесу перевезень в містах, які обслуговуються декількома видами транспорту.
Hа базi даних про мiжрайоннi пасажирськi кореспонденцiї здiйснюється прогнозування пасажирської завантаженостi вулично-дорожньої мережi в
рамках методу взаємних кореспонденцiй. На сьогодні застосовується три класи моделей прогнозування: до першого класу належать моделi, в яких
пасажиропотоки спрямованi одним найкоротшим за часом шляхом мiж кожною парою кореспондуючих районiв; до другого класу належать моделi, в яких
пасажиропотоки розподiляються за групою шляхiв, але також на основi критерiю часу; до третього класу належать моделi багаторядного розподiлу, в
яких розподiл виконується на безлiч шляхiв, обмежене областю зглаження iснуючого критерiю, без фiксацiї одиничних шляхiв. Задача моделювання розподілу пасажирських кореспонденцій по маршрутній мережі міста має важливе значення, оскільки від адекватності відтворення математичною моделлю реальних пасажиропотоків на транспортній мережі залежить оцінка ефективності і якості вдосконалення процесу перевезень. Ця обставина викликала інтенсивні дослідження проблеми вибору пасажирами шляхів слідування, на основі яких були розроблені моделі розподілу пасажирських кореспонденцій по маршрутах міського транспорту.
Hеобхiдно вiдзначити, що теорiя розподiлу пасажирських кореспонденцiй на транспортнiй мережi недостатньо розроблена. Тому для всiх класiв моделей необхiдне накопичення емпiричних даних i проведення наукових дослiджень, як щодо подальшого удосконалення розрахункових методiв, так i раціональності їх використання. Hаступною задачею в формуваннi пасажиропотокiв є їх розподiл за видами транспорту. При цьому видiляються в першу чергу головнi, тобто найбiльш концентрованi i потужнi пасажиропотоки, якi можуть бути освоєні транспортом з великою провiзною здатнiстю – примiськi поїзди, метрополiтен i швидкісний трамвай.
Пасажиропотоки середньої i малої потужностi можуть бути освоєні менш мобільним видом транспорту – трамваєм, автобусом, тролейбусом. Подальше вирiшення задачi організації перевезень полягає в розрахунках необхiдної кiлькостi ТЗ для випуску на маршрути i в визначеннi оптимального режиму їх функцiонування.
Найбiльш трудомісткою задачею в визначеннi елементiв мiкрорайонних кореспонденцiй пасажирiв є визначення кiлькостi мешканцiв, якi проживають в транспортному мiкрорайонi та кількості працюючих в кожному мiкрорайонi міста.
В зв’язку з цим, виникає необхiднiсть в розробцi методу, який дозволяє оперативно визначити названі величини. Hа транспортi розрiзняють довгострокове, поточне i оперативне планування перевезень. Серед задач, якi розв'язують в процесi планування, виділимо задачi вибору, прокладання маршрутiв, розподiл ТЗ, визначення елементiв розкладу. Комплекс цих задач носить назву маршрутизацiї. Часто при плануваннi цi задачi розв'язуються окремо. Спочатку розв’язується задача створення транспортної мережi, наступним кроком визначається план розподiлу ТЗ за маршрутами, i тiльки потiм встановлюються елементи розкладу руху (час обороту, час простою на зупинки тощо).
При маршрутизації міських перевезень, перш за все, визначаються основнi пасажироутворюючi райони шляхом обстеження попиту населення на
перевезення. Далi визначається взаємотяжiння окремих районiв, тобто обсяг мiжрайонних перевезень. Отримані райони проектуються на
вулично-дорожню мережу, i здiйснюється попередня побудова транспортної мережi. При цьому будуються такі моделi, якi дозволяють визначити
пересування пасажирiв в мiстi [135]. Транспортна мережа, яка проектується, повинна задовольняти таким критерiям: кожний маршрут окремо повинен зв’язувати найкоротшим шляхом пасажироутворюючі райони; машрутна мережа в цiлому повинна забезпечувати найменшу пересадочнiсть;
вся система повинна забезпечувати найменшi витрати часу на перевезення.
Крiм цих критерiїв, як правило, виставляються додатковi вимоги, якi торкаються вартостi побудови всiєї мережi, розташування початкових i кiнцевих зупинок маршрутiв, територiальних зручностей пересадок тощо.
Побудова маршрутної системи в такому виглядi проводиться на етапi довгострокового планування. Оскiльки достовiрнiсть даних низька, точнiсть вирiшення задачi визначається в основному достовiрнiстю вхiдних даних.
Час вирiшення таких задач не є лiмiтованим i може бути досить великий. Пiсля попереднього вирiшення задачi побудови транспортної мережi вирiшується задача розподiлу транспортних засобів на існуючій системi маршрутiв. Вирiшення цiєї задачi допускає наявнiсть такої моделi, яка описує характер руху транспортних засобів за маршрутом. В подальшому (при поточному плануваннi) виконується корекцiя маршрутної системи з метою локальної змiни окремих дiлянок системи. В цю корекцiю входять введення додаткових маршрутiв для бiльш рiвномiрного завантаження системи i перерозподiлу пасажиропотокiв, лiквiдацiя незавантажених маршрутiв, економiчнi показники яких нижче планових тощо. Достовiрнiсть такої iнформацiї вища, в порівнянні вирішення задач довгострокового планування.
Данi про структуру мережi i її функцiонування отримують достатньо точно. Значно важче отримати iнформацiю щодо пасажиропотоків. Низька точнiсть
цiєї iнформацiї вiдбивається на точностi вирiшення задач корекцiї транспортної мережi. Час вирiшення таких задач також не є обмеженням i може бути
достатньо великим. Розглянутi величини, що характеризують транспортну мережу i технічне обслуговування, що на нiй працюють, є вхiдною iнформацiєю для постановки задачi маршрутизацiї. Формулюючи задачу, необхiдно або задати функцiї, що характеризують вершини i дуги (ребра) транспортної мережi, або розрахувати їх, використовуючи відомі моделi, якi описують роботу транспортних засобів на дугах i вершинах графа. Крiм того, необхiдно задати систему обмежень i критерiїв. Комбiнуючи цю вхiдну iнформацiю, можна отримати рiзнi постановки задачi маршрутизацiї.
Розглянемо, як формалiзуються практичнi задачi, які описанi вище. Згiдно роботі , задачi маршрутизацiї на мiському пасажирському транспортi складаються з двох задач – вибору маршрутiв i розподiлу транспортних засобів на iснуючих маршрутах.
В обох задачах вершини графа – це множина можливих зупинок ТЗ або розгалуження дорiг, ребра – дороги мiж вершинами. В першiй задачi iнформацiя про пасажиропотоки – складається в заданнi матрицi мiжрайонних кореспонденцiй. Iнформацiя про ТЗ полягає в тому, що кiлькiсть ТЗ вважається нескiнченною, а їх швидкiсть однаковою. Показники маршрутної системи: пересадочнiсть, час перевезення всіх пасажирiв тощо.
Моделi здаються досить простими, наприклад, час руху пасажира за маршрутом не залежить вiд iнших маршрутiв, пасажир обирає шлях з найменшим часом слідування. Критерiями є один або декiлька показникiв.Важливим питанням, яке необхiдно вирiшити при розробцi програмного забезпечення для вирiшення загальної задачі маршрутизації, є визначення типу методiв (гiлок i меж, метод вiдсiкань, еврiстичні підходи). Вiд методу залежить допомiжне математичне забезпечення, необхiдне для роботи програм вирiшення загальних задач маршрутизації.
Вирiшення задач за допомогою ЕОМ ставить питання порiвняння мiж собою програм, за допомогою яких вирiшується задача.
Основними параметрами програм, якi цiкавлять користувачiв, є час вирiшення задачi (n) Т i потрiбна для вирiшення машинна пам'ять (n) L (n) – розмір вхідних даних для задач).
Велика кiлькiсть типiв ЕОМ i рiзноманiтнiсть їх характеристик ускладнює порiвняння програм, написаних для рiзних ЕОМ. Бiльш об'єктивною
характеристикою якостi алгоритма є порядок зростання величин (n) Т i (n) L . Ця характеристика не змiнюється при переходi вiд однiєї ЕОМ до другої.
Для багатьох задач були розробленi полiномiальнi алгоритми. До них вiдносяться задачi сортування масиву чисел, пошуку максимального потоку
інтегральній в мережi тощо. Але в iнших випадках, наприклад, для задачi комiвояжера, незважаючи на всi спроби дослiдникiв, такi алгоритми не були
знайденi. Ситуацiя прояснилась пiсля робiт, в яких був описаний клас задач, що вирiшуються на недетермiнованiй машинi Т’юринга.
Таким чином, вищенаведена оглядова складність побудови оптимальних пасажирських маршрутних систем свідчить про подальший інтенсивний
науково-технічний пошук оптимізаційних постінформаційних методів такої пободови.