Simultaneous vehicle routing, vehicle scheduling, and crew scheduling

• US 8,572,001 B2
• Filed: 04/08/2008
• Issued: 10/29/2013
• Est. Priority Date: 04/08/2008
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Hollis, Benjamin Leslie
• Primary Examiner(s): ZARE, SCOTT A
• Application Number:
  US12/099,327
• Publication Number:
  US 20090254405A1
• Time in Patent Office: 2,030 Days
• Field of Search: 705/7.25, 705/330, 705/337
• US Class Current: 705/337
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis

Abstract

A method for generating a transportation plan. A set of transportation requests are identified. An initial transportation plan having a set of vehicle routes, a set of vehicle schedules, and a set of crew schedules that satisfy the set of transportation requests is created. A set of vehicle routes, a set of vehicle schedules, and a set of crew schedules are simultaneously modified repeatedly using a policy to generate a new transportation plan until an objective is met.

Claims

1. A computer assisted method for generating a transportation plan, the method comprising:

identifying a set of transportation requests;

creating an initial transportation plan having a set of vehicle routes, a set of vehicle schedules, and a set of crew schedules that satisfy the set of transportation requests; and

simultaneously modifying on the computer the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules repeatedly using a policy to generate a new transportation plan until an objective is met, in which specific pairs of items are transported with a given pick-up and drop-off sequence within a shift for a crew schedule in the set of crew schedules, and wherein simultaneously modifying further comprises;

determining whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet a threshold for an objective for the transportation plan;

responsive to a determination that the threshold is unmet, determining whether any simplifying feature is still present in a dynamic programming algorithm;

responsive to removing a simplifying feature from the dynamic programming algorithm after a determination that the threshold is unmet, determining whether all simplifying features of the dynamic programming algorithm have been removed;

responsive to a determination that the all simplifying features have not been removed, sequentially performing random greedy enumeration, performing breadth first best only enumeration, calling the dynamic programming algorithm, performing explicit vehicle substitution, and performing least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules;

responsive to a determination that the all simplifying features have been removed, sequentially calling the dynamic programming algorithm, performing the explicit vehicle substitution, and performing the least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules to form the new transportation plan;

solving a linear program problem for the new transportation plan using the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules; and

repeating the step of determining whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet the threshold for the objective for the transportation plan, the new transportation plan resulting from solving the linear programming problem for the new transportation plan.

2. The method of claim 1 further comprising:

pruning the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules in the new transportation plan based on an identified reduced cost.

3. The method of claim 1 further comprising:

modifying the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules to minimize a number of vehicles used.

4. The method of claim 1, wherein the simultaneously modifying step comprises:

simultaneously modifying the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules repeatedly using the policy to generate the new transportation plan until the objective is met for a set of vehicle types selected from at least one of trucks, trains, aircraft, and ships.

5. The method of claim 1, wherein the simultaneously modifying step further comprises:

responsive to a determination that the threshold is met, determining whether all of the simplifying features of the dynamic programming algorithm have been removed;

responsive to a determination that all of the simplifying features of the dynamic programming algorithm have been removed, performing shipment sequence fixing;

determining whether a suitable fix is found by performing the shipment sequence fixing;

responsive to a determination that the suitable fix is found, solving a linear integer mathematical formulation for a planning problem to form the transportation plan;

responsive to a determination that the suitable fix is absent, determining whether the any simplifying features are still present in the dynamic programming algorithm;

responsive to a determination that the any simplifying features are present in the dynamic programming algorithm;

repeating the step of sequentially performing the random greedy enumeration, performing the breadth first best only enumeration, calling the dynamic programming algorithm, performing the explicit vehicle substitution, and performing the least cost insertion on the vehicle routes, the set of vehicle schedules, and the set of crew schedules; and

responsive to a determination that the any the simplifying features are absent in the dynamic programming algorithm, repeating the step of sequentially calling the dynamic programming algorithm, performing the explicit vehicle substitution, and performing the least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules.

6. The method of claim 1, further comprising:

determining whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet a threshold for an objective for the transportation;

determining whether any simplifying feature is still present in a dynamic programming algorithm in response to a determination that the threshold is unmet; and

determining whether all simplifying features of the dynamic programming algorithm have been removed in response to removing a simplifying feature from the dynamic programming algorithm after a determination that the threshold is unmet.

7. The method of claim 6, further comprising:

sequentially performing random greedy enumeration, perform breadth first best only enumeration, call the dynamic programming algorithm, perform explicit vehicle substitution, and perform least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules in response to a determination that the all simplifying features have not been removed; and

sequentially calling the dynamic programming algorithm, perform the explicit vehicle substitution, and perform the least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules to form the new transportation plan in response to determination that all simplifying features have been removed.

8. The method of claim 7, further comprising:

solving a linear program problem for the new transportation plan using the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules; and

repeating the execution of the computer usable program code to determine whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet the threshold for the objective for the transportation plan, the new transportation plan resulting from solving the linear programming problem for the new transportation plan.

9. A computer implemented method for creating a transportation plan, the computer implemented method comprising:

identifying data relating to vehicle routing, vehicle scheduling, and crew scheduling to form input data; and

simultaneously identifying a set of vehicle routes, a set of vehicle schedules, and a set of crew schedules using the input data, the set of vehicle schedules corresponding to at least a first vehicle and a second vehicle, the first vehicle and the second vehicle being different vehicle types, wherein the simultaneously identifying step comprises;

identifying an initial transportation plan comprising the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules;

changing values in the initial transportation plan to optimize an objective to form a subsequent transportation plan; and

iteratively changing prior values in the initial transportation plan to optimize the objective to form the subsequent transportation plan until a threshold is reached for the objective to form the transportation plan, wherein iteratively changing prior values further comprises;

determining whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet the threshold for an objective for the transportation plan;

responsive to a determination that the threshold is unmet, determining whether any simplifying feature is still present in a dynamic programming algorithm;

responsive to removing a simplifying feature from the dynamic programming algorithm after a determination that the threshold is unmet, determining whether all simplifying features of the dynamic programming algorithm have been removed;

responsive to a determination that the all simplifying features have not been removed, sequentially performing random greedy enumeration, performing breadth first best only enumeration, calling the dynamic programming algorithm, performing explicit vehicle substitution, and performing least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules;

responsive to a determination that the all simplifying features have been removed, sequentially calling the dynamic programming algorithm, performing the explicit vehicle substitution, and performing the least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules to form the new transportation plan;

solving a linear program problem for the new transportation plan using the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules; and

repeating the step of determining whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet the threshold for the objective for the transportation plan, the new transportation plan resulting from solving the linear programming problem for the new transportation plan.

10. A data processing system comprising:

a bus;

a communications unit connected to the bus;

a storage device connected to the bus, wherein the storage device includes computer usable program code; and

a processor unit connected to the bus, wherein the processor unit executes the computer usable program code to identify a set of transportation requests;

create an initial transportation plan having a set of vehicle routes, a set of vehicle schedules, and a set of crew schedules that satisfy the set of transportation requests, and simultaneously modify the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules repeatedly using a policy to generate a new transportation plan until an objective is met, in which specific pairs of items are transported with a given pick-up and drop-off sequence within a shift for a crew schedule in the set of crew schedules, wherein in executing the computer usable program code to simultaneously modify the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules repeatedly using the policy to generate the new transportation plan until the objective is met, the processor unit executes the computer usable program code to determine whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet a threshold for an objective for the transportation;

determine whether any simplifying feature is still present in a dynamic programming algorithm in response to a determination that the threshold is unmet;

determine whether all simplifying features of the dynamic programming algorithm have been removed in response to removing a simplifying feature from the dynamic programming algorithm after a determination that the threshold is unmet;

sequentially perform random greedy enumeration, perform breadth first best only enumeration, call the dynamic programming algorithm, perform explicit vehicle substitution, and perform least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules in response to a determination that the all simplifying features have not been removed;

sequentially call the dynamic programming algorithm, perform the explicit vehicle substitution, and perform the least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules to form the new transportation plan in response to determination that all simplifying features have been removed;

solve a linear program problem for the new transportation plan using the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules; and

repeat the execution of the computer usable program code to determine whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet the threshold for the objective for the transportation plan, the new transportation plan resulting from solving the linear programming problem for the new transportation plan.

11. The data processing system of claim 10, wherein the processor unit further executes the computer usable program code to prune the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules in the new transportation plan based on an identified reduced cost.

12. The data processing system of claim 10, wherein the processor unit further executes the computer usable program code to modify the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules to minimize a number of vehicles used.

13. The data processing system of claim 10, wherein in executing the computer usable program code to simultaneously modify the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules repeatedly using the policy to generate the new transportation plan until the objective is met, the processor unit executes the computer usable program code to simultaneously modify the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules repeatedly using the policy to generate the new transportation plan until the objective is met for a set of vehicle types selected from at least one of trucks, trains, aircraft, and ships.

14. The data processing system of claim 10, wherein in executing the computer usable program code to simultaneously modify the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules repeatedly using the policy to generate the new transportation plan until the objective is met, wherein the processor unit further executes the computer usable program code to determine whether all of the simplifying features of the dynamic programming algorithm have been removed in response to a determination that the threshold is met;

performing shipment sequence fixing in response to a determination that all of the simplifying features of the dynamic programming algorithm have been removed;

determine whether a suitable fix is found by performing the shipment sequence fixing;

solve a linear integer mathematical formulation for a planning problem to form the transportation plan in response to a determination that the suitable fix is found;

determine whether the any simplifying features are still present in the dynamic programming algorithm in response to a determination that the suitable fix is absent;

responsive to a determination that the any simplifying features are present in the dynamic programming algorithm, repeat the execution of the computer usable program code to sequentially perform the random greedy enumeration, perform the breadth first best only enumeration, call the dynamic programming algorithm, perform the explicit vehicle substitution, and perform the least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules in response to a determination that the any simplifying features are present;

repeat execution of the computer usable program code to sequentially call the step of sequentially performing the random greedy enumeration; and

responsive to a determination that any the simplifying features are absent in the dynamic programming algorithm, perform the explicit vehicle substitution, perform the explicit vehicle substitution, and perform the least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules in response to a determination that the any simplifying features are absent in the dynamic programming algorithm.

15. A computer program product for generating a transportation plan, the computer program product comprising:

a non-transitory computer readable medium;

program code, stored on the computer readable medium, for identifying a set of transportation requests;

program code, stored on the computer readable medium, for creating an initial transportation plan having a set of vehicle routes, a set of vehicle schedules, and a set of crew schedules that satisfy the set of transportation requests, the set of vehicle schedules corresponding to at least a first vehicle and a second vehicle, the first vehicle and the second vehicle being different vehicle types; and

program code, stored on the computer readable medium, for simultaneously modifying the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules repeatedly using a policy to generate a new transportation plan until an objective is met, in which specific pairs of items are transported with a given pick-up and drop-off sequence within a shift for a crew schedule in the set of crew schedules and in which a crew member changes between a first vehicle and a second vehicle during a shift for the crew member, wherein the first vehicle is of a different type from the second vehicle, and wherein simultaneously modifying further comprises;

determining whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet a threshold for an objective for the transportation plan;

responsive to a determination that the threshold is unmet, determining whether any simplifying feature is still present in a dynamic programming algorithm;

responsive to removing a simplifying feature from the dynamic programming algorithm after a determination that the threshold is unmet, determining whether all simplifying features of the dynamic programming algorithm have been removed;

responsive to a determination that the all simplifying features have not been removed, sequentially performing random greedy enumeration, performing breadth first best only enumeration, calling the dynamic programming algorithm, performing explicit vehicle substitution, and performing least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules;

responsive to a determination that the all simplifying features have been removed, sequentially calling the dynamic programming algorithm, performing the explicit vehicle substitution, and performing the least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules to form the new transportation plan;

solving a linear program problem for the new transportation plan using the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules; and

repeating the step of determining whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet the threshold for the objective for the transportation plan, the new transportation plan resulting from solving the linear programming problem for the new transportation plan.

16. The computer program product of claim 15, wherein the program code, stored on the computer readable medium, for simultaneously modifying the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules repeatedly using the policy to generate the new transportation plan until the objective is met comprises:

program code, stored on the computer readable medium, for simultaneously modifying the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules repeatedly using the policy to generate the new transportation plan until the objective is met in which a crew member changes between a first vehicle and a second vehicle during a shift for the crew member, wherein the first vehicle is of a different type from the second vehicle.

17. A data processing system comprising:

a bus;

a communications unit connected to the bus;

a storage device connected to the bus, wherein the storage device includes program code; and

a processor unit connected to the bus, wherein the processor unit executes the program code to identify data relating to vehicle routing, vehicle scheduling, and crew scheduling to form input data; and

simultaneously identify a set of vehicle routes, a set of vehicle schedules, and a set of crew schedules using the input data, the set of vehicle schedules corresponding to at least a first vehicle and a second vehicle, the first vehicle and the second vehicle being different vehicle types, using a policy to generate a new transportation plan until an objective is met, in which specific pairs of items are transported with a given pick-up and drop-off sequence within a shift for a crew schedule in the set of crew schedules and in which a crew member changes between a first vehicle and a second vehicle during a shift for the crew member, wherein the first vehicle is of a different type from the second vehicle, and wherein the processor unit further executes the processor code to;

determine whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet a threshold for an objective for the transportation plan;

responsive to a determination that the threshold is unmet, determine whether any simplifying feature is still present in a dynamic programming algorithm;

responsive to removing a simplifying feature from the dynamic programming algorithm after a determination that the threshold is unmet, determine whether all simplifying features of the dynamic programming algorithm have been removed;

responsive to a determination that the all simplifying features have not been removed, sequentially perform random greedy enumeration, perform breadth first best only enumeration, call the dynamic programming algorithm, perform explicit vehicle substitution, and perform least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules;

responsive to a determination that the all simplifying features have been removed, sequentially call the dynamic programming algorithm, perform the explicit vehicle substitution, and perform the least cost insertion on the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules to form the new transportation plan;

solve a linear program problem for the new transportation plan using the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules; and

repeat the step of determining whether the set of vehicle routes, the set of vehicle schedules, and the set of crew schedules meet the threshold for the objective for the transportation plan, the new transportation plan resulting from solving the linear programming problem for the new transportation plan.