Search

JP-7855057-B2 - System and method for generating alternative routes

JP7855057B2JP 7855057 B2JP7855057 B2JP 7855057B2JP-7855057-B2

Inventors

  • オルテンホフ， ラジャ ソル
  • ラスナック， ライアン

Assignees

  • エアスペース テクノロジーズ， インコーポレイテッド

Dates

Publication Date
20260507
Application Date
20220811
Priority Date
20210812

Claims (20)

  1. A computer implementation method for generating alternative routes, wherein the method is (a) One or more computing devices identify the optimal path to a destination node on a first graph, wherein the identification is: Determining one or more optimal path nodes, This includes determining one or more tree edges that represent connections between the one or more optimal path nodes, (b) The one or more computing devices generate a path graph, the generation being: (i) Generate a dummy node connected to the destination node as an entry point to the first graph, (ii) generating a false edge indicating a connection from the destination node to the dummy node, (iii) Assigning the dummy node as the root node of the path graph, (iv) Determining an alternative route node on the first graph, wherein the alternative route node is directly connected to the destination node or one of the one or more optimal route nodes, (v) Determining a detour edge that represents a connection from the alternative route node to the destination node or one of the one or more optimal route nodes, (vi) Specifying the determined detour edge as a child node of the root node of the path graph, (vii) Identifying the detour cost associated with traversing the detour edge in order to reach the destination node, (viiii) Inserting the detour cost as a variable in the path graph, (ix) Determining further alternative path nodes on the first graph, wherein the further alternative path nodes are directly connected to the alternative path nodes, (x) Determine further detour edges representing further connections from the further alternative path nodes to the further alternative path nodes, (xi) Specify the determined further detour edge as a further child node of the child node, (xi) Identifying the further detour costs associated with traversing the further detour edges to reach the alternative path node, (xiiii) Inserting the further detour cost as a further variable in the path graph, (xiv) Repeating steps (iv) to (xiii) in succession until all of the alternative path nodes and further alternative path nodes and the detour edges and further detour edges and the detour cost and further detour cost are determined with respect to the first graph, (c) One or more computing devices generate an alternative route sequence based on the route graph, wherein the generation is (xv) Traversing the path graph from the root node to the child node, (xvi) Determining the bypass edge associated with the child node, (xvii) Traversing the first graph from the destination node to the determined detour edge associated with the child node, (xviiii) Based on determining the detour edge, determine an alternative path including the detour edge , (xix) Traversing from the child node to the further child node, (xx) Determining the further detour edge associated with the further child node, (xxi) Traversing the first graph from the destination node until the determined further detour edge associated with the further child node is found on the first graph, (xxii) Based on determining the further detour edges, determine further alternative routes including the further detour edges , (xxiii) Repeating (xv) to (xxii) in succession until all of the above alternative routes and the further alternative routes are determined, (d) One or more computing devices generate a bidirectional graphical user interface (GUI) for displaying the alternative route sequence, (e) A method comprising one or more computing devices transmitting the bidirectional GUI to a display unit for display .
  2. The method according to claim 1, wherein identifying the optimal path to the destination node in (a) is based on applying either Dijkstra's algorithm or the A * algorithm.
  3. The method according to claim 2, further comprising applying either Dijkstra's algorithm or A * algorithm up to a predetermined distance, wherein the predetermined distance represents the maximum aggregated sum of one or more weights of the tree edge , the detour edge, and the further detour edge, each weight representing one or more of time, monetary cost, and distance .
  4. The method according to claim 1, further comprising storing the path graph as an ordered heap data structure.
  5. Identifying the detour cost associated with traversing the detour edge to reach the destination node is: Identifying the starting node on the first graph, Identifying the path from the starting node to the destination node, wherein the path includes the detour edge. Aggregating the weights of a first set associated with the one or more tree edges that represent the connection between the one or more optimal path nodes and the destination node, The weights of the second set are aggregated, wherein the weights of the second set include each weight along the path from the starting node to the destination node . The method according to claim 1, wherein the detour cost is determined by subtracting the weight of the aggregated second set from the weight of the aggregated first set .
  6. Identifying the further detour costs associated with traversing the further detour edges to reach the alternative path node is, Identifying the starting node on the first graph, Identifying the path from the starting node to the destination node, wherein the path includes the further detour edges, Aggregating the weights of a third set associated with the one or more tree edges that represent the connection between the one or more optimal path nodes and the alternative path nodes, The fourth set of weights is aggregated, wherein the fourth set of weights includes each weight along the path from the starting node to the alternative path node . The method according to claim 1, wherein the further detour cost is determined by subtracting the weight of the aggregated third set from the weight of the aggregated fourth set.
  7. The aforementioned method, The system receives a user selection to choose a route from the alternative route sequence via the aforementioned bidirectional GUI, The method according to claim 1, further comprising the one or more computing devices generating a transport route based on the selected route for transporting a person or goods.
  8. A non- transient computer -readable medium, the non- transient computer -readable medium containing instructions , the instructions causing a processor to perform an operation for generating an alternative path, the operation being, (a) One or more computing devices identify the optimal path to a destination node on a first graph, wherein the identification is: Determining one or more optimal path nodes, This includes determining one or more tree edges that represent connections between the one or more optimal path nodes, (b) The one or more computing devices generate a path graph, the generation being: (i) Generate a dummy node connected to the destination node as an entry point to the first graph, (ii) generating a false edge indicating a connection from the destination node to the dummy node, (iii) Assigning the dummy node as the root node of the path graph, (iv) Determining an alternative route node on the first graph, wherein the alternative route node is directly connected to the destination node or one of the one or more optimal route nodes, (v) Determining a detour edge that represents a connection from the alternative route node to the destination node or one of the one or more optimal route nodes, (vi) Specifying the identified detour edge as a child node of the root node of the path graph, (vii) Identifying the detour cost associated with traversing the detour edge in order to reach the destination node, (viiii) Inserting the detour cost as a variable in the path graph, (ix) Determining further alternative path nodes on the first graph, wherein the further alternative path nodes are directly connected to the alternative path nodes, (x) Determine further detour edges representing further connections from the further alternative path nodes to the further alternative path nodes, (xi) Specify the determined further detour edge as a further child node of the child node, (xi) Identifying the further detour costs associated with traversing the further detour edges to reach the alternative path node, (xiiii) Inserting the further detour cost as a further variable in the path graph, (xiv) Repeating steps (iv) to (xiii) in succession until all of the alternative path nodes and further alternative path nodes and the detour edges and further detour edges and the detour cost and further detour cost are determined with respect to the first graph, (c) One or more computing devices generate an alternative route sequence based on the route graph, wherein the generation is (xv) Traversing the path graph from the root node to the child node, (xvi) Determining the bypass edge associated with the child node, (xvii) Traversing the first graph from the destination node to the determined detour edge associated with the child node, (xviiii) Based on determining the detour edge, determine an alternative path including the detour edge , (xix) Traversing from the child node to the further child node, (xx) Determining the further detour edge associated with the further child node, (xxi) Traversing the first graph from the destination node until the determined further detour edge associated with the further child node is found on the first graph, (xxii) Based on determining the further detour edges, determine further alternative routes including the further detour edges , (xxiii) Repeating (xv) to (xxii) in succession until all of the above alternative routes and the further alternative routes are determined, (d) One or more computing devices generate a bidirectional graphical user interface (GUI) for displaying the alternative route sequence, (e) A non- transient computer- readable medium comprising one or more computing devices transmitting the bidirectional GUI to a display unit for display .
  9. The non-transient computer-readable medium according to claim 8 , wherein the operation further includes identifying the optimal path to the destination node in (a) based on applying either Dijkstra's algorithm or A * algorithm.
  10. The operation further comprises applying either Dijkstra's algorithm or A * algorithm up to a predetermined distance , wherein the predetermined distance represents the maximum value of the aggregated sum of one or more weights of the tree edge , the detour edge, and the further detour edge, each weight representing one or more of time, monetary cost, and distance, as described in claim 9.
  11. The non- transient computer- readable medium according to claim 8 , further comprising storing the path graph as an ordered heap data structure.
  12. The operation involves identifying the detour cost associated with traversing the detour edge in order to reach the destination node . Identifying the starting node on the first graph, Identifying the path from the starting node to the destination node, wherein the path includes the detour edge. Aggregating the weights of a first set associated with the one or more tree edges that represent the connection between the one or more optimal path nodes and the destination node, The weights of the second set are aggregated, wherein the weights of the second set include each weight along the path from the starting node to the destination node . The non-transient computer-readable medium according to claim 8, further comprising determining the detour cost by subtracting the weight of the aggregated second set from the weight of the aggregated first set .
  13. The operation involves identifying the additional detour cost associated with traversing the additional detour edge to reach the alternative path node . Identifying the starting node on the first graph, Identifying the path from the starting node to the destination node, wherein the path includes the further detour edges, Aggregating the weights of a third set associated with the one or more tree edges that represent the connection between the one or more optimal path nodes and the alternative path nodes, The fourth set of weights is aggregated, wherein the fourth set of weights includes each weight along the path from the starting node to the alternative path node . The non-transient computer-readable medium according to claim 8, further comprising determining the further detour cost by subtracting the weight of the aggregated third set from the weight of the aggregated fourth set .
  14. The aforementioned operation is , The system receives a user selection to choose a route from the alternative route sequence via the aforementioned bidirectional GUI, The non- transient computer-readable medium according to claim 8, further comprising one or more computing devices generating a transport route based on the selected route for transporting a person or goods.
  15. A computing system for generating alternative routes, wherein the computing system is A memory unit for storing instructions, A control unit coupled to the aforementioned storage unit , A communication unit coupled to the storage unit and Equipped with, The control unit processes the stored instructions , (a) Identifying the optimal path to the destination node on the first graph, wherein the identification is Determining one or more optimal path nodes, This includes determining one or more tree edges that represent connections between the one or more optimal path nodes, (b) generating a path graph, the generation of which means (i) Generate a dummy node connected to the destination node as an entry point to the first graph, (ii) generating a false edge indicating a connection from the destination node to the dummy node, (iii) Assigning the dummy node as the root node of the path graph, (iv) Determining an alternative route node on the first graph, wherein the alternative route node is directly connected to the destination node or one of the one or more optimal route nodes, (v) Determining a detour edge that represents a connection from the alternative route node to the destination node or one of the one or more optimal route nodes, (vi) Specifying the determined detour edge as a child node of the root node of the path graph, (vii) Identifying the detour cost associated with traversing the detour edge in order to reach the destination node, (viiii) Inserting the detour cost as a variable in the path graph, (ix) Determining further alternative path nodes on the first graph, wherein the further alternative path nodes are directly connected to the alternative path nodes, (x) Determine further detour edges representing further connections from the further alternative path nodes to the further alternative path nodes, (xi) Specify the determined further detour edge as a further child node of the child node, (xi) Identifying the further detour costs associated with traversing the further detour edges to reach the alternative path node, (xiiii) Inserting the further detour cost as a further variable in the path graph, (xiv) Repeating steps (iv) to (xiii) in succession until all of the alternative path nodes and further alternative path nodes and the detour edges and further detour edges and the detour cost and further detour cost are determined with respect to the first graph, (c) Generating an alternative route sequence based on the route graph, wherein the generation is (xv) Traversing the path graph from the root node to the child node, (xvi) Determining the bypass edge associated with the child node, (xvii) Traversing the first graph from the destination node to the determined detour edge associated with the child node, (xviiii) Based on determining the detour edge, determine an alternative path including the detour edge , (xix) Traversing from the child node to the further child node, (xx) Determining the further detour edge associated with the further child node, (xxi) Traversing the first graph from the destination node until the determined further detour edge associated with the further child node is found on the first graph, (xxii) Based on determining the further detour edges, determine further alternative routes including the further detour edges , (xxiii) Repeating (xv) to (xxii) in succession until all of the above alternative routes and the further alternative routes are determined, (d) The system is configured to generate a bidirectional graphical user interface (GUI) for displaying the alternative route sequence , The communication unit processes the stored instructions , (e) Transmitting the bidirectional GUI to a display unit for display , (f) The system is configured to receive a user selection to select a route from the alternative route sequence via the bidirectional GUI, The control unit is further configured to generate a transport route based on the selected route for transporting a person or goods , a computing system.
  16. The computing system according to claim 15 , wherein the control unit is further configured to identify the optimal path to the destination node in (a) based on applying either Dijkstra's algorithm or A * algorithm.
  17. The computing system according to claim 16 , wherein the control unit is further configured to apply either Dijkstra's algorithm or A * algorithm up to a predetermined distance , the predetermined distance representing the maximum value of the aggregated sum of one or more weights of the tree edge, the detour edge and the further detour edge, each weight representing one or more of time, monetary cost, and distance .
  18. The control unit is further configured to generate the path graph as an ordered heap data structure , The computing system according to claim 15 , wherein the storage unit is further configured to store the path graph as the ordered heap data structure.
  19. The control unit identifies the detour cost associated with traversing the detour edge in order to reach the destination node . Identifying the starting node on the first graph, Identifying the path from the starting node to the destination node, wherein the path includes the detour edge. Aggregating the weights of a first set associated with the one or more tree edges that represent the connection between the one or more optimal path nodes and the destination node, The weights of the second set are aggregated, wherein the weights of the second set include each weight along the path from the starting node to the destination node . The detour cost is determined by subtracting the weight of the second aggregated set from the weight of the first aggregated set . The computing system according to claim 15, further configured to be determined by
  20. The control unit identifies the further detour cost associated with traversing the further detour edge in order to reach the alternative path node . Identifying the starting node on the first graph, Identifying the path from the starting node to the destination node, wherein the path includes the further detour edges, Aggregating the weights of a third set associated with the one or more tree edges representing the connection between the one or more optimal path nodes and the alternative path nodes, The fourth set of weights is aggregated, wherein the fourth set of weights includes each weight along the path from the starting node to the alternative path node . The further detour cost is determined by subtracting the weight of the aggregated third set from the weight of the aggregated fourth set . The computing system according to claim 15, further configured to be determined by

Description

The aspects of this disclosure generally relate to computing systems for generating alternative routes for use in transportation and logistics. Transportation and logistics are crucial to commercial activity. For example, it is essential to be able to efficiently schedule and transport goods and/or personnel from one place to another. This often involves complex scheduling between carriers (e.g., airlines, ships, trucks, etc.) and other entities (e.g., warehouses, ports, storage facilities, factories, collection points, etc.). However, unforeseen events often occur during the transportation process, including disruptions to transportation routes due to weather or other natural disasters, delays in the shipment/dispatch of goods and personnel due to damaged or broken aircraft, vessels, and/or vehicles, and order cancellations. Therefore, when these unforeseen events occur, systems and methods are needed to quickly and dynamically modify transportation and logistics needs. Modifications may include providing alternative routes to ensure the smooth transport of goods and personnel from one place to another, or to change the routes of resources, goods, or personnel. Despite technological advancements, current technology still lacks the capability to efficiently implement such modifications. Thus, the need for improved techniques to solve the aforementioned problems remains. The accompanying drawings incorporated herein and forming part of this specification illustrate and describe aspects of this disclosure, and further explain the principles of this disclosure, enabling those skilled in the art to construct and use this disclosure. Figure 1 shows a computing system for generating alternative routes according to the aspects of this disclosure. Figure 2 illustrates a method for operating a computing system to generate alternative routes, according to an aspect of this disclosure. Figure 3A illustrates a method, according to an aspect of this disclosure, of causing a computing system to operate to identify the optimal route to a destination node in order to facilitate the step of generating an alternative route. Figure 3B shows a graphical illustration of how the method of Figure 3A is carried out, from an aspect of this disclosure. Figures 4A and 4B illustrate how to operate a computing system to generate a path graph in order to facilitate the step of generating alternative paths, according to aspects of this disclosure.Figures 4A and 4B illustrate how to operate a computing system to generate a path graph in order to facilitate the step of generating alternative paths, according to aspects of this disclosure. Figures 4C-4G show a graphical illustration of how the methods of Figures 4A and 4B are carried out, according to aspects of this disclosure.Figures 4C-4G show a graphical illustration of how the methods of Figures 4A and 4B are carried out, according to aspects of this disclosure.Figures 4C-4G show a graphical illustration of how the methods of Figures 4A and 4B are carried out, according to aspects of this disclosure.Figures 4C-4G show a graphical illustration of how the methods of Figures 4A and 4B are carried out, according to aspects of this disclosure.Figures 4C-4G show a graphical illustration of how the methods of Figures 4A and 4B are carried out, according to aspects of this disclosure. Figure 5A illustrates a method for operating a computing system to generate an alternative path sequence, according to an aspect of this disclosure. Figures 5B-5E show a graphical illustration of how the method of Figure 5A is carried out, from an aspect of this disclosure.Figures 5B-5E show a graphical illustration of how the method of Figure 5A is carried out, from an aspect of this disclosure.Figures 5B-5E show a graphical illustration of how the method of Figure 5A is carried out, from an aspect of this disclosure.Figures 5B-5E show a graphical illustration of how the method of Figure 5A is carried out, from an aspect of this disclosure. Figure 6 shows an exemplary architecture of components that implement a computing system, according to the aspects of this disclosure. Figure 7-9 shows a graphical user interface (GUI) for displaying alternative route sequences and enabling a user to interface with the computing system, according to aspects of this disclosure.Figure 7-9 shows a graphical user interface (GUI) for displaying alternative route sequences and enabling a user to interface with the computing system, according to aspects of this disclosure.Figure 7-9 shows a graphical user interface (GUI) for displaying alternative route sequences and enabling a user to interface with the computing system, according to aspects of this disclosure. The following aspects are described in sufficient detail to enable those skilled in the art to create and use this disclosure. It should be understood that other aspects are evident from this disclosure, and that system, process, or mechanical modifications may be made witho