A A+ A++

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.

© Politechnika Śląska

Ogólna klauzula informacyjna o przetwarzaniu danych osobowych przez Politechnikę Śląską

Całkowitą odpowiedzialność za poprawność, aktualność i zgodność z przepisami prawa materiałów publikowanych za pośrednictwem serwisu internetowego Politechniki Śląskiej ponoszą ich autorzy - jednostki organizacyjne, w których materiały informacyjne wytworzono. Prowadzenie: Centrum Informatyczne Politechniki Śląskiej (www@polsl.pl)

Zasady wykorzystywania „ciasteczek” (ang. cookies) w serwisach internetowych Politechniki Śląskiej

Deklaracja dostępności

„E-Politechnika Śląska - utworzenie platformy elektronicznych usług publicznych Politechniki Śląskiej”

Fundusze Europejskie
Fundusze Europejskie
Fundusze Europejskie
Fundusze Europejskie