Реферат циклу наукових праць «Моделі і методи оптимізації замкнених маршрутів у транспортній логістиці»



Скачати 361.95 Kb.
Сторінка1/2
Дата конвертації25.12.2016
Розмір361.95 Kb.
#5830
ТипРеферат
  1   2
Реферат циклу наукових праць «Моделі і методи оптимізації
замкнених маршрутів у транспортній логістиці»


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

Предметом дослідження Морозова А.В. є математичні моделі та методи розв’язання задач побудови замкнених маршрутів, що знайшло відображення у наукових публікаціях. Ключовими задачами, що розглядаються у статтях, є задачі класу комівояжера. Зокрема, у публікаціях автором запропоновані нові підходи до підвищення швидкодії методів розв’язання гамільтонової (ГЗК), симетричної (СЗК) та загальної задач комівояжера (ЗЗК), гамільтонової (ЗГСЛ) та кільцевої задач про сільського листоношу (КЗСЛ).

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

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

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

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



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

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

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

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



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

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

2. Дослідження структурних особливостей математичних моделей транс­портних мереж.

3. Розробка наближеного методу розв’язання СЗК, який перевершує за швидкодією відомі алгоритми і не поступається їм за точністю.

4. Розробка методу пошуку розв’язку ГЗК з меншими потребами в обчислювальних ресурсах, ніж у відомих методів.

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

6. Розробка математичних моделей двох нових варіантів задачі про сільського листоношу (ЗСЛ), які розширюють область її застосування.

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

8. Вибір та обґрунтування засобів економії обчислювальних ресурсів для точного розв’язання задач оптимізації замкнених маршрутів.

9. Розробка схеми побудови точного та наближеного розв’язку загальної задачі комівояжеру.

10. Розробка модифікації класичного методу гілок та меж (алгоритму Літла), що прискорює пошук оптимальних розв’язків задач класу комівояжера.

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



Наукова новизна:

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

2. Вперше отримано нові достатні умови негамільтоновості графа, які встановлюються за поліноміальний час. Для прискорення процесу пошуку розв’язку ГЗК вперше використано метод, що поєднує алгоритм типу гілок та меж і процедуру перевірки відомих і отриманих умов, що дає змогу відразу встановлювати факт негамільтоновості (нерозв’язності) задачі.

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

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

5. Вперше розроблено математичні моделі для розв’язання ГЗСЛ та КЗСЛ − гамільтонової та кільцевої задач про сільського листоношу, які розширюють клас задач про листоношу.

6. Набув подальшого розвитку двоетапний точний перебірний метод типу гілок та меж, який знаходить оптимальний розв’язок ГСЗЛ чи КЗСЛ, або встановлює факт нерозв’язності задачі; перший етап методу включає перевірку достатніх умов нерозв’язності задачі та процедуру вершинно-реберного перетворення, яка приводить до одного з трьох можливих результатів: побудовано оптимальний розв’язок; задача не має розв’язку; пошук оптимального розв’язку потрібно продовжити на перетвореному графі зі степенями вершин, більшими 2, що дає можливість скоротити час пошуку точного розв’язку задачі.

7. Модифіковано класичний метод Літтла; запропоновані два правила розгалуження та спосіб пошуку нижньої оцінки дають можливість застосовувати метод для розв’язання ГЗСЛ та гамільтонової задачі комівояжера.

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

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

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

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



Практична значимість. Проблема маршрутизації потоків пасажирів та вантажів є однією з найбільш актуальних проблем виробничого та транспортного комплексу держави. Прискорення темпу пересування транспортних потоків вимагає застосування новітніх комп’ютерних технологій та сучасних методів оптимізації перевезень. Використання сучасного програмного та математичного забезпечення в управлінні транспортом забезпечує економію в межах 5-20% від загального товару, який перевозиться. Не менш актуальною залишається розробка методу розв’язання ключових задач проблеми маршрутизації: СЗК, ГЗК, ЗЗК та ЗСЛ за єдиною схемою обчислень, найбільш ефективною серед відомих. Розв’язання задач, які формулюються в термінах ЗК, знаходять застосування в генетиці, вони використовуються в автоматиці для оптимізації переміщення космічних оптичних телескопів, в управлінні механічними роботами, в проектуванні плат та каналів зв’язку.

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

Створені програмні модулі дозволяють розв’язати низку прикладних задач проблеми комівояжера в умовах, визначених вимогами практики. Розроблений програмний продукт використовується на ЗАТ «Агротонпром» та Броварській експериментально-виробничій базі ВАТ УкрНДІПСК ім. В.М.Шимановського. Результати досліджень використовуються у навчальному процесі за напрямком «Програмна інженерія» при викладанні дисциплін «Математичні методи дослідження операцій», «Дискретна математика», «Алгоритми і структури даних», у лабораторному практикумі, при курсовому і дипломному проектуванні.

Основні науково-технічні результати у порівнянні з аналогами:


  1. Для наближеного методу розв’язання СЗК та ГЗК з матрицями вартостей порядку 50-400 без обмежень на значення елементів, найточнішим є алгоритм ММ. Проте задачі такої ж розмірності з матрицями, заповненими на 20% – 80% однаковими значеннями, розв’язуються запропонованим методом i*-tree з меншою похибкою.

  1. Для метричної СЗК розмірністю 3-50 розроблений метод i*-tree будує більш точні розв’язки, ніж відомі методи розв’язання СЗК.

3. Задачі ГЗСП та КЗСП є новими і методи їх розв’язання не мають аналогів.

4. Розроблена модифікація класичного методу гілок та меж (алгоритму Літла) суттєво прискорює знаходження розв'язків СЗК, ГЗК та ЗЗК. Покращання показників ефективності методу Літтла досягається за рахунок швидкого і більш точного обчислення нижніх оцінок вартості шуканого маршруту, скорочення часу на пошук елемента, ініціюючого розгалуження, і гранично обмеженого обсягу пам'яті, необхідної для побудови дерева перебору.



Обґрунтування об’єднання у цикл праць. Усі задачі та методи їх розв’язання, які пропонуються у циклі наукових статей, пов’язані між собою. Автором циклу праць розроблено класифікацію задач циклічної маршрутизації.

Базовою моделлю транспортної мережі міста або району обрано зв’язний граф H = (V, U), де V – множина вершин, |V| = n, U – множина ребер. Вершині , , відповідає перехрестя на карті міста або населений пункт на транспортній мережі регіону. Вершини i та j утворюють ребро {i, j} у графі H, якщо вони представлені сусідніми перехрестями вулиці або населеними пунктами, які безпосередньо зв’язані ділянками дороги. Граф H не містить петель. Кожному ребру приписано вагу що дорівнює відстані між пунктами, – множина невід’ємних дійсних чисел.

Каталог: sites -> default -> files
files -> Положення про порядок підготовки фахівців ступенів доктора філософії та доктора наук в аспірантурі (ад’юнктурі) та докторантурі вищих навчальних закладів
files -> Відділ аспірантури та докторантури Уманського державного педагогічного університету імені Павла Тичини
files -> Київський національний університет імені Тараса Шевченка
files -> Програма вступного іспиту до аспірантури зі спеціальності 22. 00. 03 соціальні структури та соціальні відносини Затверджено
files -> Культура Античності. Культура Давньої Греції
files -> Системотехнічні засади та інструментально-програмні засоби створення та підтримки цифрових словників сидорчук надія Миколаївна
files -> Міністерство освіти І науки україни державний економіко-технологічний університет транспорту
files -> Конспект лекцій для студентів усіх спеціальностей освітньо-кваліфікаційних рівнів «спеціаліст»,
files -> Конструкції для енергоефективного відновлення забудови, постраждалої від надзвичайних ситуацій

Скачати 361.95 Kb.

Поділіться з Вашими друзьями:
  1   2




База даних захищена авторським правом ©uchika.in.ua 2022
звернутися до адміністрації

    Головна сторінка