Приклад

Курєр косметичної компанії «tianDe» має розвести продукцію в чотири магазини і повернутися на склад.

4 магазини описані матрицею відстаней між ними (км)

Етап 1. Курєр має потрапити в останнє місто. При цьому він

може знаходитися в містах 1, 2, 3. Локальний дохід розраховуємо за

формулою:

W= = D_MiM4

Для кожного з міст;

W₃(M₁(M₂)) = D_{12 +} W₄(M₂(0)) = 8+6=14

W₃(M₁(M₃)) = D_{13 +} W₄(M₃(0)) = 8+4=12

W₃(M₂(A₁)) = D2_{1 +} W₄(M₁(0)) = 9+5=14

W₃(M₂(A₃)) = D_{23 +} W₄(M₃(0)) = 1+4=5

W₃(M₃(A₁)) = D_{31 +} W₄(M₁(0)) = 11+5=16

W₃(M₁(A₂)) = D_{32 +} W₄(M₂(0)) = 4+6=10

Етап 3. Курєр має потрапити в останній магазин, відвідавши при

цьому два проміжних магазина. Локальний дохід на даному етапі

визначається:

W₂(M₁(M₂M₃)) = min(D_{12 +} W₃(M₂(M₃)), D_{13 +} W₃(M₃(M₂))) = min (8+16,8+10)=

=18

W₂(M₂(M₁M₃)) = min(D_{21 +} W₃(M₁(M₃)), D_{23 +} W₃(M₃(M₁))) = min (9+12,1+16)=

=17

W₂(M₃(M₁M₂)) = min(D_{31 +} W₃(M₁(M₂)), D_{32 +} W₃(M₂(M₁))) = min (11+14,4+14)=

=18

Останній 4 етап. Курєр знаходиться в останньому магазині,

повинен об’їхати всі магазини і повернутися на склад. Локальний дохід

визначається наступним чином

W₁(M₄(M₁M₂M₃))

=min(D₄₁ + W₂(M₁(M₂M₃)),D_{42 +} W₂(M₂(M₁M₃)),D₄₃

+ W₂(M₃(M₁M₂))) =min(6+13,3 + 17,2 + 18)=19

Таким чином оптимальний маршрут, який має пройти курєр буде таким

W=4 1 , з довжиною шляху 19.

Дата добавления: 2015-08-17