Methods and systems for routing selection based on routing distance and capacity
First Claim
1. A method, comprising:
- obtaining transportation network demand information of a transportation network comprising a plurality of locations and a plurality of roads, the transportation network demand information including a transportation network graph comprising nodes and edges interconnecting the nodes, each node of the transportation network graph representing a location from among the plurality of locations, each edge representing a road between locations, the transportation network demand information further including an outbound demand value of each node, the outbound demand value corresponding to a number of packages and parcels to be delivered from each location;
generating a simplified demand graph from the transportation network graph based on the outbound demand values of each node pair and a distance between each node pair, the simplified demand graph comprising the nodes, at least one of the edges and an effective demand value of each node pair, the generating of the simplified demand graph including determining the effective demand value of each node pair by determining a difference between a first outbound demand value and a second outbound demand value, the first outbound demand value corresponding to a first node of the node pair, the second outbound demand value corresponding to a second node of the node pair;
for each starting node in the simplified demand graph, determining, using one or more processors, a plurality of possible return routes using the simplified demand graph, each of the plurality of possible return routes being a path connecting the location represented by the starting node to one or more other locations using one or more roads, the path originating and terminating at the location represented by the starting node;
determining a payload delivery capacity for each possible return routes of the plurality of possible return routes for each starting node based in part on a transmission capacity of delivery vehicles used in the transportation network and a number of nodes in the possible return route;
determining a routing distance of each possible return route of the plurality of possible return routes for each starting node based on a length of roads traversed in each possible return route;
for starting each node in the simplified demand graph, selecting an advised return route from the plurality of possible return routes based on the payload delivery capacity and the routing distance of the advised return route, the selecting of the advised return route from the plurality of possible return routes including selecting a route from the plurality of possible return routes having the greatest payload delivery capacity; and
causing presentation on a client device of a graphical representation of the simplified demand graph and each of the advised return routes.
2 Assignments
0 Petitions
Accused Products
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.
7 Citations
19 Claims
-
1. A method, comprising:
-
obtaining transportation network demand information of a transportation network comprising a plurality of locations and a plurality of roads, the transportation network demand information including a transportation network graph comprising nodes and edges interconnecting the nodes, each node of the transportation network graph representing a location from among the plurality of locations, each edge representing a road between locations, the transportation network demand information further including an outbound demand value of each node, the outbound demand value corresponding to a number of packages and parcels to be delivered from each location; generating a simplified demand graph from the transportation network graph based on the outbound demand values of each node pair and a distance between each node pair, the simplified demand graph comprising the nodes, at least one of the edges and an effective demand value of each node pair, the generating of the simplified demand graph including determining the effective demand value of each node pair by determining a difference between a first outbound demand value and a second outbound demand value, the first outbound demand value corresponding to a first node of the node pair, the second outbound demand value corresponding to a second node of the node pair; for each starting node in the simplified demand graph, determining, using one or more processors, a plurality of possible return routes using the simplified demand graph, each of the plurality of possible return routes being a path connecting the location represented by the starting node to one or more other locations using one or more roads, the path originating and terminating at the location represented by the starting node; determining a payload delivery capacity for each possible return routes of the plurality of possible return routes for each starting node based in part on a transmission capacity of delivery vehicles used in the transportation network and a number of nodes in the possible return route; determining a routing distance of each possible return route of the plurality of possible return routes for each starting node based on a length of roads traversed in each possible return route; for starting each node in the simplified demand graph, selecting an advised return route from the plurality of possible return routes based on the payload delivery capacity and the routing distance of the advised return route, the selecting of the advised return route from the plurality of possible return routes including selecting a route from the plurality of possible return routes having the greatest payload delivery capacity; and causing presentation on a client device of a graphical representation of the simplified demand graph and each of the advised return routes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A non-transitory 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 transportation network demand information of a transportation network comprising a plurality of locations and a plurality of roads, the transportation network demand information including a transportation network graph comprising nodes and edges interconnecting the nodes, each node of the transportation network graph representing a location from among the plurality of locations, each edge representing a road between locations, the transportation network demand information further including an outbound demand value of each node, the outbound demand value corresponding to a number of packages and parcels to be delivered from each location; generating a simplified demand graph from the transportation network graph based on the outbound demand values of each node pair and a distance between each node pair, the simplified demand graph comprising the nodes, at least one of the edges and an effective demand value of each node pair, the generating of the simplified demand graph including determining the effective demand value of each node pair by determining a difference between a first outbound demand value and a second outbound demand value, the first outbound demand value corresponding to a first node of the node pair, the second outbound demand value corresponding to a second node of the node pair; for each starting node in the simplified demand graph, determining a plurality of possible return routes using the simplified demand graph, each of the plurality of possible return routes being a path connecting the location represented by the starting node to one or more other locations using one or more roads, the path originating and terminating at the location represented by the starting node; determining a payload delivery capacity for each possible return route of the plurality of possible return routes for each starting node based in part on a transmission capacity of delivery vehicles used in the transportation network and a number of nodes in the possible return route; determining a routing distance of each possible return route of the plurality of possible return routes for each starting node based on a length of roads traversed in each possible return route; for each starting node in the simplified demand graph, selecting an advised return route from the plurality of possible return routes based on the payload delivery capacity and the routing distance of the advised return route, the selecting of the advised return route from the plurality of possible return routes including selecting a route from the plurality of possible return routes having the greatest payload delivery capacity; and causing presentation on a client device of a graphical representation of the simplified demand graph and each of the advised return routes. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
19. A system comprising:
-
at least one processor of a machine; a data collection module configured to obtain transportation network demand information of a transportation network comprising a plurality of locations and a plurality of roads, the transportation network demand information including a transportation network graph comprising nodes and edges interconnecting the nodes, each node of the transportation network graph representing a location from among the plurality of locations, each edge representing a road between locations, the transportation network demand information further including an outbound demand value of each node, the outbound demand value corresponding to a number of packages and parcels to be delivered from each location; a demand graph simplification module to generate, using the at least one processor of the machine, a simplified demand graph from the transportation network graph based on the outbound demand values of each node pair and a distance between each node pair, the simplified demand graph comprising the nodes, at least one of the edges and an effective demand value of each node pair;
the demand graph simplification module to generate the simplified demand graph by performing operations including determining the effective demand value of each node pair, the determining the effective demand value of each node pair including determining a difference between a first outbound demand value and a second outbound demand value, the first outbound demand value corresponding to a first node of the node pair, the second outbound demand value corresponding to a second node of the node pair;a route generation module to generate, for each starting node in the simplified demand graph, a plurality of possible return routes using the simplified demand graph, each of the plurality of possible return routes being a path connecting the location represented by the starting node to one or more other locations using one or more roads, the path originating and terminating at the location represented by the starting node; and a route selection module to determine a payload delivery capacity for each possible return route of the plurality of possible return routes for each starting node based in part on a transmission capacity of delivery vehicles used in the transportation network and a number of nodes in the possible return route, the route selection module further to select an advised return route from the plurality of possible return routes based at least in part on a payload delivery capacity and a routing distance of the advised return route, the selecting of the advised return route from the plurality of possible return routes including selecting a route from the of possible return routes having the greatest payload delivery capacity; and an interface module to cause presentation on a client device of a graphical representation of the simplified demand graph and each of the advised return routes.
-
Specification