SYSTEMS AND METHODS FOR ROUTING AND SCHEDULING

• US 20060262967A1
• Filed: 05/09/2006
• Published: 11/23/2006
• Est. Priority Date: 05/09/2005
• Status: Active Grant

• Current Assignee: Roadnet Technologies (Solera Holdings Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Simon, Stephen Patrick, Kraisser, Clifton Brian, Hurst, Karl David
• Granted Patent: US 9,135,575 B2
• Time in Patent Office: Days
• US Class Current: 382/128
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• 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: G06T 11/206 Drawing of charts or graphs

Abstract

The present invention provides systems, methods and computer program-product for calculating and storing time and distance information in an economical and efficient manner. The time and distance information may be used in the development of traversable networks for the delivery and retrieval of items from multiple locations in a timely and efficient manner.

Claims

1. A computer program product for controlling a computing device having at least a memory, a processor and a display device, the computer program product is for calculating and storing shortest path information between two or more delivery locations, and comprises a computer-readable storage medium having computer-readable program code portions stored therein, said computer-readable program code portions comprising:

a first executable portion comprising a grid partitioning module that is executable on said processor, wherein said grid partitioning module divides an overall delivery region into multiples of a defined number of grids and said two or more delivery locations are located within at least one of said defined number of grids;

a second executable portion comprising an initial friend selection module that is executable on said processor, wherein one of said defined number of grids is selected and for each particular delivery location within said selected grid a friends list is created, said friends list is comprised of a set of delivery locations that are most likely to appear on the same route as said particular delivery location; and

a third executable portion comprising a super matrix creation module that is executable on said processor, wherein said super matrix creation module creates a traversable network comprised of nodes and arcs for the selected grid, calculates time/distance data from each delivery location within said selected grid to every node within the traversable network, and populates a super matrix containing time/distance data from each particular delivery location within the selected grid to each delivery location in that location'"'"'s friends list and any in-range depots.

2. The computer program product of claim 1, further comprising:

a fourth executable portion comprising a geo-balancing module that is executable on said processor, wherein said geo-balancing module balances each delivery location'"'"'s said friends list by selecting each delivery location, dividing the delivery region about the selected delivery location into four quadrants such that the selected delivery location forms an origin for the four quadrants and expanding an arc in each of the four quadrants equidistant from the origin to form a bounded substantially circular area about the origin until a defined number of delivery locations in said selected delivery location'"'"'s friends list are located within said bounded substantially circular area, determining the number of delivery locations in said selected delivery location'"'"'s friends list that are in each quadrant, and if said number of delivery locations in said selected delivery location'"'"'s friends list is less than a ((defined number of delivery locations in said selected delivery location'"'"'s friend list)/4) in any quadrant then marking such quadrant as a deficient quadrant and expanding the arc in any deficient quadrant until at least the ((defined number of delivery locations in said selected deliver location'"'"'s friend list)/4) delivery locations that are in the selected delivery location'"'"'s friends list are contained within the are bounded by the arc and axes forming the quadrant, or until a maximum distance from the origin is achieved.

3. The computer program of claim 2, wherein said ((defined number of delivery locations in said selected delivery location'"'"'s friend list)/4) is 625 and said maximum distance from the origin is 250 miles.

4. A system for delivering items to two or more delivery locations comprising:

a delivery vehicle capable of transporting one or more items for delivery at each of said two or more delivery locations, wherein said one or more items for delivery are obtained at a depot;

a computer program product for controlling a computing device having at least a memory, a processor and a display device, the computer program product is for calculating and storing shortest path information between said two or more delivery locations, and comprises a computer-readable storage medium having computer-readable program code portions stored therein, said computer-readable program code portions comprising;

a first executable portion comprising a grid partitioning module that is executable on said processor, wherein said grid partitioning module divides an overall delivery region into multiples of a defined number of grids and said two or more delivery locations are located within at least one of said defined number of grids;

a second executable portion comprising an initial friend selection module that is executable on said processor, wherein one of said defined number of grids is selected and for each particular delivery location within said selected grid a friends list is created, said friends list is comprised of a set of delivery locations that are most likely to appear on the same route as said particular delivery location; and

a third executable portion comprising a super matrix creation module that is executable on said processor, wherein said super matrix creation module creates a traversable network comprised of nodes and arcs for the selected grid, calculates time/distance data from each delivery location within said selected grid to every node within the traversable network, and populates a super matrix containing time/distance data from each particular delivery location within the selected grid to each delivery location in that location'"'"'s friends list and any in-range depots,

wherein said delivery vehicle utilizes said shortest path information in determining a route for obtaining said one or more items for delivery at each of said two or more delivery locations and transporting said one or more items for delivery at each of said two or more delivery locations to each delivery location.

5. The system of claim 4, wherein said computer program product is further comprised of:

a fourth executable portion comprising a geo-balancing module that is executable on said processor, wherein said geo-balancing module balances each delivery location'"'"'s said friends list by selecting each delivery location, dividing the delivery region about the selected delivery location into four quadrants such that the selected delivery location forms an origin for the four quadrants and expanding an arc in each of the four quadrants equidistant from the origin to form a bounded substantially circular area about the origin until a defined number of delivery locations in said selected delivery location'"'"'s friends list are located within said bounded substantially circular area, determining the number of delivery locations in said selected delivery location'"'"'s friends list that are in each quadrant, and if said number of delivery locations in said selected delivery location'"'"'s friends list is less than a ((defined number of delivery locations in said selected delivery location'"'"'s friend list)/4) in any quadrant then marking such quadrant as a deficient quadrant and expanding the arc in any deficient quadrant until at least the ((defined number of delivery locations in said selected deliver location'"'"'s friend list)/4) delivery locations that are in the selected delivery location'"'"'s friends list are contained within the are bounded by the arc and axes forming the quadrant, or until a maximum distance from the origin is achieved.

6. The system of claim 5, wherein said ((defined number of delivery locations in said selected delivery location'"'"'s friend list)/4) is 625 and said maximum distance from the origin is 250 miles.

7. A computer system for calculating and storing shortest path information between two or more potential delivery locations, wherein said computer system comprises:

a processor configured to;

(1) partition a delivery region into multiples of one or more discrete geographic areas, wherein each of the geographic areas includes a first set of one or more potential delivery locations;

(2) select a first geographic area;

(3) create a unique second set of potential delivery locations for each of said first set of one or more potential delivery locations;

(4) create a traversable network, wherein the traversable network comprises a set of nodes and arcs and further includes a set of two or more nodes comprising at least the potential delivery locations geographically located within the first geographic area and all potential delivery locations included within any of the unique second sets of potential delivery locations created at Step (3);

(5) calculate shortest path information from each of the potential delivery locations geographically located within the first geographic area to every node contained within the traversable network;

(6) select particular shortest path information and store the particular shortest path information for future lookup by a routing and scheduling system.

8. The system of claim 7, wherein the traversable network includes at least one node that corresponds to a depot.

9. The system of claim 7, wherein creating a unique second set of potential delivery locations for each potential delivery location geographically located within the first geographic area further comprises:

balancing the unique second set of potential delivery locations for each potential delivery location in said first set of one or more deliver locations by selecting each potential delivery location in said first set of one or more delivery locations, dividing the delivery region about the selected delivery location into four quadrants such that the selected delivery location forms an origin for the four quadrants and expanding an arc in each of the four quadrants equidistant from the origin to form a bounded substantially circular area about the origin until a defined number of second set of potential delivery locations for said selected delivery location are located within said bounded substantially circular area, determining the number of delivery locations in said selected delivery location'"'"'s second set of potential delivery locations that are in each quadrant, and if said number of delivery locations in said selected delivery location'"'"'s second set of potential delivery locations is less than a ((defined number of delivery locations in said selected deliver location'"'"'s second set of potential delivery locations)/4) in any quadrant marking such quadrant as a deficient quadrant, and expanding the arc in any deficient quadrant until at least the ((defined number of delivery locations in said selected deliver location'"'"'s second set of potential delivery locations)/4) delivery locations that are in the selected delivery location'"'"'s second set of potential delivery locations are contained within the area bounded by the arc and axes forming the quadrant or until a maximum distance from the origin is achieved.

10. The system of claim 9, wherein said ((defined number of delivery locations in said selected delivery location'"'"'s friend list)/4) is 625 and said maximum distance from the origin is 250 miles.

11. A computer system for calculating and storing shortest path information between two or more potential delivery locations, wherein said computer system comprises:

a processor configured to;

(1) create a unique set of potential delivery locations for each potential delivery location geographically located within a geographic area;

(2) create a traversable network uniquely associated with the geographic area, wherein the traversable network comprises a set of nodes and arcs and further includes a set of two or more nodes comprising at least the potential delivery locations geographically located within the geographic area and all potential delivery locations included within the unique set of potential delivery locations created at Step (1);

(3) calculate shortest path information from each of the potential delivery locations geographically located within the geographic area to every node contained within the traversable network;

(4) select particular shortest path information and store the selected particular shortest path information for future lookup by a routing and scheduling system.

12. The system of claim 11, wherein the traversable network includes at least one node that corresponds to a depot.

13. A method for calculating and storing shortest path information between two or more potential delivery locations comprising the steps of:

(A) partitioning a delivery region into multiples of one or more discrete geographic areas, wherein each of the geographic areas includes a first set of one or more potential delivery locations;

(B) electing a first geographic area;

(C) creating a corresponding unique second set of potential delivery locations for each potential delivery location geographically located within the selected geographic area;

(D) creating a traversable network, wherein the traversable network comprises a set of nodes and arcs and further includes a set of two or more nodes comprising at least the potential delivery location geographically located within the selected geographic area and all potential delivery locations included within the unique second set of potential delivery locations that correspond to the potential delivery locations geographically located within the selected geographic area;

(E) calculating shortest path information from the delivery location geographically located within the selected geographic area to every node contained within the traversable network;

(F) selecting particular shortest path information and storing the selected particular shortest path information for future lookup by a routing and scheduling system;

(G) repeating steps (D) through (F) for each potential delivery location geographically located within the selected geographic area; and

(H) repeating steps (B) through (G) for every geographic area created at step (A).

14. The method of claim 13, wherein creating a traversable network comprises creating a traversable network that includes at least one node that corresponds to a depot.

15. The method of claim 13, wherein creating a corresponding unique second set of potential delivery locations for each potential delivery location geographically located within the first geographic area further comprises balancing the unique second set of potential delivery locations for each potential delivery location geographically located within the first geographic area by selecting each potential delivery location in said first set of one or more delivery locations, dividing the delivery region about the selected delivery location into four quadrants such that the selected delivery location forms an origin for the four quadrants and expanding an arc in each of the four quadrants equidistant from the origin to form a bounded substantially circular area about the origin until a defined number of second set of potential delivery locations for said selected delivery location are located within said bounded substantially circular area, determining the number of delivery locations in said selected delivery location'"'"'s second set of potential delivery locations that are in each quadrant, and if said number of delivery locations in said selected delivery location'"'"'s second set of potential delivery locations is less than a ((defined number of delivery locations in said selected deliver location'"'"'s second set of potential delivery locations)/4) in any quadrant marking such quadrant as a deficient quadrant, and expanding the arc in any deficient quadrant until at least the ((defined number of delivery locations in said selected deliver location'"'"'s second set of potential delivery locations)/4) delivery locations that are in the selected delivery location'"'"'s second set of potential delivery locations are contained within the area bounded by the arc and axes forming the quadrant or until a maximum distance from the origin is achieved.

16. The method of claim 15, wherein said ((defined number of delivery locations in said selected delivery location'"'"'s friend list)/4) is 625 and said maximum distance from the origin is 250 miles.