Method and system for efficiently dispatching service vehicles

• US 7,788,121 B1
• Filed: 04/28/2005
• Issued: 08/31/2010
• Est. Priority Date: 04/28/2004
• Status: Expired due to Fees

• Current Assignee: Dennis E. Smith, Martin Selbrede
• Original Assignee: Dennis E. Smith, Martin Selbrede
• Inventors: Smith, Dennis E, Selbrede, Martin
• Primary Examiner(s): DIXON, THOMAS A
• Application Number:
  US11/116,843
• Time in Patent Office: 1,951 Days
• Field of Search: 705/8, 705/9
• US Class Current: 705/7.26
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management

Abstract

A method for allocating articulated tasks to determinate resources such that enterprise efficiency is maximized. The method uses geographic parameters to perform a set of incrementally rotated reassessments using subtended angular offsets to optimally allocate tasks to resources, thereby rapidly approximating the results that would be obtained from a full permutation suite, but without the massive computational overhead associated with comprehensive permutation weighting. The method provides for proper handling of post-posited task insertions at optimal points within the parameter space, providing final determination authority to the system user. The parameter space can include temporal banding for resource-to-task association. The utility of the method for handling the core calculations of routing and dispatching software, such as is used in the many service industries, is transparent.

Claims

1. A computer-implemented method for scheduling a plurality of service vehicles from a selected origin point to a plurality of geographically dispersed tasks within a selected period of time by evaluating parametrically filtered assessments on a series of incrementally rotated optimization overlays, the method comprising:

identifying a candidate set of tasks to be scheduled, and, for each of the tasks in the candidate set, identifying a geographic position, and approximate required task duration;

identifying a set of constraints associated with each member of the candidate set of tasks to be scheduled;

determining the number of vehicles to be allocated to the tasks, and for each vehicle determining a vehicle task sequence by

determining a first trial schedule comprising a sequence for each vehicle by allocating the candidate set of tasks into a pie shape with slices radiating from the starting point, such that the number of slices is determined by the number of vehicles to be allocated,

for each slice

identifying a distal point task, while satisfying any imposed constraints, such that the distal point task is located at the extremity of the slice, such that the starting point and the distal point task define a central axis of the slice, establishing a vehicle task sequence, the initial vehicle task sequence comprising the starting point to distal point task back to starting point, identifying an intermediate task set comprising other tasks geographically located within a specified distance from the central axis of the slice, continuing to build the vehicle task sequence by sequentially selecting intermediate points from the intermediate task set, and inserting the selected points into the vehicle task sequence until a capacity limit for the vehicle is reached;

restricting eligibility for inclusion in the vehicle task sequence by comparative assessment against one or more parameters that serve to filter candidate tasks according to the parametric filtration thus implemented, thereby imposing the appropriate constraints on a task by task basis relative to each specific vehicle for which a sequence of tasks is being assembled;

determining at least one evaluation metric for the first trial schedule;

determining additional trial schedules by reallocating the candidate set of tasks by rotating the coordinate set centered on the origin point through an arbitrary angle, and determining at least one evaluation metric for each additional trial schedule; and

selecting a schedule from the set of trial schedules;

wherein said determining a vehicle task sequence, determining at least one evaluation metric, and determining additional trial schedules are performed by the computer.

2. The method of claim 1 wherein

the constraints comprise at least one of

the urgency of the task;

the complexity of the task;

preference of vehicle to be assigned to the task; and

time constraints for when the task must be conducted.

3. The method of claim 2 wherein

time constraints further comprise a set of time bands.

4. The method of claim 2 wherein

time constraints further comprise a two-band system distinguishing tasks requiring vehicle dispatch during a first time period, and tasks requiring vehicle dispatch during a second time period.

5. The method of claim 4 wherein

time constraints further comprise multiple-band systems that further constrain the dispatch time to shorter periods of available time during the day, such that the shorter periods of available time are shorter than the first time period and the second time period.

6. The method of claim 1 wherein identifying an intermediate task set comprising other tasks geographically located within a specified band distance from the central axis of the slice further comprises:

determining and utilizing the shortest of the distances determined by

the distance of a new intermediate task to any other given point within an existing task sequence,

and the tangential distance of a new intermediate task to a line drawn between any two consecutive tasks already existing in a task sequence, where such tangential distance is calculated by

calculating the line between the two consecutive existing tasks in a given vehicle task sequence,

drawing a line perpendicular to the line joining the two consecutive existing tasks, and

causing the perpendicular line to pass through the new intermediate task, and allowing the distance from the new task to the line joining the two consecutive existing tasks to be calculated algebraically.

7. The method of claim 1 wherein continuing to build the vehicle task sequence by sequentially selecting intermediate points from the intermediate task set, and inserting the selected points into the vehicle task sequence until a capacity limit for the vehicle is reached further comprises:

storing the vehicle task sequence;

changing a capacity constraint;

determining a modified vehicle task sequence; and

determining and reporting an incremental cost associated with the modified vehicle task sequence.

8. The method of claim 1 wherein continuing to build the vehicle task sequence by sequentially selecting intermediate points from the intermediate task set, and inserting the selected points into the vehicle task sequence until a capacity limit for the vehicle is reached further comprises:

storing the vehicle task sequence,

allowing a user to manually alter the vehicle task sequence, and determining and reporting an incremental cost associated with the manually modified vehicle task sequence.

9. The method of claim 1 wherein identifying a distal point task, while satisfying any imposed constraints further comprises:

imposing a two-band system.

10. The method of claim 9 wherein imposing a two-band system further comprises:

identifying the farthest distal point tasks in a first time band;

identifying the farthest distal point tasks in a second time band, such that the second time band is later than the first time band;

applying a proximity test to identify pairings between distal point tasks in the first and second time bands;

designating the closest of the identified pairings as explicitly consecutive tasks within a pie slice, temporally occurring at the transitional boundary between the two time bands, for the vehicle to be assigned to the slice.

11. The method of claim 1 wherein the distances computed between various points in the vehicle task sequence is determined by actual travel distances as extracted from third-party mapping software.

12. The method of claim 1 wherein establishing a vehicle task sequence, the initial vehicle task sequence comprising the starting point to distal point task back to starting point further comprises:

vehicles where the respective starting points do not match from vehicle to vehicle.

13. The method of claim 1 wherein establishing a vehicle task sequence, the initial vehicle task sequence comprising the starting point to distal point task back to starting point further comprises:

one or more vehicles where the vehicle does not return to the starting point, but to another selected point after the distal task is completed.