Automaton-based framework for asset network routing

Patent metadata

Field	Value
Publication number	US-10474985-B2
Application number	US-201414459262-A
Country	US
Kind code	B2
Filing date	Aug 13, 2014
Priority date	Aug 13, 2014
Publication date	Nov 12, 2019
Grant date	Nov 12, 2019

Abstract

A rule handler may receive a first routing rule and a second routing rule, each routing rule characterizing at least one potential physical transportation route. A rule converter may convert the first routing rule and the second routing rule into a first finite automaton (FA) and a second finite automaton, respectively, and may combine the first finite automaton and the second finite automaton into a finite automaton network graph. A graph comparator may then compare the finite automaton network graph to existing physical transportation routes, and a route selector may select, based on the comparing, at least one feasible physical transportation route from the existing physical transportation routes, the at least one feasible physical transportation route being an instance of the at least one potential physical transportation route.

First claim

What is claimed is:

1. A system comprising:
at least one processor; and
instructions recorded on a non-transitory computer-readable medium, and executable by the at least one processor, the system comprising:
a rule handler configured to receive a first routing rule and a second routing rule through a route management user interface presented at a display device, each routing rule characterizing at least one potential physical transportation route,
a rule converter configured to convert the first routing rule and the second routing rule received through the route management user interface into a first finite automaton (FA) and a second finite automaton, respectively, and further configured to combine the first finite automaton and the second finite automaton into a finite automaton network graph stored using the non-transitory computer-readable medium, wherein nodes represent potential physical locations and transition edges between the nodes of the finite automaton network graph represent the first routing rule and the second routing rule received through the route management user interface,
a graph comparator configured to compare the finite automaton network graph to existing physical transportation routes, the existing physical transportation routes represented as geographic network graphs stored using the non-transitory computer-readable medium, wherein the geographic network graphs include transition edges between a plurality of nodes representing physical locations and further wherein the graph comparator is configured to determine whether each transition edge between pairs of nodes of the finite automaton network graph conforms with a corresponding transition edge between pairs of nodes of the geographic network graphs, wherein the graph comparator is further configured to generate a combined graph stored in the non-transitory computer-readable medium, wherein the combined graph represents at least one potential physical transportation route whose transition edges conform to the finite automaton network graph, and the combined graph comprises one or more of the nodes representing potential physical locations of the finite automaton network graph included within one or more of the nodes representing physical locations of the geographic network graphs, and
a route selector configured to select, based on the comparing, at least one physical transportation route from the existing physical transportation routes, the at least one selected physical transportation route being an instance of the at least one potential physical transportation route, wherein the at least one potential physical transportation route selected by the route selector conforms to the first routing rule and the second routing rule received through the route management user interface and is displayed in the route management user interface for selection.

2. The system of claim 1 , wherein the first routing rule and the second routing rule are defined with respect to a shipment type corresponding to anticipated shipments.

3. The system of claim 2 , wherein the route selector is further configured to receive a geographical start location and destination location characterizing a shipment instance of the shipment type.

4. The system of claim 3 , wherein the existing physical transportation routes are selected from a transportation management system, based on the geographical start location and destination location.

5. The system of claim 1 , wherein each of the first finite automaton, the second finite automaton, and the FA network graph each include a unique START state and a unique FINISH state.

6. The system of claim 1 , wherein the rule converter is configured to construct the FA network graph independently of potential geographical start and end locations.

7. The system of claim 1 , wherein the rule converter is further configured to combine the first and second finite automata using an OR operation.

8. The system of claim 1 , wherein the rule converter is further configured to combine the first and second finite automata using an AND operation.

9. The system of claim 1 , wherein:
the system further comprises instructions that, when executed, cause the at least one processor to perform the following:
before selecting the at least one physical transportation route, removing one or more nodes from the finite automaton network graph in the non-transitory computer-readable medium that do not lead to a unique FINISH state.

10. The system of claim 1 , wherein:
at least one node representing a potential physical location of the finite automaton network graph is included, in the combined graph, in a plurality of nodes representing different physical locations of the geographic network graphs.

11. The system of claim 1 , wherein:
in the combined graph, a node representing a physical location in the geographic network graphs contains one or more nodes representing potential physical locations in the finite automaton network graph.

12. The system of claim 1 wherein:
the system is further configured to recommend a specific physical transportation route from the at least one physical transportation route based on one or more additional constraints that are not characterized by any routing rules included in the finite automaton network graph.

13. A computer-implemented method comprising:
receiving a first routing rule and a second routing rule through a route management user interface, each routing rule characterizing at least one potential physical transportation route;
converting the first routing rule and the second routing rule received through the route management user interface into a first finite automaton and a second finite automaton, respectively;
combining the first finite automaton and the second finite automaton into a finite automaton network graph stored using a non-transitory computer-readable medium, wherein nodes represent potential physical locations and transition edges between the nodes of the finite automaton network graph represent the first routing rule and the second routing rule received through the route management user interface;
comparing the finite automaton network graph to existing physical transportation routes, the existing physical transportation routes represented as geographic network graphs stored using the non-transitory computer-readable medium, wherein the geographic network graphs include transition edges between nodes representing physical locations and further wherein the comparing includes determining whether each transition edge between pairs of nodes of the finite automaton network graph conform with a corresponding transition edge between pairs of nodes of the geographic network graphs;
generating a combined graph stored in the non-transitory computer-readable medium, wherein the combined graph represents at least one potential physical transportation route whose transition edges conform to the finite automaton network graph, and the combined graph comprises one or more of the nodes representing potential physical locations of the finite automaton network graph, and the one or more of the nodes representing potential physical locations of the finite automaton network graph are included within one or more of the nodes representing physical locations of the geographic network graphs; and
selecting, based on the comparing, at least one physical transportation route from the existing physical transportation routes, the at least one selected physical transportation route being an instance of the at least one potential physical transportation route, wherein the selected at least one potential physical transportation route conforms to the first routin

Assignees

• Sap Se

Inventors

• Cen Yuanyuan
• Zheng Yingbin
• Tan Yan
• Wang Honggang
• Nemery Philippe
• Shi Xingtian
• Chen Irene
• Wang Terry
• Finch Mark

Classifications

• G06Q10/08355 Primary

  Routing methods · CPC title

• G06Q10/083

  Shipping · CPC title

• G06Q10/08

  Logistics, e.g. warehousing, loading or distribution; Inventory or stock management · CPC title