Оптимізація графіка роботи водіїв автопідприємства з урахуванням їх взаємодії в транспортному процесі, з обмеженням ЄУТР

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

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

Оптимізація графіка роботи водіїв автопідприємства з урахуванням їх взаємодії в транспортному процесі, з обмеженням ЄУТР

Хомин Н.Я., Національний транспортний університет, Київ, Україна,

Optimization of the work schedule of the drivers of the automobile company taking into account their interaction in the transportation process, with the limitation of eutr

Khomin N.Y., National Transport University, Kyiv, Ukraine,

Реферат

Хомин Н.Я. Оптимізація графіка роботи водіїв автопідприємства з урахуванням їх взаємодії в транспортному процесі, з обмеженням ЄУТР / Н.Я. Хомин // Вісник Національного транспортного університету. Серія «Технічні науки». Науковий журнал. - К. : НТУ, 2023. - Вип. 1 (55).

Проаналізовано можливі варіанти режимів праці та відпочинку водіїв вантажівок на міжнародному сполученні. Розроблено модель оптимізації плану роботи автопарку.

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

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

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

КЛЮЧОВІ СЛОВА: РЕЖИМ РОБОТИ ВОДІЇВ, МАРШРУТИЗАЦІЯ, РОЗКЛАД РОБОТИ.

Abstract

режим праці та відпочинку водій вантажівки

Khomin N.Y. Оptimization of the work schedule of the drivers of the automobile company taking into account their interaction in the transportation process, with the limitation of EUTR. Visnyk National Transport University. Series «Technical sciences». Scientific journal. - Kyiv: National Transport University, 2023. - Issue 1 (55).

Possible variants of work and rest regimes of truck drivers on international traffic have been analyzed. A model for the optimization of the fleet operation plan has been developed. This model is two-level, that is, the general graph contains subgraphs that are designed with incompatible vertices to determine the active and shortest time schedule, unlike known optimization methods.

Each of the subgraphs displays an alternative route and truck schedule. The model also contains constraints on the total cycle time and the active period of availability of unloading points, so-called time windows. Integer binary variables are applied to transform the initial graph into a cycle-free graph. Integer programming with a guaranteed optimal solution is used to find the shortest schedule.

The obtained results are valid and comply with the rules of the European

Agreement. They indicate that choosing the best schedule for an individual car on a single route is not the best decision for the entire fleet and the entire order flow.

KEY WORDS: DRIVERS' WORK MODE, ROUTING, WORK SCHEDULE.

Постановка проблеми

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

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

Аналіз досліджень і публікацій

Про проблему узгодження роботи автотранспорту з іншими обслуговуючими ланками при забезпеченні вчасної та якісної доставки вантажів в місце призначення згадується в багатьох сучасних працях, у тому числі [0, 2, 3]. Вчені називають різні шляхи її вирішення, Зокрема, в роботі [1] наголошується, що узгодження роботи рухомого складу та, наприклад, навантажувально-розвантажувальних засобів можливе, якщо застосовувати так звані «плаваючі» розклади руху транспортних засобів, які дають змогу змінювати час подачі рухомого складу в певному діапазоні (наприклад, 2-5 %) внаслідок затримок транспорту або невчасного упорядкування роботи вантажної техніки.

У роботі Н. Шраменко досліджено вплив тривалості митних процедур на дотримання часу доставки з врахуванням вимог ЄУТР [4]. При цьому застосовано імітаційне моделювання, яке потребує чималу кількість початкових даних та довгий час спостережень. Митні процедури є дуже вагомим обмеженням і випадковим чинником, який важко передбачити, з одного боку, і який стримує вчасне прибуття в пункт призначення. Особливо це стосується в'їзду транспортних засобів і ввезення товарів на територію ЄС з України. Однак, потрібно відмітити тут присутність суб'єктивних чинників, які не становлять наукового інтересу для досліджень. Тому час виконання митних процедур можна вважати величиною в цілому передбачуваною.

Існує дуже багато праць, які пов'язані з маршрутизацією автомобілів, у тому числі на далекі відстані. Одні автори вважають її первинним етапом при складанні розкладів [5]. При цьому застосовуються відомі та модифіковані алгоритми: Дейкстри [6], мурашиний [9], відпалу [7] тощо. Більшість дослідників схиляються до того, що задача маршрутизації та складання розкладів має розв'язуватись комплексно, особливо щодо пасажирського транспорту [7, 3]. Однак, застосування правил роботи водіїв міжнародних екіпажів значно ускладнюють формалізацію проблеми. Нижче подано огляд деяких спроб здійснити її.

Проблема маршрутизації транспортного засобу, що залежить від часу, визначається наступним чином [9]. Автопарк фіксованої місткості обслуговує клієнтів постійних вимог з центрального депо. Клієнти розподіляються за транспортними засобами та транспортними засобами, які маршрутизуються, щоб мінімізувати загальний час маршрутів. Час у дорозі між двома клієнтами або між клієнтом і депо залежить від відстані між пунктами та часу доби. Також можуть бути присутні часові вікна для обслуговування клієнтів. Залежна від часу задача комівояжера є окремим випадком задач маршрутизації, у якому доступний лише один транспортний засіб нескінченної місткості. Представлені формули змішаного цілочисельного лінійного програмування, які розглядають функції часу подорожі як ступінчасті функції. Характеристики та властивості таких задач виключають модифікацію більшості алгоритмів, які були розроблені для задачі маршрутизації транспортного засобу. Проблема маршрутизації транспортного засобу, залежного від часу визначається наступним чином. Автомобільний парк фіксованих потужностей обслуговує клієнтів з фіксованими вимогами з центрального депо. Клієнти призначені для транспортних засобів, а транспортні засоби маршрутизовані таким чином, щоб загальний час маршрутів було мінімізовано. Час подорожі між двома клієнтами або між клієнтом і депо залежить від відстані між пунктами та часом дня. Також можуть бути присутні часові вікна для обслуговування клієнтів. Характеристики та властивості задачі виключають модифікацію більшості алгоритмів, розроблених для проблеми маршрутизації транспортного засобу [10].

Модель, представлена в статті [12], є дуже гнучким і може бути налаштована для розгляду різних наборів правил, встановлених урядовими положеннями та профспілковими договорами. Представлено підхід до динамічного програмування, а його ефективність демонструється для регулювання робочого часу в Сполучених Штатах і в Європейському Союзі [13]. У даній роботі досліджується проблема планування мінімальної тривалості водія вантажівки (MD-TDSP), яка є проблемою визначення графіка, що відповідає чинному законодавству, в якому вся робота починається в межах одного з відповідних часових вікон і має мінімальну тривалість. У MD-TDSP, водій вантажівки може приймати відпочинкові періоди лише на місцях або в місцях відпочинку. Більшість попередніх підходів до планування водіїв вантажних автомобілів дозволили водіям вантажних автомобілів будь-коли відпочити. Проте розгляд місця розташування відповідних місць відпочинку є особливо важливим, якщо використовуються автомагістралі, а водії вантажних автомобілів повинні продовжувати керувати автомобілем до досягнення наступної відповідної зони відпочинку. Ця стаття показує, як в рамках підходу до розгляду можуть розглядатися факультативні правила в Європейському Союзі, які дозволяють робити перерви та періоди відпочинку в двох частинах [2].

У [7] сформульована єдина модель маршрутизації вантажівки з часом, що залежать від часу, правилами HOS, кількома місцями доставки та вікнами обслуговування. Мета полягає в мінімізації загального часу, необхідного для обслуговування певної кількості клієнтів. У цій роботі є модель, що залежить від часу вантажівки та планування вантажівки з часовими вікнами та правилами «Години обслуговування» (HOS). Використано жадібну евристику, щоб генерувати хороші початкові рішення проблеми, які були додатково вдосконалені за допомогою імітаційного відпалу.

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

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

При розгляді запитів на перевезення на великі відстані тривалість періодів відпочинку та перерв впливає на загальний час, необхідний для виконання. У Європейському Союзі Регламент (ЄС) № 561/2006 визначає правила, що стосуються кількості, тривалості та часових інтервалів, коли необхідно вживати періоди відпочинку та перерви. У даному дослідженні запропоновано дві змішані цілі лінійні моделі програмування та стратегії оптимізації, які разом з алгоритмом перетворення дозволяють планувати діяльність водія відповідно до цього правила для даної послідовності розташування клієнтів та інших зупинок, які необхідно відвідати. Одна з моделей враховує всі правила, включаючи розширені правила, а інша враховує регулярні вимоги. Кожне місцезнаходження клієнта має один або декілька часових вікон, серед яких має бути зроблений вибір. Особливістю є розгляд «м'яких» часових вікон, які досі не вивчалися в цьому контексті. Якщо часові вікна не можуть бути виконані, отриманий графік надає диспетчеру важливу інформацію, необхідну для встановлення кращого графіка. У режимі онлайн-перепланування запізнення може бути виявлено на ранній стадії, так що можна реорганізувати графік або обговорити час прибуття з клієнтами до того, як зв'язок та витрати збільшаться, а подальші затримки або скасування неминучі. На додаток до математичних моделей, був розроблений міопічний алгоритм, який може тільки "побачити" маршрут до наступного припинення клієнта і відповідного часового вікна клієнта заздалегідь і планує діяльність водія відповідно. Прості стратегії були обрані для інтеграції додаткових правил. Тестові приклади були отримані з реальних даних і включали маршрути транспортних засобів протягом одного тижня. Проведено аналіз чисельних результатів, отриманих за допомогою математичних моделей та міопічного алгоритму, за часом виконання, затримкою та загальним часом руху [12].

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

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

Формулювання мети і постановка завдання

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

Застосовано такі припущення.

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

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

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

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

Виклад основного матеріалу

Альтернативні маршрути можна урізноманітнити розробкою варіантів допустимих розкладів роботи і відпочинку водіїв. Їх отримано при застосуванні допустимих можливих опцій, як це зроблено в роботі [12]:

- поділу часу перерв керування;

- поділу часу міжзмінного відпочинку;

- зменшення часу щодобового відпочинку;

- збільшення щоденного часу керування.

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

Для прикладу покажемо варіанти виконання вантажних перевезень за маршрутом Львів (Україна) - Бидгощ (Польща). На рисунку 1 показана карта маршруту з Google Map, на якій вказано три альтернативні траси, які проходять відповідно, по магістралях Е40, Е371, Е372.

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

Рисунок 2 - Варіанти розкладів роботи водіїв Figure 2 - Variants of drivers' work schedules

Варіант на рис.2а стосується проїзду по магістралях Е40, Е75, через Краків, Катовіце, Ченстохова, Лодзь. Тривалість навантаження у всіх варіантах - 2 години. Тривалість простою на митниці Краківць-Корчова - 4 години. У зв'язку з тим, що більшість часу простою на митниці - це очікування початку митних процедур, то даний на рис. 2а розклад включає першу частину розділеної перерви в керуванні -- 15 хв. для того, щоб сумістити непродуктивні простої. Час міжзмінного відпочинку тут не скорочується. Тривалість керування збільшена до 10,2 годин. Загальна тривалість циклу становить 29,5 год. Після цього циклу водій може виконувати наступний нескорочений робочий цикл. Такий самий маршрут, але виконаний за продовженою робочою зміною приводить до скорочення тривалості циклу на 2,5 години -- 27,1 год. (рис. 2.б).

Але у цьому випадку час виконання наступних замовлень, або ж руху до пункту наступного завантаження може бути довшим через необхідність застосувати вимогу ст. 6, п. 2. і 3 ЄУТР. Інші розклади також побудовані з дотриманням вимог і приписів (рис. 2.c-d). Якщо після виконання рейсу A. Львів-Бидгощ для водія даного транспортного засобу поставити завдання інших рейсів, то вони будуть виконуватись з різним успіхом, який залежить від:

a) вибраного варіанту розкладу А;

b) вибраного варіанту наступного розкладу B.

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

a) наявну кількість вільних транспортних засобів;

b) допустимий горизонт планування;

c) наявні замовлення.

Задача формулюється так. На період часу T задана множина замовлень P, кожне p_i з яких можна виконати k альтернативними маршрутами і розкладами, які побудовані попередньо. Альтернативні варіанти виконання кожного із замовлень є несумісними в часі. Серед усіх альтернативних маршрутів і відповідних розкладів виконання одного і того ж замовлення потрібно вибрати, щонайбільше, один. Загалом потрібно знайти таку послідовність виконання перевезень заданою кількістю автотранспортних засобів т, при якій загальна тривалість проекту в рамках горизонту планування Т, буде мінімальною, а усі обмеження режимів праці і відпочинку водіїв, а також щодо терміновості замовлень будуть дотримані. Фактично у цій задачі потрібно комплексно виконати такі дії:

a) розподілити наявні транспортні засоби по завданнях, при цьому умова об'язкого залучення усіх т з них не ставиться;

b) вибрати раціональну послідовність виконання замовлень кожним із залучених автопоїздом; виконання усіх відомих замовлень не вимагається;

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

Кожне i-те замовлення може мати такі характеристики:

а) часові вікна \t_bi, t_ei ] , де t_bi - момент часу, не раніше якого його потрібно розпочати у пункті його відвантаження; t_ei - момент часу, до якого його потрібно завершити; впродовж горизонту планування кожне замовлення може мати декілька часових вікон;

б) t_o - фактичний момент початку виконання 7-го замовлення;

в) tf _i - фактичний момент завершення у кінцевому пункті його доставки;

г) t^k - математичне сподівання тривалості виконання замовлення за альтернативним розкладом k, k=1..m, обчислене з припущенням, що водій, який виконував його, попередньо завершив щотижневий цикл керування, і мав відповідний період відпочинку, тобто t^k не залежить від попередньо виконаної роботи.

Оскільки t^k < T, то впродовж горизонту планування кожен з автомобілів може виконати не менше, ніж одне замовленнядекілька замовлень, якщо це не суперечить конвенціям про міжнародні перевезення, наприклад, про заборону каботажних перевезень без відповідної ліцензії []. Якщо замовлень є декілька, то, Щоб розпочати виконання першого з них, потрібно подати транспортний засіб в той пункт, де і-те замовлення є сформоване не пізніше директивного моменту t_{e t}. Час, необхідний водієві, для виконання замовлень потрібно узгодити з правилами ЄУТР. Вибір варіантів розкладу залежить від тривалості руху і простоювання. Отже, потрібно врахувати тривалість нульових пробігів, а також час руху і перерв у поїздці між пунктами i,j.

де tfj _mov - час руху вантажівки між пунктами і та j за k варіантом розкладу;

k

t_i j br - тривалість перерв для відпочинку водія;

k

ti j res - тривалість щоденного відпочинку водія;

t^kj _rrv -- тривалість інших робіт, таких як заправка автомобіля паливом, навантаження

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

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

або для оберненої послідовності виконання.

Усю множину Р відомих замовлень можна відобразити з допомогою змішаного графа A (G,U,V), де G - множина вершин, |g_p g₂,..., g_p-1, g_p j, в якій g₂...gp-\ символізують моменти початку виконання замовлень. Вершина gi - фіктивна, представляє формальний момент початку усього проекту. Вершина g_p -- фіктивна, символізує кінець планового циклу тривалістю Т. U -- множина дуг, кожна з яких відображає часовий зв'язок a'kj між моментами початку виконання і-го та j-го замовлення за k-м варіантом маршруту, одним і тим ж транспортним засобом. Дуги графа A -- зважені. Якщо існує замовлення, то воно відображається у графі A дугою ваги а.>0. При цьому повинна виконуватись вимога (2), або (3). Крім того, з допомогою дуг задаються часові обмеження проекту. Так, дуги а_1л- - це найбільш ранні моменти можливого початку виконання кожного і-го замовлення. Кожна дуга а_іР -- це часовий зв'язок, «чиста» тривалість виконання і-го замовлення так, що ніби транспортний засіб до початку завантаження перебував у і-му пункті уже, і на марний, чи нульовий пробіги, а також на відпочинок водія не витрачено часу. Очевидно, що.

Умова (4) виконуватиметься для будь-яких і та j .

Дуга з від'ємною вагою, --а. ₁ відображає часове обмеження для виконання і-го замовлення. Наприклад, --а_Р.₁ -- це дозволений час для виконання усіх відомих замовлень (як правило, він збігається з періодом Т). Усі дуги --а_Р._і відображають директивні моменти найбільш пізнього закінчення і-х замовлень. Усі ж інші неіснуючі, або несуттєві зв'язки відображені дугами з вагою -да. У моделі графа A (рис. 3) задана, також, множина V -- ребер (зв'язки без стрілок, або з обопільними стрілками), кожному [i, j] з яких поставлена у відповідність пара ваг а., a_j._i.

Якщо між вершинами i, j є ребро, то це означає їх часову взаємозалежність і відповідні і, та j замовлення виконуватимуться в довільному порядку. Шляхом в графі A(Q,U,V) називається послідовність дуг U_k _|(g₁,gj),^,gj),...(g_x,g_p)j, де всі вершини різні, а початкова і кінцева -- можуть збігатись. Контур -- це замкнутий шлях в графі А. Вагою шляху назвемо суму ваг дуг, що входять до нього. Вага шляху виражається чисельно в межах інтервалу (-да,+да ), тобто є дійсним числом. В зв'язку з цим використовується термін контур, або шлях додатної (або від'ємної) ваги. Шлях найбільшої додатної ваги в графі А, що з'єднує і, j вершини, позначимо Щ. Якщо в графі A не існує шляху з вершини і у вершину j через ліквідацію деяких ребер, то Щ= --да.

До процесу перевезення може бути задіяно m транспортних засобів. Вони повинні працювати синхронно, виконуючи по декілька замовлень послідовно. Це означає, що у графі А потрібно знайти m ланцюгів, які починаються у вершині g₁, проходять через деякі вершини графа, які стосуються наявних замовлень і закінчуються у вершині g_p. Шукані ланцюги мають проходити по тих вершинах, для яких q_x._y >0. Якщо ланцюг доходить до вершини у, а далі нема жодного шляху у графі А з невід'ємною, або ненульовою вагою, то ланцюг при цьому прямує до вершини g_p.

Рисунок 3 - Модель складання розкладу виконання замовлень на перевезення вантажів:

а) змішаний граф з відміченими на ньому вагами а₁₀ відповідних дуг; б) орієнтований граф без циклів і контурів додатної ваги з відміченими змінними 5₁.,

Figure 3 - The model of the schedule of execution of cargo transportation orders: a) a mixed graph with the weights а₁₀ of the corresponding arcs marked on it; b) directed graph without cycles and contours of positive weight with marked variables 5_LJ

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

Формальний зміст задачі побудови розкладу полягає у тому, що потрібно знайти шляхи Щ для усіх, і, j=1...P. Ваги цих шляхів визначають моменти найбільш раннього початку виконання кожного 7-го замовлення [18]. Для того, щоб шуканий розклад {р_л,t_o2,...t_op] був однозначним (не було часового неузгодження), потрібно дотримуватися умови

Момент початку виконання будь-якого 7-го замовлення шукається із співвідношення [12]:



Момент завершення будь-якого і-го замовлення знаходимо з виразу:

Розклад, для якого для всіх замовлень й усіх автомобілів виконується умова (5) називається активним, а величина t_fj, що розрахована за (6), буде найбільш раннім завершенням ,-го замовлення. Існує взаємно однозначна відповідність між множиною всіх активних розкладів, що побудовані з графа A і множиною P (A) всіх графів, які не містять контурів додатної ваги [18]. Отже, однозначним вважаємо розклад, що породжений графом A(G,U,V)і не містить контурів додатної ваги, а значить і ребер V. Застосовано послідовний аналіз варіантів з перебором усіх графів з множини P(A), і пошуком серед них оптимального за критерієм (4). Для організації такого пошуку, з метою уникнути непродуктивного перебору неоптимальних варіантів, використано процедуру послідовного розбивання P (Л) на підмножини.

Між вершинами графа А, які відносяться до однієї підмножини k, встановлені ребра, які означають їх незалежність. Однак фактично ці вершини відображають взамовиключні альтернативи одного і того ж замовлення, хоча й мають різні часові зв'язки. Такі відношення неможливо відобразити в графічній моделі з допомогою дуг, або ребер. Наприклад, на рис. 3 є обведені штриховою лінією вершини, які означають різні маршрути, або різні розклади. Між ними проставлено ребра, хоча має бути встановлений жорсткий взаємовиключний зв'язок. Це означає, що розклад виконання замовлень має будуватись по шляху в графі, який проходить лише через одну з трьох вершин 2.1 / 2.2 / 2.3 і, відповідно 3.1 / 3.2 / 3.3. Для реалізації цього введено додаткові змінні 5_t є {0,1 j . Якщо шлях проходить у графі через вершину g,._k, то усі інші вершини підмножини k мають бути ізольовані з використанням змінної Sтак:

де s - кількість альтернативних шляхів виконання j-го замовлення.

Алгоритм розв'язування задачі є таким. Множину замовлень G також розбито на k непорожніх підмножин G_k, k = 1,2,...,s, кожна з яких відображає унітарне замовлення. В задачі потрібно побудувати розклад виконання заданих замовлень на перевезення, тобто для кожної поїздки з вантажем j є G вказати момент її початку t_oj, і момент закінчення t_fj, а також номер автопоїзда M_k, на якому вона повинна виконуватись. Оптимальним вважається розклад для якого виконується умова:

де F - функція мети, що є, у даному випадку, загальною тривалістю проекту. Враховуючи уведені змінні (5), обчислення критерію буде таким:

Зміст операцій з графом A полягає в наступному.

1. Ототожнити усі вершини, які входять у кожну підмножину k=1...s в одну. Вершини будь- якої множини k будуть об'єднані, а усі зв'язки їх з іншими вершинами, що не належать цій множині, будуть еліміновані, крім вершини, з якою проведено утотожнення. Наприклад, підмножина 2 графа початкової моделі, що на рис 3 а, містить 3 вершини: 2.1, 2.2, 2.3. В результаті ототожнення у підмножині еліміновано вершини 2.2 і 2.3, які стають ізольованими, оскільки змінні 8_і.₂.2 та 5_г-.₂.₃ набувають нульових значень, тобто усі зв'язки цих вершин також знищуються. Представником множини стає вершина 2.1, зв'язки якої з іншими вершинами графа залишаються.

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

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

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

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

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

Результат застосованого впорядкування початкового графа -- орієнтований граф без циклів. Окремі результати оптимізації за розробленим алгоритмом подано на рис. 3 b. Потовщеними стрілками показані дуги на результуючих графах, які входять до критичного шляху, тобто такі, за якими обчислюються моменти ранніх закінчень виконання замовлень t_{o t}.

Результати досліджень

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

A) Львів (Україна) - Бидгощ (Польща); B) Львів-Вроцлав (Польща), C) Брно (Чехія)-Львів; D)Катовіце (Польща) - Львів; E) Краків (Польща)-Львів; F) Брно-Краків. Для виконання цих перевезень можуть бути використані 5 вантажних автопоїздів, які розташовані на виробничій базі під містом Львовом. Виконання кожного замовлення може бути здійснено із застосуванням різних схем організації праці і відпочинку водія, а також різних маршрутів. Показники тривалості різних варіантів цих замовлень подано в таблиці 1. Горизонт планування -- 56 годин, що відповідає одному тижню роботи. Кожним транспортним засобом керує один водій. Відпочинок і перерва водія може здійснюватись тільки у фіксованих транспортних пунктах. Тривалість простою на митному контролі в пунктах пропуску на кордоні Україна-Польща -- 4 год. Тривалість навантаження/розвантаження автопоїзда для усіх замовлень є однакова -- 2 години. наведені в таблиці параметри маршрутів обчислені.

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

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

a) час нульового пробігу до місця першого завантаження;

b) час простою, пов'язаного з щоденним відпочинком водія;

c) час простою, пов'язаний перервами у керуванні;

d) час очікування початку часових вікон.

Для того, щоб, наприклад, знайти перехідну тривалість від замовлення А1 (Львів-Бидгощ) до замовлення Е1 (Краків-Львів), визначимо залишковий робочий час водія після виконання замовлення А1 згідно з табл. 1. Тривалість цього циклу становить 25,2 год., у тому числі робота водія -- 13 годин, розподілений відпочинок 3 + 9 =12 годин. Керування транспортним засобом -- 8,2 годин. Оскільки водій не перевищив дозволену нормативну тривалість робочого часу, то у нього залишився резерв часу для того, щоб добратись в Краків для завантаження. Часове вікно в Кракові -- [32, 44]. Крім того, після останнього міжзмінного відпочинку на маршруті А1, Львів-Бидгощ використано 4,5 годин робочого часу разом з 2 години розвантаження у Бидгощі. Час руху за маршрутом Бидгощ-Краків -- 5,2 год. по трасі A1. Це означає, що впродовж чинної зміни водій зможе виконати поїздку до Кракова. У Кракові транспортний засіб має вибір: розпочати 11 годинний відпочинок і завантажитись, або ж простояти близько 40 хвилин до початку завантаження, завантажитись упродовж 2 годин і відправитись на міжзмінний відпочинок. У першому випадку витрачається зайвий час на простоювання, тому доцільно вибрати другий, згідно з яким тривалість перехідного процесу до завантаження становить: 5,2 +11 = 16,2 годин. Після початку виконання циклу А1 до початку E1 минає 41,4 години, що вкладається у друге часове вікно.

Висновки та перспективи подальших досліджень

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

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

Таблиця 1 - Параметри виконання замовлень із дотриманням правил ЄУТР

Table 1 - Parameters of execution of orders in compliance with EUTR rules

Позна чення	Початковий- кінцевий пункти	Часові вікна, годин	Тривалості виконання, годин	Тривалість роботи водія, годин	Тривалість керування, годин
A	Львів-Бидгощ	[24; 32]	1) 25,2	1) 13	1) 8,2
		[48; 56]	2) 26	2) 15	2) 11
			3) 27,1	3) 16	3) 7,7
			4) 29,5	4) 19	4) 10,2
B	Львів-Вроцлав	[12; 20]	1) 19,52	1) 10,5	1) 6,5
		[29; 38]	2) 20,31	2) 12	2) 6,5
			3) 23,1	3)	3) 8,2
			4) 29,2	4)	4) 8,2
C	Брно-Львів	[32; 42]	1) 16,7	1)	1)
			2) 21	2)	2)
			3) 25	3)	3)
			4) 31,4	4)	4)
D	Катовіце-Львів	[0; 12]	1) 11	1)	1)
		[25; 37]	2) 14	2)	2)
		[49; 61]	3) 16	3)	3)
E	Краків-Львів	[10; 22]	1) 9,5	1)	1)
		[32; 44]	2) 12,5	2)	2)
			3) 14	3)	3)
F	Брно-Краів	[0; 12]	1) 10	1)	1)
		[20; 32]	2) 11	2)	2)
		[46; 58]	3) 12,5	3)	3)

Рисунок 4 - Результати оптимізації міжнародних маршрутів з врахуванням норм ЄУТР Figure 4 - Results of optimization of international routes taking into account EUTR norms

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

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

Перелік посилань

режим праці та відпочинку водій вантажівки

1. Бондарєв С. І. Обґрунтування математичної моделі розрахунку тривалості оборотного рейсу при виконанні міжнародних автоперевезеннях Scientific Journal «ScienceRise» №3/2(3)2014 DOI: 10.15587/2313-8416.2014.27461 7-10.

2. The minimum duration truck driver scheduling problem Goel, A. EURO J Transp Logist (2012) 1: 285. https://doi.org/10.1007/s13676-012-0014-9

3. Taran, I & Litvin V. Determination of rational parameters for urban bus route with combined operating mode. Transport Problems 2018, V.13 Issue 4. 157-171 DOI: 10.20858/tp.2018.13.4.14

4. Шраменко ВПЛИВ ТРИВАЛОСТІ МИТНОГО ОФОРМЛЕННЯ НА СТРОК ДОСТАВКИ ВАНТАЖІВ У МІЖНАРОДНОМУ СПОЛУЧЕННІ

5. Hokey Min Combined Truck Routing and Driver Scheduling Problems under Hours of Service Regulations Final Report August 20, 2009

6. G. Prokudin, О. Chupaylenko, O. Dudnik, O. Prokudin, А. Dudnik, V. Svatko 2018 APPLICATION OF INFORMATION TECHNOLOGIES FOR THE OPTIMIZATION OF ITINERARY WHEN DELIVERING CARGO BY AUTOMOBILE TRANSPORT Eastern-European Journal of Enterprise Technologies 2/3 ( 92 ) 2018 51-59

7. Vidit Divyang Shah Time Dependent Truck Routing and Driver Scheduling Problem with Hours of Service Regulations Northeastern University Boston, Massachusetts December 19, 2008

8. European agreement concerning the work of crews of vehicles engaged in international road transport (AETR) (Consolidated version*)

9. В.Д. ДАНЧУК, В.В. СВАТКО ОПТИМІЗАЦІЇ ПОШУКУ ШЛЯХІВ ПО ГРАФУ В ДИНАМІЧНІЙ ЗАДАЧІ КОМІВОЯЖЕРА МЕТОДОМ МОДИФІКОВАНОГО МУРАШИНОГО АЛГОРИТМУ System Research & Information Technologies, 2012, № 2 78-86.

10. Jean-Yves Potvina,b,*,Ying Xua,b, Ilham Benyahiac Vehicle routing and scheduling with dynamic travel times doi:10.1016/j.cor.2004.09.015 J.-Y. Potvin et al. / Computers & Operations Research 33 (2006) 1129-1137

11.Stetsenko I.V. State equations of stokhastic timed Petri Nets with Informational relations // Cybernetics and Systems Analysis. - 2012. - 48, N 5. - P. 784-797.

12. Bernhardt, A.; Melo, Teresa; Bousonville, Thomas; Kopfer, Herbert (2016) : Scheduling of driver activities with multiple soft time windows considering European regulations on rest periods and breaks, Schriftenreihe Logistik der Fakultat fur Wirtschaftswissenschaften der htw saar, No. 12, Fakultat fur Wirtschaftswissenschaften der htw saar, Saarbrucken

13. Goel, A. and Vidal, T. (2014). Hours of service regulations in road freight transport: An optimization-based international assessment. Transportation Science, 48(3):391-412.

14. Vehicle routing with dynamic travel times: a queueing approach T. Van Woensela,*, L. Kerbacheb, H. Peremansc and N. Vandaeled European Journal of Operational Research * January 2008

15. Chryssi Malandraki , Mark S. Daskin Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms Transportation Science Volume 26, Issue 3 August 1992 Pages 161-260 https://doi.org/10.1287/trsc.26.3.185

16. W Maden et al. Vehicle routing and scheduling with time-varying data: A case study W Maden1, R Eglese2 and D Black2 Journal of the Operational Research Society (2010) 61, , No. 3 515--522

17. Goel, A. The minimum duration truck driver scheduling problem EURO J Transp Logist (2012) December 2012, Volume 1, Issue 4, pp 285-306. https://doi.org/10.1007/s13676-012-0014-9

18. Танаев В. С., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы. Москва: Наука. 1989. 328 с.

REFERENCES

1. Bondarev S. I. Justification of the mathematical model for calculating the duration of a return trip when performing international road transportation Scientific Journal "ScienceRise" No. 3/2(3) 2014 DOI: 10.15587/2313-8416.2014.27461 7-10.

2. The minimum duration truck driver scheduling problem Goel, A. EURO J Transp Logist (2012) 1: 285. https://doi.org/10.1007/s13676-012-0014-9

3. Taran, I & Litvin V. Determination of rational parameters for urban bus route with combined operating mode. Transport Problems 2018, V.13 Issue 4. 157-171 DOI: 10.20858/tp.2018.13.4.14

4. Shramenko THE INFLUENCE OF THE DURATION OF CUSTOMS CLEARANCE ON THE DELIVERY TIME OF CARGO IN INTERNATIONAL COMMUNICATION

5. Hokey Min Combined Truck Routing and Driver Scheduling Problems under Hours of Service Regulations Final Report August 20, 2009

6. G. Prokudin, O. Shupaylenko, O. Dudnik, O. Prokudin, A. Dudnik, V. Svatko 2018 APPLICATION OF INFORMATION TECHNOLOGIES FOR THE OPTIMIZATION OF ITINERARY WHEN DELIVERING CARGO BY AUTOMOBILE TRANSPORT Eastern-European Journal of Enterprise Technologies 2/ 3 (92) 2018 51-59

7. Vidit Divyang Shah Time Dependent Truck Routing and Driver Scheduling Problem with Hours of Service Regulations Northeastern University Boston, Massachusetts December 19, 2008

8. European agreement concerning the work of crews of vehicles engaged in international road transport (AETR) (Consolidated version*)

9. V.D. DANCHUK, V.V. SWATKO OPTIMIZATION OF GRAPH PATH SEARCH IN THE DYNAMIC TRAVELER'S PROBLEM USING THE MODIFIED ANT ALGORITHM System Research & Information Technologies, 2012, No. 2 78-86.

10. Jean-Yves Potvina,B,Ying Xua, Ilham Benyahiac Vehicle routing and scheduling with dynamic travel times doi:10.1016/j.cor.2004.09.015 J.-Y. Potvin et al. / Computers & Operations Research 33 (2006) 1129-1137.

11. Stetsenko I.V. State equations of stochastic timed Petri Nets with Informational relations // Cybernetics and Systems Analysis. - 2012. - 48, N 5. - P. 784-797.

12. Bernhardt, A.; Melo, Teresa; Bousonville, Thomas; Kopfer, Herbert (2016) : Scheduling of driver activities with multiple soft time windows considering European regulations on rest periods and breaks, Schriftenreihe Logistik der Fakultat fur Wirtschaftswissenschaften der htw saar, No. 12, Fakultat fur Wirtschaftswissenschaften der htw saar, Saarbrucken

13. Goel, A. and Vidal, T. (2014). Hours of service regulations in road freight transport: An optimization-based international assessment. Transportation Science, 48(3):391-412.

14. Vehicle routing with dynamic travel times: a queuing approach T. Van Woensela,*, L. Kerbacheb, H. Peremansc and N. Vandaeled European Journal of Operational Research * January 2008

15. Chryssi Malandraki, Mark S. Daskin Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms Transportation Science Volume 26, Issue 3 August 1992 Pages 161-260 https://doi.org/10.1287/trsc.26.3.185

16. W Maden et al. Vehicle routing and scheduling with time-varying data: A case study W Maden1, R Eglese2 and D Black2 Journal of the Operational Research Society (2010) 61, , No. 3 515-522

17. Goel, A. The minimum duration truck driver scheduling problem EURO J Transp Logist (2012) December 2012, Volume 1, Issue 4, pp 285-306. https://doi.org/10.1007/s13676-012-0014-9

18. Tanaev V. S., Sotskov Y. N., Strusevych V. A. The theory of painting. Multi-stage systems. Moscow: Nauka. 1989. 328 p.

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

...