×

Methods and systems for routing selection based on routing distance and capacity

  • US 9,350,643 B2
  • Filed: 10/11/2013
  • Issued: 05/24/2016
  • Est. Priority Date: 08/28/2013
  • Status: Active Grant
First Claim
Patent Images

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 all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×