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

Анотація наукової статті з математики, автор наукової роботи - Нирків Анатолій Павлович, Караваєв Василь Ігорович, Багаєва Наталія Георгіївна, Караваєва Олена Дмитрівна, Соколов С. З.


The article deals with multimodal transport management algorithms, touchs upon basic functions of automated management system for multimodal transport.


Область наук:

  • Математика

  • Рік видавництва: 2010


    Журнал: Вісник державного університету морського і річкового флоту ім. адмірала С.О. Макарова


    Наукова стаття на тему 'Алгоритми автоматизованого управління технологічними процесами мультимодальних перевезень'

    Текст наукової роботи на тему «Алгоритми автоматизованого управління технологічними процесами мультимодальних перевезень»

    ?ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ

    УДК 681.3.07.656.6 А. П. Нирків,

    д-р. техн. наук, професор, СПГУВК;

    В. І. Караваєв,

    канд. техн. наук, СПГУВК;

    Н. Г. Багаєва,

    СПГУВК;

    Е. Д. Караваєва,

    СПГУВК;

    С. С. Соколов,

    СПГУВК

    АЛГОРИТМИ АВТОМАТИЗОВАНОГО УПРАВЛІННЯ ТЕХНОЛОГІЧНИМИ ПРОЦЕСАМИ мультимодальних перевезень

    AUTOMATED MANAGEMENT ALGORITHMS OF MULTIMODAL TRANSPORT'S

    TECHNOLOGICAL PROCESSES

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

    The article deals with multimodal transport management algorithms, touchs upon basic functions of automated management system for multimodal transport.

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

    Key words: algorithm, automated management, multimodal transport.

    КЛІЄНТИ і оператори перевезень все частіше вдаються до системи доставки вантажів, де різні види транспорту діють не відокремлено, а інтегровано один з одним, - до мультимодальних перевезень. Мультимодальна перевезення - це перевезення вантажів, коли особа, її організуючий, несе відповідальність за вантаж на всьому шляху проходження незалежно від кількості приймаючих участь видів транспорту при оформленні єдиного перевізного документа [1].

    Можна виділити наступні особливості мультимодальних перевезень:

    - узгоджене використання в перевезенні одного виду транспорту;

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

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

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

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

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

    Випуск4

    | Випуск4

    оптимізацію та управління процесом перевезень.

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

    - організатор мультимодальной перевезення (ЗМУ) одноосібно несе відповідальність за збереження вантажу, тому виникає необхідність зменшення витрат, пов'язаних з втратами при здійсненні перевезення;

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

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

    Транспортний процес при мультимодальних перевезеннях складається з послідовної доставки вантажу різними видами транспорту, складування і проміжного перевантаження (рис. 1). Для кожного конкретного

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

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

    До основних критеріїв при виборі способу перевезення відносяться:

    - мінімальні витрати на перевезення;

    - заданий час доставки вантажу;

    - максимальна надійність і безпека;

    - мінімальні витрати на утримання запасів в дорозі;

    - максимальна продуктивність і доступність видів транспорту.

    При виборі способу перевезення і виду транспорту враховуються обмеження, пов'язані з часом доставки вантажу, витратами на перевезення, збереженням вантажу, факторами навколишнього середовища, а також технічні обмеження, обумовлені обладнанням транспортних магістралей, особливостями вантажу, наявністю механізмів для вантажно-розвантажувальних робіт і т. Д. [2].

    Якість управління мультимодальной перевезенням можна оцінити наступними критеріями:

    - загальні витрати;

    - прибуток;

    - рентабельність;

    - загальна тривалість доставки;

    - величина втрат вантажу, коефіцієнт

    Мал. 1. Технологічна схема мультимодальной перевезення

    збереження вантажу, як можливий варіант - дотримання повного збереження вантажу;

    - дотримання термінів доставки;

    - зміна фактичної вартості доставки в порівнянні з договірної.

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

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

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

    Координати стану: поточні загальні витрати; поточна тривалість; поточні втрати; Середня швидкість.

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

    Система автоматизованого управління мультимодальних перевезень забезпечує реалізацію таких функцій:

    - збір, обробку та аналіз інформації про стан об'єкта управління - мультимодальной перевезення (прийом заявок від замовників, оперативне відстеження стану і місцезнаходження вантажів, реєстрація проведених з вантажами операцій);

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

    - обмін інформацією з взаємопов'язаними автоматизованими системами виконавців етапів мультимодальной перевезення - підрядників (стан конкретної перевезення, тарифи, терміни, розкладу, стан технічних засобів) і замовників (прийом заявок);

    Випуск4

    | Випуск4

    - ведення бази даних контрагентів, транспортних та інших технічних засобів, вантажів з повним набором характеристик і умов перевезення, місць обробки вантажів і т. Д .;

    - забезпечення захисту інформації.

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

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

    1. Вибір варіантів маршруту, розбиття на етапи.

    2. Визначення варіантів здійснення перевезення на кожному етапі з використанням різних видів транспорту.

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

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

    5. Розрахунок загальної тривалості, вартості доставки і надійності.

    6. Вибір найкращого варіанту з урахуванням виконання умов договору із замовником перевезення.

    7. Укладання договорів або подача заявок обраним виконавцям перевезення, оформлення документів.

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

    Алгоритм отримання інформації про стан вантажу може бути наступним. При прибутті (вибуття) в пункт призначення, а також в моменти початку і закінчення операцій

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

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

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

    цям прямокутних областей. Відразу відзначимо, що окремим розміщення з n об'єктів відповідає, за оцінками [3], O (4n2) різних векторів двійкових змінних, і для вирішення практичних завдань розміщення кінцевого безлічі взаємопов'язаних прямо -угольних об'єктів використовуються різні евристичні алгоритми. Завдання оптимально щільного розкрою - упаковки геометричних об'єктів зазвичай вирішуються алгоритмами, побудованими:

    - на методі послідовного одиночного розміщення, розробленого Ю. Г. Стоячи-ном;

    - на методі прямоугольно орієнтованого лінійного розкрою, запропонованого

    Е. А. Мухачева;

    - на методі силових аналогій (Н. Р. Квін).

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

    У загальному випадку при розміщенні партії

    контейнерів розміром G штук, що складається з в

    B типів, де G = ^ gb і gb - кількість контейнерів b-го типу, для повного перебору всіх можливих розміщень буде потрібно

    G!

    перестановок контейнерів.

    Якщо припустити, що основних типів контейнерів тільки чотири, то для партії з 8 контейнерів треба перебрати близько 5 тисяч перестановок, для 16 - вже понад 200 мільярдів, для 32 - більше 1,5 • 1031. На знаходження квазіоптимального (раціонального) розміщення партії з 25 контейнерів серед 1500 різних перестановок витрачається близько 4,5 хвилини на Pentium MMX / 200 Мгц / 64 Мб; на Pentium-III / 650 Мгц / 128 Мб - 8-9 секунд (для повного перебору всіх варіантів знадобиться понад 5 мільйонів років!). На ньому ж розміщення партії в 51 контейнер займає 26-28 секунд при переборі 1500 перестановок. При цьому витрачається час істотно залежить від якості одержуваних наближень, так як алгоритм побудований таким чином, щоб не доводити до кінця

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

    У загальному вигляді евристичний алгоритм розміщення партії контейнерів на основі випадкового пошуку виглядає наступним чином:

    1. Внесення відносини часткового порядку фа на безлічі всіх контейнерів {О.}, т. Е. Фа: N ^ {О.}.

    2. Формування стековой структури {<5} на поточній складському майданчику, т. Е. Ц: {2} ^ {5}, де {2} - сукупність складських зон, заборонених для розміщення вантажів, упорядкованих по? -Й координаті північно-західного кута кожної зони.

    3. Заповнення з одночасним перетворенням складських стеків {5 ^} контейнерами чергової партії {Про}, т. Е.

    в; (&}&})->&} • '

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

    5. Вибір нового відносини фа часткового порядку і перехід до пункту 1 або припинення перебору варіантів з вибором поточного кращого варіанту розміщення контейнерів.

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

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

    випуск 4

    | Випуск4

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

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

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

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

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

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

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

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

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

    Спочатку проводиться 54 генерації перестановок контейнерів з трьома раз-

    Мал. 2. Розміщення партії контейнерів на складі після 4000 випадкових перестановок

    випуск 4

    | Випуск4

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

    Для партії з 51 контейнера інтерактивний спосіб пошуку серед 4000 перестановок поліпшив значення критерію з 117 до 113 м (рис. 2). Застосовувався випадковий режим генерації перестановок. Після цього, починаючи з отриманої квазіоптимальний перестановки, було згенеровано ще 5000 перестановок за допомогою методу повного перебору. Це дозволило поліпшити результуюче значення критерію до 109 м (рис. 3).

    Пошук оптимального розміщення контейнерів в автоматичному режимі з генерацією 5000 перестановок привів до значення критерію, рівному 108 м з витратами часу в два рази меншими, ніж при інтерактивному режимі (рис. 4).

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

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

    Генетичні алгоритми працюють з сукупністю «особин» - населенням, каж-

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

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

    Отже, кожна особина характеризується своєю хромосомою. Хромосома визначає пристосованість особини / (Бк) (к = 1, ..., п; п - чисельність популяції). Хромосома є ланцюжком символів Бк = (5к,, ..., 5к), N - довжина ланцюжка. симво-

    ли - це гени особини, розташовані в хромосомі 5к. Завдання алгоритму полягає в максимізації функції пристосованості.

    Еволюція складається з послідовності поколінь. Для кожного покоління відбираються особини з великими значеннями пристосованість. Хромосоми пристосованих особин рекомбінуються і піддаються малим мутацій. Формально схема генетичного алгоритму може бути представлена ​​наступним чином (популяція? -Го покоління позначається як {5к (t)}):

    Крок 0. Створити початкову популяцію

    {5к (0)}.

    Крок 1. Обчислити пристосованість / (5к) кожної особини 5к популяції {5к (t)}.

    Крок 2. Виробляючи відбір особин (Sk) відповідно до їх пристосованості f (Sk) і застосовуючи генетичні оператори (рекомбінації і точкові мутації) до відібраних особинам, сформувати популяцію наступного покоління {Sk (r + 1)}.

    Крок 3. Повторювати кроки 1, 2 для t = 0, 1,

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

    Існує ряд конкретних варіантів генетичного алгоритму, які відрізняються за схемами відбору, рекомбінації, за формою подання хромосом і т. Д. Наприклад, якщо потрібно розмістити задану множину стопок контейнерів на заданій прямокутній площині (підстава трюму судна), то для роботи алгоритму ці стопки вважаються пронумерованими, наприклад, в порядку їх слідування в списку. Як хромосоми, яка описує особина, буде виступати будь-яка послідовність номерів фігур без повторів (далі - пріоритетний список, priority list, PL). Такий опис відповідає біологічному терміну «генотип». Само по собі воно не дає можливість зрозуміти, як виглядає упаковка, яка відповідає деякому порядку перерахування предметів. Фенотип особини в даному випадку - це геометричне розміщення контейнерів на площині, що задається набором координат розташування кожної стопки контейнерів. Тільки за фенотипом особини можна судити про якість розміщення - про частку корисної площі, частці площі втрат, довжині відповідної упаковки.

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

    Випуск4

    | Випуск4

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

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

    1. Створити вихідну популяцію з N особин. Кожна особина задається випадковою перестановкою номерів стопок контейнерів з

    списку: S, = (S,, S, S,), k = 1..М g-число

    k k1 k2? •••-> kN

    стопок контейнерів, S = 1..m - номер стопки

    ki

    контейнерів, sKi * sKj Vfc, Vi = 1..ті.

    2. Провести схрещування всіх особин з випадковим для кожної особини партнером. Зберегти всіх нащадків (2N).

    3. Обчислити значення пристосованості для кожної особини, включаючи потомство, за допомогою процедури декодування: f (Sk) = decoder {Sk), k -1 ... 3 Ns.

    4. метод значення пристосованість за спаданням, залишити Ns кращих особин.

    5. Застосувати оператор мутації до кожної особини з малою вірогідністю ц.

    6. Повторювати етапи 2-5 до тих пір, поки найвище значення функції пристосованості в популяції не перестане змінюватися. Передбачити ще два способи завершення еволюції: якщо виконано Ns поколінь і примусове завершення.

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

    Нехай Sk, Sm - дві хромосоми, два списки стопок контейнерів, відповідні парі батьків, Sk, Sm - два нових

    knew mnew

    списку, створені схрещуванням. Спочатку вибираються два випадкових числа g і q, 1 < ^ q < N Починаючи з випадковою позиції g, скре-

    щівающій оператор копіює д елементів з 5к в 5к. Потім залишилися позиції в 5,

    до knew КПЕ-м

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

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

    Як класичний декодера для генетичного алгоритму розглядається алгоритм з процедурою декодера «покращений нижній лівий», 1БЬ, на першому кроці якого перший прямокутник поміщається в лівий нижній кут. На другому кроці: послідовно пересувається / -й прямокутник згідно пріоритетного списку, / = 2, ..., N починаючи від верхнього правого кута трюму вліво настільки, наскільки це можливо, потім вниз, знову вліво, вниз і т. Д., Причому при розташуванні смуги горизонтальне пересування вліво має перевагу. Переміщення відбувається до тих пір, поки прямокутник не зможе бути зрушене вліво або вниз. Один з недоліків цього декодера - низька середня щільність упаковки.

    Для завдання прямокутного розкрою дослідний колектив Е. А. Мухачева розробив евристичну процедуру, що називається «блоковий декодер». Цей алгоритм приміщення прямокутників на смугу в порядку їх перерахування в пріоритетному списку - один з найефективніших. Блоковий декодер вважається найменш трудомістким для вирішення завдань прямокутного розкрою. Серед його переваг - важлива можливість обліку утворилися в процесі розміщення попередніх предметів пустот. Однак при зміні постановочної частини можливе застосування і інших декодерів, приклади яких можна знайти в [5].

    Список літератури

    1. «Концепція узгодженої транспортної політики держав - учасниць СНД на період до 2010 г.», затв. Рішенням Ради глав урядів СНД, 2004.

    2. Ворожейкіна Т. М., Ігнатова В. Д. Логістика в АПК. - М .: Колос, 2005.

    3. Віхров Н. М., Нирків А. П. Моделі технологічних процесів на транспорті. - СПб .: Суднобудування, 2002.

    4. Нирків А. П. та ін. Генетичні алгоритми в математичному моделюванні перевантажувальних процесів / Зб. тр. VIII міжнародній науково-практичній конференції «Дослідження, розробка і застосування високих технологій в промисловості» // Високі технології, фундаментальні дослідження, освіту: Т. 2. - СПб .: Изд-во політехн. ун-ту 2009.

    5. Ермаченко А. І. Моделі і методи розв'язання задач прямокутного розкрою і упаковки на базі метаеврістікі «Пошук із заборонами»: дис. ... канд. техн. наук. - Уфа, 2004.

    УДК 517 Д. П. Голоскоков,

    д-р техн. наук, професор, СПГУВК

    МОДЕЛЮВАННЯ ТЕМПЕРАТУРНИХ ПОЛІВ ПРИ ЧАСТКОВОМУ ПОРУШЕННЯ теплоізоляції

    MODELLING TEMPERATURE FIELDS AT PARTIAL IMBALANCE THERMAL

    COVERING

    У статті отримані аналітичні рішення трьох основних крайових задач для рівняння Лапласа в півпросторі - завдання Дирихле, Неймана і третьої крайової задачі. Рішення будуються на основі розкладів в інтеграл Фур'є - Бесселя. Як додаток запропоновані математичні моделі розподілу температурних полів при частковому порушенні теплоізоляції нагрітих поверхонь суднового енергетичного устаткування і металевих конструкцій суднових машинних приміщень.

    In article the analytical decisions of three basic boundary problems for Laplace's equation in half-space - problems Dirichlet, Neumann and the third boundary problem are received. Decisions are under construction on the basis of decomposition in Fourier - Bessel's integral. As the appendix mathematical models of distribution of temperature fields are offered at partial infringement of a thermal protection heated surfaces of the ship power equipment and metal designs of ship machine premises.

    Ключові слова: крайова задача, задача Дирихле, завдання Неймана, третя крайова задача, рівняння Лапласа, інтеграл Фур'є - Бесселя, розкладання Фур'є - Бесселя, завдання Штурма - Ліувілля.

    Key words: boundary problem, Dirichlet's problem, Neumann's problem, the third boundary problem, Laplace 's equation, Fourier - Bessel's integral, Fourier - Bessel's decomposition, Sturm - Liouville's problem.

    1. Завдання Дирихле для рівняння Лапласа в півпросторі. Розглянемо першу крайову задачу для рівняння Лапласа в півпросторі: знайти функцію і (г, г), що задовольняє рівняння Лапласа в півпросторі 0 < г < да, т > 0 і граничним умовам:

    л 1 Е '

    Дм = -

    г аг

    Ем

    &

    ~ а

    ; (1)

    oz

    1г- »0

    lz- + 0

    - обмежена, і \ ^

    = / (4

    - обмежена; (2)

    (3)

    Будемо шукати рішення у вигляді і (г, т) = Я (г) 2 (т).

    Поділяючи змінні, отримаємо:

    (ГЯ) + ХгЯ = 0, причому

    Я | - обмежена, Я - обмежена; (5)

    (4)

    Комерсант - = 0. (6)

    У рівняннях (4) і (6) штрихами позначена звичайна похідна за відповідним аргументу - по змінної г для функції Я (г) і по змінної г для функції 2 (Т).

    [53 |

    випуск 4


    Ключові слова: АЛГОРИТМ /АВТОМАТИЗОВАНЕ УПРАВЛІННЯ /мультимодальні перевезення /ALGORITHM /AUTOMATED MANAGEMENT /MULTIMODAL TRANSPORT

    Завантажити оригінал статті:

    Завантажити