24

Размещено на http://www.allbest.ru/

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

“ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Система підтримки прийняття рішень при управлінні транспортуваннями в умовах невизначеності

Спеціальність 05.13.03 -системи і процеси керування

Зінченко Іван Володимирович

УДК 519.6

Харків - 2007

Дисертацією є рукопис.

Робота виконана в Національному технічному університеті “Харківський політехнічний інститут” Міністерства освіти і науки України

Науковий керівник - доктор технічних наук, професор Раскін Лев Григорович, Національний технічний університет “Харківський політехнічний інститут”, професор кафедри економічної кібернетики та маркетингового менеджменту

Офіційні опоненти: доктор технічних наук, професор Богатиренко Костянтин Іванович, Національний технічний університет “Харківський політехнічний інститут”, професор кафедри колісних і гусеничних машин

кандидат технічних наук, Васильченков Олег Георгійович, СП ТОВ “Моніс”, м. Харків, директор дирекції розробки

Захист відбудеться 29 листопада 2007 року о 14-30 годині на засіданні спеціалізованої вченої ради Д 64.050.14 у Національному технічному університеті “Харківський політехнічний інститут”, за адресою: 61002, Харків, вул. Фрунзе, 21.

З дисертацією можна ознайомитись у бібліотеці Національного технічного університету “Харківський політехнічний інститут”, 61002, Харків, вул. Фрунзе, 21.

Автореферат розісланий “ 22” жовтня 2007 р.

Вчений секретар спеціалізованої вченої ради Ліберг І.Г.

Анотації

Зінченко І.В. Система підтримки прийняття рішень при управлінні транспортуваннями в умовах невизначеності. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.03 - системи і процеси керування. - Національний технічний університет “Харківський політехнічний інститут”, Харків, 2007.

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

У роботі розглянуто методику рішення задачі раціонального планування внутрішньозаводських перевезень з використанням запропонованого евристичного алгоритму. Проблемна задача оптимізації транспортувань у системі “поставщик-проміжні центри-споживачі” розв'язана для випадків, коли положення проміжних центрів задано або не задано. Показано, що задача приводиться до несиметричної трьох індексної задачі лінійного програмування. Описана методика рішення задачі транспортного типу є з нечітко заданими параметрами. Запропонована технологія розв'язання таких задач, яка використовує методи рішення чітких задач квадратичного програмування.

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

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

Теоретичні результати роботи використано при рішенні практичної задачі комівояжера для одного з районів м. Харкова з урахуванням реально існуючих магістралей, які зв'язують пункти призначення.

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

Зинченко И.В. Система поддержки принятия решений при управлении транспортировками в условиях неопределенности. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.03 - системы и процессы управления. - Национальный технический университет “Харьковский политехнический институт”, Харьков, 2007.

Диссертационная работа посвящена решению актуальной народнохозяйственной проблемы разработки системы поддержки принятия решений (СППР) при управлении транспортировками в условиях нечетких исходных данных. В соответствии с этим, целью работы является разработка структуры и математических моделей функционирования СППР при управлении перевозками, а также комплекса математических моделей, обеспечивающих решение оптимизационных задач математического программирования высокой размерности с нечетко заданными параметрами целевой функции и ограничений.

В работе рассмотрена методика решения задачи рационального планирования внутризаводских перевозок с использованием предложенного эвристического алгоритма. Разработан критерий эффективности назначений. Проблемная задача оптимизации транспортировок в системе “поставщик - промежуточные центры - потребители” решена для случаев, когда положение промежуточных центров задано или не задано. Показано, что задача сводится к несимметричной трехиндексной задаче линейного программирования. Описана методика решения задачи транспортного типа с нечетко заданными параметрами. Предложена технология решения таких задач, использующая методы четких задач квадратического программирования.

В работе исследованы возможности решения комбинаторных булевых задач, в частности задачи коммивояжера, высокой размерности с использованием генетических алгоритмов. Показано, что целесообразность применения генетических алгоритмов тем выше, чем больше размерность задачи. Кроме того, установлено, что если размерность задачи коммивояжера имеет порядок - сотни пунктов, то для её решения необходима декомпозиция. Предложена методика расчета параметров декомпозиционной процедуры (одно- и двухэтапной).

Наконец, в диссертации показано, что эффективность решения высоко размерных задач может быть повышена за счет адаптации параметров генетического алгоритма (размер популяции, тип кроссовера, вероятность мутации и т.д.). Проведена оценка эффективности разработанного варианта генетического алгоритма при решении тестовых задач коммивояжера различной размерности, подтверждающая его высокую производительность.

Теоретические результаты работы использованы при решении практической задачи коммивояжера для одного из районов г. Харькова с учетом реально существующих магистралей, которые связывают пункты назначения.

Ключевые слова: система поддержки принятия решений, управление транспортировками, внутризаводские перевозки, нечетко заданные исходные данные, генетические алгоритмы, задача коммивояжера высокой размерности.

Zinchenko I.V. Decision support system for transportation controlling problem within undefined conditions. - Manuscript.

A thesis to obtain a scientific degree of a candidate of technical sciences, specialty 05.13.03 - controlling systems and processes. - National Technical University “Kharkiv Polytechnic Institute”, Kharkiv, 2007.

Dissertational work is devoted to the decision of an actual economic problem of system engineering of support of decision-making at management of transportations conditions of the indistinct initial data.

The work presents the solution method for the problem of rational in-plant transportations planning using heuristic algorithm. The problem of optimization of transportations system “the supplier - the intermediate centers - consumers” is solved for cases when position of the intermediate centers is set or is not set. It is shown, that the problem is reduced to an asymmetrical three index problem of linear programming. The technique of the decision of a transportation planning problem type with indistinctly set parameters is described. The technology of the decision of such problems, using methods of precise problems of quadratic programming is offered.

Work uses opportunities of the decision combinatory Boolean problems, in particular Traveling Salesman Problem (TSP), high dimension with use of genetic algorithms are researched. Besides it is established, that if dimension of a TSP has the number of points reaching hundreds - decomposition is necessary for its solution. The design procedure of parameters decomposition procedures (one- and two-stage) is offered.

At last, in the dissertation it is shown, that efficiency of high dimensional problems solution can be raised due to adaptation of parameters of genetic algorithm (the size of a population, type of a crossover, probability of a mutation, etc.).

Theoretical results of work are used to resolve a practical TSP-like problem for one of Kharkov city areas regarding to real-life highways and transportation routes which connect destinations.

Key words: decision support system, transportation management, the in-plant transportations, indistinctly set initial data, genetic algorithms, high dimensioned traveling salesman problem.

1. Загальна характеристика роботи

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

Аналіз відомих методів рішення задач оперативного управління перевезеннями дозволяє виявити ряд недостатньо пророблених серйозних проблем: по-перше, висока розмірність розв'язуваних задач, типова для схеми "постачальник - проміжні центри - споживачі"; по-друге, управління маршрутизацією в умовах, коли вхідні дані задачі неточні (наприклад, задані нечітко).

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

Зв'язок роботи з науковими програмами, планами, темами. Дослідження, які були виконані в рамках дисертаційної роботи, тісно пов'язані з темами науково-дослідних робіт, які виконувалися в НТУ "ХПІ" при особистій участі здобувача як виконавця: "Розробка інформаційних моделей для реалізації процедур структурного синтезу в комп'ютерно-інтегрованих системах" (ДР № 0103U001543), "Розробка методів для системи підтримки прийняття рішень у задачах розподільної й транспортної логістики молочного виробництва" з ВАТ "Федоровське" (м. Харків, 2005 р.).

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

- розробка структури системи підтримки прийняття рішень і математичних моделей управління внутрішньозаводськими перевезеннями;

- розробка методики управління внутрішньозаводськими перевезеннями в умовах нечітко заданих вихідних даних;

- розробка математичних моделей і методик рішення задач оптимізації транспортувань за схемою "постачальник - проміжні центри - споживачі" для нечітко заданих вихідних даних;

- розробка методики рішення задачі маршрутизації за схемою "від одного до багатьох" (задачі комівояжера) високої розмірності в умовах нечітко заданих вихідних даних з використанням генетичного алгоритму.

Об'єкт дослідження - процес управління транспортуваннями.

Предмет дослідження - математичні моделі управління транспортуваннями в задачах високої розмірності при нечітко заданих вихідних даних.

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

Наукова новизна одержаних результатів. У дисертації при рішенні поставлених задач одержані наступні нові наукові результати:

уперше:

- розроблена методика рішення задач оптимізації транспортувань за схемою "постачальник - проміжні центри - споживачі" в умовах нечітких вхідних даних;

- розроблена методика використання генетичного алгоритму для рішення задач маршрутизації за схемою "від одного до багатьох" високої розмірності в умовах нечітких вхідних даних;

одержали подальші розвиток:

- методи побудови систем підтримки прийняття рішень при управлінні внутрішньозаводськими перевезеннями;

- методика управління внутрішньозаводськими перевезеннями в умовах нечітких вихідних даних;

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

Практичне значення одержаних результатів. Практична цінність одержаних результатів складається в можливості їхнього безпосереднього використання при рішенні реальних задач управління транспортуваннями. Всі розроблені методики доведені до програмної реалізації мовою С++ Buіlder 5.0.

Розроблені методики використовуються при рішенні задач транспортуваннями у ВАТ "Федоровське" (акт про реалізацію).

Особистий внесок здобувача. Всі основні результати дисертаційної роботи, які винесені на захист, отримані здобувачем особисто. Серед них: модель задач управління внутрішньозаводськими перевезеннями як багатоіндексної задачі призначення; евристичний метод рішення задачі управління внутрішньозаводськими перевезеннями; методика рішення задачі транспортування за схемою "постачальник-проміжні центри-споживачі"; методика відшукання числа й місць розташування проміжних центрів; методика використання генетичного алгоритму для рішення задачі комівояжера; декомпозиційна процедура рішення задачі комівояжера високої розмірності.

Апробація результатів дисертації. Основні результати досліджень доповідалися на: XІІ, XІІІ, XІV міжнародних науково - практичних конференціях ""Інформаційні технології: наука, техніка, технологія, освіта, здоров'я" (м. Харків, 2004-2006 рр.); V-й міжнародній науково - технічній конференції "Проблеми інформатики й моделювання" (м. Харків, 2005р.); міжнародній науково - методичної конференції "Проблеми математичного моделювання" (м. Дніпродзержинськ, 2005 р.); міжнародній науково - практичній конференції "Розвиток економіки в трансформаційний період" (м. Запоріжжя, 2005 р.).

Публікації. Основний зміст дисертації опубліковано у 8 наукових статтях у спеціалізованих наукових виданнях ВАК України.

Структура й обсяг дисертації. Дисертація складається із вступу, 5-х розділів, висновків і додатків. Повний обсяг дисертації становить 230 сторінок основного тексту, 8 додатків на 52 сторінках, список використаних літературних джерел містить 66 найменувань на 5 сторінках, 9 таблиць за текстом, 33 ілюстрації за текстом, 10 ілюстрацій на 7 окремих сторінках.

2. Основний зміст роботи

У вступі розкрито стан проблеми, обґрунтована актуальність теми, сформульована мета роботи, позначені об'єкт і предмет дослідження, показані наукова новизна та практичне значення одержаних результатів.

У першому розділі роботи обговорюються відомі трактування поняття транспортна логістика та розглядаються відомі моделі транспортної логістики. Формулюється комплекс задач планування та управління перевезеннями, найбільш важкі з яких розпадаються на два класи задач: транспортування за схемою "від багатьох до багатьох" і транспортування за схемою "від одного до багатьох".

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

До другого класу відносяться задачі оптимізації транспортувань за схемою "одні до багатьох" (задачі комівояжера).

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

На завершення розділу формуються задачі дослідження.

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

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

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

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

База знань - це сукупність правил формування групових заявок і призначення ТЗ на перевезення вантажів.

Сукупність технічних характеристик автотранспортних засобів, а також дані, що містяться в заявках, описані формально.

Уведені: - номер заявки, , - номер ТЗ, , - тип -ї машини, , - вантажопідйомність -го ТЗ, - максимальний габарит -го ТЗ, - середня швидкість -го ТЗ, - середня витрата пального -го ТЗ, - ознака працездатності -го ТЗ, - час звільнення -го ТЗ, - пункт навантаження для -ї заявки, - пункт розвантаження для -ї заявки, - час початку виконання -ї заявки, - важливість -ї заявки, - тип -ї заявки, - вага вантажу для -ї заявки, - час готовності до навантаження для -ї заявки, - тривалість навантаження для -ї заявки, - відстань між пунктами звільнення ТЗ із номером і пунктом навантаження для -ї заявки, - час закінчення робочого дня. Крім того, уведені: ознака взаємного розташування пунктів навантаження й розвантаження для -ї заявки; ознака сумісності типів вантажу та ТЗ - ; ознака сумісності пунктів навантаження (розвантаження) і ТЗ - ; .

З метою відшукання раціонального плану призначень сформульоване завдання планування внутрішньозаводськими перевезеннями як деяке завдання математичного програмування. Сукупність параметрів призначень утворять план перевезень.

З використанням уведених позначень сформульовані вимоги, яким повинен задовольняти план перевезень Х.

Якість реалізованого плану Х може бути оцінено сукупністю критеріїв:

Критерій визначає загальне число ТЗ, які задіяні при виконанні плану заявок. Критерій робить план Х неефективним, якщо вантажопідйомність призначуваного ТЗ значно перевершує вага вантажу.

Кожна зі сформульованих задач (1)-(5), (6); (1)-(5), (7) є трьохіндексною задачею призначення.

Слід зазначити, що якість одержуваних у результаті рішення поставленої задачі планів не можна вважати високим, що пов'язане з конструктивними недоліками моделі. Сформулюємо їх.

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

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

Результатом роботи СППР є маршрутний аркуш, що містить: постійний номер машини, час початку виконання заявки, тип вантажу, пункт навантаження, розвантаження, вага вантажу, тривалості навантаження/ розвантаження, час звільнення.

Співвідношення для розрахунку критерію доцільності призначення машини з номером для виконання -ї заявки має вигляд

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

,

де - рівень відповідності тактико-технічних показників -го ТЗ точно оцінюваним характеристикам -ї заявки й умовам її виконання, - рівень відповідності тактико-технічних показників -го ТС неточно оцінюваним характеристикам -ї заявки.

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

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

Отримана задача (13)-(14) є трьохіндексною несиметричної аксіально-біпланарною транспортною задачею (Тз-А-2р) лінійного програмування.

У роботі розглянута наближена процедура рішення задачі (12)-(13). Пропонована процедура є двохкроковою. На першому кроці виведемо з розгляду аксіальне обмеження та розглянемо задачу мінімізації (14), яка залишилася, при планарних обмеженнях. Отримана задача є трьохіндексною біпланарною транспортною задачею (Тз-2р) лінійного програмування та може бути ефективно вирішена шляхом зведення до звичайної двохіндексної транспортної задачі. Перший крок рішення вихідної задачі завершений. Якщо отриманий на першому кроці план задовольняє виведеному з розгляду аксіальному обмеженню, то рішення задачі закінчене. У противному випадку приходимо до другого кроку.

На цьому кроці вирішується задача відшукання плану, який мінімізує (13), задовольняє (12), і найменшим чином відхиляється від отриманого раніше плану.

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

.

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

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

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

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

Тепер задача нечіткого лінійного програмування формулюється в такий спосіб: знайти вектор , який максимізує на множині обмежень .

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

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

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

Для виділення найкращих особин використається турнірний відбір, що складається у виборі деякого заданої кількості особин з найвищою пристосованістю. Далі в розділі дається опис принципів функціонування основних операторів ГА стосовно до рішення задачі комівояжера (кроссовер, мутація, інверсія). У зв'язку з високою розмірністю реальних задач розглянуто декомпозиційний ГА рішення задачі комівояжера. Результати експериментального рішення задачі комівояжера різної розмірності з використанням ГА наведені в таблиці 1.

Таблиця 1 Залежність часу пошуку найкоротшого маршруту (в умовних одиницях) від кількості пунктів

Кількість пунктів	10	18	26	34	42	50	58	66	74	80
Час рішення	1	8	23	50	90	195	285	401	597	780

Для аналітичного опису залежності уведена модель

.

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

Експериментальна й теоретична криві наведені на рис. 1.

З метою зниження тривалості рішення задачі й ослаблення залежності цього часу від числа пунктів запропонована двохетапна процедура декомпозиції задачі. При цьому на першому етапі вся множина пунктів шляхом рішення задачі кластеризації розбивається на деяке число компактних груп. Потім кожний з отриманих кластерів розглядається як точка, положення якої визначається центром ваги кластера. Для отриманої в такий спосіб сукупності точок вирішується задача комівояжера. У результаті першого етапу буде отримано оптимальний маршрут обходу груп. У завершення цього етапу для кожної пари сусідніх на маршруті обходу груп відшукується найкоротша "перемичка", що з'єднує ці групи. Таким чином, у кожній групі визначається пункт входу й пункт виходу. На другому етапі процедури для кожної групи вирішується задача комівояжера з обліком певних на попередньому етапі пунктів початку й кінця маршруту.

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

.

Аналіз виграшу від декомпозиції показує, що, незважаючи на значний виграш, забезпечуваний описаним алгоритмом, тривалість рішення задачі при великих значеннях n (500 і вище) залишається неприйнятно високою. У зв'язку із цим запропонована двохетапна декомпозиційна процедура, яка організується в такий спосіб.

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

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

, .

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

Далі в розділі розглянуто задачу комівояжера при нечітких вихідних даних.

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

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

2. Число особин, які зберігаються при формуванні нової популяції - двадцять.

3. Імовірність мутації - 0,02.

4. Доцільна тривалість очікування пов'язана із числом пунктів співвідношенням , але не повинна перевищувати поколінь.

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

Як приклад у роботі вирішувалася реальна задача комівояжера. Розташування пунктів призначення (трикутники) і перехресть магістралей (кружки) наведено на рис. 3. Початковий пункт - №65. За методикою, запропонованою в роботі, розраховується матриця найкоротших шляхів між вузлами мережі. З матриці виділена підматриця , елементи якої визначають найкоротші відстані між пунктами призначення.

Тепер з використанням матриці вирішується задача комівояжера. Тому що кількість пунктів призначення досить велика, то попередньо була проведена кластеризація. Далі визначалася послідовність обходу кластерів і найближчі пункти із сусідніх кластерів. Після цього за допомогою ГА знаходяться локальні маршрути усередині кожного кластера й визначається порядок обходу пунктів призначення для всієї карти. Далі отриманий порядок обходу деталізується вказівкою переліку перехресть, які зв'язують кожну пару пунктів призначення в оптимальному маршруті (рис. 4.).

Висновки

1. Описано структуру СППР при плануванні внутрішньозаводських перевезень. Задача планування сформульована як багатоіндексна задача призначення.

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

3. Розглянуто технологію рішення задачі для випадку, коли параметри задачі визначені нечітко.

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

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

6. Описано методику рішення задач транспортного типу з нечітко заданими параметрами. Показано, що вихідні нечіткі задачі можуть бути скорочені до чітких задач квадратичного програмування, які розв'язуються відомими методами.

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

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

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

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

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

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

13. Розроблено методику використання генетичного алгоритму для рішення реальних задач комівояжера з обліком фактично існуючих магістралей, що зв'язують пункти призначення. Розглянуто приклад реального задачі комівояжера для одного з районів міста Харкова.

Список опублікованих праць по темі дисертації

1. Раскин Л.Г., Серая О.В., Зинченко И.В. Методика решения иерархической нелинейной транспортной задачи в условиях неопределенности // Вісник Національного технічного університету “Харківський політехнічний інститут”. - Харків: НТУ “ХПІ”. - 2003.-№21. - С.191-196. Здобувачу належить математична модель задачі.

2. Серая О.В., Зинченко И.В. Многономенклатурная задача оптимизации транспортировки товаров системе “поставщик-промежуточные центры -потребители” // Вісник Національного технічного університету “Харківський політехнічний інститут”. - Харків: НТУ “ХПІ”. - 2005.-№7. - С. 153-158. Здобувачем розроблена методика рішення задачі.

3. Серая О.В., Лолашвили Б.Г., Зинченко И.В. Нечеткая проблема назначения. // Вісник Національного технічного університету “Харківський політехнічний інститут”. - Х.: НТУ “ХПІ”. - 2005. - №19. - С.121-124. Здобувачу належить модель і формулювання нечіткого критерію якості рішення.

4. Раскин Л.Г., Лолашвили Б.Г. Зарубин В.С., Зинченко И.В. Принятие решений в нечетко определенной среде.// Вісник Національного технічного університету “Харківський політехнічний інститут”. - Харків: НТУ “ХПІ”. - 2005.-№56. - С. 104-110. Здобувачем розроблені критерії ефективності рішень у нечітко визначеному середовищі.

5. Серая О.В.Зарубин В.С., Лолашвили Б.Г., Зинченко И.В. Решение задач линейного программирования в нечеткой постановке. // Вісник Національного технічного університету “Харківський політехнічний інститут”. - Харків: НТУ “ХПІ”. - 2005.-№54. - С.160-167. Здобувачу належить модель задачі лінійного програмування в нечіткій постановці.

6. Серая О.В.,Зарубин В.С., Лолашвили Б.Г., Зінченко И.В. Задача математического программирования при нечетких исходных данных. // Математичне моделювання.- Дніпродзержинськ: Дніпродзерж. держ. техн. універ. - 2006. - №1,2. - С. 3-5. Здобувач розробив методику рішення задачі математичного програмування при нечітких параметрах цільової функції задачі.

7. Серая О.В., Зинченко И. В., Бачкир Л.В. Декомпозиционный генетический алгоритм решения задачи коммивояжера высокой размерности // Інформаційно-керуючі системи на залізничному транспорті. - Харків: ІКСЗТ, 2007. - № 1. - С. 23-26. Здобувачу належить критерій оцінки ефективності й методика декомпозиції.

8. Серая О.В., Зинченко И. В., Бачкир Л.В. Стохастические транспортные задачи с промежуточными центрами. // Восточно-европейский журнал передовых технологий. - 2007. -№2/6 (26). - С. 3-5. Здобувачем розроблена модель задачі й методика її рішення при стохастично заданих вартостях транспортувань.

Размещено на Allbest.ru