Cost and latency reductions through dynamic updates of order movement through a transportation network

• US 10,043,150 B2
• Filed: 12/16/2013
• Issued: 08/07/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
• Primary Examiner(s): Apple, Kirsten
• Application Number:
  US14/107,698
• Publication Number:
  US 20140180952A1
• Time in Patent Office: 1,695 Days
• Field of Search: 705 35, 705 36 R
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/08355 Routing methods

Abstract

A method, system, and computer program product for shipping management. The computer implemented method commences upon identifying a set of orders to be shipped from a source region to a destination region using a transportation network, and determining candidate options for performing stops over possible routes between the source region and the destination region. A clustering analysis process is performed over the candidate options such that the clustering analysis considers many order consolidation possibilities while observing timing constraints. Low-cost options from among the candidate options are considered to identify one or more low-cost options, and a multi-stop route plan is generated to correspond to a selected low-cost option. The orders are shipped in accordance with the multi-stop route plan, and in accordance with the corresponding consolidation of the set of orders.

Claims

1. A method comprising:

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

receiving a set of route data;

converting the set of route data from a first data format to a second data format to generate data suitable for processing by a clustering engine, the second data format comprising 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;

identifying a set of orders to be shipped from a source region to a destination region using a transportation network;

converting the set of orders into graph items, the graph items including at least a source node and a destination node, the graph items further comprising graph item constraints specifying conditions for using the edges of the graph of nodes, wherein the graph items are to be merged with the graph of nodes and edges as part of generating a plurality of multi-stop route plans;

generating relaxed constraints from the graph item constraints;

identifying candidate options for performing stops at locations corresponding to a subset of the nodes over possible routes represented by a plurality of the nodes and a plurality of the edges between the source region and the destination region, wherein the candidate options correspond to individual orders of the set of orders and satisfy the relaxed constraints, and the relaxed constraints increase the probability that the lowest cost route can be found;

performing clustering analysis upon the candidate options using the clustering engine by generating the plurality of multi-stop route plans that meet the edge constraints and the graph item constraints, at least some of the plurality of multi-stop route plans including at least a plurality of the candidate options, and generating the plurality of multi-stop route plans comprises at least a consolidation of two or more of the graph items with at least a subset of the graph of nodes and edges, wherein clustering analysis considers a plurality of order consolidation possibilities; and

generating a multi-stop route schedule for a selected multi-stop route plan for execution on the transportation network.

2. The method of claim 1, further comprising adding one or more orders to the selected multi-stop route plan, and wherein:

the possible routes comprise a starting point of a leg, at least one throughpoint and an ending point of a leg

the candidate options for performing stops over possible routes comprise a multi-leg itinerary

clustering analysis comprises analysis of a pickup timing constraint, a delivery timing constraint, and costs of the candidate options, and clustering analysis uses a network solver to observe least one of a pickup timing constraint, and a delivery timing constraint the selection multi-stop route plan observes crossdock constraints comprising crossdock arrival constraints and a crossdock departure constraints, and the crossdock constraints corresponds to at least an order consolidation, and the selected multi-stop route plan corresponds to a source region and a destination region different from the source region and includes a land sea, and air legs and satisfies the relaxed constraints, and

generating relaxed constraints occurs before route generation, relaxing one or more constraints results in a penalty used in optimization, an identification of more nodes for routing and additional orders for routing wherein at least one of the source region and the destination region comprises at least one overland leg.

3. The method of claim 1, wherein the possible routes comprise a starting point of a leg, at least one throughpoint, and an ending point of a leg.

4. The method of claim 1, wherein the candidate options for performing stops over possible routes comprise a multi-leg itinerary.

5. The method of claim 1, wherein clustering analysis comprises analysis of at least some costs of the candidate options.

6. The method of claim 1, wherein clustering analysis comprises analysis of at least one of, a pickup timing constraint, and a delivery timing constraint.

7. The method of claim 1, wherein clustering analysis uses a network solver to observe least one of, a pickup timing constraint, and a delivery timing constraint.

8. The method of claim 1, wherein the multi-stop route plan observes a crossdock arrival constraint.

9. The method of claim 1, wherein the multi-stop route plan observes a crossdock departure constraint.

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, the process comprising:

receiving a set of route data;

converting the set of route data from a first data format to a second data format to generate data suitable for processing by a clustering engine, the second data format comprising 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;

identifying a set of orders to be shipped from a source region to a destination region using a transportation network;

converting the set of orders into graph items, the graph items including at least a source node and a destination node, the graph items further comprising graph item constraints specifying conditions for using the edges of the graph of nodes, wherein the graph items are to be merged with the graph of nodes and edges as part of generating a plurality of multi-stop route plans;

generating relaxed constraints from the graph item constraints;

identifying candidate options for performing stops at locations corresponding to a subset of the nodes over possible routes represented by a plurality of the nodes and a plurality of the edges between the source region and the destination region, wherein the candidate options correspond to individual orders of the set of orders and satisfy the relaxed constraints, and the relaxed constraints increase the probability that the lowest cost route can be found;

performing clustering analysis upon the candidate options using the clustering engine by generating the plurality of multi-stop route plans that meet the edge constraints and the graph item constraints, at least some of the plurality of multi-stop route plans including at least a plurality of the candidate options, and generating the plurality of multi-stop route plans comprises at least a consolidation of two or more of the graph items with at least a subset of the graph of nodes and edges, wherein clustering analysis considers a plurality of order consolidation possibilities; and

generating a multi-stop route schedule for a selected multi-stop route plan for execution on the transportation network.

11. The computer program product of claim 10, the process further comprising adding one or more orders to the selected multi-stop route plan, and wherein:

the possible routes comprise a starting point of a leg, at least one throughpoint and an ending point of a leg

the candidate options for performing stops over possible routes comprise a multi-leg itinerary

clustering analysis comprises analysis of a pickup timing constraint, a delivery timing constraint, and costs of the candidate options, and clustering analysis uses a network solver to observe least one of, a pickup timing constraint, and a delivery timing constraint

the selection multi-stop route plan observes crossdock constraints comprising crossdock arrival constraints and a crossdock departure constraints, and the crossdock constraints corresponds to at least an order consolidation, and the selected multi-stop route plan corresponds to a source region and a destination region different from the source region and includes a land, sea, and air legs and satisfies the relaxed constraints, and

generating relaxed constraints occurs before route generation, relaxing one or more constraints results in a penalty used in optimization, an identification of more nodes for routing, and additional orders for routing.

12. The computer program product of claim 10, wherein the possible routes comprise a starting point of a leg, at least one throughpoint, and an ending point of a leg.

13. The computer program product of claim 10, wherein the candidate options for performing stops over possible routes comprise a multi-leg itinerary.

14. The computer program product of claim 10, wherein clustering analysis comprises analysis of at least some costs of the candidate options.

15. The computer program product of claim 10, wherein clustering analysis comprises analysis of at least one of, a pickup timing constraint, and a delivery timing constraint.

16. The computer program product of claim 10, wherein clustering analysis uses a network solver to observe least one of, a pickup timing constraint, and a delivery timing constraint.

17. The computer program product of claim 10, wherein the multi-stop route plan observes a crossdock arrival constraint.

18. The computer program product of claim 10, wherein the multi-stop route plan observes a crossdock departure constraint.

19. A computer system comprising:

a memory for storing instructions; and

a processor which performs the following actions when executing instructions;

receiving a set of route data;

converting the set of route data from a first data format to a second data format to generate data suitable for processing by a clustering engine, the second data format comprising 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;

identifying a set of orders to be shipped from a source region to a destination region using a transportation network;

converting the set of orders into graph items, the graph items including at least a source node and a destination node, the graph items further comprising graph item constraints specifying conditions for using the edges of the graph of nodes, wherein the graph items are to be merged with the graph of nodes and edges as part of generating a plurality of multi-stop route plans;

generating relaxed constraints from the graph item constraints;

identifying candidate options for performing stops at locations corresponding to a subset of the nodes over possible routes represented by a plurality of the nodes and a plurality of the edges between the source region and the destination region, wherein the candidate options correspond to individual orders of the set of orders and satisfy the relaxed constraints, and the relaxed constraints increase the probability that the lowest cost route can be found;

performing clustering analysis upon the candidate options using the clustering engine by generating the plurality of multi-stop route plans that meet the edge constraints and the graph item constraints, at least some of the plurality of multi-stop route plans including at least a plurality of the candidate options, and generating the plurality of multi-stop route plans comprises at least a consolidation of two or more of the graph items with at least a subset of the graph of nodes and edges, wherein clustering analysis considers a plurality of order consolidation possibilities; and

generating a multi-stop route schedule for a selected multi-stop route plan for execution on the transportation network.

20. The computer system of claim 19, the actions further comprising adding one or more orders to the selected multi-stop route plan, and wherein:

the possible routes comprise a starting point of a leg, at least one throughpoint and an ending point of a leg

the candidate options for performing stops over possible routes comprise a multi-leg itinerary

clustering analysis comprises analysis of a pickup timing constraint, a delivery timing constraint, and costs of the candidate options, and clustering analysis uses a network solver to observe least one of a pickup timing constraint, and a delivery timing constraint

the selection multi-stop route plan observes crossdock constraints comprising crossdock arrival constraints and a crossdock departure constraints, and the crossdock constraints corresponds to at least an order consolidation, and the selected multi-stop route plan corresponds to a source region and a destination region different from the source region and includes a land, sea, and air legs and satisfies the relaxed constraints, and generating relaxed constraints occurs before route generation, relaxing one or more constraints results in a penalty used in optimization, an identification of more nodes for routing and additional orders for routing.