Jednym z najczęstszych zadań optymalizacji jest wyznaczanie tras pojazdów, w ramach którego celem jest znalezienie najlepszych tras dla floty pojazdów odwiedzających określone lokalizacje. Zazwyczaj „najlepsza” oznacza trasy o najmniejszej odległości lub koszcie. Oto kilka przykładów problemów z wyznaczaniem tras:
- Firma kurierska chce przypisać kierowcom trasy, w których będą realizować dostawy.
- Firma zajmująca się telewizją kablową chce wyznaczyć trasy technikom w celu nawiązywania połączeń z punktami usługowymi.
- Firma oferująca wspólne przejazdy chce wyznaczyć trasy, w których kierowcy będą mogli wsiąść i wysiąść.
Najsłynniejszy problem z wyznaczaniem trasy to problem dotyczący podróżujących pracowników działu sprzedaży. Należy znaleźć najkrótszą trasę dla sprzedawcy, który musi odwiedzać klientów w różnych lokalizacjach i wracać do punktu początkowego. Dostawca usługi tokenów może być reprezentowany za pomocą wykresu, na którym węzły odpowiadają lokalizacjom, a krawędzie (lub łuki) – bezpośrednie przejazdy między lokalizacjami. Na przykład wykres poniżej przedstawia dostawcę usług tokenów z tylko 4 lokalizacjami oznaczonymi etykietami A, B, C i D. Odległość między dowolnymi dwoma lokalizacjami jest określona przez liczbę obok łączącej je krawędzi.
Po obliczeniu odległości wszystkich możliwych tras widać, że najkrótsza trasa to ACDBA, dla której całkowita odległość wynosi 35 + 30 + 15 + 10 = 90.
Problem bardziej się komplikuje, gdy liczba lokalizacji jest większa. W powyższym przykładzie istnieje tylko 6 tras. Jeśli jednak jest 10 lokalizacji (nie licząc punktu początkowego), liczba tras będzie wynosić 362 880. W przypadku 20 lokalizacji numer zwiększa się do wartości 2432902008176640000. Wyczerpujące przeszukanie wszystkich możliwych tras na pewno znajdzie najkrótszą trasę, ale w przypadku małych zbiorów lokalizacji obliczenia te mogą być trudne. W przypadku większych problemów potrzebne są techniki optymalizacji, które pozwolą na inteligentne przeszukanie przestrzeni rozwiązań i znalezienie optymalnego (lub prawie optymalnego) rozwiązania.
Bardziej ogólna wersja dostawcy usługi tokenów to problem z wyznaczaniem tras (VRP), w którym występuje wiele pojazdów. W większości przypadków platformy VRP podlegają pewnym ograniczeniom: na przykład pojazdy mogą mieć maksymalną wagę lub maksymalną ilość przewożonych przedmiotów, a kierowcy mogą być zobowiązani do wizyty w określonych przedziałach czasowych, o których klienci mówią klientom.
LUB-Narzędzia obsługują wiele typów VRP, w tym:
- Problem z podróżnym sprzedawcą – klasyczny problem z wyznaczaniem tras, w którym występuje tylko jeden pojazd.
- Problem z wyznaczaniem tras dla pojazdów, uogólnienie dostawcy usługi tokenów w przypadku kilku pojazdów.
- VRP z ograniczeniami pojemności, w przypadku których pojazdy mogą pomieścić maksymalną liczbę pojazdów.
- VRP z przedziałami czasu, w przypadku których pojazdy muszą odwiedzić lokalizacje w określonych odstępach czasu.
- VRP z ograniczeniami zasobów, takimi jak przestrzeń lub personel na załadowanie i rozładowywanie pojazdów w zajezdni (punkt początkowy tras).
- VRP w przypadku utraconych wizyt, w przypadku których pojazdy nie muszą odwiedzać wszystkich lokalizacji, ale muszą płacić za każdą wizytę w ramach utraconych wizyt.
Ograniczenia rozwiązywania problemów z wyznaczaniem tras pojazdów
Problemy z wyznaczaniem tras dla pojazdów są z natury nieuniknione: czas potrzebny na ich rozwiązanie rośnie wykładniczo z rozmiarem problemu. W przypadku wystarczająco dużych problemów znalezienie optymalnego rozwiązania może potrwać wiele lat. W efekcie OR-Tools zwraca czasami rozwiązania, które są dobre, ale nie optymalne. Aby znaleźć lepsze rozwiązanie, zmień jego opcje wyszukiwania. Przykład znajdziesz w sekcji Zmiana strategii wyszukiwania.