Routing shipments according to criticality

• US 6,980,885 B2
• Filed: 09/24/2001
• Issued: 12/27/2005
• Est. Priority Date: 09/24/2001
• Status: Expired due to Term

• 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
• Primary Examiner(s): Walsh, Donald P.
• Application Number:
  US09/962,663
• Publication Number:
  US 20030060924A1
• Time in Patent Office: 1,555 Days
• Field of Search: 700/215, 700/216, 700/217, 700/218, 705/6, 705/7, 705/8
• 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 predetermined shipments to a plurality of predetermined 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 first operation comprising splitting each of one or more selected critical loads in a current solution into two new critical loads;

a second operation comprising, for each of one or more selected pairs of critical loads in a current solution, performing at least one of moving a sequence of stops from one critical load in the pair to the other critical load in the pair and swapping two sequences of stops between the critical loads in the pair; and

a third operation comprising, 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, breaking up the indirect critical load into a plurality of new direct critical loads having no in-transit stops and for each of one or more selected pairs of critical loads, each selected pair of critical loads including at least one new direct critical load, performing at least one of moving a sequence of stops from one critical load in the pair to the other critical load in the pair and swapping two sequences of stops between the critical loads in the pair.

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

5. 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 the 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.

6. 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.

7. The system of claim 1, wherein for each selected pair of critical loads for the second operation, the optimizer is further operable to:

determine a quadruple for each possible move and each possible 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.

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

determine a destination distance associated with each pair of critical loads; and

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

9. The system of claim 7, 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.

10. The system of claim 7, 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.

11. The system of claim 7, 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 pairs of critical loads 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.

12. The system of claim 7, wherein for the third operation 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.

13. The system of claim 12, 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.

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

accessing an initial solution to an optimization problem of routing a plurality of predetermined shipments to a plurality of predetermined 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 first operation comprising splitting each of one or more selected critical loads in a current solution into two new critical loads;

a second operation comprising, for each of one or more selected pairs of critical loads in a current solution, performing at least one of moving a sequence of stops from one critical load in the pair to the other critical load in the pair and swapping two sequences of stops between the critical loads in the pair; and

a third operation comprising, 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, breaking up the indirect critical load into a plurality of new direct critical loads having no in-transit stops and for each of one or more selected pairs of critical loads, each selected pair of critical loads including at least one new direct critical load, performing at least one of moving a sequence of stops from one critical load in the pair to the other critical load in the pair and swapping two sequences of stops between the critical loads in the pair.

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

16. The method of claim 14, 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.

17. The method of claim 14, 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.

18. The method of claim 14, 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.

19. The method of claim 14, 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.

20. The method of claim 14, further comprising, for each selected pair of critical loads for the second operation:

determining a quadruple for each possible move and each possible 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.

21. The method of claim 20, further comprising:

determining a destination distance associated with each pair of critical loads; and

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

22. The method of claim 20, 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.

23. The method of claim 20, 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.

24. The method of claim 20, 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 pairs of critical loads 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.

25. The method of claim 20, further comprising for the third operation:

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.

26. The method of claim 25, 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.

27. 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 predetermined shipments to a plurality of predetermined 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 first operation comprising splitting each of one or more selected critical loads in a current solution into two new critical loads;

a second operation comprising, for each of one or more selected pairs of critical loads in a current solution, performing at least one of moving a sequence of stops from one critical load in the pair to the other critical load in the pair and swapping two sequences of stops between the critical loads in the pair; and

a third operation comprising, 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, breaking up the indirect critical load into a plurality of new direct critical loads having no in-transit stops and for each of one or more selected pairs of critical loads, each selected pair of critical loads including at least one new direct critical load, performing at least one of moving a sequence of stops from one critical load in the pair to the other critical load in the pair and swapping two sequences of stops between the critical loads in the pair.

29. The software of claim 27, wherein for each selected critical load pair for the second operation, the software further operable to:

determine a quadruple for each possible move and each possible 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.

30. The software of claim 27, further operable to:

determine a destination distance associated with each pair of critical loads; and

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

31. The software of claim 27, wherein a quadruple is considered only if the software 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.

32. The software of claim 27, wherein if one or more capacity constraints are violated for a new critical load created as a result of the move or swap, the software 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.

33. The software of claim 27, wherein following acceptance of the move or swap on the critical loads of the pair, the software further operable to:

discard all remaining quadruples involving these original critical loads;

determine a plurality of new pairs of critical loads 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.

34. The software of claim 27, wherein for the third operation the software 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.

35. The software of claim 27, wherein a critical load may be broken up only if the critical load has a fullness below a predetermined threshold and the software 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.

28. 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 predetermined shipments to a plurality of predetermined 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 first operation comprising splitting each of one or more selected critical loads in a current solution into two new critical loads;

a second operation comprising, for each of one or more selected pairs of critical loads in a current solution, performing at least one of moving a sequence of stops from one critical load in the pair to the other critical load in the pair and swapping two sequences of stops between the critical loads in the pair; and

a third operation comprising, 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, breaking up the indirect critical load into a plurality of new direct critical loads having no in-transit stops and for each of one or more selected pairs of critical loads, each selected pair of critical loads including at least one new direct critical load, performing at least one of moving a sequence of stops from one critical load in the pair to the other critical load in the pair and swapping two sequences of stops between the critical loads in the pair.