Systems and methods for routing and scheduling visits to delivery locations

• US 9,135,575 B2
• Filed: 05/09/2006
• Issued: 09/15/2015
• Est. Priority Date: 05/09/2005
• Status: Active Grant

• Current Assignee: Roadnet Technologies (Solera Holdings Incorporated)
• Original Assignee: Roadnet Technologies (Solera Holdings Incorporated)
• Inventors: Simon, Stephen Patrick, Kraisser, Clifton Brian, Hurst, Karl David
• Primary Examiner(s): Miller, Alan
• Assistant Examiner(s): Anderson, Folashade
• Application Number:
  US11/382,405
• Publication Number:
  US 20060262967A1
• Time in Patent Office: 3,416 Days
• Field of Search: 705/7.14, 705/15, 705/338, 382/128, 701/209
• US Class Current: 1/1
• 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 system for delivering items to a set of delivery locations within a delivery region, the system comprising one or more memory storage areas and one or more processors, the system configured to:

partition, using the one or more processors, a delivery region into multiple rectangular geographic areas, wherein each of the geographic areas includes one or more delivery locations;

select a delivery location in a first geographic area of the multiple rectangular geographic areas, the selected delivery location being associated with a first list comprising closest delivery locations from the selected delivery location, at least some of said closest delivery locations being located in a second geographic area distinct from the first geographic area;

partition the delivery region into four discrete partitions in response to a size of the first list exceeding a maximum list size;

calculate, using the one or more processors, a preferred partition population size by dividing, using the one or more processors, the maximum list size by four;

geobalance the first list, wherein geobalancing includes at least one of;

removing, from the first list, a delivery location located in a partition with a size greater than the preferred partition population size, and

adding, to the first list, a delivery location located in a partition with a size less than the preferred partition population size;

create, using the one or more processors, a traversable network,

wherein the traversable network comprises a set of nodes and arcs,

wherein said set of nodes comprises the set of delivery locations including the delivery locations within the first geographic area and the delivery locations included within the geobalanced first list, said geobalanced first list containing at least one delivery location not contained in the first geographic area;

calculate shortest path information for the set of delivery locations from each of the delivery locations geographically located within the first geographic area to every node contained within the traversable network for future lookup by a routing and scheduling system; and

route a delivery vehicle using the shortest path information to each of the delivery locations, the system further comprising;

the delivery vehicle that obtains one or more items for delivery from a depot and transports, using the route, the one or more items for delivery to each delivery location.

2. The system of claim 1, wherein the traversable network includes at least one node that corresponds to the depot.

3. The system of claim 1, wherein said predetermined maximum list size is 2500.

4. The system of claim 1, wherein said system is further configured to:

generate the first list, said generating including the steps of;

select the delivery locations located within a predetermined distance from the selected delivery location;

organize the delivery locations based on distance to the selected delivery location;

wherein the first list is geobalanced based at least on the distance of the delivery locations in the first list to the selected delivery location.

5. The system of claim 1, wherein said system is further configured to:

route the at least one delivery vehicle to a delivery location not in the set of delivery locations by calculating shortest path information from one of the delivery locations in the set of delivery locations to the delivery location.

6. A method for delivering items to a set of delivery locations within a delivery region comprising the steps of:

(A) selecting, via one or more processors, a first rectangular geographic area;

(B) selecting a delivery location in the first rectangular geographic area, the selected delivery location being associated with a list that includes closest delivery locations located within a predetermined distance from the selected delivery location, at least some of said closest delivery locations being located in a second geographic area, said second geographic area surrounding the selected delivery location and including one or more rectangular geographic areas not contained in the first rectangular geographic area;

(C) dividing the first geographic area and the second geographic area into four geographic partitions in response to a population of the list exceeding a maximum list size;

(D) calculating a preferred partition population size by dividing the maximum list size by four;

(E) geobalancing the list, said geobalancing includes;

1) removing, from the list, a location located in a partition with a size greater than the preferred partition population size, and

2) adding, to the list, a location located in a partition with a size less than the preferred partition population size;

(F) repeating steps (B) through (E) for each delivery location geographically located within the first geographic area;

(G) creating a traversable network, wherein the traversable network comprises a set of nodes and arcs, the nodes comprising the set of delivery locations including the delivery locations within the first rectangular geographic area and the delivery locations included within the geobalanced list for all delivery locations contained in the first rectangular geographic area, the geobalanced list containing at least one delivery location not contained in the first rectangular geographic area;

(H) calculating, via the one or more processors, shortest path information from the delivery locations geographically located within the first geographic area to every node contained within the traversable network; and

(I) selecting, via the one or more processors, particular shortest path information for the set of the selected delivery locations and storing the selected particular shortest path information for future lookup by a routing and scheduling system;

(J) routing a delivery vehicle using the shortest path information to each of the delivery locations;

(K) obtaining one or more items for delivery from a depot; and

(L) transporting, by the delivery vehicle using the route, the one or more items for delivery to each delivery location.

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

8. The method of claim 6, wherein

said method further comprising the steps of:

generating the list, said generating including the steps of;

selecting all delivery locations located within a predetermined distance from the selected delivery location;

organizing the delivery locations based on distance to the selected delivery location;

wherein the list is geobalanced at step (E) based at least on the distance of the delivery locations in the list to the selected delivery location.

9. The method of claim 6, further comprising:

routing the at least one delivery vehicle to a delivery location not in the set of delivery locations by calculating shortest path information from one of the delivery locations of the set of delivery locations to the delivery location.