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 zrealizowanych jest kilka pierwszych opcji:
- TSP (Traveling Salesman Problem) - problem komiwojażera,

- 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 jak najkrótszych trasach i jak najmniejszej liczbie pojazdów,

  o określonej ładowności).


W dalszej kolejności będą dołączone opcję służące do rozwiązywania zadań VRPTW (Vehicle Routing Problem with Time Windows) i CVRPTW (Capacitated Vehicle Routing Problem with Time Windows) czyli problemy z oknami czasowymi. Program pozwala na optymalizację tras przejazdu ze względu na najkrótszą trasę (czas przejazdu) oraz minimalizację liczby pojazdów. W programie Trasa obliczenia są realizowane 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 

- wybór najlepszego rozwiązania spośród wielu 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 (Przykłady).


W części praktycznej program korzysta z map Google (Geocoding API, Directions API) aby wyznaczać współrzędne geograficzne, odległości i czasy przejazdu między poszczególnymi lokalizacjami oraz w celu prezentacji lokalizacji na mapie. Wszelkie prace związane z mapą (wyznaczanie: współrzędnych geograficznych, odległości i czasów przejazdu oraz prezentacje lokalizacji na mapie itp.) mogą się wiązać z opłatami - konieczny jest klucz dostępu do API Google. Aktualnie, przez okres roku, można korzystać z tych funkcji za darmo (oczywiście przy pewnych limitach). W efekcie obliczeń optymalizacyjnych, 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

- uwzględnia średni czas obsługi danego punktu

- prezentuje na mapie: zestaw lokalizacji, trasę początkową (losową, przed optymalizacją) i trasę po optymalizacji oraz 

- szczegółowe mapy z trasami dla poszczególnych pojazdów (dla SD-MTSP lub MD-MTSP).


Oto kilka przykładów:
50 lokalizacji: zestaw 50 lokalizacji, trasa początkowa i trasa po optymalizacji
30 lokalizacji: zestaw 30 lokalizacji, trasa początkowa oraz trasa po optymalizacji
60 lokalizacji (TSP): zestaw lokalizacji, trasa początkowa oraz trasa po optymalizacji oraz SD-MTSP dla 60 lokalizacji: pojazd_1, pojazd_2 i pojazd_3

95 lokalizacji (TSP): zestaw lokalizacji, trasa początkowa oraz trasa po optymalizacji i MD-MTSP dla 95 lokalizacji:  pojazd_1, pojazd_2, pojazd_3, pojazd_4


Program występuje w wersji 32-bitowej oraz 64-bitowej (umożliwiającej rozwiązywanie dużych zadań np. kilkadziesiąt tysięcy lokalizacji (miejscowości)). 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 (lokalizacji).
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

rozw_opt

czas [s]

komputer


rozw

czas [s]

 z grafiką

komputer

(rozw - rozw_opt)
/ rozw_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.2 GHz

3.88

usa115475


6204999




6567669

6.8 dnia (korzystanie z pliku wymiany)

Intel Core i7 CPU 8700 3.2 GHz

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

rozw_opt


liczba pojazdów

rozw

(rozw - rozw_opt)
/ rozw_opt
  [%]

F-n45-k4

45

2010

4

724.0


4

762.3

5.29

X-n200-k36

200

402

36

58578.0


37

61718.8

5.36

Li-25

761

900

19

16668.5


17

16768.7

0.60

M-n101-k10

101

200

10

820.0


10

859.9

4.86

B-n78-k10

78

100

10

1221.0


10

1267.1

3.77