Routing shipments according to criticality
First Claim
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.
17 Assignments
0 Petitions
Accused Products
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.
-
Citations
36 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
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. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
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.
-
Specification