Analiza sieci transportowej

Szersze omówienie tego tematu zawiera sekcja Analiza bliskości .

Aby zapoznać się z matematyczną teorią grafów sieci transportowej, zobacz Sieć przepływu .

Sieć transportowa lub sieć transportowa to sieć lub wykres w przestrzeni geograficznej opisujący infrastrukturę, która umożliwia i ogranicza ruch lub przepływ. Przykłady obejmują między innymi sieci drogowe , linie kolejowe , trasy lotnicze , rurociągi , akwedukty i linie energetyczne . Cyfrowa reprezentacja tych sieci i metody ich analizy to podstawowa część analizy przestrzennej , systemów informacji geograficznej , użyteczności publicznej i inżynierii transportu . Analiza sieci jest zastosowaniem teorii i algorytmów teorii grafów i jest formą analizy bliskości .

Historia

Możliwość zastosowania teorii grafów do zjawisk geograficznych uznano za wczesną datę. W rzeczywistości wiele wczesnych problemów i teorii podejmowanych przez teoretyków grafów było inspirowanych sytuacjami geograficznymi, takimi jak Siedmiu Mostów w Królewcu , który był jednym z pierwotnych fundamentów teorii grafów, kiedy został rozwiązany przez Leonharda Eulera w 1736 roku.

W latach 70. połączenie zostało przywrócone przez wczesnych twórców systemów informacji geograficznej , którzy wykorzystali je w topologicznych strukturach danych wielokątów (co nie ma tu znaczenia) oraz w analizie sieci transportowych. Wczesne prace, takie jak Tinkler (1977), koncentrowały się głównie na prostych sieciach schematycznych, prawdopodobnie ze względu na brak znacznych ilości danych liniowych i złożoność obliczeniową wielu algorytmów. Pełna implementacja algorytmów analizy sieciowej w oprogramowaniu GIS pojawiła się dopiero w latach 90. XX wieku, ale raczej zaawansowane narzędzia są dziś powszechnie dostępne.

Dane sieciowe

Analiza sieci wymaga szczegółowych danych reprezentujących elementy sieci i jej właściwości. Rdzeniem zestawu danych sieciowych jest wektorowa polilinii reprezentujących ścieżki podróży, albo precyzyjne trasy geograficzne, albo schematyczne diagramy, znane jako krawędzie . Ponadto potrzebne są informacje na temat topologii sieci , reprezentującej połączenia między liniami, umożliwiając w ten sposób modelowanie transportu z jednej linii do drugiej. Zazwyczaj te punkty połączeń lub węzły są uwzględniane jako dodatkowy zestaw danych.

Zarówno krawędziom, jak i węzłom przypisuje się właściwości związane z ruchem lub przepływem:

• Przepustowość , pomiary wszelkich ograniczeń dozwolonego natężenia przepływu, takich jak liczba pasów na drodze, przepustowość telekomunikacyjna lub średnica rury.
• Impedancja , pomiary wszelkich oporów przepływu lub prędkości przepływu, takich jak ograniczenie prędkości lub zakaz skrętu na skrzyżowaniu ulic
• Koszt skumulowany poprzez indywidualną podróż wzdłuż krawędzi lub przez węzeł, zwykle upływający czas, zgodnie z zasadą tarcia o odległość . Na przykład węzeł w sieci ulic może potrzebować innej ilości czasu na wykonanie określonego skrętu w lewo lub w prawo. Takie koszty mogą zmieniać się w czasie, na przykład schemat czasu podróży ulicą miejską w zależności od dobowych cykli natężenia ruchu.
• Objętość przepływu , pomiary rzeczywistego ruchu. Mogą to być określone pomiary zakodowane w czasie, zebrane za pomocą sieci czujników , takich jak liczniki ruchu , lub ogólne trendy w danym okresie, takie jak średni dzienny ruch roczny (AADT).

Metody analizy

Opracowano szeroką gamę metod, algorytmów i technik rozwiązywania problemów i zadań związanych z przepływem sieci. Niektóre z nich są wspólne dla wszystkich typów sieci transportowych, podczas gdy inne są specyficzne dla określonych domen aplikacji. Wiele z tych algorytmów jest zaimplementowanych w komercyjnym i otwartym oprogramowaniu GIS, takim jak GRASS GIS i rozszerzenie Network Analyst do Esri ArcGIS .

Optymalne trasowanie

Główne artykuły: Problem najkrótszej ścieżki i algorytm Dijkstry

Jednym z najprostszych i najczęstszych zadań w sieci jest znalezienie optymalnej trasy łączącej dwa punkty wzdłuż sieci, przy czym optymalna jest definiowana jako minimalizacja jakiejś formy kosztu, takiej jak odległość, wydatek energetyczny lub czas. Typowym przykładem jest wyszukiwanie wskazówek w sieci ulic, funkcja prawie każdej internetowej aplikacji do mapowania ulic, takiej jak Mapy Google . Najpopularniejszą metodą rozwiązania tego zadania, zaimplementowaną w większości programów GIS i kartograficznych, jest algorytm Dijkstry .

Oprócz podstawowego trasowania typu punkt-punkt, często występują również problemy z trasowaniem złożonym . Problem komiwojażera wymaga optymalnego (najmniejsza odległość/koszt) zamówienia i trasy, aby dotrzeć do wielu miejsc docelowych; jest to problem NP-trudny, ale nieco łatwiejszy do rozwiązania w przestrzeni sieciowej niż w przestrzeni nieograniczonej ze względu na mniejszy zbiór rozwiązań. Problem wyznaczania tras pojazdów jest uogólnieniem tego, pozwalając na wiele jednoczesnych tras prowadzących do miejsc docelowych. Inspekcja trasy lub problem „chińskiego listonosza” wymaga podania optymalnej (najmniejszej odległości/kosztu) ścieżki, która przechodzi przez każdą krawędź; powszechnym zastosowaniem jest wyznaczanie tras śmieciarek. Okazuje się, że jest to znacznie prostszy problem do rozwiązania za pomocą czasu wielomianowego .

Analiza lokalizacji

Główne artykuły: Problem lokalizacji obiektu i alokacja lokalizacji

Ta klasa problemów ma na celu znalezienie optymalnej lokalizacji dla jednego lub więcej obiektów wzdłuż sieci, przy czym optymalna definicja to minimalizacja zagregowanego lub średniego kosztu podróży do (lub z) innego zestawu punktów w sieci. Typowym przykładem jest określenie lokalizacji magazynu w celu zminimalizowania kosztów wysyłki do zestawu punktów sprzedaży detalicznej lub lokalizacji punktu sprzedaży w celu zminimalizowania czasu podróży z miejsca zamieszkania potencjalnych klientów. W przestrzeni nieograniczonej (współrzędne kartezjańskie) jest to problem NP-trudny wymagający rozwiązań heurystycznych, takich jak algorytm Lloyda , ale w przestrzeni sieciowej można to rozwiązać deterministycznie.

Poszczególne zastosowania często powodują dodatkowe ograniczenia, takie jak lokalizacja istniejących lub konkurencyjnych obiektów, możliwości obiektów lub maksymalne koszty.

Obszary usługowe

Obszar usług sieciowych jest analogiczny do bufora w nieograniczonej przestrzeni, przedstawiający obszar, do którego można dotrzeć z punktu (zwykle obiektu usługowego) w odległości mniejszej niż określona odległość lub inny skumulowany koszt. Na przykład preferowanym obszarem obsługi remizy strażackiej byłby zestaw odcinków ulic, do których może ona dotrzeć w krótkim czasie. Gdy istnieje wiele obiektów, każda krawędź byłaby przypisana do najbliższego obiektu, dając wynik analogiczny do diagramu Woronoja .

Analiza usterek

Powszechnym zastosowaniem w sieciach użyteczności publicznej jest identyfikacja możliwych lokalizacji usterek lub przerw w sieci (która często jest zakopana lub w inny sposób trudna do bezpośredniego zaobserwowania), wywnioskowana z łatwych do zlokalizowania zgłoszeń, takich jak skargi klientów.

Inżynieria transportu

Główne artykuły: Inżynieria transportu i Przepływ ruchu

Ruch drogowy był szeroko badany przy użyciu metod fizyki statystycznej.

Zobacz też

• Paradoks Braessa
• Sieć przepływu
• Routing heurystyczny
• Międzyplanetarna sieć transportowa
• Nauka o sieciach
• Teoria perkolacji
• Sieć ulic
• Sieć kolejowa
• Transport multimodalny
• Łańcuch dostaw
• Logistyka