Algorytm: Planowanie podróży

Question

Potrzebuję zaplanować podróż łączącą n lokalizacji na morzu z określonym początkiem i określonym miejscem docelowym z następującymi ograniczeniami.
Podróż musi dotknąć wszystkich lokalizacji.
Jeśli istnieje rezerwacja od A do B, to należy dotknąć przed B
Czas spędzony w każdej lokalizacji jest różny (w zależności od rezerwacji w tej lokalizacji).
Każda lokalizacja ma okno robocze. Jeśli statek dojdzie do okna roboczego, musi poczekać.
Uwaga: Algorytmy "minimalnego drzewa opinającego" mogą nie być takie, jak czas wymagany w każdym porcie zależy od poprzedniej trasy (z powodu okna roboczego).
Czy jest dostępny jakiś algorytm?

Answer 1

Ant colony optimization wydaje się być najlepszym rozwiązaniem tego znany. Zauważ, że jest to NP problem, a nawet problem NP-zupełny. Oznacza to, że "łatwo" sprawdzić, czy rozwiązanie jest poprawne, ale "ciężko" je znaleźć. Jedynym sposobem na znalezienie "optymalnego" rozwiązania byłoby wypróbowanie wszystkich możliwych rozwiązań, porównanie wyników i zrobienie najlepszego. Oczywiście nie można tego zaakceptować, jeśli chcesz rozwiązać problem w rozsądnym czasie.

Algorytmy ACO znajdą dobre rozwiązanie, zbliżone do optimum. Mówię blisko, ponieważ AFAIK nie może zagwarantować, że zawsze znajdzie najlepszą. Mogą istnieć lepsze rozwiązania. Jednak często nie jest konieczne, aby naprawdę znaleźć najlepsze rozwiązanie, rozwiązanie, które jest po prostu "bardzo dobre", wystarczy, a ACO jest dokładnie tym, czego szukasz. Może znaleźć rozwiązanie w rozsądnych odstępach czasu, a rozwiązanie będzie na pewno dobre.

W Twoim przypadku musisz nieco go zmodyfikować. Zwykle stara się znaleźć tylko najkrótszą trasę, uwzględniając jedynie ścieżkę. W twoim przypadku musi to uwzględniać twoje okno robocze, rezerwacje i czas spędzony na lokalizacji. Ale to tylko modyfikacje "jak mrówki podróżują", podstawowy algorytm pozostaje taki sam i nadal będzie działał tak samo.

Answer 2

Zobacz Traveling salesman problem

Answer 3

To jest problem komiwojażera z modyfikacją dodającą ograniczenie dla okna roboczego ... co oznacza, że ​​rozwiązanie tego problemu będzie jeszcze trudniejsze do znalezienia niż standardowy problem komiwojażera.

Mam kilka podejść, które działają przyzwoicie, aby podać przybliżone rozwiązania.

1. Genetic Algorithms
2. Tabu Search
3. Randomized Algorithm (Np błądzenia losowego)

ja nie wiem, czy odnosi się do problemu, z góry na głowie mówię, że nie , ale dynamic programming może być czasami używany w trudnych sytuacjach.

Answer 4

Jest wiele pracy nad tym problemem. Różni się on pod różnymi nazwami:

1. Problem sprzedawcy samochodowego (routing pojazdu) z oknami czasowymi i ograniczeniami pierwszeństwa.
2. Problem z odbiorem i dostawą.

Istnieje wiele badań na ten temat, wiele z nich w badaniu operacji Journals. Ten problem jest generalnie NP-trudny, więc ogólne, dokładne rozwiązanie problemu, który opisałeś, nie jest praktyczne, ale mogą istnieć dobre, dokładne lub przybliżone rozwiązania konkretnego problemu. Najlepszy algorytm będzie funkcją twoich danych.

• Jak duży jest twój zestaw danych. Jeśli "n" jest względnie małe (30-100), możliwe jest dokładne rozwiązanie z math programming.
• Jak szczelne są okna czasowe i ograniczenia pierwszeństwa. Jeśli liczba możliwych lokalizacji do odwiedzenia w dowolnym oknie czasowym jest niewielka, możliwe jest rozwiązanie takie jak programowanie dynamiczne.
• Jeśli nie możesz znaleźć szczególnego przypadku, prawdopodobnie chcesz połączyć heurystyczny algorytm budowy z post-procesorem lokalnego wyszukiwania. W prosty alternatywą jest tzw GRASP heurystyki, gdzie
• przystąpienia do istniejącej konstrukcji heurystyki,
• losowy jest tak, że wielu biegnie dadzą Ci wiele rozwiązań,
• uruchomić randomizowane wersję wiele razy
• wynos najlepsze rozwiązanie, które wynika.