Wiele firm, których zysk zależy od obsługi punktów czy Klientów w terenie nie korzysta z żadnej matematycznej metody wyboru najbardziej optymalnych kombinacji tras między nimi. Kolejność wizyt wynika z doświadczenia, przyjętej praktyki czy intuicji planisty, a czasem wręcz przypadku. Mało kto zastanawia się, jaka jest skala możliwych rozwiązań, a co za tym idzie, ile może kosztować przedsiębiorcę taki przypadek w skali miesiąca, roku czy w perspektywie kilku lat.
10 punktów, miliony możliwości
Poniżej oszacowana została liczba możliwych kombinacji tras odpowiednio przy 10, 25 i 50 punktach do odwiedzenia i tylko dla 1 kierowcy.
Gdy mamy za zadanie odwiedzić niewielką liczbę, bo tylko 10 punktów, wybieramy spośród:
10! = 3628800
kombinacji możliwych tras. Zakładając, że jest dokładnie jedno najlepsze rozwiązanie dla 10 – punktowej trasy, to losowo wybierając kolejność punktów mamy szansę w nie trafić z takim samym prawdopodobieństwem jak kupując 4 zakłady w Lotto na trafienie 6.
Alternatywnie, sprawdzając 8 rozwiązań na sekundę już w rok można sprawdzić je wszystkie.
W przypadku 25 punktów liczba wzrasta już do
25! = 15511210043330985984000000 = ok. 1.5 * (10 ^ 25)
kombinacji.
Wiek wszechświata to około 4 * 10 ^ 17. Inaczej, sprawdzając po kolei 150 milionów rozwiązań co sekundę zaczynając od startu Wszechświata, mniej więcej teraz byśmy dochodzili do sprawdzenia ich wszystkich.
Dla 50 punktów liczba możliwych tras to już całkiem sporo, bo:
50! = 30414093201713378043612608166064768844377641568960512000000000000 = ok. 3 * (10 ^ 64)
Ziemia ma około 10 ^ 50 atomów (1 i 50 zer). Inaczej, dla problemu 50 punktów jest około 3 * 10^15 rozwiązań na każdy atom na Ziemi.
Alternatywnie, kombinację tę otrzymamy wybierając nieco większą liczbę – jedno rozwiązanie na około od 10-1000 atomów w naszej galaktyce (w naszej galaktyce jest prawie 10^67 atomów).
20 sekund pracy algorytmu Emapy
Algorytm Emapy na rozwiązanie tak małych problemów potrzebuje kilkadziesiąt sekund obliczeń. Dwie minuty to aż nadto. Dzieje się tak dlatego z wielu powodów, a najprostszy jest taki, że większość z możliwych rozwiązań (tras) jest całkowicie bez sensu. Na przykład po przejechaniu 2 punktów algorytm wie, że niezależnie od tego jaki trzeci punkt trasy wybierze, kierowca nie zdąży wrócić na czas do swojej bazy.
Gdy mamy do dyspozycji tylko jeden pojazd stosunkowo łatwo jest obliczyć liczbę możliwych kombinacji tras. Ciekawsze i znacznie bardziej skomplikowane są kombinacje dla wielu pojazdów . Z czym algorytm Emapy również poradzi sobie bez większych problemów.
Korzystając z 2 pojazdów w firmie należałoby do powyższych szacunków dodać wszystkie możliwe podziały zbioru punktów na 2 podzbiory i pomnożyć to przez ilości możliwych permutacji tych zbiorów, dla 3 na 3 podzbiory, etc.
Jak widać, nie trudno o pomyłkę próbując wyznaczać trasy bazując na własnej intuicji. Koszty takiej pomyłki to przede wszystkich niepotrzebnie zużywane paliwo, zbyt duża liczba zatrudnionych pracowników do obsługi określonej liczby zleceń czy straceni, potencjalni Klienci, nie mogący doczekać się na nasz przyjazd. Już w skali jednego dnia, dla niewielkiej firmy niepotrzebne straty mogą sięgać kilkuset złotych.
Rekordy pobijane na co dzień
Obecne prace programistów Spółki Emapa polegają na ciągłym udoskonalaniu algorytmów VRP, które już i tak znajdują się u szczytu światowych rankingów. Najwięcej rekordów, jakie pobiła Emapa w ostatnich miesiącach należy do przedziału 1000 punktów. Mając jeden pojazd i 1000 klientów do odwiedzenia, mamy około 4 * 10 ^ 2568 sposobów ułożenia dróg.
To jest liczba, która nie ma żadnego porównania z czymkolwiek istniejącym we Wszechświecie, w żadnej jednostce. Największa liczba widoczna w tablicach to liczba rzędu 10^100, przy czym jest to liczba w zasadzie nierozróżnialna od zera w stosunku do 10 ^ 2568.