Routing shipments according to criticality

• US 20030060924A1
• Filed: 09/24/2001
• Published: 03/27/2003
• Est. Priority Date: 09/24/2001
• Status: Active Grant

• Current Assignee: Blue Yonder Group, Inc. (Panasonic Holdings Corporation)
• Original Assignee: i2 Technologies US Incorporated (Panasonic Holdings Corporation)
• Inventors: Ye, Jian, Leih, Todd Christopher, Szabady, Roy J., Lu, Pei
• Granted Patent: US 6,980,885 B2
• Time in Patent Office: Days
• US Class Current: 700/217
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A computer-implemented method for routing shipments according to criticality includes accessing an initial solution to an optimization problem of routing multiple shipments to multiple locations using multiple vehicles, the initial solution including multiple loads such that each shipment is routed within exactly one load and a global cost across all loads is minimized, the initial solution being generated independent of the criticality of the shipments. Into each of one or more critical loads in a current solution, one or more non-critical shipments are inserted that are within a neighborhood of the critical load, a critical load being a load containing at least one critical shipment. One or more local search operations are executed to improve the initial solution, the operations including at least one of: (a) splitting each of one or more selected critical loads in a current solution into two new critical loads; (b) for each of one or more selected critical load pairs in a current solution, move a sequence of stops from one critical load in the pair to the other critical load in the pair and/or swap two sequences of stops between the critical loads in the pair; and (c) for each of one or more selected critical loads in a current solution that are indirect critical loads having at least one in-transit stop, break up the indirect critical load into a plurality of new direct critical loads having no in-transit stops and execute operation (b) on each of one or more selected critical load pairs, each selected critical load pair including at least one new direct critical load.

Claims

1. A computer-implemented system for routing shipments according to criticality, the system comprising one or more software components collectively operable to:

access an initial solution to an optimization problem of routing a plurality of shipments to a plurality of locations using a plurality of vehicles, the initial solution comprising a plurality of loads such that each shipment is routed within exactly one load and a global cost across all the loads is minimized, the initial solution being generated independent of the criticality of the shipments;

insert, into each of one or more critical loads in a current solution, one or more non-critical shipments that are within a neighborhood of the critical load, a critical load being a load containing at least one critical shipment; and

execute one or more local search operations to improve the initial solution, the executed local search operations comprising at least one of;

(a) splitting each of one or more selected critical loads in a current solution into two new critical loads;

(b) for each of one or more selected critical load pairs in a current solution, move a sequence of stops from one critical load in the pair to the other critical load in the pair and/or swap two sequences of stops between the critical loads in the pair; and

(c) for each of one or more selected critical loads in a current solution that are indirect critical loads having at least one in-transit stop, break up the indirect critical load into a plurality of new direct critical loads having no in-transit stops and execute operation (b) on each of one or more selected critical load pairs, each selected critical load pair including at least one new direct critical load.

2. The system of claim 1, wherein the optimization problem is a basic Vehicle Routing Problem (VRP) and the initial solution is a solution to the basic VRP.

3. The system of claim 1, wherein a critical shipment is a shipment that must be delivered in a current time period and a non-critical shipment is a shipment that may be delivered in a future time period.

4. The system of claim 1, wherein the optimizer is further operable to:

sort the critical loads in order of decreasing priority and, among critical loads having the same priority, in order of decreasing fullness prior to insertion of the non-critical shipments; and

select the critical loads in the sorted order for insertion of the non-critical shipments.

5. The system of claim 1, wherein a non-critical shipment is inserted into a critical load only if the resulting critical load is executable and doing so does not increase the global cost by more than a predetermined amount.

6. The system of claim 1, wherein the optimizer is further operable to, according to a strategy script:

execute operation (a) on each of one or more selected critical loads in the initial solution and on each of one or more selected new critical loads created as a result of executing operation (a), thereby generating a solution (a) that is more optimal than the initial solution;

execute operation (b) on each of one or more selected critical load pairs in solution (a) and on each of one or more selected new critical load pairs created as a result of executing operation (b), thereby generating a solution (b) that is more optimal than solution (a); and

execute operation (c) on each of one or more selected critical loads in solution (b) and on each of one or more selected new critical loads created as a result of executing operation (c), thereby generating a solution (c) that is more optimal than solution (b).

7. The system of claim 1, wherein for each critical load that may be split using operation (a), the optimizer is further operable to:

determine a distance savings associated with each possible split of the critical load;

sort the possible splits in order of decreasing distance savings;

select the first possible split in the sorted order for evaluation; and

temporarily split the critical load into two new critical loads according to the selected possible split, insert into the two new critical loads one or more non-critical shipments that are within neighborhoods of the two new critical loads, accept the split if both new critical loads are fuller than a predetermined amount after insertion of the non-critical shipments and a unit cost across all critical loads is improved as a result of the split, else discard the split and select the next possible split for evaluation.

8. The system of claim 1, wherein the optimizer is further operable to:

sort the critical loads in order of decreasing priority and, among critical loads having the same priority, in order of decreasing fullness prior to splitting the critical loads; and

select the critical loads in the sorted order for splitting.

9. The system of claim 1, wherein a critical load may be split only if the critical load includes at least one in-transit stop, the critical load has a fullness that exceeds a predetermined threshold, and the optimizer estimates there are sufficient non-critical shipments within a neighborhood of the critical load to make the two new critical loads executable if they are filled with these non-critical shipments.

10. The system of claim 1, wherein for each selected critical load pair for operation (b), the optimizer is further operable to:

determine a quadruple for each possible move and swap between the critical loads of the pair, a quadruple for a move specifying a first critical load of the pair, a second critical load of the pair, a sequence of stops of the first critical load to be moved, and a position of the second critical load at which the sequence of stops is to be inserted, a quadruple for a swap specifying a first critical load of the pair, a second critical load of the pair, a first sequence of stops of the first critical load, and a second sequence of stops of the second critical load to be swapped with the first sequence of stops;

determine a distance savings associated with each quadruple;

sort the quadruples in order of decreasing distance savings;

select the first quadruple in the sorted order for evaluation; and

temporarily implement the move or swap associated with the selected quadruple to create two new critical loads, accept the move or swap if both new critical loads are fuller than a predetermined amount and a unit cost across all critical loads is improved as a result of the move or swap, else discard the move or swap and select the next quadruple for evaluation.

11. The system of claim 10, wherein the optimizer is further operable to:

determine a destination distance associated with each critical load pair; and

determine quadruples only for critical load pairs having associated destination distances exceeding a predetermined threshold.

12. The system of claim 10, wherein a quadruple is considered only if the optimizer estimates there are sufficient non-critical shipments within neighborhoods of the critical loads in the pair to make these critical loads executable if they are filled with these non-critical shipments after the associated move or swap occurs.

13. The system of claim 10, wherein if one or more capacity constraints are violated for a new critical load created as a result of the move or swap, the optimizer is further operable to remove all non-critical shipments from the new critical load and insert into the new critical load one or more non-critical shipments within a neighborhood of the new critical load, provided the resulting new critical load is executable and doing so does not increase the global cost by more than a predetermined amount.

14. The system of claim 10, wherein following acceptance of the move or swap on the critical loads of the pair, the optimizer is further operable to:

discard all remaining quadruples involving these original critical loads;

determine a plurality of new critical load pairs involving the two new critical loads created as a result of the move or swap;

determine a new quadruple for each possible move and swap between the critical loads of each new pair;

determine a distance savings associated with each new quadruple; and

sort all quadruples, including the previously existing quadruples and the new quadruples, in order of decreasing distance savings before selecting the next quadruple for evaluation.

15. The system of claim 10, wherein for operation (c) the optimizer is further operable to:

given a set comprising all the new direct critical loads created, determine a new quadruple for each possible move and swap between the new direct critical loads in the set and all critical loads not in the set;

determine a distance savings associated with each new quadruple;

sort the new quadruples in order of decreasing distance savings;

select the first new quadruple in the sorted order for evaluation; and

temporarily implement the move or swap associated with the selected new quadruple to create two additional critical loads, accept the move or swap if both additional critical loads are fuller than a predetermined amount and a unit cost across all critical loads is improved as a result of the move or swap, else discard the move or swap and select the next new quadruple for evaluation.

16. The system of claim 15, wherein the optimizer is further operable to:

sort the critical loads in order of decreasing priority and, among critical loads having the same priority, in order of decreasing fullness prior to breaking up the critical loads; and

select the critical loads in the sorted order for breaking up.

17. The system of claim 15, wherein a critical load may be broken up only if the critical load has a fullness below a predetermined threshold and the optimizer estimates that there are sufficient non-critical shipments within neighborhoods of the new critical loads to make the new critical loads executable if they are filled with these non-critical shipments.

18. A computer-implemented method for routing shipments according to criticality, comprising:

accessing an initial solution to an optimization problem of routing a plurality of shipments to a plurality of locations using a plurality of vehicles, the initial solution comprising a plurality of loads such that each shipment is routed within exactly one load and a global cost across all the loads is minimized, the initial solution being generated independent of the criticality of the shipments;

inserting, into each of one or more critical loads in a current solution, one or more non-critical shipments that are within a neighborhood of the critical load, a critical load being a load containing at least one critical shipment; and

executing one or more local search operations to improve the initial solution, the executed local search operations comprising at least one of;

(a) splitting each of one or more selected critical loads in a current solution into two new critical loads;

(b) for each of one or more selected critical load pairs in a current solution, move a sequence of stops from one critical load in the pair to the other critical load in the pair and/or swap two sequences of stops between the critical loads in the pair; and

(c) for each of one or more selected critical loads in a current solution that are indirect critical loads having at least one in-transit stop, break up the indirect critical load into a plurality of new direct critical loads having no in-transit stops and execute operation (b) on each of one or more selected critical load pairs, each selected critical load pair including at least one new direct critical load.

19. The method of claim 18, wherein the optimization problem is a basic Vehicle Routing Problem (VRP) and the initial solution is a solution to the basic VRP.

20. The method of claim 18, wherein a critical shipment is a shipment that must be delivered in a current time period and a non-critical shipment is a shipment that may be delivered in a future time period.

21. The method of claim 18, further comprising:

sorting the critical loads in order of decreasing priority and, among critical loads having the same priority, in order of decreasing fullness prior to insertion of the non-critical shipments; and

selecting the critical loads in the sorted order for insertion of the non-critical shipments.

22. The method of claim 18, wherein a non-critical shipment is inserted into a critical load only if the resulting critical load is executable and doing so does not increase the global cost by more than a predetermined amount.

23. The method of claim 18, further comprising, according to a strategy script:

executing operation (a) on each of one or more selected critical loads in the initial solution and on each of one or more selected new critical loads created as a result of executing operation (a), thereby generating a solution (a) that is more optimal than the initial solution;

executing operation (b) on each of one or more selected critical load pairs in solution (a) and on each of one or more selected new critical load pairs created as a result of executing operation (b), thereby generating a solution (b) that is more optimal than solution (a); and

executing operation (c) on each of one or more selected critical loads in solution (b) and on each of one or more selected new critical loads created as a result of executing operation (c), thereby generating a solution (c) that is more optimal than solution (b).

24. The method of claim 18, further comprising, for each critical load that may be split using operation (a):

determining a distance savings associated with each possible split of the critical load;

sorting the possible splits in order of decreasing distance savings;

selecting the first possible split in the sorted order for evaluation; and

temporarily splitting the critical load into two new critical loads according to the selected possible split, inserting into the two new critical loads one or more non-critical shipments that are within neighborhoods of the two new critical loads, accepting the split if both new critical loads are fuller than a predetermined amount after insertion of the non-critical shipments and a unit cost across all critical loads is improved as a result of the split, else discarding the split and select the next possible split for evaluation.

25. The method of claim 18, further comprising:

sorting the critical loads in order of decreasing priority and, among critical loads having the same priority, in order of decreasing fullness prior to splitting the critical loads; and

selecting the critical loads in the sorted order for splitting.

26. The method of claim 18, wherein a critical load may be split only if the critical load includes at least one in-transit stop, the critical load has a fullness that exceeds a predetermined threshold, and it is estimated that there are sufficient non-critical shipments within a neighborhood of the critical load to make the two new critical loads executable if they are filled with these non-critical shipments.

27. The method of claim 18, further comprising, for each selected critical load pair for operation (b):

determining a quadruple for each possible move and swap between the critical loads of the pair, a quadruple for a move specifying a first critical load of the pair, a second critical load of the pair, a sequence of stops of the first critical load to be moved, and a position of the second critical load at which the sequence of stops is to be inserted, a quadruple for a swap specifying a first critical load of the pair, a second critical load of the pair, a first sequence of stops of the first critical load, and a second sequence of stops of the second critical load to be swapped with the first sequence of stops;

determining a distance savings associated with each quadruple;

sorting the quadruples in order of decreasing distance savings;

selecting the first quadruple in the sorted order for evaluation; and

temporarily implementing the move or swap associated with the selected quadruple to create two new critical loads, accepting the move or swap if both new critical loads are fuller than a predetermined amount and a unit cost across all critical loads is improved as a result of the move or swap, else discarding the move or swap and select the next quadruple for evaluation.

28. The method of claim 27, further comprising:

determining a destination distance associated with each critical load pair; and

determining quadruples only for critical load pairs having associated destination distances exceeding a predetermined threshold.

29. The method of claim 27, wherein a quadruple is considered only if it is estimated that there are sufficient non-critical shipments within neighborhoods of the critical loads in the pair to make these critical loads executable if they are filled with these non-critical shipments after the associated move or swap occurs.

30. The method of claim 27, further comprising, if one or more capacity constraints are violated for a new critical load created as a result of the move or swap, removing all non-critical shipments from the new critical load and inserting into the new critical load one or more non-critical shipments within a neighborhood of the new critical load, provided the resulting new critical load is executable and doing so does not increase the global cost by more than a predetermined amount.

31. The method of claim 27, further comprising, following acceptance of the move or swap on the critical loads of the pair:

discarding all remaining quadruples involving these original critical loads;

determining a plurality of new critical load pairs involving the two new critical loads created as a result of the move or swap;

determining a new quadruple for each possible move and swap between the critical loads of each new pair;

determining a distance savings associated with each new quadruple; and

sorting all quadruples, including the previously existing quadruples and the new quadruples, in order of decreasing distance savings before selecting the next quadruple for evaluation.

32. The method of claim 27, further comprising for operation (c):

given a set comprising all the new direct critical loads created, determining a new quadruple for each possible move and swapping between the new direct critical loads in the set and all critical loads not in the set;

determining a distance savings associated with each new quadruple;

sorting the new quadruples in order of decreasing distance savings;

selecting the first new quadruple in the sorted order for evaluation; and

temporarily implementing the move or swap associated with the selected new quadruple to create two additional critical loads, accepting the move or swap if both additional critical loads are fuller than a predetermined amount and a unit cost across all critical loads is improved as a result of the move or swap, else discarding the move or swap and select the next new quadruple for evaluation.

33. The method of claim 32, further comprising:

sorting the critical loads in order of decreasing priority and, among critical loads having the same priority, in order of decreasing fullness prior to breaking up the critical loads; and

selecting the critical loads in the sorted order for breaking up.

34. The method of claim 32, wherein a critical load may be broken up only if the critical load has a fullness below a predetermined threshold and it is estimated that there are sufficient non-critical shipments within neighborhoods of the new critical loads to make the new critical loads executable if they are filled with these non-critical shipments.

35. Software for routing shipments according to criticality, the software being embodied in computer-readable media and when executed operable to:

access an initial solution to an optimization problem of routing a plurality of shipments to a plurality of locations using a plurality of vehicles, the initial solution comprising a plurality of loads such that each shipment is routed within exactly one load and a global cost across all the loads is minimized, the initial solution being generated independent of the criticality of the shipments;

insert, into each of one or more critical loads in a current solution, one or more non-critical shipments that are within a neighborhood of the critical load, a critical load being a load containing at least one critical shipment; and

execute one or more local search operations to improve the initial solution, the executed local search operations comprising at least one of;

(a) splitting each of one or more selected critical loads in a current solution into two new critical loads;

(b) for each of one or more selected critical load pairs in a current solution, move a sequence of stops from one critical load in the pair to the other critical load in the pair and/or swap two sequences of stops between the critical loads in the pair; and

(c) for each of one or more selected critical loads in a current solution that are indirect critical loads having at least one in-transit stop, break up the indirect critical load into a plurality of new direct critical loads having no in-transit stops and execute operation (b) on each of one or more selected critical load pairs, each selected critical load pair including at least one new direct critical load.

36. A computer-implemented system for routing shipments according to criticality, comprising:

means for accessing an initial solution to an optimization problem of routing a plurality of shipments to a plurality of locations using a plurality of vehicles, the initial solution comprising a plurality of loads such that each shipment is routed within exactly one load and a global cost across all the loads is minimized, the initial solution being generated independent of the criticality of the shipments;

means for inserting, into each of one or more critical loads in a current solution, one or more non-critical shipments that are within a neighborhood of the critical load, a critical load being a load containing at least one critical shipment; and

means for executing one or more local search operations to improve the initial solution, the executed local search operations comprising at least one of;

(a) splitting each of one or more selected critical loads in a current solution into two new critical loads;

(b) for each of one or more selected critical load pairs in a current solution, move a sequence of stops from one critical load in the pair to the other critical load in the pair and/or swap two sequences of stops between the critical loads in the pair; and

(c) for each of one or more selected critical loads in a current solution that are indirect critical loads having at least one in-transit stop, break up the indirect critical load into a plurality of new direct critical loads having no in-transit stops and execute operation (b) on each of one or more selected critical load pairs, each selected critical load pair including at least one new direct critical load.