Декомпозиція задачі маршрутизації з часовими вікнами

Автор: Перцовський Олександр Костянтинович Переклад: Джерело: «RSDN Magazine», www.rsdn.ru Матеріал надав: Перцовський Олександр Костянтинович

задачі

Математична постановка задачі

Завдання кластеризації

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

де ρ – лінійна відстань, а c – геометричний центр кластерного географічного району.

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

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

Схема методу декомпозиції безлічі завдань на доставку на КМР

Метод далекої точки

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

  1. Визначити точкуp0,найбільш віддалену від депо;
  2. Створити кластерС0, додати до нього точкуp0;
  3. Серед нерозподілених точок вибрати найближчу до вже створених кластерів;
  4. Визначити два найближчих до точкиpкластераC1, C2;
  5. Перевірити обмеження на додаванняpкластер послідовно дляC1,C2у порядку близькості їх до точки і додати точку до першого кластера, для якого обмеження виконуються;
  6. У разі, якщо обмеження не виконані для жодного з кластерів, створити новий і додати розглянуту точку до нього;
  7. Повторювати кроки 3-6 поки що є нерозподілені точки.

Теорема 1.Метод дальньої точки має складність O(n2), де n - кількість точок доставки в розглянутій постановці задачі.

Доказ теореми конструктивний і випливає з оцінок

Метод, заснований на алгоритмі Свіра

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

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

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

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

Теорема 2.Складність алгоритму побудови початкового розбиття на географічні райони, заснованого на алгоритмі Свіра, становить O(n*log(n)+n), де n – кількість точок доставки у розглянутій постановці задачі

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

Алгоритм покращення розбиття на КМР

Після отримання початкової декомпозиції у вигляді сформульованої постановки завдання необхідно провести додаткову обробку отриманого розбиття для поліпшення значення цільового функціоналу. При цьому в ході аналізу даних користувача було зроблено висновок про необхідність розробки додаткового алгоритму вибір точки, що розглядається на поточному кроці. Це з боротьбою з так званими «викидами», тобто КГР, містять по кілька точок. Їхня поява можлива на увазінаявності масо-габаритних обмежень.

1. Для кожної точки, не приписаної до існуючого кластера визначити відстані до побудованих кластерівd1, ..., dm

2. Упорядкувати отримані відстані за зростанням;

3. Для кожної точки визначити параметр ?

4. Розглядати точку, для якої Δ максимальна.

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

1. Отримати центри початкового розбиття;

2. Якщо є нерозподілені точки, вибрати точку за описаним вище алгоритмом;

3. Визначити відстані від отриманої точки до КГР;

4. Перевірити виконання обмежень за вагою, обсягом та розкладом для найближчого кластерного географічного району. Якщо точку можна додати, то додати та перейти до пункту 2;

5. Якщо точку не можна додати до найближчого КГР, то аналогічним чином спробувати додати її до другої за віддаленістю КГР. У разі успіху додати та перейти до пункту 2;

6. При невиконанні пункту 5 створити новий КМР та додати до нього цю точку. Перейти до пункту 2.

Апробація алгоритму декомпозиції

Побудований метод протестували на кількох базах транспортних компаній. У таблиці нижче наведено результати роботи методів побудови КГР з використанням методу, заснованого на алгоритмі Свира, та методу дальньої точки як алгоритм побудови початкової декомпозиції відповідно.