Проблеми з маршрутизації транспортних засобів (VRP) мають першорядне значення в різних промислових програмах, таких як логістика (Büyüközkan, Lmaz, Özçelik, & Lmaz, 2025), інтелектуальне транспортування (Liang, Gao, & Shen, 2023) та управління ланцюгами поставок (Dondo, Méndez, & Cerdá, 2011). Серед варіантів VRP проблема збору та доставки (PDP) особливо значна через його моделювання парних запитів, де кожне замовлення клієнта включає місце для пікапів та відповідне місце доставки. Ця структура сполучення є основоположною для численних реальних послуг, таких як обмін їздою (Guo, Long, Xu, Yu, & Yuan, 2022) та доставка їжі (Luo, Gu, Poon, Li, & Lim, 2022). Помітним особливим випадком PDP є проблема з проїздом для пікапів та доставки (PDTSP), яка має на меті визначити найкоротший маршрут для одного транспортного засобу, який починається і закінчується в депо, відвідуючи всі вузли пікапа та доставки рівно один раз. PDTSP характеризується двома первинними обмеженнями: (1) відвідування обмеженьвимагаючи відвідувати кожен вузол рівно один раз; та (2) Обмеження про пріоритетзастосовуючи, що кожен вузол пікапів повинен бути відвіданий перед його парним вузлом доставки. На рис. 1 зображено приклад екземпляра та рішення PDTSP з чотирма запитами, де сині сфери представляють точки пікапів, а помаранчеві квадрати позначають їх парні точки доставки.
Завдяки NP-HARD Nature (Arora, 2003) PDP залишається непереборним для оптимальної роздільної здатності з використанням точних розв'язувачів (Pessoa, Sadykov, Uchoa, & Vanderbeck, 2019). Як бажані альтернативи, евристичні методи (Olgun, Koç, & Parmak, 2021), як правило, покладаються на ручні правила, розроблені для спрощення процесу пошуку, і зазвичай використовуються в промисловості для отримання майже оптимальних рішень із значно меншими обчислювальними витратами. Однак вони часто пристосовуються до конкретних проблем і вручну створюються за допомогою значних випробувань та помилок, вимагаючи переробки, коли обмеження або цілі змінюються. Ці обмеження можуть перешкоджати їх застосуванню та доступності в швидко розвиваються галузях. Підкреслене відносини з прецедентом, притаманному PDP, ускладнює оптимізацію маршрутів, тим самим представляючи додаткові проблеми порівняно з канонічними VRP, такими як проблема подорожей продавця (TSP), що вимагає інноваційних стратегій рішення.
Останнім часом зростає увага щодо застосування глибокого підкріплення навчання (DRL) (Qin et al., 2021, Zhang et al., 2022), щоб вивчити нейронні евристичні методи для VRP, автоматично вивчаючи правила у звичайній евристиці, а не за допомогою рукотворних. Моделі DRL можуть загалом класифікувати на два класи, тобто нейронні будівництво і вдосконалення методи відповідно. Колишній послідовно вирішує наступного клієнта, який відвідує рішення, який успішно сприяє високоякісних рішеннях із швидкими обчисленнями. На відміну від цього, останні ітеративно покращує повне початкове рішення за допомогою пошуку в сусідстві (Chang, Shi, Luo, & Liu, 2023), хоча вони потужні, вони зазвичай потребують вибору оператора, що стосується проблем, і включає широкі локальні оновлення, що призводить до великої кількості ітерацій та збільшення обчислювальних витрат. Таким чином, це дослідження зосереджено на моделях нейронних будівель завдяки їх ефективності та гнучкості. Trained in the fashion of advanced reinforcement learning (Nazari et al., 2018a, Wu et al., 2024) or supervised learning (Min, Bai, & Gomes, 2023), the DRL models, particularly neural construction ones, demonstrate promising performance with significantly enhanced computational efficiency for solving simple VRPs such as TSP and Capacitated VRP (CVRP) (Wu, Song, Cao, Чжан, і Лім, 2021). Крім того, включивши більш складні та реалістичні обмеження, адаптуючи архітектуру моделі для їх вирішення, ці моделі DRL можуть бути гнучко розширилися для вирішення більш складних проблем маршрутизації, таких як варіанти PDP (Ma et al., 2022).
Незважаючи на деякі помітні успіхи, існуючі методи нейронної будівництва страждають від двох основних обмежень для вирішення ПДП. По -перше, вони часто борються за створення різноманітних рішень через обмеження, накладені детермінованими вбудовуваннями вузла та статичними розподілами ймовірностей. Хоча можна відібрати кілька рішень, більшість з них можуть бути суттєво однаковими з огляду на незмінний розподіл, що серйозно погіршує різноманітність пошуку. Для пом'якшення цього питання деякі роботи приймають оптимізацію політики за допомогою декількох оптимських (POMO) (Kwon et al., 2020) для сприяння розвідці, виконуючи різноманітні перші дії під час побудови рішення. Іншими словами, кожен клієнт призначений для обслуговування спочатку, щоб диверсифікувати створені рішення. Однак для варіантів PDP початкові дії обмежуються клієнтами, які потребують пікапу через обмеження пріоритету, що робить ці методи, менш ефективними при створенні різноманітних рішень. Друге обмеження полягає в дизайні декодерів. Процес побудови рішення може вважатися послідовно завданням прийняття рішень, яке передбачає вибір наступного (невірного) клієнта після відвідування поточного клієнта. Представлений на графіку, завдання підкреслює необхідність вивчення більш інформативних представлень клієнтів. Більше того, хороший вибір наступного вузла для відвідування, як правило, лежить в межах поточного вузла замість всього пулу кандидатських вузлів. З цією метою ефективне вилучення особливостей з невирішених вузлів сусідніх вузлів є важливим для покращення навчання представництва і, отже, покращення якості рішення. Однак більшість існуючих моделей нейронної будівництва покладаються виключно на поточний вузол, що вбудовується, щоб відобразити контекст під час побудови рішення, не підкреслюючи критичну інформацію, орієнтовану на рішення (тобто околиці), що стосується поточного вузла, який може погіршити ефективність та продуктивність.
Для вирішення вище двох обмежень ми пропонуємо оптимізацію політики на основі населення на основі ваги (LPPO), яка не тільки вивчає населення різноманітних стратегій рішення, що характеризуються чіткими розподілами ймовірностей для полегшення розвідки пошуку, але й гнучко підкреслюють нестримані вузли поблизу по відношенню до поточного вузла під час процесу декодування для підвищення ефективності пошуку. Зокрема, ми спочатку вводимо стратегію пошуку на основі населення, яка спрямована на інтеграцію факторів збурень у нейронний декодер будівництва через легку мережу. Роблячи це, засвоюється населення декількох стратегій, що дозволяє швидко створити різноманітні рішення для проблемного екземпляра. На відміну від методів на основі POMO, які накладають різноманітність шляхом забезпечення різноманітних початкових вузлів, запропонований механізм різноманітності в LPPO підвищує як продуктивність рішення, так і пристосованість до нових проблем, особливо для варіантів PDP, вивчених у цій роботі. Потім ми вводимо мережу локалізованого синтезу уваги (LAS), щоб покращити точність вибору вузла, використовуючи більш релевантну та інформативну контекстну інформацію, пов'язану з поточним вузлом. Він також включає гіпернетуру, яка використовує вбудовування нинішнього вузла та його сусідніх сусідів, щоб інтелектуально адаптувати ваги уваги декодера під час побудови рішення. Крім того, ми пропонуємо схему пошуку кластерів, яка організовує фактори збурень у різні групи, що дозволяє швидко відбору найбільш ефективних факторів для виявлення перспективних стратегій розчину з населення для кожного проблемного екземпляра. Ця схема значно підвищує ефективність пошуку під час висновку, тим самим полегшуючи швидку ідентифікацію високоякісних рішень. Ми оцінили наш LPPO за двома канонічними варіантами PDP, тобто проблемою продавця пікапів та доставки (PDTSP) та його варіантом з мультимбором (M-PDTSP), щоб перевірити наш дизайн. Емпіричні результати показують, що наш LPPO досягає менших прогалин та кращого узагальнення, ніж найсучасніші методи, зберігаючи порівнянну ефективність обчислень.
Наші внески узагальнені наступним чином: (1) ми пропонуємо нову легку оптимізацію політики на основі населення (LPPO) для сприяння різноманітності пошуку нейронних конструкторів для варіантів PDP. Використовуючи розроблені фактори збурень, LPPO вивчає населення різноманітних стратегій пошуку за допомогою одного декодера, без значного збільшення часу обчислення; (2. Він включає гіпернету роботу для адаптивного виділення чітких особливостей та вдосконалення процесу побудови рішення; (3) Ми розробляємо схему пошуку кластерів під час висновку, яка може ефективно визначити найбільш ефективні коефіцієнти збурень, що дозволяє вибору перспективних стратегій пошуку від населення для конкретного екземпляра проблем, що підвищує ефективність пошуку та якість рішення. Широкі експериментальні результати як на PDTSP, так і для M-PDTSP перевіряють перевагу нашого LPPO до найсучасніших нейронних моделей, спеціалізованих для варіантів PDP.
