Systems and Methods for Multi-Vehicle Resource Allocation and Routing Solutions

• US 20120310691A1
• Filed: 06/03/2011
• Published: 12/06/2012
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Cardinal Optimization, Inc.
• Original Assignee: Cardinal Optimization, Inc.
• Inventors: Ye, Yinyu, Carlsson, John Gunnar, Jin, Holly
• Granted Patent: US 8,630,958 B2
• Time in Patent Office: Days
• US Class Current: 705/7.13
• 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 servicing objects within a map of a region such that work load is balanced across the plurality of servicing objects, 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 instructions that are executed by at least one of the one or more processing units, the instructions comprising instructions for;

(A) formulating a model for allocating and routing the plurality of servicing objects in the 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 each sub-region in the plurality of sub-regions, wherein, 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; and

(D) outputting at least one sub-region in the plurality of sub-regions and, for each respective sub-region outputted, outputting the tour graph corresponding to the respective sub-region.

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.

3. The computer system of claim 1, wherein the model is a segment only model and wherein the distance matrix is based upon the first plurality of segments.

4. The computer system of claim 1, wherein the model is an intersection only model and wherein the distance matrix is based upon the second plurality of intersections.

5. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism for allocating and routing a plurality of servicing objects within a region such that work load is balanced across the plurality of servicing objects, the computer program mechanism comprising computer executable instructions for:

(A) formulating a model for allocating and routing the plurality of servicing objects in the 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 each sub-region in the plurality of sub-regions, wherein, 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; and

(D) outputting at least one sub-region in the plurality of sub-regions and, for each respective sub-region outputted, outputting the tour graph corresponding to the respective sub-region.