🚚 Оптимізатор Маршрутів Доставки — Симульоване Відпалювання Наживо

Симульоване відпалювання — це ймовірнісна техніка оптимізації, натхненна металургійним процесом нагрівання металу й повільного його охолодження так, щоб його атоми осіли в кристалічній структурі з низькою енергією. Застосована до задачі комівояжера/маршрутизації транспорту, «енергія» — це загальна відстань маршруту. За високої температури алгоритм приймає багато погіршувальних ходів, дозволяючи широко досліджувати й вистрибувати з поганих локальних компоновок; у міру падіння температури він стає дедалі жадібнішим, уточнюючи маршрут, доки не зійдеться близько до короткого маршруту. Він популярний для маршрутизації, бо простір пошуку можливих упорядкувань зупинок факторіальний за розміром, занадто великий для вичерпного пошуку, проте околиці 2-opt у поєднанні з відпалюванням надійно знаходять маршрути в межах кількох відсотків від оптимуму.

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

Після обчислення дельти вартості кандидатного ходу алгоритм завжди приймає ходи, що скорочують маршрут (Δ < 0). Для ходів, що подовжують його, він приймає з ймовірністю e^(−Δ/T), де T — поточна температура. Це означає, що великий погіршувальний хід рідко приймається, але малі погіршувальні ходи все ще досить ймовірні на початку, коли T висока. У міру спадання T до нуля, e^(−Δ/T) стягується до нуля для будь-якого позитивного Δ, тож алгоритм фактично стає чистим жадібним спуском — підйом на пагорб заборонений, і виживають лише покращувальні ходи.

Ця симуляція використовує геометричне охолодження: T множиться на швидкість охолодження α (близьку до, але меншу за 1) після кожного запропонованого ходу, тож T спадає експоненційно з кількістю ітерацій. Швидкість охолодження дуже близька до 1 (наприклад, 0,9995) охолоджує повільно, даючи пошуку багато ітерацій при вищих температурах для широкого дослідження, перш ніж зафіксуватися на уточненні рішення, — це зазвичай знаходить коротші маршрути, але потребує більше часу для осідання. Нижча швидкість охолодження (наприклад, 0,985) охолоджує швидко й поводиться майже як жадібний локальний пошук 2-opt, швидко сходячись, але з більшою ймовірністю застрягання в посередньому локальному мінімумі.

У цьому вся суть відпалювання: за високої температури критерій Метрополіса навмисно приймає деякі ходи, що збільшують довжину. Маршрут може виглядати локально оптимальним (жоден окремий хід 2-opt його не покращує), водночас все ще будучи далеким від найкоротшого можливого маршруту — це локальний мінімум. Іноді приймаючи гірший хід, пошук може вибратися з басейну цього локального мінімуму й пізніше потрапити в інший, коротший. Спостерігаючи за графіком відстані, ви зазвичай побачите, що спочатку він швидко падає, іноді різко зростає, поки T ще висока, а потім осідає в гладке монотонне зниження в міру наближення T до нуля.

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