Systems and methods for multi-vehicle resource allocation and routing solutions

• US 8,630,958 B2
• Filed: 06/03/2011
• Issued: 01/14/2014
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Cardinal Optimization, Inc.
• Original Assignee: Cardinal Optimization, Inc.
• Inventors: Carlsson, John Gunnar, Jin, Holly, Ye, Yinyu
• Primary Examiner(s): MEINECKE DIAZ, SUSANNA M
• Application Number:
  US13/153,208
• Publication Number:
  US 20120310691A1
• Time in Patent Office: 956 Days
• Field of Search: 705/338
• US Class Current: 705/338
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching

Abstract

A computer system for allocating and routing a plurality of servicing objects within a map of a region such that work load is balanced across the plurality of servicing objects is provided. The system formulates a model for allocating and routing the plurality of servicing objects in the region. The model comprises a distance matrix based upon a first plurality of segments or a second plurality of intersections in the map. The memory stores instructions for partitioning the map into a plurality of disjoint contiguous sub-regions in view of the distance matrix using an equitable convex region partition algorithm. The memory further stores instructions for calculating a corresponding tour graph for each sub-region in the plurality of sub-regions, where, for each respective sub-region in the plurality of sub-regions, a servicing object in the plurality of servicing objects is assigned to the tour graph that corresponds to the respective sub-region.

Claims

1. A computer system for allocating and routing a plurality of vehicles within a map of a geographic region such that work load is balanced across the plurality of vehicles, the computer system comprising:

one or more processing units;

a memory, coupled to at least one of the one or more processing units, the memory storing one or more programs that are executed by at least one of the one or more processing units, the one or more programs comprising instructions for determining a route plan for each vehicle of the plurality of vehicles, by;

(A) formulating a model for allocating and routing the plurality of vehicles in the geographic region, wherein the model comprises a distance matrix based upon a first plurality of segments or a second plurality of intersections in the map;

(B) partitioning the map into a plurality of disjoint contiguous sub-regions in view of the distance matrix using an equitable convex region partition algorithm;

(C) calculating a corresponding tour graph for two or more respective sub-regions in the plurality of sub-regions, wherein, for each of the two or more respective sub-regions in the plurality of sub-regions, a vehicle in the plurality of vehicles is assigned to the tour graph that corresponds to the respective sub-region; and

(D) outputting route plans for two or more of vehicles the plurality of vehicles, each output route plan specifying a route to be traversed by a corresponding vehicle in accordance with the tour graph calculated for at least one sub-region in the plurality of sub-regions.

2. The computer system of claim 1, wherein the model is a segment plus intersection model and wherein the distance matrix is based upon the first plurality of segments and the second plurality of intersections.

5. The computer system of claim 1, wherein the (C) calculating the corresponding tour graph for two or more respective sub-regions in the plurality of sub-regions includes:

calculating the corresponding tour graph for each of the two or more respective sub-regions in the plurality of sub-regions in accordance with at least one factor selected from the group consisting of;

(i) a direction associated with a segment in the plurality of segments;

(ii) a priority associated with the segment;

(iii) one or more characteristic associated with a particular lane in a plurality of lanes associated with the segment;

(iv) a speed limit associated with the segment;

(v) a road condition associated with the segment; and

(vi) an occurrence of an-unplanned event associated with the segment.

6. The computer system of claim 1, wherein the at least one sub-region is associated with a first client destination and a second client destination, and the tour graph corresponding to the at least one sub-region is calculated in accordance with at least one of:

(i) time associated with travelling between the first client destination and the second client destination;

(ii) fuel expenditure associated with travelling between the first client destination and the second client destination;

(iii) a service time constraint associated with the first client destination; and

(iv) time associated with performing a service at the first client destination.

7. The computer system of claim 1, wherein a vehicle in the plurality of vehicles corresponds to a street-scanning vehicle.

8. The computer system of claim 1, wherein a vehicle in the plurality of vehicles corresponds to a delivery vehicle.

9. The computer system of claim 1, wherein a vehicle in the plurality of vehicles corresponds to a pick-up vehicle.

10. The computer system of claim 1, wherein each segment in the plurality of segments corresponds to a street travelable by a vehicle, and each intersection in the plurality of sections corresponds to a street intersection reachable by a vehicle.

11. The computer system of claim 1, wherein the one or more programs further comprise instructions for:

in response to occurrence of a predefined event,

(E) calculating an updated tour graph for a first sub-region in the plurality of sub-regions, in accordance with the predefined event; and

(F) outputting an updated route plan, specifying an updated route to be traversed by a respective vehicle, the updated route plan corresponding to the updated tour graph for the first sub-region.

12. The computer system of claim 11, wherein the predefined event is an event occurs at real time.

13. The computer system of claim 1, wherein at least one tour graph includes a portion of, but less than all, segments included in the corresponding sub-region.

14. The computer system of claim 1, wherein at least one tour graph includes all segments included in the corresponding sub-region.

3. A computer program product for use in conjunction with a computer system, the computer program product comprising a non-transitory computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism for allocating and routing a plurality of vehicles within a geographic region such that work load is balanced across the plurality of vehicles, the computer program mechanism comprising computer executable instructions for determining a route plan for each vehicle of the plurality of vehicles, by:

(A) formulating a model for allocating and routing the plurality of vehicles in the geographic region, wherein the model comprises a distance matrix based upon a first plurality of segments or a second plurality of intersections in the map;

(B) partitioning the map into a plurality of disjoint contiguous sub-regions in view of the distance matrix using an equitable convex region partition algorithm;

(C) calculating a corresponding tour graph for two or more respective sub-regions in the plurality of sub-regions, wherein, for each of the two or more respective sub-regions in the plurality of sub-regions, a vehicle in the plurality of vehicles is assigned to the tour graph that corresponds to the respective sub-region; and

(D) outputting route plans for two or more of the vehicles in the plurality of vehicles, each output route plan specifying a route to be traversed by a corresponding vehicle in accordance with the tour graph calculated for at least one sub-region in the plurality of sub-regions.

4. The computer program product of claim 3, wherein the model is a segment plus intersection model and wherein the distance matrix is based upon the first plurality of segments and the second plurality of intersections.

15. The computer program product of claim 3, wherein the instructions for (C) calculating the corresponding tour graph for two or more respective sub-regions in the plurality of sub-regions include instructions for:

calculating the corresponding tour graph for two or more respective sub-regions in the plurality of sub-regions in accordance with at least one factor selected from one of;

(i) a direction associated with a segment in the plurality of segments;

(ii) a priority associated with the segment;

(iii) one or more characteristic associated with a particular lane in a plurality of lanes associated with the segment;

(iv) a speed limit associated with the segment;

(v) a road condition associated with the segment; and

(vi) an occurrence of an-unplanned event associated with the segment.

16. The computer program product of claim 3, wherein the at least one sub-region is associated with a first client destination and a second client destination, and the tour graph corresponding to the at least one sub-region is calculated in accordance with at least one of:

(i) time associated with travelling between the first client destination and the second client destination;

(ii) fuel expenditure associated with travelling between the first client destination and the second client destination;

(iii) a service time constraint associated with the first client destination; and

(iv) time associated with performing a service at the first client destination.

17. The computer program product of claim 3, wherein a vehicle in the plurality of vehicles corresponds to a street-scanning vehicle.

18. The computer program product of claim 3, wherein a vehicle in the plurality of vehicles corresponds to a delivery vehicle.

19. The computer program product of claim 3, wherein a vehicle in the plurality of vehicles corresponds to a pick-up vehicle.

20. The computer program product of claim 3, wherein each segment in the plurality of segments corresponds to a street travelable by a vehicle, and each intersection in the plurality of sections corresponds to a street intersection reachable by a vehicle.

21. The computer program product of claim 3, wherein the one or more programs further comprises instructions for:

in response to occurrence of a predefined event,

(E) calculating an updated tour graph for a first sub-region in the plurality of sub-regions, in accordance with the predefined event; and

(F) outputting an updated route plan, specifying an updated route to be traversed by a respective vehicle, the updated route plan corresponding to the updated tour graph for the first sub-region.

22. The computer program product of claim 21, wherein the predefined event is an event that occurs at real time.

23. The computer program product of claim 3, wherein at least one tour graph includes a portion of, but less than all, segments included in the corresponding sub-region.

24. The computer program product of claim 3, wherein at least one tour graph includes all segments included in the corresponding sub-region.

25. A computer-implemented method for allocating and routing a plurality of vehicles within a map of a geographic region such that work load is balanced across the plurality of vehicles, the method comprising:

at a computing system having at least one processor,

determining a route plan for each vehicle of the plurality of vehicles, by;

(A) formulating a model for allocating and routing the plurality of vehicles in the geographic region, wherein the model comprises a distance matrix based upon a first plurality of segments or a second plurality of intersections in the map;

(B) partitioning the map into a plurality of disjoint contiguous sub-regions in view of the distance matrix using an equitable convex region partition algorithm;

(C) calculating a corresponding tour graph for two or more respective sub-regions in the plurality of sub-regions, wherein, for each of the two or more respective sub-regions in the plurality of sub-regions, a vehicle in the plurality of vehicles is assigned to the tour graph that corresponds to the respective sub-region; and

(D) outputting route plans for two or more of vehicles of the plurality of vehicles, each output route plan specifying a route to be traversed by a corresponding vehicle in accordance with the tour graph calculated for at least one sub-region in the plurality of vehicles.

26. The computer-implemented method of claim 25, wherein the model is a segment plus intersection model and wherein the distance matrix is based upon the first plurality of segments and the second plurality of intersections.

27. The computer-implemented method of claim 25, wherein the (C) calculating the corresponding tour graph for two or more respective sub-regions in the plurality of sub-regions include instruction for:

calculating the corresponding tour graph for each of the two or more respective sub-regions in the plurality of sub-regions in accordance with at least one factor selected from one of;

(i) a direction associated with a segment in the plurality of segments;

(ii) a priority associated with the segment;

(iii) one or more characteristic associated with a particular lane in a plurality of lanes associated with the segment;

(iv) a speed limit associated with the segment;

(v) a road condition associated with the segment; and

(vi) an occurrence of an-unplanned event associated with the segment.

28. The computer-implemented method of claim 25, wherein the at least one sub-region is associated with a first client destination and a second client destination, and the tour graph corresponding to the at least one sub-region is calculated in accordance with at least one of:

(i) time associated with travelling between the first client destination and the second client destination;

(ii) fuel expenditure associated with travelling between the first client destination and the second client destination;

(iii) a service time constraint associated with the first client destination; and

(iv) time associated with performing a service at the first client destination.

29. The computer-implemented method of claim 25, wherein a vehicle in the plurality of vehicles corresponds to a street-scanning vehicle.

30. The computer-implemented method of claim 25, wherein a vehicle in the plurality of vehicles corresponds to a delivery vehicle.

31. The computer-implemented method of claim 25, wherein a vehicle in the plurality of vehicles corresponds to a pick-up vehicle.

32. The computer-implemented method of claim 25, wherein each segment in the plurality of segments corresponds to a street travelable by a vehicle, and each intersection in the plurality of sections corresponds to a street intersection reachable by a vehicle.

33. The computer-implemented method of claim 25, wherein the one or more programs further comprising instructions for:

in response to occurrence of a predefined event,

(E) calculating an updated tour graph for a first sub-region in the plurality of sub-regions, in accordance with the predefined event; and

(F) outputting an updated route plan, specifying an updated route to be traversed by a respective vehicle, the updated route plan corresponding to the updated tour graph for the first sub-region.

34. The computer-implemented method of claim 33, wherein the predefined event is an event occurs at real time.

35. The computer-implemented method of claim 25, wherein at least one tour graph includes a portion of, but less than all, segments included in the corresponding sub-region.

36. The computer-implemented method of claim 25, wherein at least one tour graph include all segments included in the corresponding sub-region.