2 Математичні моделі (методи оптимізації, транспортні задачі, алгоритми).

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

1. Методи оптимізації

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

а) Лінійне програмування:

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

• Класична транспортна задача: Це фундаментальна модель лінійного програмування.

  • Формалізація: Є m пунктів виробництва (депо, парки) з запасами рухомого складу (РС) a_i та n пунктів споживання (маршрути) з потребою в РС b_j. Відома вартість (або час, відстань) переміщення одиниці РС c_ij між i-м депо та j-м маршрутом.

  • Цільова функція: Z = ΣΣ c_ij * x_ij → min, де x_ij – кількість РС, направлених з i в j.

  • Обмеження:

    1. Σ x_ij = a_i (весь РС з кожного депо повинен бути розподілений).

    2. Σ x_ij = b_j (потреба кожного маршруту повинна бути задоволена).

    3. x_ij ≥ 0 (кількість РС не може бути від'ємною).

• Приклад: Мінімізація порожніх пробігів при призначенні автобусів з різних депо на маршрути міста.

б) Цілочислове програмування:

• Застосування: Використовується, коли змінні можуть приймати тільки цілі значення (наприклад, кількість автобусів не може бути дробовою).

• Приклад: Задача комівояжера (Traveling Salesman Problem - TSP) та її розширення – Задача маршрутизації транспортних засобів (Vehicle Routing Problem - VRP).

  • VRP для пасажирських перевезень: Потрібно знайти оптимальний набір маршрутів для флоту транспортних засобів, щоб обслужити набір замовлень (пасажирів) з різними точками посадки/висадки, мінімізуючи загальний пробіг або час, з урахуванням обмежень на місткість, тривалість робочого дня тощо.

в) Нелінійне програмування та стохастичне програмування:

• Нелінійне програмування: Застосовується, коли цільова функція або обмеження нелінійні (наприклад, залежність часу поїздки від інтенсивності руху).

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

2. Транспортні задачі (як окремий клас оптимізаційних задач)

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

• Відкрита транспортна задача: Коли сумарна пропозиція (наявний РС) не дорівнює сумарному попиту (потреба маршрутів). У цьому випадку вводяться фіктивні маршрути або депо для зведення задачі до закритої форми.

• Транспортна задача з обмеженнями на пропускну здатність: Коли на деяких напрямках (i, j) існує обмеження на максимальну кількість РС x_ij ≤ d_ij (наприклад, обмежена можливість паркування на кінцевій станції).

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

3. Алгоритми

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

а) Точні алгоритми:

• Метод гілок та меж (Branch and Bound): Використовується для цілочислових задач. Алгоритм систематично перебирає можливі рішення, відкидаючи цілі гілки перебору, якщо вони заведомо не призведуть до оптимального рішення.

• Застосування: Для вирішення задач невеликої розмірності або як складова частина евристичних методів.

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

• Евристики:

  • Алгоритми найближчого сусіда (Nearest Neighbour): Для побудови маршруту послідовно вибирається найближча невідвідана точка.

  • Алгоритми вставки (Insertion Heuristics): Послідовно "вставляють" точки в частково побудований маршрут у найвигідніше з точки зору цільової функції місце.

• Метаевристики:

  • Генетичні алгоритми (Genetic Algorithms): Імітують процес природної еволюції. Рішення ("особини") оцінюються за функцією пристосованості, найкращі "схрещуються" і "мутують", утворюючи нові покоління покращених рішень.

  • Імунітет алгоритми (Immune Algorithms): Моделюють роботу імунної системи для виявлення та видалення поганих рішень.

  • Метод відпалу (Simulated Annealing): Імітує процес повільного охолодження металу. Алгоритм дозволяє з певною ймовірністю приймати "гірші" рішення, щоб уникнути застрягання в локальному оптимумі.

  • Мурашині алгоритми (Ant Colony Optimization): Імітує поведінку мурах, що знаходять найкоротший шлях до джерела їжі. "Мурахи" (агенти) залишають "феромони" на хороших маршрутах, приваблюючи інших.

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

• Лінійне програмування – для макро-планування та розподілу ресурсів.

• Цілочислове програмування та VRP – для тактичного планування маршрутів.

• Стохастичні моделі – для роботи в умовах невизначеності.

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

Інтеграція цих методів в єдину систему підтримки прийняття рішень дозволяє перетворити мистецтво управління перевезеннями на точну науку.