тійних вантажів існує 2 групи методів:
отримання точних результатів
отримання приблизних результатів.
У зв'язку з тим, що застосування точних методів обмежено розмірністю вирішуваних завдань, то на практиці користуються в основному приблизними методом.
Ідея методу Кларка-Райта полягає в тому, що митників маршрути, які виходять з одного пункту ГО, попарно групуються в кільцеві маршрути за принципом отримання на кожному максимальних "виграшу" від цього об'єднання.
"Виграш" від об'єднання пунктів i і j маршрутів визначається за формулою, де li, o-найкоротший відстань від пункту i до ГО, lo, j - найкоротша відстань від ГО до j пункту, li, j - найкоротша відстань від пункту i до пункту j.
Сенс "виграшу" укладений у скороченні пробігу автомобілями при заміні двох маятникових маршрутів на кільцевій, що складається з двох пунктів.
За оцінкою всіх можливих комбінацій об'єднань пунктів i і j в пари (у таблиці оцінок), в першу чергу включають у маршрут пару вершин, мають максимальне значення в "виграші". При наступному кроці підключення проводиться або на вході в маршрут (у точці i), або на виході з нього (в точці j). p> У даному випадку відшукується максимальний "виграш" у стовпці i і в рядку j таблиці оцінок, залежно від якого виробляють підключення чергового пункту в споруджуваний фрагмент маршруту.
При побудові маршруту здійснюється перевірка на задоволення обмеження (по вантажомісткості автомобіля, часу знаходження в наряді, термінів доставки вантажу тощо). Формування маршруту закінчується при вичерпанні списку вершин або відсутності можливості підключення пункту без порушення заданих обмежень. В останньому випадку приступають до побудови чергового маршруту. Процедура повторюється до отримання всього плану маршрутизації. p> На практиці зазвичай задається умова неподільності дрібної партії вантажу, тобто в кожному пункті маршруту автомобіль повинен здійснити лише одну розвантаження. Алгоритмічно це здійснюється викреслюванням рядків і стовпців, а також блокуванням елемента в таблиці. p align="justify"> Приклад заповнення таблиці "виграшів":
f 1-2 = 4 +12-10 = 6, f 1-6 = 4 +16-12 = 8, f 1-3 = 4 +9-7 = 6, f 1 - 7 = 4 +12-8 = 8, f 1-4 = 4 +8-4 = 8, f 1-8 = 4 +9-11 = 2, f 1-5 = 4 +4-8 = 0, f 1-9 = 4 +7-5 = 6, f 1-10 = 4 +5-7 = 2.
Таблиця № 9. p align="justify"> Таблиця "виграшів"
обсяг грузаГПА2А3А4Б1Б2Б3Б4Б5Б6Б72А2-6680882622А36-86112412 71414А468-125161013 7-04Б72110101810100-
Вибираємо найбільше значення з таблиці "виграшів", рівне 24 з осередків Б3А3 і А3Б3. Потреба у вантажі цих ДП Б3 = 8 пакетів, А3 = 2 пакети. У Б3 вивезення складе 8 пакетів, а у А3-2 пакети, так як вантажопідйомність автомобіля дорівнює 10 пакетам. Отримаємо:
М1: ГО - Б3-А3-ГО (8 ...
