УДК 656.073 : 519.872.7
DOI: 10.15587/1729-4061.2022.251082
Оптимізація розкладів раннього збору і вивезення сміття у мегаполісі І. Саукенова, М. С. Оліскевич, І. О. Таран, А. Токтамисова,
Д. Аліакпаркизи, Р. А. Пельо
Показано, що у зв’язку із зростанням обсягів відходів, що продукує мегапо- ліс, процеси їх вивезення й утилізації повинні мати точніший облік і контроль.
При неможливості запровадити «розумні» системи контролю, резерви підви- щення ефективності процесів запропоновано шукати в їх структурі. Розроб- лено таку структурну модель операцій, яка може забезпечити скорочення ча- сових витрат. Використання неповної інформації про нагромадження і виве- зення сміття зумовлює незапланований пробіг автомобілів. Для того, щоб уни- кнути непередбачених витрат, запропоновано застосовувати ранній забір сміття, при якому періодичність спорожнення контейнерів скорочується. Це приводить до збільшення кількості заїздів автомобілів для забору, але усуває непередбачений пробіг через невідповідність прогнозу завантаження. Показа- но, що для ефективної організації роботи автомобілів-сміттєвозів на транс- портній мережі міста потрібен активний, найкоротший розклад операцій, який потрібно складати на декілька періодів. Для розроблення оптимального за швидкодією циклічного розкладу роботи сукупності автомобілів-сміттєвозів запропоновано методику, яка базується на впорядкуванні змішаних графів.
Змішаний граф відображає множину операцій по збору сміття і часові зв’язки між моментами їх виконання. Для того, щоб з такого графа можна було роз- робити оптимальний розклад, з графа потрібно видалити цикли. Для цього бу- ло застосовано методику «розділяй і пануй». Запропонований алгоритм впоря- дкування графа застосовано для дослідження чинної системи збору сміття. В результаті досліджень досягнуто вищої продуктивності сміттєвозів і вчасно- го вивезення органічних відходів. Скорочення тижневої тривалості роботи 6 автомобілів сміттєвозів при застосуванні 70 %-го рівня заповнення контейне- рів досягло 42 годин.
Ключові слова: організація перевезень, побутові відходи, розклад операцій, періодичність процесів, змішані графи.
1. Вступ
Організація збору, вивезення й утилізації міського сміття є найбільш скла- дною ділянкою муніципального управління. Основна причина – це те, що логіс- тика збору сміття найчастіше не відповідає об’єктивним потребам міст стосов- но їх утилізації. Процес нагромадження відходів є стохастичним. Його інтенси- вність є лише частково відома комунальникам. Відомо також, що утворення твердих побутових відходів (ТПВ) характеризується сезонністю, а також тиж- невою і добовою нерівномірністю. Тому спланувати роботу автотранспортних засобів (АТЗ) в таких умовах є вкрай важко.
Not
a reprint
Існує також суперечність в методології організації вивезення ТПВ у вели- ких мегаполісах. Комунальні служби до цього часу керуються нормами утво- рення сміття залежно від чисельності населення. При відсутності достовірної інформації про фактичне нагромадження відходів автомобільні вантажні пере- візники намагаються вкорочувати планові збірні маршрути руху АТЗ для того, щоб не виконувати зайвий пробіг. При цьому періодичність збору сміття є, як правило, більшою, ніж реальне його нагромадження у контейнерах фіксованого об’єму. Для автомобілів-сміттєвозів важливо є не тільки розробити найкорот- ший маршрут, але й розклад його виконання. Внаслідок відсутності чітких роз- кладів роботи АТЗ на маршрутах окремі контейнери залишаються переповнені відходами, що порушує умови санітарних норм.
Сучасний рівень технологій дає можливість комунальним службам засто- совувати засоби дистанційного контролю за процесом наповнення сміттєвих контейнерів. Однак використання автоматизованих засобів обліку не сприяє вирішенню проблеми у повній мірі. Поточна і ретроспективна інформація уто- чнює прогноз про обсяги перевезення сміття. Доступні прогнози не відповіда- ють методиці складання маршрутів поїздок автомобілів-сміттєвозів. Складання розкладу роботи сміттєвозів на території мегаполісу відповідно до наповнення контейнерів не практикується. У більшості випадків перехід муніципальної си- стеми утилізації сміття на автоматизований рівень стримується через економіч- ні фактори. Часто територіальні громади мегаполісів є фінансово неспроможними дообладнати усі сміттєві контейнери мегаполісу телеметричними засобами. Про- блема посилюється у зв’язку зі зростанням чисельності населення міст і, відповід- но, інтенсивності утворення відходів. Тому дослідження, пов’язані з вирішенням проблеми організації збору сміття, є актуальними і ця актуальність зростає.
2. Аналіз літературних даних та постановка проблеми
В статті [1] підтверджується, що організація і планування збору ТПВ є складною і ступінь її складності зростає. Посилюються вимоги світової спіль- ноти щодо зменшення забруднення довкілля, розділення сміття на сорти у зв’язку із зростанням чисельності громадян мегаполісів. З іншого боку, у статті було відмічено, що для маршрутизації сміттєвозів не використовуються ефек- тивні комп’ютерні засоби прийняття рішень. Авторами було запропоновано розв’язувати задачу маршрутизації АТЗ для роздільного збору ТПВ з допомогою алгоритму пошуку великого сусідства. На конкретному прикладі мегаполіса пока- зано, що задача відноситься до таких, що містить велику множину вхідних даних, через це її розв’язання є ускладненим, а подеколи – неможливим. Однак в дослі- дженнях не бралась до уваги фактична інтенсивність нагромадження сміття в сміттєвих баках, що в принципі не вирішує сформульовану проблему.
У дослідженні [2] автори визнають, що менеджмент збору і утилізації ТПВ часто є неефективним через високу невизначеність, пов’язану з реальними рів- нями заповнення сміттєвих баків. І тому одним з можливих рішень названо ви- користання сенсорів наповнення сміттєвих баків. Однак використання даних від сенсорів має супроводжуватись відповідними алгоритмами оптимізації ма- ршрутів автомобілів-сміттєвозів. Такі спеціальні алгоритми дотепер є невідомі.
For
reading
only
Сучасні пристрої нагляду і спостереження, а саме сенсори об’єму, радіочас- тотної ідентифікації, технології GPRS (General Packet Radio Service) і GPS (Global Positioning System), дають можливість отримувати дані про нагромадження ТПВ дистанційно, в режимі реального часу. Це є основою для удосконалення менедж- менту збору відходів. Відомі публікації, які стосуються «розумних» технологій управління збором сміття, можна поділити на три групи. Різниця полягає у вико- ристаних принципових підходів щодо організації збору ТПВ:
1) методика нормативів і лімітів;
2) «розумної» послідовності збору сміття – Smart Waste Collection Routing (SWCR);
3) «розумних» періодів збору сміття [3].
Усі алгоритми лімітованого підходу не мають обґрунтування встановлено- го мінімального рівня заповнення сміттєвих баків (лімітів) kd. Таким чином, усі баки для сміття, які мають рівень заповнення ki≥kd, розглядаються на етапі ма- ршрутизації. Другий вагомий недолік лімітованого підходу полягає у тому, що задачі маршрутизації розв’язуються циклічно, з фіксованим періодом, переваж- но – одна доба. При цьому не враховується вплив минулих досягнутих резуль- татів на новозбудований план збору сміття автомобілями. Тому на окремих ста- діях планування маршрутів можуть виникати проблеми, пов’язані з нагрома- дженням сміття до рівня kd у багатьох контейнерах, які не увійшли до поперед- нього плану збору ТПВ. Робота сміттєвозів у цьому випадку є нерівномірною щодоби, значить – неефективною.
Дещо зменшено вплив нерівномірного завантаження автомобілів- сміттєвозів у підході SWCR, при якому вибір контейнерів, які потрібно відвіду- вати щодня, і обґрунтування послідовності їх збору здійснюється одночасно [4].
Використовуються критерії максимального прибутку від перевезення ТПВ. Мо- дель, використана дослідниками, представляє задачу маршрутизації АТЗ, при умові, що поточний рівень заповнення контейнерів є відомий тому, хто приймає рішення. Проте, у моделі немає обмежень щодо швидкості заповнення контейне- рів в кінці періоду планування. Через це модель матиме неоптимальний розв’язок, коли показники заповнення наближаються до місткості контейнера в останні дні горизонту. Крім того, така задача розв’язана лише для одного АТЗ.
Підхід «розумних» періодів збору сміття модель SWCR є дещо модифіко- вана дослідниками в роботі [5]. Модель поєднується з евристичною процеду- рою, яка визначає, коли (в який день) слід розпочати плануван- ня/перепланування маршрутів, щоб максимізувати прибуток впродовж певного періоду часу. Цей підхід досліджує мінімізацію неефективності ресурсів, а та- кож враховує попередньо визначений рівень обслуговування. Однак викорис- тана авторами модель динамічно покращує отриманий розклад роботи АТЗ ли- ше відносно переповнених контейнерів. Результати застосування парків АТЗ на зборі сміття невідомі.
Зростання складності методів й алгоритмів планування збору ТПВ пов’язано з тим, що кількість пунктів мережі сміттєвих контейнерів мегаполісу зростає. Автори оглядової статті [6] стверджують, що не зважаючи на те, що для задач маршрутизації розроблено достатньо задовільних методів. Однак ці
Not
a reprint
задачі залишаються в центрі уваги при дослідженні проблем управління проце- сами збору і доставки вантажів.
Процеси збору і доставки на утилізацію сміття, які оснащені засобами он- лайн контролю параметрів вважають частиною «розумних» міст. Однак, у стат- ті [7] на основі огляду відомих досліджень було вказано, що можливість майбу- тньої роботи «розумних» міст базується на підтримці й залучення усіх зацікав- лених сторін, особливо громадян, до процесів прийняття рішень. Таким чином, обсяг даних майбутніх систем збору ТПВ зростатиме зі значно більшою інтен- сивністю, що ускладнить застосування сучасних алгоритмів.
У статті [8] досліджується стохастичний варіант проблеми маршрутизації АТЗ, де невизначеними є як розташування клієнтів, так і обсяги перевезення.
Створена модель децентралізованої системи прийняття рішень, де АТЗ автоно- мно встановлюють свої маршрути відповідно до спостережуваного стану сис- теми. Однак саме для цієї задачі дослідники надали формулювання, засновані на процесах прийняття рішень Маркова, що є неефективним при розвитку «ро- зумних» систем мегаполіса.
У роботі [9] розглянуто проблему планування та маршрутизації збору від- ходів без встановлення періодичності маршрутизації. Проте цей вибір збільшує складність вирішення моделі і нівелює можливість застосувати динамічну мар- шрутизацію для забезпечення найкоротших маршрутів при ранньому напов- ненню контейнерів.
Задачі математичного програмування є основними засобами для математи- чного формулювання проблеми збору і транспортування сміття. Незважаючи на їх велику різноманітність, кількість формулювань продовжує зростати і зали- шається актуальним питання їх адаптації під конкретні формулювання. Зокре- ма, у статті [10] представлено нещодавно розроблену модель змішаного цілочи- сельного програмування (MIP) для задачі селективного збору ТПВ із часовими вікнами, обмеженим гетерогенним парком та різними сортами ТПВ, які збира- ються окремо. Разом з цим задачі математичного програмування володіють ва- гомим недоліком, за якого їх неможливо застосувати для циклічних проблем – вони не відображають фізичної суті процесів, які контролюють.
Вагомою цінністю статті [11] є опис математичної моделі традиційної та кібер-фізичної системи управління відходами, яка описує вплив технологій Ін- дустрії 4.0, таких як RFID, хмарні та туманні обчислення, аналіз великих даних.
Науковий внесок цієї роботи – це математичне моделювання та оптимізація процесів збору відходів на основі оптимізації на основі бінарного алгоритму.
Проте така інтелектуальна технологія в все ще знаходиться на ранній стадії, але її потенціал потребує подальшого вивчення.
З аналізу літературних джерел [1–11] можна зробити такий загальний ви- сновок, що проблема організації збору та утилізації ТПВ на вулично-дорожній мережі мегаполісів є актуальною і, водночас, стала складнішою. Задачі марш- рутизації сміттєвозів без інформації про інтенсивність наповнення контейнерів не мають змісту. При використанні інтелектуальних систем подання даних що- до збору сміття умови задачі організації перевезень ускладнюються тим, що оптимальні маршрути потрібно встановити з врахуванням наповнення контей-
For
reading
only
нерів. Для ефективного планування потрібно рівномірно розподіляти маршрути по днях календарного періоду планування. А це означає, що процес планування є циклічним. Для циклічних процесів і для зростаючого мегаполісу кількість вхідних даних по нагромадженню відходів дуже стрімко зростає, з іншого боку нагромаджується інформація у вигляді досвіду виконаних перевезень. Також є підстави вважати, що майбутні системи збору сміття повинні враховувати об- мін інформацією між усіма суб’єктами процесу збору і утилізації: від громадян – до підприємств переробки. У зв’язку зі зростанням інтенсивності утворення відходів автомобільний транспорт, який використовується в процесі їх збору і транспортування як основний, стає ще однією загрозою забруднення довкілля.
Тому усі наступні задачі повинні вирішуватись за критерієм мінімізації його впливу у вигляді, передусім, тривалості транспортних циклів, а також застосу- вання електромобілів та інших заходів по зменшенню шкідливих викидів.
3. Мета та задачі дослідження
Мета досліджень – сформувати оптимальний циклічний розклад роботи автомобілів-сміттєвозів. Оптимальний розклад забезпечить рух по найкорот- ших збірних маршрутах мережі контейнерних майданчиків із врахуванням фак- тичної інтенсивності їх наповнення. Це дасть змогу зменшити транспортні ви- трати на збір і утилізацію ТПВ у великих містах.
Така мета була досягнута шляхом вирішення наступних задач:
– розробити математичну модель вантажопотоків і часових зв’язків транс- портних операцій зі збору і транспортування сміття;
– розробити алгоритм пошуку найкоротшого активного розкладу опера- цій зі збору сміття, який залежить від фактичної інтенсивності наповнення сміттєвих баків;
– дослідити вплив фонду часу при ранньому зборі сміття за активним оп- тимальним розкладом на тривалість процесу та на ефективність використання парку автомобілів-сміттєвозів.
4. Матеріали та методи дослідження
Процес нагромадження сміття є дискретним і стохастичним. Об’єм сміття, який міститься в момент часу t в і-му контейнері зони збору сміття є кусково- монотонна функція з неперервним аргументом ki(t) (рис. 1).
Графік наповнення контейнерів сміттям є типовим як для систем збору, які оснащені телеметричними засобами контролю об’єму, так і звичайними кон- тейнерами. Їх об’єднує те, що випорожнення баків відбувається у фіксовані моменти часу, які розділені періодом τ – тактом. При наявності сенсорів об’єму випорожнення здійснюється у моменти, коли ki≈kmax. Іноді встановлюється пев- ний допуск на максимальну величину kmax, але його важко забезпечити через фіксовані моменти збору сміття. З графіка видно, що в «розумних» системах збору ТПВ моменти випорожнення можуть настати при τ4, а також при τ3 при наявності допуску. Якщо використовується звичайна система збору, то автомо- більні перевізники користуються досвідом попередніх періодів, складаючи роз- клад збору сміття. Однак, як показано на рис. 1, інформація про фактичні
Not
a reprint
об’єми є занижена (пунктирні лінії). У такому випадку настають вимушені від- хилення від запланованих маршрутів, пробіг автомобілів-сміттєвозів стає необ- ґрунтовано більшим, санітарні норми вивезення сміття порушуються.
Рис. 1. Графік нагромадження, контролю та випорожнення сміттєвого контей- нера при часовій модуляції потоку вхідних даних: kmax – максимальний об’єм
контейнера; τ1… τ4 – моменти контролю рівня заповнення контейнера Відповідність апріорної інформації фактичним даним може бути тоді, коли такт контролю є достатньо малим. Але такий потік даних важко забезпечити практично і «розумних» і у звичайних системах збору. Тому розглянемо систе- му контролю вхідних потоків ТПВ на сміттєвих майданчиках при застосуванні модуляції вхідних даних по величині ki (рис. 2). Як видно з рис. 2, процес збору сміття у даному випадку підпорядковується потоку контрольних даних по об’ємах наповнення.
Рис. 2. Графік нагромадження, контролю та випорожнення сміттєвого контей- нера при модуляції процесу за об’ємом наповнення: kd – допустимий фактичний
об’єм контейнера; Δk – рівень заповнення
При цьому потрібно чітко встановити допуск на максимальне заповнення контейнерів Δk, який є мірою невизначеності процесу наповнення. Інша відмін-
kmax
ki, m3
τ1 τ2 τ3 τ4 t, год.
0,75kmax Δk 0,5kmax
0,25kmax
kd
kmax
ki, m3
τ1 τ2 τ3 τ4
t, год.
For
reading
only
ність такого підходу: контейнери можуть спорожнюватись раніше, ніж у мо- мент τ4. Вибір моменту спорожнення кожного конкретного контейнера зале- жить від спланованого маршруту руху АТЗ і побудованого оптимального розк- ладу збору сміття на території мегаполісу. Таким чином, здійснивши
«прив’язку» розкладу до моментів досягнення запланованого рівня наповнення контейнерів, задано більш жорсткішими часовими зв’язками між операціями випорожнення сміттєвих контейнерів.
5. Результати оптимізації роботи парку автомобілів-сміттєвозів при ранньому зборі сміття
5. 1. Математична модель матеріалопотоків на основі часових зв’язків процесу
Часові зв’язки операцій процесу можна відобразити з допомогою таких за- лежностей. Нехай середня інтенсивність нагромадження сміття в і-му сміттєво- му контейнері µi є величина стала. З достатньою точністю ця величина є апріо- рно відома, з досвіду попередніх операцій по збору сміття на і-му контейнері.
Ймовірно також, що ця величина зчитувалась з телеметричних сенсорів об’єму.
Враховуючи дискретний характер процесу нагромадження сміття, інтенсив- ність наповнення контейнера можна записати таким чином:
. ,
d i i
i
k (1)
де kd.i – допустимий фактичний об’єм контейнера, який потрібно виванта- жити, м3; τi – такт надходження даних про наповнення і-го контейнера. Врахо- вуючи те, що операція вивантаження контейнера має співпадати з моментом часу, коли контейнер наповнено, то такт τi – це величина між моментом початку і завершення і-ї операції, яка періодично повторюється.
Збирання сміття з контейнерних майданчиків здійснюється циклічно. Цикл збору сміття – це сукупність операцій по вивантаженню контейнерів у один ав- томобіль-сміттєвоз. Цикл збору займає час між моментами відправлення поро- жнього АТЗ на маршрут до моменту вивантаження АТЗ на сміттєвому полігоні, або на сміттєпереробному заводі. Кожна j-та операція, яка стосується випорож- нення j-го контейнера, може виконуватись від циклу до циклу зі змінною послі- довністю відносно інших операцій (рис. 3).
Рис. 3. Схема циклу виконання j-ї операції процесу збору сміття: τj.1, τj.2 – такт циклічного повторення j-ї операції
τj.1
i j ζ ξ j φ
τi.2
Not
a reprint
На рис. 3 позначено точками моменти початку виконання відповідних опе- рацій – tb.i, tb.j, tb.j+1, … , tb.i+ξ, tb.i+φ. Тривалість виконання будь-якої j-ї операції залежить від того, яка операція виконувалась попередньо одним і тим ж АТЗ.
Адже виконання операції складається з таких прийомів як під’їзд і позиціону- вання сміттєвоза біля контейнерів, підготовчі прийоми, завантаження, рух з ва- нтажем до наступного контейнерного майданчика. Тривалість кожної операції є випадкова величина від циклу до циклу. Її гарантоване числове значення не пе- ревищує з вірогідністю 0,995 деяку максимальну величину ai.j. Таким чином, момент завершення і-ї операції визначимо як:
. . . ,
e i b i i j
t t a (2)
На рис. 3 тривалість виконання операції j у першому циклі становить аi.j, а у другому – аξ.j, що є різними числами. Також такти різних циклів для однієї і тієї ж операції можуть відрізнятись, тобто в загальному випадку може викону- ватись умова: i z. i z. 1 i z. w. Однак враховуємо припущення про те, що рі- вень наповнення одного і того ж контейнера від циклу до циклу має бути ста- лим, тобто, виходячи з виразу (1), τi.z=const, де z – номер циклу. Це також озна- чає, що розклад операцій можна складати на один цикл роботи АТЗ, і він буде проектуватись на декілька послідовних циклів з метою забезпечення однознач- ності. Враховуючи те, що парк автомобілів-сміттєвозів одного підприємства є пов’язаний спільним виробничим завданням, однозначний розклад потрібно складати для усієї сукупності АТЗ у парку. Однозначний розклад задається од- ним із можливих способів:
а) множинами моментів початку операцій {tb.1, tb.2,… tb.N} і дійсних значень {ai.j}, де i≠j, i,j=1..N, N – загальна кількість контейнерів в зоні обслуговування;
б) множинами моментів {tb.1, tb.2,… tb.N} і {te.1, te.2,… te.N}, при tb.z≠ te.z; в) множинами моментів завершення операцій {te.1, te.2,… te.N} і значень {ai.j}.
Прийнято, що жодний сміттєвоз не буде мати часової затримки з виконан- ням операцій і транспортного циклу зокрема. Тому має строго виконуватись умова (2), або ж умова:
. . . ,
e j e i i j
t t e ei j. ai j. , (3)
де ei.j – часовий зв’язок моментів завершення двох послідовний операцій.
Для активного оптимального розкладу збору сміття, у якому будь-які дві операції i, j можуть виконуватись в довільній послідовності, згідно з теорією розкладів [12] повинна виконуватись вимога:
. .
1
m a x 0 , ,
b i j i
j N
t (4)
де υj.i – ланцюг операцій від операції і до операції j найдовшої тривалості.
For
reading
only
Також відома вимога однозначності розкладу [Ошибка! Источник ссыл- ки не найден.]. Якщо за умовами задачі операція і має передувати операції j, і ці операції виконує один і той ж АТЗ за один цикл, то повинні виконуватись рівності:
, , . , , . ,
b j b i i j b i b j j i
t t a t t a
звідки:
. . .
i j j i
a a (5)
Таку умову можна продемонструвати на прикладі (рис. 4).
Рис. 4. Модель зворотних часових зв’язків: 0, F – фіктивні операції
На рис. 4 показано модель процесу у вигляді орієнтованого графа, верши- нами якого є моменти початку виконання операцій 1, 2 – фактичних, 0, F – фік- тивних. Фіктивні операції використовуються тільки для того, щоб окреслити часові межі процесу. Дуги графа a0.1, a1.2, a2.F мають вагу, яка відповідає трива- лості операцій. Дуги графа aF.1, aF.2 згідно з виразом (5) означають обмеження на часові зв’язки a1.2, a2.F, тобто:
1 .2 2 .F F.1 ,
a a a a2 .F aF.2. (6)
Обмеження (6) означають, що тривалість операцій 1, 2 не повинна переви- щувати заданої величини, відповідно aF.1, aF.2.
Дуги графа a1.0, a2.0 аналогічно відповідно до виразу (5) означають обме- ження, що операції 1, 2 повинні розпочатися не раніше, ніж відповідні часові величини a1.0 і a2.0. Беручи до уваги означення такту операції, можна записати вирази, які пов’язують такт операції зі структурою процесу:
.0 . .
i ai aF i (7)
Для того, щоб автомобілі-сміттєвози використовувались максимально ефе- ктивно, потрібно щоб сумарна тривалість їх перебування на маршрутах була мінімальною. При цьому є умова, що увесь обсяг нагромадженого сміття був вивезений на утилізацію за час, який не перевищує санітарних норм. Це озна- чає, що потрібно побудувати такий розклад виконання операцій по збору ТПВ,
aF.0
0 1 2 F
a2.0
a1.0
aF.1 aF.2
Not
a reprint
при якому тривалість процесу відповідатиме умові [Ошибка! Источник ссыл- ки не найден.]:
0 . .
m in m a x .
p b i i F
i N
T t a (8)
де i=0 – фіктивна операція, яка формально означає старт усього процесу; F – фік- тивна операція, яка формально означає завершення усього процесу; ai.F – часові зв’язки кінцевих операцій процесу, які мають значення тривалості доставки зібра- них ТПВ цілком заповненими АТЗ до сміттєзвалищ, або переробних заводів.
Обмеження процесу щодо повноти збору відходів означають, що інтенсив- ність вивезення сміття має визначатись за виразом, з врахуванням (1):
1 1
,
N N
o u t i
i i i
k (9)
де µі – інтенсивність нагромадження ТПВ в і-му контейнері; k – прийнятий у задачі рівень заповнення сміттєвих контейнерів (у % від kmax).
5. 2. Метод і алгоритм побудови оптимального розкладу роботи ав- томобілів
За основу методу оптимізації розкладу прийнято впорядкування змішаного графа [Ошибка! Источник ссылки не найден.]. Формулювання задачі є та- ким. Транспортна мережа міста задана у вигляді графа G(Q, V), вершинами G якого є контейнерні майданчики збору ТПВ, а ребра V – найкоротші шляхи між кожною парою вершин. Припускаємо, що аi.j=aj.i, тобто матриця інцидентності графа G є симетричною відносно діагоналі. Прийнято, що між будь-якими дво- ма пунктами на транспортній мережі міста існує шлях (мережа – сильно зв’язана). Отже відстань між ними відома, але для зручності вона оцінюється опосередковано − часом руху ai.j при відомій сталій середній експлуатаційній швидкості.
Кожен контейнерний майданчик мегаполісу містить сукупність контейне- рів, які поділяються за сортом відходів. Кількість сортів визначається законода- вчо та на рівні територіальної громади міста. Згідно із технологіями, які вико- ристовуються, кожен сорт сміття транспортується на утилізацію окремим АТЗ.
Відповідно складаються окремі маршрути. Якщо сортування сміття взято за но- рму в населеному пункті, то кожен сорт і кожен контейнерний майданчик хара- ктеризується інтенсивністю нагромадження µі, яка є випадковою величиною і характеризується середнім значенням µm.і. Серед усіх сортів сміття майданчика є таке, яке характеризується найвищою інтенсивністю нагромадження. Перева- жно це стосується органічних відходів і пластику [Ошибка! Источник ссылки не найден.]. Сміття, посортоване, характеризується також допустимими термі- нами утилізації, згідно із локально прийнятими санітарними нормами. Таким чином, для кожного контейнера встановлюється допустимий максимальний те- рмін зберігання, навіть якщо контейнер не переповнений. Виходячи з цього,
For
reading
only
встановлюється тривалість планування перевезень Т, яка має бути дотримана з врахуванням обмежень. Особливостями даної задачі є те, що усі пункти транс- портної мережі, крім останнього пункту усіх маршрутів, є пунктами заванта- ження, тобто шукані маршрути є збірними. Також не усі контейнерні майдан- чики мають бути відвідані сміттєвозами за один цикл, оскільки прийнято підхід про вивезення сміття за рівнем заповнення. Крім того, два різних сміттєвози не можуть заїжджати на один майданчик за один цикл, оскільки все сміття одного сорту вивантажується на АТЗ при одному заїзді. Враховуючи перелічені умови, задачу можна віднести до складання циклічних унітарних розкладів для пото- кового виконання операцій процесу декількома засобами [Ошибка! Источник ссылки не найден.]. Тому, плануючи виконання перевезень, потрібно розроби- ти найкоротший за тривалістю маршрут руху для кожного АТЗ, який буде заді- яний в процесі. З іншого боку потрібен найкращий розклад виконання замов- лень для сукупності сміттєвозів при наявності часових обмежень на вивезення вантажу. Враховуючи структуру і властивості типового транспортного процесу у середніх і великих транспортних системах, таку задачу потрібно віднести до оптимізаційних [12]. За складністю алгоритму пошуку оптимального розв’язку вона відноситься до задач складності О(n3). Існує недетермінований алгоритм пошуку успішного точного, або наближеного розв’язку за допустимий час [13].
На відміну від класичного методу впорядкування змішаних графів, усю множи- ну контейнерних пунктів відображає неорієнтований граф G(Q,V). Вершина q0
графа – фіктивна, представляє формальний момент початку усього процесу.
Вершина qF − фіктивна, символізує кінець планового циклу тривалістю Т. V − множина ребер, кожне з яких відображає часові зв’язки ai.j та aj.i між моментами початку виконання і-ї та j-ї операції одним і тим ж АТЗ. Якщо між вершинами qi, qj графа G є ребро, то це означає їх часову незалежність і відповідні операції по обслуговуванню і-го та j-го контейнера виконуватимуться одночасно, або з частковим перекриттям у часі різними АТЗ. До процесу перевезення може бути залучено R транспортних засобів. Вони повинні працювати синхронно, вико- нуючи по декілька завантажень послідовно. Це означає, що у графі G потрібно знайти R шляхів, які починаються у вершині q0, проходять через деякі вершини графа, які стосуються наявних контейнерів і закінчуються у вершині qF. У да- ному варіанті задачі шукаємо мінімальний час виконання усіх операцій наяв- ними АТЗ. Тому шукані ланцюги вершин мають проходити по тих вершинах, для яких аi.j >0. Якщо аi.j=∞, то це означає, що j-та операція не може виконува- тись вслід за i-ю. Ланцюг доходить до вершини і, а далі нема жодного шляху у графі G з невід’ємною, або ненульовою вагою, то ланцюг при цьому прямує до вершини qF. Транспортний цикл для цього автомобіля вважатимемо заверше- ним, незважаючи на те, що є резерв часу на виконання інших, ще не виконаних замовлень. Задача в такому формулюванні є схожа на типову задачу декількох комівояжерів [Ошибка! Источник ссылки не найден.] з відмінностями:
1) період планування Т є наперед заданою величиною;
2) довжина будь-якої ланки будь-якого ланцюга є величиною змінною і за- лежить від послідовності виконання операцій;
Not
a reprint
3) кожна операція має обмеження стосовно моменту початку і моменту за- вершення її виконання.
Алгоритм розв’язування задачі є таким. Множина готових для виконання операцій формується впродовж періоду Т. Між кожною парою вершин, що си- мволізують операції, проставлено ребро з відповідними вагами ai.j, aj.i. Кількість АТЗ R – обмежена. Потрібно побудувати розклад виконання заданих операцій по збору сміття, тобто для кожної операції вказати момент її початку tb.i і часо- вий зв’язок з наступною операцією ai.j, а також номер АТЗ, який цю операцію виконає. Оптимальним вважається розклад для якого виконується критерій (8).
Пошукова частина запропонованого алгоритму базується на методі «розді- ляй і пануй». Для цього відомий алгоритм побудови оптимального розкладу [Ошибка! Источник ссылки не найден.] адаптовано до сформульованих умов задачі. Означимо деякі використані терміни. Шляхом в графі G (Q, U, V) нази- вається послідовність дуг Uk={(q1, qi), (qi, qj), … (qx, qp)}, де всі вершини qi…qp – різні, а початкова і кінцева − можуть збігатись. Контур − це замкнутий шлях в графі G. Вагою шляху назвемо суму ваг дуг, що входять до нього. Вага шляху виражається чисельно в межах інтервалу (-, +), тобто є дійсним числом. В зв’язку з цим використовується термін контур, або шлях додатної (або від’ємної) ваги. Шлях найбільшої додатної ваги в графі G, що з’єднує i, j вер- шини, позначимо ij. Якщо в графі G не існує шляху з вершини i у вершину j через ліквідацію деяких ребер, то ij=−. Для того, щоб шуканий розклад був однозначним (не було часового неузгодження), потрібно дотримуватися умови (3). Момент початку виконання будь-якої і-ї операції шукається із співвідно- шення (4).
Існує взаємно однозначна відповідність між множиною всіх активних роз- кладів, що побудовані з графа G і множиною P’(G) всіх графів, які не містять контурів додатної ваги. Отже, однозначним вважаємо розклад, що породжений графом G’ і не містить контурів додатної ваги, а значить і ребер V. Застосовано послідовний аналіз варіантів з перебором усіх графів з множини P’, і пошуком серед них оптимального за критерієм (8). Для організації такого пошуку, з ме- тою уникнути непродуктивного перебору неоптимальних варіантів, використа- но процедуру послідовного розбивання P’ на підмножини за ознакою поточно- го рекорду за критерієм (8) [13].
Зміст операцій з графом G(Q, U, V) полягає в наступному. Якщо дві опера- ції i, j призначені для незалежного виконання різними автомобілями, то ніякий часовий зв’язок між ними не повинен бути, і ребро невпорядкованої моделі G усувається. Якщо ж ці операції виконуватимуться послідовно, незалежно від їх обсягу, то ребро [i, j] замінюється дугою (i, j) ваги ai.j, або дугою (j, i) ваги aj.i.
Крім оперування з основним графом G (Q, U, V), створюємо і використову- ємо допоміжний неорієнтований граф Hr (Qr, Vr), вершинами якого є операції підмножини Qr, де r≤R. Кожна підмножина Qr складається з вершин, які симво- лізують операції, що виконуються одним автомобілем. На нульовому кроці мо- делювання Qr=Q, Vr=V, Hr (α0)=Hr (Q, ). Відповідно, кількість таких графів на початку моделювання може бути r>R. Далі граф Hr перетворюється так. Якщо операція α1 з основним графом G є ліквідація ребра [i, j], то граф Hr(α1) отриму-
For
reading
only
ємо з графа Hr(α0) в результаті додавання ребра [i, j]. Якщо операція α1 − заміна ребра [i, j] однією з дуг (i, j), або (j, i) в графі G, то граф Hr(α1) отримуємо з гра- фа Hr(α0), ототожнивши вершини i, j з однією вершиною. На кожному n-му кроці алгоритму обчислюємо хроматичне число графа χ (Hr(αn)) за методикою [Ошибка! Источник ссылки не найден.]. Внаслідок цього можна визначити обмеження, яке накладає на поточний отриманий варіант розкладу наявна кіль- кість АТЗ:
. Hr n R (10)
Ця умова означає обмежені можливості процесу: виконувати декілька опе- рацій одночасно через відсутність необхідної кількості АТЗ.
Для того, щоб вести цілеспрямований пошук доцільних перетворень в гра- фі G, використано розуміння конфліктного ребра, тобто такого, для якого не виконується умова (5), (6). Серед конфліктних ребер графа G можна знайти найконфліктніші, тобто такі, перетворення яких приводить до більш ефектив- ного пошукового ефекту. Для цього для кожного конфліктного ребра потрібно знайти величину:
. , , . , ,
ij e j j i j
h t G U G U a G U (11)
де ϑj (G, U) − максимальна вага шляху в графі G (Q, U), що починається у вер- шині qj; ϑ (G, U) – найдовший (критичний) шлях у графі G (Q, U).
Вибираючи найконфліктніше ребро з усіх конфліктних множини V(αn), ке- руємось величиною min(hi.j, hj.i). Для якого ребра знайдена величина буде най- більшою, те й назвемо найконфліктнішим.
Розроблений алгоритм складається з одинадцяти кроків:
1. Перевірити, чи граф G (αn)=G (Q, U) містить контур додатної ваги, де αn
− n-й цикл алгоритму, n=0, 1, …. Якщо такий контур є, то перейти до кроку 10.
2. Знайти ранній початок виконання кожного замовлення за (4). Знайти найбільш пізнє закінчення виконання замовлень за (2). Якщо знайдені величини не відповідають директивам, то перейти до кроку 10.
3. Знайти множину конфліктних ребер графа G(αn) і найконфліктніше се- ред них за критерієм (11). Якщо множина порожня, то перейти до кроку 11.
4. Замінити конфліктне ребро [i, j] в графі G(αn.1) дугою (i, j), в графі G(αn.2)
− дугою (j, i); в графі G(αn.3) − знищити ребро [i, j].
5. Створити відповідні допоміжні графи Hr(αn.1), Hr(αn.2), Hr(αn.3). Обчисли- ти хроматичне число кожного з допоміжних графів Hr.
6. Якщо для жодного графа Hr не виконується нерівність (10), то перейти до кроку 10.
7. Якщо в графі Hr є петлі, тобто Hr (i, i)=1, то перейти до кроку 10.
8. Для графів G (αn.1), G (αn.2), G (αn.3) здійснити почергово кроки 2, 3, 9.
9. Обчислити нижню оцінку оптимальності шуканого розкладу серед вве- дених графів за (8). Якщо Tp(G(αn))≤Tp(G(αn–1)), то перейти до кроку 11, якщо ж ні – до кроку 4.
