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),
- 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 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.
W części praktycznej program korzysta, w tle, z map Google (Geocoding API, Directions API) aby wyznaczać współrzędne geograficzne oraz odległości i czasy przejazdu między poszczególnymi lokalizacjami. 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. Program generuje gotowe do wydruku tabele z ustaloną kolejnością lokalizacji, z podanymi realnymi odległościami i czasami przejazdów oraz prezentuje na mapie (tutaj 50 lokalizacji): zestaw lokalizacji, trasę początkową i trasę po optymalizacji (kolejny przykład dla 30 lokalizacji: zestaw lokalizacji, trasa początkowa oraz trasa po optymalizacji).
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.
- TSP (Traveling Salesman Problem - problem komiwojażera),
- 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 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.
W części praktycznej program korzysta, w tle, z map Google (Geocoding API, Directions API) aby wyznaczać współrzędne geograficzne oraz odległości i czasy przejazdu między poszczególnymi lokalizacjami. 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. Program generuje gotowe do wydruku tabele z ustaloną kolejnością lokalizacji, z podanymi realnymi odległościami i czasami przejazdów oraz prezentuje na mapie (tutaj 50 lokalizacji): zestaw lokalizacji, trasę początkową i trasę po optymalizacji (kolejny przykład dla 30 lokalizacji: zestaw lokalizacji, trasa początkowa oraz trasa po optymalizacji).
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.
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 |
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 znaczne wydłużenie czasu obliczeń.
Należy wziąć pod uwagę, że w przypadku programu Trasa, obliczenia były wykonywane z włączonym podglądem graficznym co powodowało znaczne 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 | ||||
| usa115475 | 6204999 | 6567669 | 6.8 dnia (korzystanie z pliku wymiany) | Intel Core i7 CPU 8700 3.2GHz | 5.84 |
| 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.2GHz | 3.88 | |
| usa115475 | 6204999 | 6567669 | Intel Core i7 CPU 8700 3.2GHz | 5.84 |
Wyznaczanie optymalnych tras pojazdów
