Published January 1, 2020 | Version v1
Publication Open

A Novel Urban Emergency Path Planning Method Based on Vector Grid Map

Creators

  • 1. Beijing University of Technology
  • 2. Beijing Institute of Big Data Research
  • 3. Institute of Software
  • 4. Chinese Academy of Sciences

Description

When an emergency occurs in the city, a large area of road congestion usually occurs. Therefore, it is particularly important to provide an effective emergency path planning strategy for vehicles. However, existing emergency path planning methods do not take into account the connectivity characteristics of the road network and commuting capacity. For this purpose, a Grid Map Emergency Path Planning (GMEPP) framework based on a novel model Grid Road Network (GRN) is designed in this paper. First, the road network data is divided into grids under equal spacing bands, and the roads data divided into different grids and use the commuting capacity of each road as the weight of each edge in the grid. Then a Grid PageRank (GPR) algorithm will be introduced, the output value of this methodology is calculated based on the capacity and number of connected edges of all vertices pointed by the external grid in each grid. The higher value of the grid will be recommended to users first when the path is planning. According to the GRN model, an improved Bidirectional Dijkstra will be applied to query the shortest path between two points, which is called Gird Bidirectional Dijkstra (GBD). At last, GMEPP uses Reverse Contraction Hierarchies (RCH) and Multiple Reverse Contraction Hierarchies (MRCH) originality methodologies based on intersection type to speed up the query algorithm GBD. To compare the efficiency of the proposed method, this paper conducted extensive experiments to verify. The results of the test showed that the Gird Bidirectional Dijkstra Multiple Reverse Contraction Hierarchies (GBD-MRCH) is better than other methods in different grid distributions.

⚠️ This is an automatic machine translation with an accuracy of 90-95%

Translated Description (Arabic)

عندما تحدث حالة طوارئ في المدينة، عادة ما تحدث منطقة كبيرة من ازدحام الطرق. لذلك، من المهم بشكل خاص توفير استراتيجية فعالة لتخطيط مسار الطوارئ للمركبات. ومع ذلك، فإن طرق تخطيط مسار الطوارئ الحالية لا تأخذ في الاعتبار خصائص الاتصال لشبكة الطرق وقدرة التنقل. لهذا الغرض، تم تصميم إطار تخطيط مسار الطوارئ لخريطة الشبكة (GMEPP) بناءً على نموذج جديد لشبكة طرق الشبكة (GRN) في هذه الورقة. أولاً، تنقسم بيانات شبكة الطرق إلى شبكات تحت نطاقات تباعد متساوية، وتنقسم بيانات الطرق إلى شبكات مختلفة وتستخدم سعة التنقل لكل طريق كوزن لكل حافة في الشبكة. ثم سيتم تقديم خوارزمية تصنيف صفحات الشبكة (GPR)، ويتم حساب قيمة خرج هذه المنهجية بناءً على سعة وعدد الحواف المتصلة لجميع الرؤوس التي تشير إليها الشبكة الخارجية في كل شبكة. سيتم التوصية بالقيمة الأعلى للشبكة للمستخدمين أولاً عندما يكون المسار قيد التخطيط. وفقًا لنموذج إشعار استلام البضائع، سيتم تطبيق Dijkstra ثنائي الاتجاه المحسّن للاستعلام عن أقصر مسار بين نقطتين، وهو ما يسمى Gird Bidirectional Dijkstra (GBD). أخيرًا، يستخدم GMEPP التسلسلات الهرمية للانكماش العكسي (RCH) ومنهجيات أصالة التسلسلات الهرمية للانكماش العكسي المتعدد (MRCH) بناءً على نوع التقاطع لتسريع خوارزمية الاستعلام GBD. لمقارنة كفاءة الطريقة المقترحة، أجرت هذه الورقة تجارب مكثفة للتحقق. أظهرت نتائج الاختبار أن التسلسلات الهرمية الانكماشية العكسية المتعددة ثنائية الاتجاه (GBD - MRCH) أفضل من الطرق الأخرى في توزيعات الشبكة المختلفة.

Translated Description (French)

Lorsqu'une urgence survient dans la ville, une grande zone de congestion routière se produit généralement. Par conséquent, il est particulièrement important de fournir une stratégie efficace de planification de trajectoire d'urgence pour les véhicules. Cependant, les méthodes existantes de planification des voies d'urgence ne tiennent pas compte des caractéristiques de connectivité du réseau routier et de la capacité de déplacement. À cette fin, un cadre de planification des voies d'urgence (GMEPP) basé sur un nouveau modèle de réseau routier (GRN) est conçu dans ce document. Tout d'abord, les données du réseau routier sont divisées en grilles sous des bandes d'espacement égales, et les données routières sont divisées en différentes grilles et utilisent la capacité de navettage de chaque route comme poids de chaque bord de la grille. Ensuite, un algorithme Grid PageRank (GPR) sera introduit, la valeur de sortie de cette méthodologie est calculée en fonction de la capacité et du nombre de bords connectés de tous les sommets pointés par la grille externe dans chaque grille. La valeur la plus élevée du réseau sera d'abord recommandée aux utilisateurs lorsque le chemin est en cours de planification. Selon le modèle GRN, une Dijkstra bidirectionnelle améliorée sera appliquée pour interroger le chemin le plus court entre deux points, appelé Gird Bidirectional Dijkstra (GBD). Enfin, GMEPP utilise des méthodologies d'originalité RCH (Reverse Contraction Hierarchies) et MRCH (Multiple Reverse Contraction Hierarchies) basées sur le type d'intersection pour accélérer l'algorithme de requête GBD. Pour comparer l'efficacité de la méthode proposée, cet article a mené des expériences approfondies pour vérifier. Les résultats du test ont montré que les hiérarchies de contraction inverse multiple de Gird Bidirectional Dijkstra (GBD-MRCH) sont meilleures que d'autres méthodes dans différentes distributions de grille.

Translated Description (Spanish)

Cuando ocurre una emergencia en la ciudad, generalmente ocurre una gran área de congestión vial. Por lo tanto, es particularmente importante proporcionar una estrategia efectiva de planificación de rutas de emergencia para vehículos. Sin embargo, los métodos de planificación de rutas de emergencia existentes no tienen en cuenta las características de conectividad de la red vial y la capacidad de desplazamiento. Para este propósito, en este documento se diseña un marco de planificación de rutas de emergencia (GMEPP) del mapa de cuadrícula basado en un nuevo modelo de red de carreteras de cuadrícula (GRN). En primer lugar, los datos de la red de carreteras se dividen en cuadrículas con bandas de separación iguales, y los datos de carreteras se dividen en diferentes cuadrículas y utilizan la capacidad de desplazamiento de cada carretera como el peso de cada borde en la cuadrícula. Luego se introducirá un algoritmo de Grid PageRank (GPR), el valor de salida de esta metodología se calcula en función de la capacidad y el número de bordes conectados de todos los vértices apuntados por la cuadrícula externa en cada cuadrícula. El valor más alto de la cuadrícula se recomendará primero a los usuarios cuando se planifique la ruta. Según el modelo GRN, se aplicará un Dijkstra bidireccional mejorado para consultar el camino más corto entre dos puntos, que se denomina Gird Bidirectional Dijkstra (GBD). Por último, GMEPP utiliza las metodologías de originalidad de las Jerarquías de Contracción Inversa (RCH) y las Jerarquías de Contracción Inversa Múltiple (MRCH) basadas en el tipo de intersección para acelerar el algoritmo de consulta GBD. Para comparar la eficiencia del método propuesto, este documento realizó extensos experimentos para verificar. Los resultados de la prueba mostraron que las jerarquías de contracción inversa múltiple bidireccional de Dijkstra de Gird (GBD-MRCH) son mejores que otros métodos en diferentes distribuciones de cuadrícula.

Files

09174825.pdf.pdf

Files (245 Bytes)

⚠️ Please wait a few minutes before your translated files are ready ⚠️ Note: Some files might be protected thus translations might not work.
Name Size Download all
md5:e47c212d70a02a5fb09ba9c8e3229b6f
245 Bytes
Preview Download

Additional details

Additional titles

Translated title (Arabic)
طريقة جديدة لتخطيط مسار الطوارئ في المناطق الحضرية بناءً على خريطة شبكة المتجهات
Translated title (French)
Une nouvelle méthode de planification des voies d'urgence urbaine basée sur une carte à grille vectorielle
Translated title (Spanish)
Un nuevo método de planificación de rutas de emergencia urbana basado en un mapa de cuadrícula vectorial

Identifiers

Other
https://openalex.org/W3080624024
DOI
10.1109/access.2020.3018729

Is supplement to
https://openalex.org/W4383333717 (Other)
https://openalex.org/W4313270149 (Other)
https://openalex.org/W4223969905 (Other)
https://openalex.org/W3209137076 (Other)
https://openalex.org/W2350727589 (Other)
https://openalex.org/W2161379097 (Other)
https://openalex.org/W2125569607 (Other)
https://openalex.org/W2084091668 (Other)
https://openalex.org/W2007857089 (Other)
https://openalex.org/W2004837674 (Other)

GreSIS Basics Section

Is Global South Knowledge
Yes
Country
China

References

  • https://openalex.org/W158603956
  • https://openalex.org/W1981364207
  • https://openalex.org/W1998902626
  • https://openalex.org/W2050453296
  • https://openalex.org/W2057656582
  • https://openalex.org/W2072485026
  • https://openalex.org/W2127984152
  • https://openalex.org/W2148831787
  • https://openalex.org/W2165005617
  • https://openalex.org/W2356282296
  • https://openalex.org/W2400527150
  • https://openalex.org/W2469333945
  • https://openalex.org/W2580913658
  • https://openalex.org/W2597446791
  • https://openalex.org/W2606808167
  • https://openalex.org/W2634644814
  • https://openalex.org/W2784108802
  • https://openalex.org/W2811372489
  • https://openalex.org/W2890163410
  • https://openalex.org/W2894948714
  • https://openalex.org/W2909085420
  • https://openalex.org/W2910678344
  • https://openalex.org/W2924641327
  • https://openalex.org/W2940988637
  • https://openalex.org/W2971669895
  • https://openalex.org/W2972796040
  • https://openalex.org/W2979317381
  • https://openalex.org/W4249129238
  • https://openalex.org/W4254213484