Opis programu
Prezentowane oprogramowanie może być wykorzystywane do złożonych obliczeń optymalizacyjnych problemów transportowych, zarówno praktycznych jak i teoretycznych. Program Trasa przeznaczony jest do rozwiązywania problemów z dziedziny kombinatoryki a dokładnie problemów VRP (Vehicle Routing Problem). Zagadnienia te są od lat rozwijane na świecie i dostępna jest duża ilość informacji na ten temat. W programie aktualnie zrealizowane są następujące opcje:

- TSP (Traveling Salesman Problem) - problem komiwojażera - wyznaczanie (optymalnej) najszybszej lub najkrótszej trasy przejazdu (przez wiele punktów),

- SD-MTSP (Single Depot Multiple Traveling Salesman Problem) - rozbudowany TSP - problem wielu komiwojażerów, startujących ze wspólnej lokalizacji,

- MD-MTSP (Multi Depot Multiple Traveling Salesman Problem) - rozbudowany TSP - problem wielu komiwojażerów, startujących z różnych lokalizacji,

- CVRP (Capacitated Vehicle Routing Problem) - dostarczanie towarów z centralnego magazynu przy zoptymalizowanych trasach i jak najmniejszej liczbie pojazdów, o określonej ładowności,

- VRPTW (Vehicle Routing Problem with Time Windows - problem komiwojażera | wielu komiwojażerów z nałożonymi ograniczeniami w postaci okien czasowych w poszczególnych lokalizacjach - wyznaczanie najkrótszych tras (minimalnych czasów) przejazdu),

- CVRPTW (Capacitated Vehicle Routing Problem with Time Windows - dostarczanie towarów z centralnego magazynu przy jak najkrótszych trasach i jak najmniejszej liczbie pojazdów, o określonej ładowności, z nałożonymi ograniczeniami w postaci okien czasowych oraz wymaganego ładunku, w poszczególnych lokalizacjach).

Program pozwala na optymalizację tras przejazdu oraz minimalizację liczby pojazdów (kierowców). W programie Trasa obliczenia są realizowane, w głównej mierze, z wykorzystaniem zestawu autorskich algorytmów heurystycznych.

Zastosowany interfejs graficzny pozwala na obserwację przebiegu obliczeń, włączanie i wyłączanie prezentacji punktów (miast, klientów) oraz ich opisów. Można powiększać dowolne fragmenty ekranu i szczegółowo obserwować zmiany tras podczas obliczeń. Dodatkowo program zawiera na przykład opcję podglądu rozmieszczenia punktów, podglądu wybranej trasy oraz wybór najlepszego rozwiązania spośród wygenerowanych.

Program z jednej strony pozwala na rozwiązywanie problemów "teoretycznych" - specjalne testy opracowane dla zagadnień VRP (o liczności nawet kilkuset tysięcy lokalizacji), które pozwalają na ocenę jakości zastosowanych algorytmów a z drugiej strony umożliwia wykorzystanie tych procedur do różnych praktycznych zagadnień transportowych.

Program Trasa może być z powodzeniem wykorzystywany przez różne firmy, które muszą transportować swoje produkty, szczególnie dla wielu odbiorców czy firmy dostarczające towary do sklepów, klientów, instytucji (firmy kurierskie, firmy cateringowe, firmy dostarczające zaopatrzenie do sklepów, marketów, aptek, instalatorzy np. fotowoltaiki, itd.).
W części praktycznej, program korzysta z dwóch serwisów:
- Google API (Geocoding API, Directions API)
lub
- Openrouteservice API (Directions API)
aby wyznaczyć współrzędne geograficzne oraz odległości i czasy przejazdu między poszczególnymi lokalizacjami. Dodatkowo program prezentuje lokalizacje oraz trasy na mapach.

W efekcie obliczeń, na przykład dla TSP, użytkownik programu uzyskuje optymalną trasę przejazdu, pozwalającą na oszczędności czasu, paliwa oraz zaangażowanie mniejszej ilości kierowców. Poza tym nie traci czasu na każdorazowe ustalanie kolejności przejazdu przez poszczególne lokalizacje i zapobiega wyznaczaniu niemożliwych do realizacji, w danym czasie, tras przejazdów (tutaj można wykorzystać SD-MTSP lub MD-MTSP). Program generuje gotowe do wydruku tabele z ustaloną kolejnością lokalizacji, z podanymi realnymi odległościami i czasami przejazdów oraz uwzględnia średni czas obsługi danego punktu.

Program umożliwia planowanie tras, praktycznie dla dowolnej ilości lokalizacji. Jeśli czas realizacji trasy przejazdu, po wykonaniu obliczeń TSP, jest za długi, to opcja SD-MTSP jest w tym przypadku dobrym rozwiązaniem. Pozwala automatycznie podzielić początkowy zestaw lokalizacji na wybraną ilość podzbiorów i wyznaczyć optymalne trasy dla każdego z nich (ilość podtras to ilość pojazdów | kierowców).

Kolejny przypadek dotyczy przypadku wielu baz (lokalizacji z których wyruszają pojazdy – na przykład z kilku miejscowości). Jeżeli czas realizacji trasy, po wykonaniu obliczeń TSP, jest za długi, to można wykorzystać opcję obliczeń MD-MTSP. Pozwala ona podzielić początkowy zestaw lokalizacji na wybraną ilość podzbiorów (klastrów) i wyznaczyć optymalne trasy dla każdego z nich (ilość podtras to ilość pojazdów | kierowców). Przy czym każdy z podzbiorów (obszarów) ma własną bazę (miejscowość), z której wyruszają pojazdy. Wszystkie lokalizacje są zatem dzielone automatycznie na klastry (obszary), w których poruszają się pojazdy. Program realizuje obliczenia optymalizacyjne tras, dla wielu pojazdów równocześnie
oraz prezentuje na mapach: zestaw lokalizacji, trasę początkową (losową, przed optymalizacją), trasę po optymalizacji oraz szczegółowe mapy z trasami dla poszczególnych pojazdów (dla TSP, SD-MTSP, MD-MTSP, CVRP, VRPTW oraz CVRPTW). Poniżej przedstawiono kilka przykładów (więcej informacji umieszczono w pomocy programu – dostępnej w różnych formatach, w opcji ‘Pobierz program’).
Wyniki obliczeń TSP (mapy Google) - 50 lokalizacji
zestaw 50 miast w Polsce
trasa początkowa (losowa)
trasa po optymalizacji
Wyniki obliczeń TSP (mapy Google) - 30 lokalizacji
zestaw 30 miejscowości
trasa początkowa (uproszczona)
trasa początkowa (rzeczywista)
trasa po optymalizacji (uproszczona)
trasa po optymalizacji (rzeczywista)
Wyniki obliczeń TSP ( mapy OpenRouteService) - 60 lokalizacji w Poznaniu
zestaw 60 lokalizacji
trasa początkowa (uproszczona)
trasa po optymalizacji (rzeczywista)
Wyniki obliczeń TSP i SD-MTSP dla 60 lokalizacji
zestaw 60 miejscowości
trasa początkowa (uproszczona)
trasa optymalna (uproszczona)
SD-MTSP - trasa pojazdu nr 1
SD-MTSP - trasa pojazdu nr 2
SD-MTSP - trasa pojazdu nr 3
Wyniki obliczeń TSP i MD-MTSP dla 95 lokalizacji
zestaw 95 miejscowości
trasa początkowa (uproszczona)
trasa optymalna (uproszczona)
MD-MTSP - trasa pojazdu nr 1
MD-MTSP - trasa pojazdu nr 2
MD-MTSP - trasa pojazdu nr 3
MD-MTSP - trasa pojazdu nr 4
Wyniki obliczeń CVRP dla 100 lokalizacji
zestaw 100 lokalizacji
najlepsze rozwiązanie
trasa pojazdu nr 1
trasa pojazdu nr 2
trasa pojazdu nr 3
trasa pojazdu nr 4
trasa pojazdu nr 7
20 lokalizacji
VRPTW - 20 lokalizacji, 3 pojazdy
CVRPTW - 20 lokalizacji, 3 pojazdy
55 lokalizacji, Wrocław
VRPTW - 55 lokalizacji, 2 pojazdy
CVRPTW - 55 lokalizacji, 3 pojazdy
Program występuje w wersji 32-bitowej oraz 64-bitowej (umożliwiającej rozwiązywanie bardzo dużych zadań np. kilkuset tysięcy lokalizacji (punktów)). W obu przypadkach programy są realizowane z wykorzystaniem przetwarzania równoległego i mogą być zoptymalizowane pod określony procesor.
Poniżej przedstawiono przykładowe wyniki, dla standardowych testów, dotyczące TSP. Z lewej strony tabeli pokazano rozwiązania optymalne a z prawej uzyskane programem Trasa. Pierwsza kolumna tabeli zawiera nazwę testu. Liczba umieszczona w nazwie testu to ilość punktów (miast).
Należy wziąć pod uwagę, że w przypadku programu Trasa, obliczenia były wykonywane z włączonym podglądem graficznym co powodowało wydłużenie czasu obliczeń.
nazwa program ro_opt czas [s] komputer ro czas [s] z grafiką komputer (ro-ro_opt)/ro_opt [%]
ca4663 LKH 1291832 1767 - 1342413 190 Intel Core i7 CPU 6700 3.4Ghz 3.92
ho14473 LKH 177405 1373210 Compaq Alpha EV6 500 MHz 184194 14858 Intel Core i7 CPU 6700 3.4Ghz 3.83
it16862 - 557315 14 lat AMD Athlon 1900+ 585058 17579 Intel Core i7 CPU 6700 3.4Ghz 4.98
mu1979 Concorde, CPLEX 6.5 LP solver 86891 9809 Compaq Alpha EV6 500 MHz 89025 99 Intel Core i7 CPU 860 2.8Ghz 2.46
sw24978 - 855597 84.8 lat 2.8 GHz Intel Xeon 899430 17554 Intel Core i7 CPU 860 2.8Ghz 5.12
pla33810 - 66048945 - - 68900896 32826 Intel Core i7 CPU 6700 3.4GHz 4.32
pla95900 LKH 142382641 136 lat 2.4 GHz AMD Opteron 250 compute node 147902256 209783 Intel Core i7 CPU 8700 3.2GHz 3.88
usa115475 - 6204999 - - 6567669 6.8 dnia (korzystanie z pliku wymiany) Intel Core i7 CPU 8700 3.2GHz 5.84
Kolejna tabela przedstawia przykładowe wyniki, dla standardowych testów, dotyczące CVRP. Z lewej strony tabeli pokazano rozwiązania optymalne a z prawej uzyskane programem Trasa. Pierwsza kolumna tabeli zawiera nazwę testu.
nazwa rozmiar pojemność liczba pojazdów ro_opt liczba pojazdów ro (ro-ro_opt)/ro_opt [%]
F-n45-k4 45 2010 4 724 4 762.3 5.29
X-n200-k36 200 402 36 58578 37 61682 5.3
Li-25 761 900 19 16668.5 17 16677.4 0.05
M-n101-k10 101 200 10 820 10 856.0 4.39
B-n78-k10 78 100 10 1221 10 1267.1 3.77