Często zadawane pytania

Problem komiwojażera (TSP) to matematyczne zagadnienie optymalizacyjne, polegające (w uproszczeniu) na zadaniu znalezienia najkrótszej możliwej trasy, łączącej wszystkie określone punkty na mapie.

Problem decyzyjny polegający na wyznaczeniu optymalnych tras przewozowych dla pewnej ściśle określonej liczby środków transportu, której zadaniem jest obsłużenie zbioru klientów znajdujących się w różnych punktach przy zachowaniu ograniczeń. Kryterium optymalizacji jest całkowity koszt transportu (wyrażony odległościowo, cenowo lub czasowo). Istnieją również rozwinięcia problemu uwzględniające więcej niż jedno kryterium optymalizacji. Problem marszrutyzacji należy do podstawowej problematyki zarządzania operacyjnego flotą środków transportu (rzadziej zarządzania na wyższym szczeblu).

Problem został po raz pierwszy zaprezentowany przez G.B. Dantziga oraz R.H. Ramsera w 1959 roku w pracy The Truck Dispatching Problem opublikowanej na łamach czasopisma Management Science w którym napisano pierwsze podejście algorytmiczne i zastosowano je do dostaw paliw.

Często kontekst polega na dostarczaniu towarów znajdujących się w centralnym składzie klientom, którzy złożyli zamówienia na takie towary. Celem VRP jest zminimalizowanie całkowitego kosztu trasy. W 1964 roku Clarke i Wright ulepszyli podejście Dantziga i Ramsera, stosując skuteczne chciwe podejście zwane algorytmem oszczędności.

Określenie optymalnego rozwiązania VRP jest NP-trudne, więc rozmiar problemów, które można optymalnie rozwiązać za pomocą programowania matematycznego lub optymalizacji kombinatorycznej, może być ograniczony. Dlatego komercyjne solwery mają tendencję do używania heurystyk ze względu na rozmiar i częstotliwość rzeczywistych VRP, które muszą rozwiązać.

VRP ma wiele bezpośrednich zastosowań w przemyśle. W rzeczywistości użycie komputerowych programów optymalizacyjnych może przynieść firmie oszczędności rzędu 5%, ponieważ transport jest zwykle istotnym składnikiem kosztu produktu (10%) – w rzeczywistości sektor transportu stanowi 10 % PKB UE. W konsekwencji wszelkie oszczędności uzyskane przez VRP, nawet poniżej 5%, są znaczące.

Tak, przetwarzamy ok 60% ograniczeń ruchu, szczególnie tych długookresowych, które są komunikowane publicznie w dostępnych państwowych systemach informacyjnych. Uwzględniamy również indywidualne raporty od naszych klientów. Nie jesteśmy w stanie zagwarantować krótkoterminowych blokad czy remontów, ponieważ większość gmin nie komunikuje ich w serwisach cyfrowych

Aktualna sytuacja na drogach nie może znaleźć odzwierciedlenia w planie, ponieważ zmienia się co minutę. Projektujemy trasy i prognozujemy czasy przejazdów na podstawie danych historycznych z danych uzyskanych przy użyciu śledzenia pojazdów GPS o różnych porach dnia (np. Węzeł południowy jest zwykle wolniejszy w poniedziałek rano niż iw środę wieczorem). Proponowane trasy i czasy przejazdów są zatem bardzo realne.

Możemy wyłączyć uwzględnianie ruchu (np. Na potrzeby jednorazowych obliczeń analiz).