PORÓWNANIE KLASYCZNYCH ALGORYTMÓW HEURYSTY-CZNYCH STOSOWANYCH W PROCESIE ROZWIĄZYWANIA PROBLEMÓW TRANSPORTOWYCH

Wstęp: Zagadnienie transportowe (ZT) jest specjalnym przypadkiem programowania całkowitoliczbowego, charakteryzującym się niekwestionowanym znaczeniem praktycznym (w szczególności w obszarze logistyki). Z tego powodu powstało wiele technik przeznaczonych do rozwiązywania problemu zarówno w sposób optymalny, jak i przybliżony. Problem wyboru efektywnej metody konstruowania suboptymalnego rozwiązania dla ZT został poruszony przez wielu badaczy, jednakże zastosowanie przez nich tylko niektórych heurystyk, użyte "łoże testowe", a także brak przeprowadzenia testów statystycznych uniemożliwiają jednoznaczne określenie odpowiedniego podejścia do stosowania heurystyki w ZT, pozostawiając lukę badawczą, która stała się inspiracją do napisania niniejszego artykułu. Dodatkowym celem artykułu jest porównanie wybranych metod przybliżonych, z uwzględnieniem liczby iteracji niezbędnych do zaprojektowania optymalnego rozwiązania za pomocą metody Modified Distribution (MODI) oraz wykazanie potencjalnych korelacji pomiędzy parametrami opisującymi instancję problemu a skutecznością technik.

Metody: W pracy przedstawiono badania porównawcze czterech klasycznych heurystyk (NWC, LCM, VAM i RAM). Testy przeprowadzono na trzech zestawach zadań, składających się z 2500 pseudolosowo wygenerowanych instatacji problemu. Obserwacje potwierdzono za pomocą testu Wilcoxon Signed-Rank i współczynnika korelacji liniowej Pearsona.

Wyniki: Badania potwierdzają, że VAM charakteryzuje się znaczącą jakością wyznaczonych wyników, podczas gdy NWC konstruuje rezultaty o niskiej jakości. W przeciwieństwie do wyników sformułowanych dla niewielkich instatacji ZT, wyniki metody RAM dla dużego zbioru charakteryzowały się wyższą wartością błędu niż rezultaty LCM, wykazując brak możliwości uogólnienia wniosków prawdziwych dla małych problemów (przedstawionych np. w literaturze przedmiotu).

Wnioski: Zaleca się stosowanie VAM zarówno do określania bazowego rozwiązania w metodzie MODI, jak i do przygotowania alokacji zasobów, w przypadku korzystania wyłącznie z heurystyk. Biorąc jednak pod uwagę podejście utylitarne i możliwość wystąpienia konieczności rozwiązywania instancji ZT bez użycia odpowiedniego oprogramowania, zaleca się stosowanie LCM do rozwiązywania dużych instancji problemu. Zidentyfikowano także silną korelację pomiędzy liczbą węzłów opisujących instancję ZT a liczbą iteracji niezbędnych do określenia optymalnego rozwiązania za pomocą metody MODI.