Systems and methods for multi-vehicle resource allocation and routing solutions
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
36 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. - View Dependent Claims (2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
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. - View Dependent Claims (4, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
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. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
Specification