Enhanced Distance Calculation for Job Route Optimization

• US 20080235688A1
• Filed: 03/21/2007
• Published: 09/25/2008
• Est. Priority Date: 03/21/2007
• Status: Abandoned Application

• Current Assignee: Wireless Matrix USA Incorporated (CalAmp Corporation)
• Original Assignee: Sapias, Inc. (Wireless Matrix Corporation)
• Inventors: Panttaja, James T., Lange, Jonathan
• Application Number:
  US11/689,016
• Publication Number:
  US 20080235688A1
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration

Abstract

Systems and methods provide optimized distribution of jobs for execution among available workers. Categories are established for pairs of jobs based on a precise or estimated distance between each pair of jobs. Values are then assigned to the pairs of jobs and various decisions about job assignment and grouping can be made based upon the assigned value. The systems and methods allow certain job pairs to be excluded from consideration from grouping together, and emphasize which jobs are best suited for pairwise assignment, resulting in reduction of costs and necessary resources.

Claims

1. A method of optimizing job distribution, comprising:

receiving data representative of the set of jobs for execution, each job occurring at a geographic location within a geographic region;

receiving data corresponding to the geographic region, comprising data corresponding to each geographic location within the geographic region;

establishing a plurality of distance-based categories for characterizing pairs of jobs using the data corresponding to the geographic region, the pairs selected from the set of jobs for execution;

assigning a value, for each pair of jobs, based on a distance-based category corresponding to the pair; and

defining a job schedule grouping the jobs of the set for execution based upon the values assigned to the pairs of jobs and each geographic location, wherein each group comprises a list of jobs for serial execution.

2. The method of claim 1, wherein the distance-based categories are based upon absolute distances between jobs of each pair.

3. The method of claim 1, wherein the distance-based categories are based upon distances between geographical zones for the jobs in each pair.

4. The method of claim 1, wherein:

establishing a plurality of distance-based categories further comprises;

establishing a set of geographical zones for an area corresponding to the set of jobs;

assigning selected of the plurality of distance-based categories to each pair of zones; and

wherein establishing a value for each pair is based on the distance-based category assigned to each pair of zones.

5. The method of claim 4, wherein the set of geographical zones comprise borders selected to avoid geographical barriers between locations within each zone.

6. The method of claim 1, wherein establishing a plurality of distance-based categories further comprises:

calculating distances between each of the pairs of jobs;

assigning each pair one of the plurality of distance-based categories based upon the calculated distance; and

wherein establishing a value for each pair is based on the distance-based category assigned to each pair of zones.

7. The method of claim 1, wherein the value assigned to each pair is selected from the group consisting of a very high value, an estimated value, and a precise value.

8. The method of claim 7, wherein the very high value indicates that a selected pair of jobs are too far apart to be a part of a group.

9. The method of claim 7, wherein the estimated value indicates an approximate distance between a selected pair of jobs.

10. The method of claim 7, wherein the precise value indicates a turn-by-turn distance calculation between a selected pair of jobs.

11. The method of claim 1, wherein the distance-based categories comprise far, medium, and near.

12. The method of claim 11, wherein:

for pairs for which the distance-based category corresponding to the pair is far, the value assigned to each pair is a very high value;

for pairs for which the distance-based category corresponding to the pair is medium, the value assigned to each pair is an estimated value; and

for pairs for which the distance-based category corresponding to the pair is near, the value assigned to each pair is a precise value.

13. The method of claim 1, further comprising distributing the lists for execution.

14. The method of claim 1, wherein the plurality of distance-based categories are established taking into account one or more geographical barriers.

15. The method of claim 1, further comprising distributing the lists for execution.

16. A computer program product for optimizing job distribution, the computer program product comprising:

a computer-readable medium; and

computer program code, coded on the medium, for;

receiving data representative of the set of jobs for execution, each job occurring at a geographic location within a geographic region;

receiving data corresponding to the geographic region, comprising data corresponding to each geographic location within the geographic region;

establishing a plurality of distance-based categories for characterizing pairs of jobs using the data corresponding to the geographic region, the pairs selected from the set of jobs for execution;

assigning a value, for each pair of jobs, based on a distance-based category corresponding to the pair; and

defining a job schedule grouping the jobs of the set for execution based upon the values assigned to the pairs of jobs and each geographic location, wherein each group comprises a list of jobs for serial execution.

17. The computer program product of claim 16, wherein:

the computer program code coded on the medium for establishing a plurality of distance-based categories is further configured for;

establishing a set of geographical zones for an area corresponding to the set of jobs;

assigning selected of the plurality of distance-based categories to each pair of zones; and

wherein establishing a value for each pair is based on the distance-based category assigned to each pair of zones.

18. The computer program product of claim 17, wherein the set of geographical zones comprise borders selected to avoid geographical barriers between locations within each zone.

19. The computer program product of claim 16, wherein the computer program code coded on the medium for establishing a plurality of distance-based categories is further configured for:

calculating distances between each of the pairs of jobs;

assigning each pair one of the plurality of distance-based categories based upon the calculated distance; and

wherein establishing a value for each pair is based on the distance-based category assigned to each pair of zones.

20. The computer program product of claim 17, wherein:

for pairs for which the distance-based category corresponding to the pair is far, the value assigned to each pair is a very high value;

for pairs for which the distance-based category corresponding to the pair is medium, the value assigned to each pair is an estimated value; and

for pairs for which the distance-based category corresponding to the pair is near, the value assigned to each pair is a precise value.