Obliczasz optymalne trasy, dotykając wszystkich dostępnych dróg w sieci ArcGIS?

13

Dla przygotowania sezonu zimowego chcemy obliczyć najbardziej optymalne trasy do zraszania soli na drogach. Analiza zna następujące kryteria:

  • pojazdy startują i zatrzymują się w jednym punkcie załadunku
  • wszystkie dostępne drogi należy posypać solą
  • jedna trasa nie może trwać dłużej niż określony czas (załóżmy, że 2 godziny)
  • ze względu na ograniczony ładunek soli na pojazd odległość trasy jest ograniczona do ilości dostępnej soli. (załóżmy, 10 km)

Analityk sieci ArcGIS (10.0) zakłada, że ​​masz punkt początkowy i końcowy do obliczenia trasy. Jednak w tym przypadku nie chodzi o obliczenie najszybszej trasy od początku do celu, ale o najbardziej optymalne trasy do pokonania jak największej odległości w ograniczonym czasie.

Myślimy teraz o obliczeniu punktów środkowych dla każdego odcinka drogi i wykorzystania ich jako celów podróży do obliczenia trasy.

Mark Verschuur
źródło
2
Brzmi to jak rutowanie śmieciarkami tylko tam, gdzie ciężarówki wracają do składu, aby opróżnić, a tutaj sól zostaje ponownie załadowana. Oba muszą odwiedzić wszystkie części sieci.
PolyGeo
Bardzo prawdziwe. Czy masz wskazówki na temat rozwiązywania tego rodzaju pytań dotyczących routingu?
Mark Verschuur
W naszej jurysdykcji mamy dodatkową zmienną, którą jest Sand. ponieważ drogi o mniejszej objętości otrzymują piasek, a drogi o większej objętości - sól. Jeśli chcesz założyć ze mną czat, możemy w pełni omówić problem. Mogę również dać ci wgląd w to, co zrobiliśmy i czy nasze rozwiązania można porównać
dassouki,
Można go zredukować do wielu problemów związanych z odbiorem i dostawą pojazdu i jest na to mnóstwo dokumentów.
Jakub Kania

Odpowiedzi:

5

Myślę, że część odpowiedzi zależy od układu sieci drogowej, a to pytanie może być warte opublikowania na Math Stack Exchange ( /math// ), ponieważ wydaje się, że to problem teorii grafów. Nie sądzę, że będzie to optymalne rozwiązanie, ale może pomóc ci się zbliżyć.

Można podzielić sieć drogową na regiony naturalne, w których suma długości odcinków będzie w przybliżeniu równa ilości, którą ciężarówka może pokonać przy danym ładunku. Następnie dla każdego regionu możesz uruchomić wycieczkę eularian, aby uzyskać trasę, która dotknie wszystkich segmentów. Przykładowy kod python

def eulerian_tour(network_graph):
    graph = network_graph[:]
    route = []
    def find_route(start):
        for (i, j) in graph:
            if i == start:
                graph.remove((i, j))
                find_route(j)
            elif j == start:
                graph.remove((i, j))
                find_route(i)
        route.append(start)

    find_route(graph[0][0])
    route.reverse()
    return route

Następnie możesz rozważyć routing między regionami i zajezdnią i podzielić drogę dostępu na logiczne segmenty dla dostępnych ciężarówek. Mam nadzieję że to pomoże.

Ostra papryczka
źródło
1

Podejdę do tego zadania w ten sposób. ArcGIS Network Analyst ma solver o nazwie VRP , który może pomóc w zamówieniu tras i zarządzaniu nimi. Przekształciłbym każde połączenie drogowe, które masz w zbiorze danych sieciowych, w funkcje punktowe ( na przykład narzędzie GP Feature To Point (zarządzanie danymi) lub może najpierw podzieliłem linie na proste segmenty z dwoma wierzchołkami, a następnie uzyskałem środek, aby stał się punktem centralnym ).

Mówiąc o VRP, staną się twoimi zamówieniami. Następnie przypisujesz swoje trasy ograniczając je do określonego czasu (2 godziny), a miejsce zajezdni będzie zarówno punktem początkowym, jak i końcowym. Zakładając, że masz wiele pojazdów, będziesz w stanie uzyskać wiele tras dla jednego pojazdu lub wiele tras dla tego samego pojazdu.

Zdecydowanie polecam przejrzenie samouczka, który pomoże ci zrozumieć, jak zacząć korzystać z VRP w Network Analyst. Sam używałem tego solwera do wielu projektów i przekonałem się, że jest on niezwykle wydajny i można go w bardzo dużym stopniu dostosować do własnych potrzeb.

Pamiętaj, że Network Analyst działałby dobrze przy ograniczonej liczbie zamówień wejściowych (w twoim przypadku - środek drogi). Udało mi się z kilkoma tysiącami zamówień (do 9 000). Więc jeśli chcesz obsługiwać naprawdę duże miasto, możesz ograniczyć trasy do działania tylko w niektórych częściach miasta (pod względem VRP - Strefy Trasy).

Jeśli szukasz bardziej gotowego i wydajnego rozwiązania zaprojektowanego specjalnie do routingu punktów o dużej gęstości, rozważ użycie RouteSmart . Jest zbudowany na ArcGIS i został zaprojektowany w celu rozwiązania tego rodzaju problemów.

Alex Tereshenkov
źródło
Dziękuję za sugestie. Na pewno sprawdzę RouteSmart
Mark Verschuur