METHODS AND SYSTEMS FOR ROUTING SELECTION BASED ON ROUTING DISTANCE AND CAPACITY

• US 20150063123A1
• Filed: 10/11/2013
• Published: 03/05/2015
• Est. Priority Date: 08/28/2013
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Cheng, Yu, Li, Wen-Syan, Wang, Mengjiao
• Granted Patent: US 9,350,643 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth

Abstract

A system, computer-readable storage medium storing at least one program, and computer-implemented method for route selection based on payload delivery capacity and routing distance are described. Network demand information is obtained. The network demand information may include a network graph and information related to an outbound demand of each node of the network graph. A simplified demand graph based on the outbound demand of each node and a distance between each node pair is generated. A plurality of return routes for the simplified network graph is generated and a payload delivery capacity of each of the routes is calculated. An advised return route from the plurality of return routes is generated based in part on the payload delivery capacities of the plurality of return routes.

Claims

1. A method, comprising:

obtaining network demand information including a network graph comprising nodes and directed edges interconnecting the nodes, the network demand information further including information related to an outbound demand of each node;

generating a simplified demand graph based on the outbound demand of each node and a distance between each node pair, the simplified demand graph comprising the nodes, at least one of the directed edges and an effective demand of each node;

generating, using one or more processors, a plurality of return routes for the simplified demand graph, each of the plurality of return routes being a path connecting two or more nodes of the simplified demand graph, the path originating and terminating at a particular node;

determining a payload delivery capacity for each of the plurality of return routes; and

selecting an advised return route from the plurality of return routes based at least in part on the payload delivery capacity of the advised return route.

2. The method of claim 1, further comprising assigning a payload to the advised return route, the payload fulfilling the effective demand of the particular node.

3. The method of claim 1, further comprising presenting a graphical representation of the simplified demand graph on a user interface, the presentation of the simplified demand graph including the advised return route.

4. The method of claim 1, wherein the generating of the plurality of return routes comprises applying a breadth-first search algorithm on the simplified demand graph to determine the plurality of return routes.

5. The method of claim 4, wherein the plurality of return routes include only those return routes having a routing distance below a predefined threshold.

6. The method of claim 4, wherein the plurality of return routes include only those return routes having a payload delivery capacity above a predefined threshold.

7. The method of claim 1, wherein the payload delivery capacity is based on a type of transmission vehicle utilized by a network corresponding to the network graph.

8. The method of claim 1, wherein the effective demand is determined by taking the difference between a first outbound demand corresponding to a first node and a second outbound demand corresponding to a second node.

9. The method of claim 1, further comprising determining a routing distance of each of the plurality of return routes.

10. The method of claim 9, wherein the selecting of the advised return route is further based on the routing distance of the advised return route.

11. The method of claim 1, wherein the advised return route originates and terminates at a first node, and further comprising determining an additional advised route based in part on the payload delivery capacity of the additional advised return route, the additional advised route originating and terminating at a second node.

12. The method of claim 1, wherein the payload delivery capacity of the advised return route is highest among all return routes originating and terminating at a first node.

13. The method of claim 1, wherein the network graph corresponds to a communication network.

14. A tangible computer-readable storage medium including instructions that, when executed by at least one processor of a machine, cause the machine to perform operations comprising:

obtaining network demand information including a network graph comprising nodes and directed edges interconnecting the nodes, the network demand information further including information related to an outbound demand of each node;

generating a simplified demand graph based on the outbound demand of each node and a distance between each node pair, the simplified demand graph comprising the nodes, at least one of at least one of the directed edges and an effective demand of each node;

generating a plurality of return routes for the simplified demand graph, each of the plurality of return routes being a path connecting two or more nodes of the simplified demand graph, the path originating and terminating at a particular node;

determining a payload delivery capacity for each of the plurality of return routes; and

selecting an advised return route from the plurality of return routes based at least in part on the payload delivery capacity of the advised return route.

15. The tangible computer-readable storage medium of claim 14, further including instructions that, when executed by the at least one processor of the machine, cause the machine to assign a payload to the advised return route, the payload fulfilling the effective demand of the particular node.

16. The tangible computer-readable storage medium of claim 14, further including instructions that, when executed by the at least one processor of the machine, cause the machine to present a visualization of the simplified demand graph on a user interface, the presentation of the simplified demand graph including the advised return route.

17. The tangible computer-readable storage medium of claim 14, wherein the generating the plurality of return routes comprises applying a breadth-first search algorithm on the simplified demand graph to determine the plurality of return routes.

18. The tangible computer-readable storage medium of claim 14, wherein the selecting of the advised return route is further based on a routing distance of the advised return route.

19. The tangible computer-readable storage medium of claim 14, wherein the network graph corresponds to a transportation network.

20. A system comprising:

at least one processor of a machine;

a data collection module configured to obtain network demand information including a network graph comprising nodes and directed edges interconnecting the nodes, the network demand information further including information related to an outbound demand of each node;

a demand graph simplification module to generate, using the at least one processor of the machine, a simplified demand graph based on the outbound demand of each node and a distance between each node pair, the simplified demand graph comprising the nodes, at least one of the directed edges and an effective demand of each node;

a route generation module to generate a plurality of return routes for the simplified demand graph, each of the plurality of return routes being a path connecting two or more nodes of the simplified demand graph, the path originating and terminating at a particular node; and

a route selection module to select an advised return route from the plurality of return routes based at least in part on a payload delivery capacity of the advised return route.