Zastosowanie sztucznych systemów immunologicznych do rozwiązywania dużych problemów wielokryterialnych marszrutyzacji.
W zadaniu komiwojażera z dużą liczbą odbiorców:
1. dzielenie odbiorców na klastry,
2. rozwiązywanie zadania komiwojażera dla każdego klastra oddzielnie.
Analogiczny model dla zadań Eulera. Przykłady rozwiązań z kryterium ważonym i kryterium optymalności w sensie Pareto.
Cel badań
Zastosowanie sztucznych systemów immunologicznych do rozwiązywania dużych problemów w wielokryterialnych zadaniach marszrutyzacji
Zakres prac
Celem badań było opracowanie metodyki rozwiązywania dużych zadań marszrutyzacji sformułowanych jako wielokryterialny problem wielu komiwojażerów (MTSP) przy złożonych ograniczeniach oraz problem Eulera (czy bardziej znany w literaturze problem chińskiego listonosza) rozwiązywany przy podobnych kryteriach i ograniczeniach. Oba problemy są bardzo ważne dla planowania tras środków transportu.
Dla danego ważonego grafu o n wierzchołkach problem komiwojażera polega na znalezieniu minimalnego cyklu Hamiltona, czyli cyklu przechodzącego przez wszystkie wierzchołki grafu dokładnie raz, dla którego suma wag krawędzi grafu jest minimalna. Problem komiwojażera należy do problemów NP-trudnych, co oznacza, że wraz ze wzrostem liczby wierzchołków grafu znacznie wydłuża się czas obliczeń.
Jedną z metod jest zastąpienie jednego dużego zadania kilkoma mniejszymi. Stosuje się do tego metody analizy skupień, którymi wyznacza się skupienia (lub inaczej klastry) położonych blisko siebie wierzchołków grafu. W ten sposób zadanie MTSP jest sprowadzane do klastrowanego problemu komiwojażera. ( ang. - clustered traveling salesman problem – CTSP), który polega na wyznaczeniu minimalnego cyklu przechodzącego przez wierzchołki grafu w ten sposób, by w każdym klastrze były odwiedzane po kolei wszystkie wierzchołki, a suma wag krawędzi cyklu była minimalna.
Problem Eulera polega na znalezieniu w opisanym grafie cyklu Eulera, czyli cyklu przechodzącego przez wszystkie krawędzie dokładnie raz (w zadaniu chińskiego listonosza co najmniej raz). Nie jest on zadaniem tak złożonym jak TSP, ale dla wielu kryteriów i przy złożonych ograniczeniach również wymaga podziału na mniejsze zadania metodami analizy skupień.
Wyniki
Opracowano skutecznych dla dużej liczby danych algorytmy optymalizacji tras pojazdów dostawczych ze względu na minimalizację kosztów i emisji spalin. Przeprowadzono obliczenia dla zadania komiwojażera bez podziału na klastry i z podziałem. Wyniki porównano. Wyniki otrzymane w obliczeniach z podziałem na klastry były niewiele gorsze od wyników obliczeń bez podziału na klastry.