Żarty na bok, miałem problem z routingiem, który jest prawie problemem dla podróżujących sprzedawców (TSP):
- punkt początkowy jest zdefiniowany
- punkt końcowy pokrywa się z punktem początkowym
- każdy węzeł musi zostać odwiedzony
- całkowity koszt należy zminimalizować
Dwa lata temu myślałem, że TSP będzie idealnie pasować, więc przejrzałem kilka przykładowych danych tsp_solvei Concorde. Na szczęście szybko stało się jasne, że najkrótsza ścieżka TSP nie jest najkrótszą ścieżką , ponieważ problem jest łatwiejszy, ponieważ nierealistyczne wymaganie, aby węzły były odwiedzane tylko raz . To zdjęcie to tylko jednoetapowa ręczna próba optymalizacji obliczonego rozwiązania i już oszczędza odległość najdłużej używanej krawędzi.
Problem pojawił się ponownie, gdy próbuję znaleźć optymalne trasy do podzbiorów stron mapujących / monitorujących. Dane dotyczące lokalizacji i sieci dróg są dość dokładne i precyzyjne, więc takie ćwiczenie ma sens.
Patrzyłem na uogólnienia TSP, ale nie znalazłem odpowiedniego algorytmu. Minimalne drzewa opinające nie uwzględniają zwrotu z gałęzi (1. rozwiązanie tutaj kosztuje 3 dodatkowe). Z tego, co rozumiem, problem najkrótszej ścieżki w końcu obchodzi tylko dwa węzły, a te z optymalnej ścieżki zostaną pominięte. Specjalny przypadek problemu z trasowaniem pojazdu wydaje się pasować najlepiej, choć nie wiem, czy bierze pod uwagę ścieżki niebezpośrednie.
Moje pytanie: czy istnieje jakieś ustalone nazwisko, definicja tego rodzaju problemu (rodziny)? Jakiego algorytmu i narzędzia użyłbyś do jego rozwiązania?
Jestem pewien, że byłoby to trudne obliczeniowo, ale interesują mnie zarówno ogólne (nieskończone zasoby), jak i praktyczne odpowiedzi.
źródło
Odpowiedzi:
To jest TSP . Po prostu nie zdefiniowałeś prawidłowej metryki odległości, ponieważ nie spełnia ona nierówności trójkąta: jeśli istnieje trasa od A do C do B, która jest krótsza niż podana odległość od A do C, to podana odległość od A do C jest po prostu zły. Rozwiązaniem jest aktualizacja macierzy odległości poprzez ustawienie długości od A do C, aby była najkrótszą ze wszystkich tras od A do C.
źródło