Problem komiwojażera – jak ułożyć optymalną trasę

Autor 16 grudnia, 2020Field Service Management, Usługi
problem komiwojażera

Optymalne ułożenie tras dostaw/dla kierowców – oto największe wyzwanie dla centrów logistycznych, hurtowni, przedsiębiorstw zatrudniających kierowców czy pracowników terenowych. Optymalizacja marszrut jest jednak na tyle skomplikowana, że doczekała się opracowań w postaci modeli matematycznych. Jednym z takich modeli jest słynny „problem komiwojażera” – popularny ze względu na prosty opis zagadnienia i trudny obliczeniowo proces optymalizacji.

Na czym polega problem komiwojażera?

Komiwojażer (w naszym przypadku kurier, dostawca, pracownik terenowy) ma do odwiedzenia pewną liczbę miast. Musi dotrzeć do każdego i wrócić do miejsca, z którego wyruszył. Znamy odległości pomiędzy miastami. Jak komiwojażer powinien zaplanować trasę podróży, aby w sumie przebyć możliwie najkrótszą drogę? Przez odległość możemy tu rozumieć odległość w kilometrach, czas trwania podróży albo jej koszt. Możemy zatem poszukiwać trasy najkrótszej, najszybszej albo najtańszej. Zakładamy przy tym, że odległość między dowolnymi dwoma miastami jest nie większa niż długość jakiejkolwiek drogi łączącej te miasta, która wiedzie przez inne miasta.

Przełóżmy to teraz na sytuację firmy obsługującej logistykę dostaw. Codzienne planowanie np. dostarczania przesyłek do kilkudziesięciu lub kilkuset odbiorców wymaga załadowania dziesiątek czy nawet setek pojazdów. Z zasad kombinatoryki wynika, że sposobów ułożenia tras przy dużej liczbie odbiorców, z uwzględnieniem posiadanej floty, jest więcej niż możliwości trafienia w Lotto. Wybór optymalnej marszruty staje się zatem jeszcze bardziej skomplikowany niż problem komiwojażera.

Jak właściciele firm, których działalność opiera się głównie na dostarczaniu towarów lub usług w terenie, mają sprostać wyzwaniu, które frapuje matematyków?

Wsparcie algorytmów

Do tej pory planista lub spedytor poświęcał większość czasu na planowanie. Porównywanie wszystkich optymalnych wariantów było jednak niemożliwe. Kalkulacje były uproszczone i czasochłonne, a ostateczny efekt – uzyskiwany zazwyczaj w arkuszach kalkulacyjnych – nie zawsze był satysfakcjonujący. Nie wyrzucaj jednak arkusza Excela! Umieść w nim informacje o zadaniach, pracownikach i miejscach docelowych, a następnie użyj bardziej wyspecjalizowanego narzędzia, które w ciągu kilku minut przelicza wszystkie czasy, odległości i inne parametry. Narzędziem tym jest GeoTask Planner Portal – oparta na mapach Google aplikacja do automatycznego planowania tras i zadań. Chcesz zbudować własną aplikację do zarządzania dostawami – skorzystaj z chmurowego API, oferowanego przez GeoTask Planner.

Dlaczego warto korzystać z narzędzi do optymalizacji tras?

Wiemy już, że wszędzie, gdzie mamy do czynienia z rozproszoną i dużą liczbą punktów do odwiedzenia, nawet najbardziej wykwalifikowany specjalista może nie dać rady. Dlatego też warto dokładniej przyjrzeć się korzyściom z wykorzystania narzędzi IT umożliwiających automatyczną optymalizację tras. Najlepiej zobrazuje to przykład rzeczywistej analizy wykonanej przez nasz zespół w jednym z centrów logistycznych przy użyciu aplikacji GeoTask Planner.

A jak to wygląda w praktyce?

Wspomniane przedsiębiorstwo to duże centrum logistyczne o powierzchni 20 000 metrów kwadratowych, które codziennie dostarcza towar do około 300-400 sklepów. Liczba odbiorców zależy od potrzeb zaopatrzeniowych i zmienia się w zależności od pory roku lub dnia tygodnia. Analizie poddana została próbka z kolejnych pięciu dni.

Planiści centrum muszą określić przydział zleceń do pojazdów i jak najszybciej uruchomić proces kompletacji, tak aby następnego dnia rano ciężarówki mogły ruszyć w trasę. Załadunek odbywa się zgodnie z zasadą LIFO (Last In First Out) – pierwszy ładunek trafia do ostatniego sklepu, a ostatni do pierwszego. Tak też musi być ułożona marszruta.

Wykorzystanie aplikacji GeoTask Planner pozwoliło na znaczne zmniejszenie długości marszruty. Poniższy wykres prezentuje, o ile obniżyła się łączna liczba kilometrów przejechanych przez wszystkie pojazdy.

optymalizacja tras

Rys. 1 Liczba kilometrów dla tras, złożonych z tych samych punktów, ułożonych w danym dniu przez planistę i przez optymalizator, czyli GeoTask Planner.

Na podstawie analizowanego przypadku widzimy, że GeoTask Planner umożliwia skrócenie marszruty średnio o 19% – tyle możemy zaoszczędzić na samej długości trasy.

Rys.2 O tyle procent krótsze są trasy układane przez GeoTask Planner od tras układanych przez planistę.

Ponieważ aplikacja układa trasy tak, aby w jak największym stopniu wykorzystać przestrzeń ładunkową samochodów, uzyskujemy dodatkowe korzyści dzięki optymalnemu załadunkowi. Pozwoliło to na ograniczenie liczby pojazdów potrzebnych do dostarczenia towaru średnio o 1-2 pojazdy w porównaniu z wynikami planowania bez wsparcia narzędzi optymalizacyjnych. Poniższa tabela pokazuje liczbę sklepów, do których należy dostarczyć towar w poszczególnych dniach oraz liczbę pojazdów potrzebnych do wykonania tego zadania w przypadku układania marszruty przez planistę oraz przez aplikację GeoTask Planner.

Automatyzacja układania harmonogramu dostaw oszczędza do 80% czasu spedytora/dysponenta poświęcanego na planowanie tras.

Co zyskujesz dzięki automatycznej optymalizacji?

  • Szybki wybór najlepszej trasy spośród wielu tysięcy możliwości. Układanie tras trwa kilka minut zamiast godzin. Dzięki temu logistyk skraca czas poświęcony na planowanie nawet o 80%.
  • Ułożona trasa uwzględnia dane z serwisów mapowych, takie jak odległość i czas dojazdu, co zapewnia precyzyjne informacje na temat dojazdu
  • Trasy ułożone przez optymalizator są krótsze nawet o 20%.
  • Układanie tras uwzględnia ładowność pojazdów, co w wielu przypadkach pozwala obsłużyć dostawy mniejszą liczbą pojazdów.
  • Automatyzacja układania harmonogramu dostaw oszczędza do 80% czasu spedytora/dysponenta poświęcanego na planowanie tras.

Ciekawe? Wypróbuj GeoTaskPlanner

Sprawdź, jak działa GeoTaskPlanner – przez 2 tygodnie możesz bezpłatnie testować możliwości systemu i przekonać się, jak automatyczne układanie tras i harmonogramów poprawi skuteczność wizyt i jakość obsługi klienta.