Visualisez les données d'itinéraires ferroviaires et résolvez les problèmes d'itinéraires les plus courts (Python + Pandas + NetworkX)

introduction

La carte d'itinéraire et le réseau de graphiques vont bien ensemble, et lorsque vous essayez de penser à quelque chose dans la carte d'itinéraire, vous toucherez au problème d'itinéraire le plus court auquel n'importe qui puisse penser.

Transformez la carte ferroviaire en un problème graphique simple et utilisez la méthode Dyxtra pour trouver l'itinéraire le plus court. La bibliothèque Python NetworkX a une méthode Dyxtra intégrée, ce qui est pratique, nous allons donc l'utiliser cette fois.

Le programme a été téléchargé sur Google Colaboratory afin qu'il puisse être exécuté sur le navigateur. Ici https://nbviewer.jupyter.org/github/galileo15640215/train/blob/master/train_dijkstra.ipynb

couler

Même s'il s'agit d'une carte d'itinéraire, elle est trop volumineuse pour gérer soudainement les données nationales, et avant d'envisager les itinéraires à l'échelle nationale, nous commençons par extraire et créer les itinéraires du métro de Tokyo comme un petit problème.

Commande · Traitement de l'information ・ Carte d'itinéraire dans le métro de Tokyo ・ L'itinéraire le plus court dans la zone métropolitaine de Tokyo ・ Carte routière nationale ・ L'itinéraire le plus court du pays

Données requises

Depuis la station data.jp https://ekidata.jp/ Entreprise de données d'entreprise20200309.csv Ligne de données d'itinéraire20200306free.csv Station de données station20200316free.csv Joindre des données de la station de connexion20200306.csv Télécharger. (Nom du fichier CSV au 1er mai 2020)

Nous créerons les données nécessaires sur cette base.

programme

#Modules requis
import pandas as pd
import matplotlib.pyplot as plt
import japanize_matplotlib
import numpy as np
import networkx as nx

#Créer une table au format pandsa à partir d'un fichier csv
station = pd.read_csv("station20200316free.csv")
join = pd.read_csv("join20200306.csv")
#pref = pd.read_csv("pref.csv")
line = pd.read_csv("line20200306free.csv")
company = ("company20200309.csv")

Jusqu'à présent, nous avons mis les données nécessaires dans la table Pandas.

Version du métro de Tokyo

Ensuite, extrayez les données uniquement pour le métro de Tokyo.

#Métro de Tokyo qui extrait uniquement les stations de métro de Tokyo des stations du pays...company_cd == 18
metro = station[["station_cd", "station_name", "line_cd", "lon", "lat"]]
metro = pd.merge(metro, line, on = 'line_cd')
metro = metro[metro["company_cd"] == 18]
metro = metro[["station_cd", "station_name", "line_cd", "lon_x", "lat_x", "line_name", "line_color_c", "line_color_t"]]
lon = metro["lon_x"]
lat = metro["lat_x"]
metro["lon"] = lon
metro["lat"] = lat
metro = metro[["station_cd", "station_name", "line_cd", "lon", "lat", "line_name"]]

#Itinéraire pour extraire le côté connexion du métro de Tokyo...line_cd == 28001---28010
metro_join = join[(join["line_cd"]==28001)|(join["line_cd"]==28002)|(join["line_cd"]==28003)|(join["line_cd"]==28004)|(join["line_cd"]==28005)|(join["line_cd"]==28006)|(join["line_cd"]==28007)|(join["line_cd"]==28008)|(join["line_cd"]==28009)|(join["line_cd"]==28010)]
metro_join = metro_join[["station_cd1", "station_cd2"]]

De là, créez un graphique de la carte d'itinéraire du métro de Tokyo.

#Déclaration de graphe
G = nx.Graph()
#Faire du haut le nom de la station
G.add_nodes_from(metro["station_name"])
#Définir les coordonnées du tracé
pos={}
for i, j, k in zip(metro["station_name"], metro["lon"], metro["lat"]):
  pos[i] = (j, k)
#Liste e à la station_nom et station_Stocker le CD et le lien
e = []
for i, j in zip(metro["station_name"], metro["station_cd"]):
  e.append([i, j])
#Ajouter des informations sur les bords au graphique
for i, j in zip(metro_join["station_cd1"], metro_join["station_cd2"]):
    for k in e:
      if k[1] == i:
        for l in e:
          if l[1] == j:
            G.add_edge(k[0], l[0])
#Paramètres de sortie graphique
plt.figure(figsize=(10,10),dpi=200)
plt.title('Métro de Tokyo', fontsize=20)
plt.axes().set_aspect('equal', 'datalim')
nx.draw_networkx(G, pos, node_color='b', alpha=0.8, node_size=10, font_size=5, font_family='IPAexGothic')
plt.show()

J'ai pu visualiser la carte d'itinéraire du métro de Tokyo. De là, donnez au graphique les informations nécessaires pour résoudre le problème de l'itinéraire le plus court.

Donner des informations au graphique

#Création de données pour donner la distance entre les stations sous forme de poids sur le côté
dist = []
cd1_lat = []
cd1_lon = []
cd2_lat = []
cd2_lon = []
not_exist = [] #station qui existe dans la table de jointure mais pas dans la table de station_Stocker le cd
for i, j in zip(metro_join["station_cd1"], metro_join["station_cd2"]):
  flag = True
  for k, l, m in zip(metro["station_cd"], metro["lat"], metro["lon"]):
    if i == k:
      cd1_x = l
      cd1_y = m
      cd1_lat.append(l)
      cd1_lon.append(m)
      flag = False
    if j == k:
      cd2_x = l
      cd2_y = m
      cd2_lat.append(l)
      cd2_lon.append(m)
  if flag:
    not_exist.append([i, j])
    #print(i, j)
  else:
    dist.append(((cd1_x-cd2_x)**2 + (cd1_y-cd2_y)**2)**0.5)
#Si vous l'exécutez tel quel, une erreur ValueError: Length of values does not match length of index
#Apparemment"station_cd" ==2800701 et 2800702 supprimés car ils n'existent pas dans la table de station et ne sont pas nécessaires dans la table de jointure
#Les deux lignes suivantes...metro_join = metro_join[metro_join["station_cd1"] != 2800701]...Équivalent à
for i in range(len(not_exist)):
  metro_join = metro_join[metro_join["station_cd1"] != not_exist[i][0]]
#Ajouter une colonne pour joindre la table
metro_join["cd1_lat"] = cd1_lat
metro_join["cd1_lon"] = cd1_lon
metro_join["cd2_lat"] = cd2_lat
metro_join["cd2_lon"] = cd2_lon
metro_join["distance"] = dist

Je vais donner le poids de l'arête au graphique

#nodes is station_name
#Donnez les poids des bords du graphique
for i, j, m in zip(metro_join["station_cd1"], metro_join["station_cd2"], metro_join["distance"]):
    for k in e:
      if k[1] == i:
        for l in e:
          if l[1] == j:
            G.add_edge(k[0], l[0], weight=m)

La bibliothèque NetworkX, Networkx.dijkstra_path (), qui est nécessaire pour résoudre le problème de l'itinéraire le plus court, ne semble pas prendre en charge le haut du japonais. Changez les sommets de station_name en station_cd et déclarez un nouveau graphe.

#nodes is station_cd
G = nx.Graph()
G.add_nodes_from(metro["station_cd"])
pos={}
for i, j, k in zip(metro["station_cd"], metro["lon"], metro["lat"]):
  pos[i] = (j, k)
for i, j, m in zip(metro_join["station_cd1"], metro_join["station_cd2"], metro_join["distance"]):
  G.add_edge(i, j, weight=m)
#station_Station avec le même nom lorsque le cd est en haut_Même avec le nom, la station pour chaque ligne_Comme cd est défini, il n'a pas de côté de connexion avec d'autres lignes tel quel
#Par conséquent, connectez les stations avec le même nom avec un poids de 0.
for i, j in zip(metro["station_name"], metro["station_cd"]):
  for k, l in zip(metro["station_name"], metro["station_cd"]):
    if i == k and j != l:
      G.add_edge(j, l, weight=0)

#Définir les stations de départ et d'arrivée
st_name = "Ogikubo"
go_name = "Nishifunabashi"
#station_du nom à la station_Rechercher un CD
for i, j in zip(metro["station_name"], metro["station_cd"]):
  if i == st_name:
    st = j
  if i == go_name:
    go = j
#Rechercher l'itinéraire le plus court
dij = nx.dijkstra_path(G, st, go)
out = []
for k in range(len(dij)):
  for i, j in zip(metro["station_name"], metro["station_cd"]):
    if j == dij[k]:
      out.append(i)
print(out)
#Déclarez le graphique de l'itinéraire le plus court
G_root = nx.Graph()
G_root.add_nodes_from(dij)
pos_root = {}
for l in dij:
  for i, j, k in zip(metro["station_cd"], metro["lon"], metro["lat"]):
    if l == i:
      pos_root[l] = (j, k)
for i in range(len(dij)-1):
  G_root.add_edge(dij[i], dij[i+1])

plt.figure(figsize=(10,10),dpi=200)
plt.title('Métro de Tokyo', fontsize=20)
plt.axes().set_aspect('equal', 'datalim')
nx.draw_networkx(G, pos, node_color='b', alpha=0.3, node_size=10, with_labels= False)
c = ['green' if n==st else 'red' if n!=go else'yellow' for n in G_root.nodes()]
n_size = [30 if n==st else 10 if n!=go else 30 for n in G_root.nodes()]
nx.draw_networkx(G_root, pos_root, node_color=c, alpha=0.9, node_size=n_size, with_labels= False)
plt.show()

Résultat d'exécution [«Ogikubo», «Minami Asagaya», «Shinkoenji», «Higashikoenji», «Shin Nakano», «Nakano Sakagami», «Nishi Shinjuku», «Shinjuku», «Shinjuku Sanchome», «Shinjuku Gyoenmae», 'Yotsuya 3-chome', 'Yotsuya', 'Akasaka Mitsuke', 'Devant le Parlement', 'Devant le Parlement', 'Kasumigaseki', 'Hibiya', 'Hibiya', 'Ginza', 'Ginza', 'Kyobashi' , 'Nihonbashi', 'Nihonbashi', 'Kayabacho', 'Monzen Nakamachi', 'Kiba', 'Toyocho', 'Minamisago', 'Nishi Kasai', 'Kasai', 'Urayasu', 'Minami Gyotoku', «Gyotoku», «Myonori», «Log Nakayama», «Nishifunabashi»]

J'ai pu dessiner l'itinéraire le plus court dans le métro de Tokyo. Comment se compare-t-il à l'excellente application de guidage de transfert?

Le programme a plus de transferts. Cependant, l'itinéraire est presque le même pour un petit comme le métro de Tokyo.

Ensuite, la version nationale

La même chose se fait à l'échelle nationale.

zen_join = join
zen = station[["station_cd", "station_name", "line_cd", "lon", "lat"]]
zen = pd.merge(zen, line, on='line_cd')
zen = zen[["station_cd", "station_name", "line_cd", "lon_x", "lat_x", "line_name"]]
lon = zen["lon_x"]
lat = zen["lat_x"]
zen["lon"] = lon
zen["lat"] = lat
zen = zen[["station_cd", "station_name", "line_cd", "lon", "lat", "line_name"]]
cd1_lat = []
cd1_lon = []
cd2_lat = []
cd2_lon = []
dist = []
not_exist = []
for i, j in zip(zen_join["station_cd1"], zen_join["station_cd2"]):
  flag = True
  for k, l, m in zip(zen["station_cd"], zen["lat"], zen["lon"]):
    if i == k:
      cd1_x = l
      cd1_y = m
      cd1_lat.append(l)
      cd1_lon.append(m)
      flag = False
    if j == k:
      cd2_x = l
      cd2_y = m
      cd2_lat.append(l)
      cd2_lon.append(m)
  if flag:
    not_exist.append([i, j])
    #print(i, j)
  else:
    dist.append(((cd1_x-cd2_x)**2 + (cd1_y-cd2_y)**2)**0.5)
#Supprimé car il n'existe pas dans la table de station et n'est pas nécessaire dans la table de jointure
for i in range(len(not_exist)):
  zen_join = zen_join[zen_join["station_cd1"] != not_exist[i][0]]# & zen_join["station_cd2"] != not_exist[i][1]]
zen_join["cd1_lat"] = cd1_lat
zen_join["cd1_lon"] = cd1_lon
zen_join["cd2_lat"] = cd2_lat
zen_join["cd2_lon"] = cd2_lon
zen_join["distance"] = dist

#nodes is station_cd
G = nx.Graph()
G.add_nodes_from(zen["station_cd"])
pos={}
for i, j, k in zip(zen["station_cd"], zen["lon"], zen["lat"]):
  pos[i] = (j, k)
for i, j, m in zip(zen_join["station_cd1"], zen_join["station_cd2"], zen_join["distance"]):
  G.add_edge(i, j, weight=m)
for i, j, m in zip(zen["station_name"], zen["station_cd"], zen["lat"]):
  for k, l, n in zip(zen["station_name"], zen["station_cd"], zen["lat"]):
    if i == k and j != l and m == n:
      #print(i, j, k, l)
      G.add_edge(j, l, weight=0)
plt.figure(figsize=(10,10),dpi=200)
plt.title('Tout le Japon', fontsize=20)
plt.axes().set_aspect('equal', 'datalim')
nx.draw_networkx(G, pos, alpha=0.0, with_labels=False)
nx.draw_networkx_edges(G, pos)
plt.show()

st_name = "Nemuro"
go_name = "Kagoshima"
for i, j in zip(zen["station_name"], zen["station_cd"]):
  if i == st_name:
    st = j
  if i == go_name:
    go = j
dij = nx.dijkstra_path(G, st, go)
out = []
for k in range(len(dij)):
  for i, j in zip(zen["station_name"], zen["station_cd"]):
    if j == dij[k]:
      out.append(i)
print(out)

#nodes is station_cd
plt.figure(figsize=(50,50),dpi=200)
G_root = nx.Graph()
G_root.add_nodes_from(dij)
pos_root = {}
for l in dij:
  for i, j, k in zip(zen["station_cd"], zen["lon"], zen["lat"]):
    if l == i:
      pos_root[l] = (j, k)
for i in range(len(dij)-1):
  G_root.add_edge(dij[i], dij[i+1])

plt.figure(figsize=(10,10),dpi=200)
plt.title('Tout le Japon', fontsize=20)
plt.axes().set_aspect('equal', 'datalim')
nx.draw_networkx(G, pos, alpha=0.0, with_labels=False)
nx.draw_networkx_edges(G, pos, alpha=0.3)
nx.draw_networkx(G_root, pos_root, alpha=0.0, with_labels=False)
nx.draw_networkx_edges(G_root, pos_root, alpha=1.0, edge_color='r')
plt.show()

Achevée. Il est irréaliste d'établir une connexion, et à moins que vous ne soyez un grand amateur de train, c'est l'enfer. C'est fait. Grâce au Hokkaido Shinkansen, vous pouvez rejoindre Honshu par le tunnel Seikan. En parlant du temps le plus court, il est naturel de passer au Tohoku Shinkansen et au Tokaido Shinkansen, mais si l'itinéraire est le plus court, il semble que vous iriez du côté de la mer du Japon par ligne conventionnelle sans utiliser le Tohoku Shinkansen.

Résumé

L'information secondaire cette fois était la distance, mais si vous l'utilisez comme temps, vous pouvez faire quelque chose comme le temps le plus court pour le guidage de transfert. J'aimerais l'essayer si je peux créer des données de temps. To be continued...

Site référencé

Visualisez les données d'itinéraires ferroviaires sous forme de graphique avec Cytoscape 1 https://qiita.com/keiono/items/29286f49b15a5b13c987 Veuillez vous reporter ici pour le traitement des données de la station.