METHOD AND SYSTEM FOR IMPROVING ROUTE ASSIGNMENT PERFORMANCE

1 . A computer implemented method for improving route assignment performance, comprising:

in a processor of the computer:

providing a route data structure by using column generation with a labeling algorithm, the route data structure having one or more route vectors (RV 1 1 to RVn m ) representing a set of route options for a plurality of available resources to fulfill a plurality of job orders at respective physical locations, each route option being associated with route specific cost wherein a specified job order location on a route is represented by a corresponding route vector element of a respective route vector;

solving a linear program in compliance with a termination parameter to obtain a route assignment solution for the set of route options in the route data structure for the available resources wherein each solution variable (α 1 1 to α n m ) of the solution relates to a respective route option;

if the solution is non-fractional, then providing the solution as the route assignment solution for the set of route options;

if the solution is fractional, then identifying route options having solution variables with a non-fractional route-is-assigned value as assigned routes, rounding a subset of the fractional solution variables to the route-is-assigned value, and repeating the solving and rounding steps until the solution is non-fractional; and

outputting the solution in a graphical format.

2 . The computer implemented method of claim 1 , wherein rounding further comprises:

selecting as a subset of the fractional solution variables, said solution variables having a value within a predefined distance to the route-is-assigned value.

3 . The computer implemented method of claim 1 , wherein rounding further comprises:

selecting as a subset of the fractional solution variables a percentage of the fractional variables being closest to the route-is-assigned value.

4 . The computer implemented method of claim 1 , wherein identifying assigned routes includes storing the assigned routes.

5 . The computer implemented method of claim 1 , wherein providing a route data structure further comprises:

providing a net data structure having a plurality of nodes wherein pairs of nodes are connected through connections, each node corresponding to a real world physical location of a potential job order and a specified connection corresponding to a real world connection between two respective physical locations wherein the specified connection has one or more physical constraint parameters reflecting physical constraints for moving a resource between the two respective physical locations;

initializing the route data structure;

computing the one or more vectors for the plurality of available resources as a solution of a resource constraint shortest path problem by applying column generation with the labeling algorithm to the net data structure based on start locations of the available resources and a list of available job orders at respective nodes; and

adding the one or more computed vectors to the route data structure as additional route options for the available resources.

6 . The computer implemented method of claim 5 , wherein the specified connection is a directed arc and the one or more physical constraint parameters reflect physical constraints for moving a resource from the first to the second node.

7 . The computer implemented method of claim 5 , wherein the termination parameter is a time-out parameter and a termination condition for the solving step is met when the elapsed solving computation time exceeds a time interval specified by the time-out parameter.

8 . The computer implemented method of claim 5 , wherein the termination parameter is an optimality gap and a termination condition for solving is met when the difference between the current lower and upper bound falls below a specified value.

9 . The computer implemented method of claim 5 , wherein the termination parameter is a memory-out parameter and the termination condition for solving is met when the memory consumption for solving exceeds a memory allocation specified by the memory-out parameter.

10 . A computer program product including a computer program stored on a non-transitory computer readable medium that when the computer program is loaded into a memory of a computing device and executed by at least one processor of the computing device executes the steps of the computer implemented method according to claim 1 .

11 . A computer system for improving route assignment performance, comprising:

data storage means configured to store a route data structure, the route data structure being generated by column generation with labeling component and having one or more route vectors representing a set of route options for a plurality of available resources to fulfill a plurality of job orders at respective physical locations, each route option being associated with route specific cost wherein a specified job order location on a route is represented by a corresponding route vector element of a respective route vector;

a linear program solver component configured to solve a linear program to obtain a route assignment solution for the set of route options in the route data structure for the available resources in compliance with a termination parameter wherein each solution variable of the solution relates to a respective route option; and

an assigned route identifier configured:

to provide the solution as the route assignment solution for the set of route options if the solution is non-fractional,

if the solution is fractional, to identify route options having solution variables with a non-fractional route-is-assigned value as assigned routes, and to round a subset of the fractional solution variables to the route-is-assigned value, and to call the linear program solver component with the rounded subset until the solution becomes non-fractional; and

outputting the solution in a graphical format.

12 . The computer system of claim 11 , wherein the assigned route identifier is further configured to select as the subset of the fractional solution variables such variables having a value within a predefined distance to the route-is-assigned value.

13 . The computer system of claim 11 , wherein the assigned route identifier is further configured to select as the subset of the fractional solution variables a percentage of the fractional variables being closest to the route-is-assigned value.

14 . The computer system of claim 11 , wherein the assigned route identifier initiates storage of identified assigned routes in an assigned routes data structure.

15 . The computer system of claim 11 , wherein:

the data storage means is further configured to store a net data structure having a plurality of nodes wherein pairs of nodes are connected through connections, each node corresponding to a real world physical location of a potential job order and a specified connection corresponding to a real world connection between two respective physical locations wherein the specified connection has one or more physical constraint parameters reflecting physical constraints for moving a resource between the two respective physical locations,

the column generation with a labeling component configured to:

initialize the route data structure;

compute the one or more vectors for the plurality of available resources as a solution of a resource constraint shortest path problem by applying column generation with labeling to the net data structure based on start locations of the available resources and a list of available job orders at respective nodes; and

add the one or more computed vectors to the route data structure as additional route options for the available resources.