Finding minimum cost transportation routes for orders through a transportation network

• US 10,007,889 B2
• Filed: 12/16/2013
• Issued: 06/26/2018
• Est. Priority Date: 12/20/2012
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Arunapuram, Sundararajan, Tsukada, Thomas Kaeppel Payne, Drummond, Jr., Albert Charles, Wang, Yun
• Primary Examiner(s): Apple, Kirsten
• Application Number:
  US14/107,814
• Publication Number:
  US 20140180958A1
• Time in Patent Office: 1,653 Days
• Field of Search: 705 35
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/08355 Routing methods

Abstract

A method, system, and computer program product for enterprise software application modules for order consolidation management. The method commences by receiving a set of orders where individual orders have one or more order constraints, then mapping the orders onto one or more transportation legs, where the individual transportation legs have leg constraints. A set of feasible paths through the legs for the orders is generated and ranked based on a total cost through the legs to pick-up an order from a source location and deliver it to a destination location. The method continues by determining a set of shortest paths through a transportation network for the set of orders, wherein the determination of any one of the shortest paths is made subject to honoring respective order constraints while concurrently honoring the leg constraints. The orders are then remapped onto one of the shortest paths.

Claims

1. A computer implemented method comprising:

using a computing system having at least one processor to perform a process, the process comprising;

receiving a graph of nodes and edges where the nodes represent locations and the edges represent travel between locations, wherein the edges are annotated with edge constraints describing parameters regarding travel between locations;

receiving a set of orders;

converting the set of orders into a set of graph items in a format suitable for processing by a mapping engine, the graph items including at least a source node and destination node, the graph items having one or more order constraints comprising a first type of constraints that are inherent in data corresponding to the set of orders and a second type of constraints that are derived from the data corresponding to the set of orders, the first type of constraints comprising at least one of, a time constraint, a consolidation constraint, and a packing constraint;

mapping the graph items onto one or more transportation legs using the mapping engine, the one or more transportation legs comprising a plurality of locations represented by nodes and one or more edges, the graph items mapped to the one or more transportations legs satisfy the edge constraints for the one or more transportation legs and the order constraints for the graph items comprising inherent constraints and derived constraints;

generating a set of candidate paths between respective source nodes and respective destination nodes for at least a subset of the set of graph items, wherein the generation of any one of the candidate paths of the set of candidate paths is made subject to honoring respective order constraints comprising inherent constraints, derived constraints, leg constraints, and constraints for combinations of candidate paths and subsets of the subset of the set of graph items; and

assigning at least some orders of the set of orders to a selected one of the candidate paths using the graph items and the graph of nodes and edges of the selected one of the candidate paths.

2. The method of claim 1, further comprising:

receiving a set of additional orders, at least some of the set of additional orders having at least one respective order constraint; and

mapping at least some orders of the set of additional orders to a selected one of the candidate paths subject to honoring respective order constraints.

3. The method of claim 1, wherein at least one of the order constraints comprises a content characteristic of a respective order.

4. The method of claim 1, wherein at least one of the order constraints comprises a source location.

5. The method of claim 1, wherein at least one of the order constraints comprises a destination location.

6. The method of claim 1, further comprising honoring a carrier capacity constraint.

7. The method of claim 1, wherein analyzing the set of candidate paths uses a linear programming network solver.

8. The method of claim 1,

further comprising:

receiving a set of additional orders, at least some of the set of additional orders having at least one respective order constraint,

mapping at least some orders of the set of additional orders to a selected one of the candidate paths subject to honoring respective order constraints, and

ordering the candidate paths by a sum of costs associated with each leg; and

wherein;

the order constraints comprise timing constraints, rate constraints, route constraints, quantity constraints, must travers constraints, must avoid constraints, weight constraints, volume constraints, geography constraints, content characteristic constraints, source location constraint, and destination location constraint,

the leg constraints comprise load or capacity constraints, carrier constraints, equipment capacity constraints, rate constraints, weight constraints, and volume constraints,

the derived constraints correspond to at least constraints specifying when orders must be shipped together and when orders must be shipped separately,

at least some of the constraints are entered by a user using a graphical user interface,

mapping comprises at least enumerating a number of paths that respective orders can traverse while still satisfying timings and locations of itineraries, and mapping includes sequencing of pickup and delivery stop constraints,

the generation of any one of the candidate paths of the set of candidate paths is made subject to honoring respective order constraints corresponds to only generating feasible candidate paths, generating comprises the set of candidate paths comprises groupings of respective orders that satisfy the respective order constraints and travers a plurality of legs, the generation of candidate paths is subject to an iteration limit that is user definable,

at least some of the candidate paths correspond to multiple orders and correspond to multiple different transportation modes and carriers, wherein transportation modes comprise at least land, air, and sea

analyzing the set of candidate paths uses a linear programming network solver.

9. The method of claim 1, wherein mapping includes sequencing of pickup and delivery stop constraints.

10. A computer program product embodied in a non-transitory computer readable medium, the computer readable medium having stored thereon a sequence of instructions which, when executed by a processor causes the processor to execute a process to implement finding minimum cost transportation routes by consolidating orders under relaxed constraints, the process comprising:

receiving a graph of nodes and edges where the nodes represent locations and the edges represent travel between locations, wherein the edges are annotated with edge constraints describing parameters regarding travel between locations;

receiving a set of orders;

converting the set of orders into a set of graph items in a format suitable for processing by a mapping engine, the graph items including at least a source node and destination node, the graph items having one or more order constraints comprising a first type of constraints that are inherent in data corresponding to the set of orders and a second type of constraints that are derived from the data corresponding to the set of orders, the first type of constraints comprising at least one of, a time constraint, a consolidation constraint, and a packing constraint;

mapping the graph items onto one or more transportation legs using the mapping engine, the one or more transportation legs comprising a plurality of locations represented by nodes and one or more edges, the graph items mapped to the one or more transportations legs satisfy the edge constraints for the one or more transportation legs and the order constraints for the graph items comprising inherent constraints and derived constraints;

generating a set of candidate paths between respective source nodes and respective destination nodes for at least a subset of the set of graph items, wherein the generation of any one of the candidate paths of the set of candidate paths is made subject to honoring respective order constraints comprising inherent constraints, derived constraints, leg constraints, and constraints for combinations of candidate paths and subsets of the subset of the set of graph items; and

assigning at least some orders of the set of orders to a selected one of the candidate paths using the graph items and the graph of nodes and edges of the selected one of the candidate paths.

11. The computer program product of claim 10, further comprising instructions for:

receiving a set of additional orders, at least some of the set of additional orders having at least one respective order constraint; and

mapping at least some orders of the set of additional orders to a selected one of the candidate paths subject to honoring respective order constraints.

12. The computer program product of claim 10, wherein at least one of the order constraints comprises a content characteristic of a respective order.

13. The computer program product of claim 10, wherein at least one of the order constraints comprises a source location.

14. The computer program product of claim 10, wherein at least one of the order constraints comprises a destination location.

15. The computer program product of claim 10, further comprising instructions for honoring a carrier capacity constraint.

16. The computer program product of claim 10, wherein analyzing the set of candidate paths uses a linear programming network solver.

17. The computer program product of claim 10,

further comprising instructions for:

receiving a set of additional orders, at least some of the set of additional orders having at least one respective order constraint,

mapping at least some orders of the set of additional orders to a selected one of the candidate paths subject to honoring respective order constraints, and

ordering the candidate paths by a sum of costs associated with each leg; and

wherein;

the order constraints comprise timing constraints, rate constraints, route constraints, quantity constraints, must travers constraints, must avoid constraints, weight constraints, volume constraints, geography constraints, content characteristic constraints, source location constraint, and destination location constraint,

the leg constraints comprise load or capacity constraints, carrier constraints, equipment capacity constraints, rate constraints, weight constraints, and volume constraints,

the derived constraints correspond to at least constraints specifying when orders must be shipped together and when orders must be shipped separately,

at least some of the constraints are entered by a user using a graphical user interface,

mapping comprises at least enumerating a number of paths that respective orders can traverse while still satisfying timings and locations of itineraries, and mapping includes sequencing of pickup and delivery stop constraints,

the generation of any one of the candidate paths of the set of candidate paths is made subject to honoring respective order constraints corresponds to only generating feasible candidate paths, generating comprises the set of candidate paths comprises groupings of respective orders that satisfy the respective order constraints and travers a plurality of legs, the generation of candidate paths is subject to an iteration limit that is user definable,

at least some of the candidate paths correspond to multiple orders and correspond to multiple different transportation modes and carriers, wherein transportation modes comprise at least land, air, and sea

analyzing the set of candidate paths uses a linear programming network solver.

18. The computer program product of claim 10, wherein mapping includes sequencing of pickup and delivery stop constraints.

19. A computer system comprising:

a memory for storing instructions; and

a processor which performs the following actions when executing instructions;

receiving a graph of nodes and edges where the nodes represent locations and the edges represent travel between locations, wherein the edges are annotated with edge constraints describing parameters regarding travel between locations;

receiving a set of orders;

converting the set of orders into a set of graph items in a format suitable for processing by a mapping engine, the graph items including at least a source node and destination node, the graph items having one or more order constraints comprising a first type of constraints that are inherent in data corresponding to the set of orders and a second type of constraints that are derived from the data corresponding to the set of orders, the first type of constraints comprising at least one of, a time constraint, a consolidation constraint, and a packing constraint;

mapping the graph items onto one or more transportation legs using the mapping engine, the one or more transportation legs comprising a plurality of locations represented by nodes and one or more edges, the graph items mapped to the one or more transportations legs satisfy the edge constraints for the one or more transportation legs and the order constraints for the graph items comprising inherent constraints and derived constraints;

generating a set of candidate paths between respective source nodes and respective destination nodes for at least a subset of the set of graph items, wherein the generation of any one of the candidate paths of the set of candidate paths is made subject to honoring respective order constraints comprising inherent constraints, derived constraints, leg constraints, and constraints for combinations of candidate paths and subsets of the subset of the set of graph items; and

assigning at least some orders of the set of orders to a selected one of the candidate paths using the graph items and the graph of nodes and edges of the selected one of the candidate paths.

20. The computer system of claim 19,

the actions further comprising:

receiving a set of additional orders, at least some of the set of additional orders having at least one respective order constraint,

mapping at least some orders of the set of additional orders to a selected one of the candidate paths subject to honoring respective order constraints, and

ordering the candidate paths by a sum of costs associated with each leg; and

wherein;

the order constraints comprise timing constraints, rate constraints, route constraints, quantity constraints, must travers constraints, must avoid constraints, weight constraints, volume constraints, geography constraints, content characteristic constraints, source location constraint, and destination location constraint,

the leg constraints comprise load or capacity constraints, carrier constraints, equipment capacity constraints, rate constraints, weight constraints, and volume constraints,

the derived constraints correspond to at least constraints specifying when orders must be shipped together and when orders must be shipped separately,

at least some of the constraints are entered by a user using a graphical user interface,

mapping comprises at least enumerating a number of paths that respective orders can traverse while still satisfying timings and locations of itineraries, and mapping includes sequencing of pickup and delivery stop constraints,

the generation of any one of the candidate paths of the set of candidate paths is made subject to honoring respective order constraints corresponds to only generating feasible candidate paths, generating comprises the set of candidate paths comprises groupings of respective orders that satisfy the respective order constraints and travers a plurality of legs, the generation of candidate paths is subject to an iteration limit that is user definable,

at least some of the candidate paths correspond to multiple orders and correspond to multiple different transportation modes and carriers, wherein transportation modes comprise at least land, air, and sea

analyzing the set of candidate paths uses a linear programming network solver.