Patent ID: 8630958

Claim:
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.