TIME AND LOCATION BASED DELIVERY OPTIMIZATION
Methods, systems, and computer program products for logistics management are described. A root node in a tree representing a home base may be established, the root node comprising a capacity of a corresponding delivery vehicle. One or more unassigned delivery points may be added as a child node of the root node if a path to the corresponding unassigned delivery point is feasible. A next level delivery point may be added as a child node of a node in a tree level index if the delivery point is unassigned and a path to the next level delivery point is feasible. The adding step may be repeated for each combination of unassigned delivery point and node(s) in the tree level index .
1 . A computerized method for managing package delivery, the method comprising:
establishing a root node in a tree representing a home base and comprising a capacity of a corresponding delivery vehicle;
setting an index to an initial value, the index representing a level of the tree;
adding one or more unassigned delivery points as a child node of the root node if a path to the corresponding unassigned delivery point is feasible;
setting the index to the initial value plus one;
adding a next level delivery point as a child node of a node in a tree level index if the delivery point is unassigned and a path to the next level delivery point is feasible, the adding step being repeated for each combination of unassigned delivery point and node in the tree level index ;
incrementing the index; and
repeating the adding a next level delivery point and the incrementing until the index is greater than a count of delivery points.
2 . The method of claim 1 , wherein an unvisited delivery point m has an arrival time window of [LS n +T nm , LE n +T nm ] and a feasible arrival time window of
[ AS m ,AE m ]=[LS n +T nm ,LE n +T nm ]∩[TS m −TW,TE m ],
where LS n is a start of a feasible time window for node n in the tree;
LE n is an end of the feasible time window for node n in the tree;
T nm is a travel time from point n to point m;
TS m is a start of a required time window for demand point d;
TE m is an end of the required time window for demand point d;
AS m is a start of the feasible arrival time window for node n in the tree;
AE m is an end of a feasible arrival time window for node n in the tree; and
TW is a maximum wait time at a demand point.
3 . The method of claim 2 , wherein a delivery point is feasible if
[ LS n +T nm ,LE n +T nm ]∩[TS m −TW,TE m ]≠Ø and W m ≦C n
where LS n is a start of a feasible time window for node n in the tree;
LE n is an end of the feasible time window for node n in the tree;
T nm is a travel time from point n to point m;
TS m is a start of a required time window for demand point d;
TE m is an end of the required time window for demand point d;
W m is a weight of a delivery for demand point m;
C is a capacity of a truck; and
TW is a maximum wait time at a demand point.
4 . The method of claim 2 , wherein a feasible departure time window is
[ LS m ,LE m ]=[max( AS m ,TS m )+ TU m ,max( AE m ,TS m )+ TU m ]
where LS m is a start of a feasible time window for node m in the tree;
LE m is an end of the feasible time window for node m in the tree;
TS m is a start of a required time window for demand point d;
AS m is a start of a feasible arrival time window for node n in the tree;
AE m is an end of the feasible arrival time window for node n in the tree; and
TU m is an unloading time for demand point m.
5 . The method of claim 1 , further comprising pruning paths that contain a count of nodes that is less than a node threshold.
6 . The method of claim 1 , further comprising pruning paths where a total weight of deliveries on the route is lower than a weight threshold.
7 . The method of claim 1 , further comprising pruning a path of a duplicate set of paths whose finish time is later than another path of the duplicate set.
8 . The method of claim 1 , further comprising pruning a path of a duplicate set of paths whose travel distance is longer than another path of the duplicate set.
9 . The method of claim 1 , wherein a profit for a route is o=r−s G−t P
where o is the profit;
r is a total delivery revenue for the route;
s is a sum of travel distances between consecutive nodes on the route and a direct distance from a leaf node to the home base;
G is a cost for a truck to travel a unit distance;
t is a total travel time; and
P is a cost for a truck driver to be outside the home base per unit of time.
10 . An apparatus for managing package delivery, the apparatus comprising:
a processor;
memory to store instructions that, when executed by the processor cause the processor to:
establish a root node in a tree representing a home base and comprising a capacity of a corresponding delivery vehicle;
set an index to an initial value, the index representing a level of the tree;
add one or more unassigned delivery points as a child node of the root node if a path to the corresponding unassigned delivery point is feasible;
set the index to the initial value plus one;
add a next level delivery point as a child node of a node in a tree level index if the delivery point is unassigned and a path to the next level delivery point is feasible, the adding step being repeated for each combination of unassigned delivery point and node in the tree level index ;
increment the index; and
repeat the adding a next level delivery point and the incrementing until the index is greater than a count of delivery points.
11 . The apparatus of claim 10 , wherein an unvisited delivery point m has an arrival time window of [LS n +T nm , LE n +T nm ] and a feasible arrival time window of
[ AS m ,AE m ]=[LS n +T nm ,LE n +T nm ]∩[TS m −TW,TE n ],
where LS n is a start of a feasible time window for node n in the tree;
LE n is an end of the feasible time window for node n in the tree;
T nm is a travel time from point n to point m;
TS m is a start of a required time window for demand point d;
TE m is an end of the required time window for demand point d;
AS m is a start of the feasible arrival time window for node n in the tree;
AE m is an end of a feasible arrival time window for node n in the tree; and
TW is a maximum wait time at a demand point.
12 . The apparatus of claim 11 , wherein a delivery point is feasible if
[ LS n +T nm ,LE n +T nm ]∩[TS m −TW,TE m ]≠Ø and W m ≦C n
where LS n is a start of a feasible time window for node n in the tree;
LE n is an end of the feasible time window for node n in the tree;
T nm is a travel time from point n to point m;
TS m is a start of a required time window for demand point d;
TE m is an end of the required time window for demand point d;
W m is a weight of a delivery for demand point m;
C is a capacity of a truck; and
TW is a maximum wait time at a demand point.
13 . The apparatus of claim 11 , wherein a feasible departure time window is
[LS m ,LE m ]=[max( AS m ,TS m )+ TU m ,max( AE m ,TS m )+ TU m ]
where LS m is a start of a feasible time window for node m in the tree;
LE m is an end of the feasible time window for node m in the tree;
TS m is a start of a required time window for demand point d;
AS m is a start of a feasible arrival time window for node n in the tree;
AE m is an end of the feasible arrival time window for node n in the tree; and
TU m is an unloading time for demand point m.
14 . The apparatus of claim 10 , further comprising instructions that, when executed by the processor, cause the processor to prune paths that contain a count of nodes that is less than a node threshold.
15 . The apparatus of claim 10 , further comprising instructions that, when executed by the processor, cause the processor to prune paths where a total weight of deliveries on the route is lower than a weight threshold.
16 . The apparatus of claim 10 , further comprising instructions that, when executed by the processor, cause the processor to prune a path of a duplicate set of paths whose finish time is later than another path of the duplicate set.
17 . The apparatus of claim 10 , further comprising instructions that, when executed by the processor, cause the processor to prune a path of a duplicate set of paths whose travel distance is longer than another path of the duplicate set.
18 . The apparatus of claim 10 , wherein a profit for a route is o=r−s G−t P
where o is the profit;
r is a total delivery revenue for the route;
s is a sum of travel distances between consecutive nodes on the route and a direct distance from a leaf node to the home base;
G is a cost for a truck to travel a unit distance;
t is a total travel time; and
P is a cost for a truck driver to be outside the home base per unit of time.
19 . A non-transitory machine-readable storage medium comprising instructions that, when executed by one or more processors of a machine, cause the machine to perform operations comprising:
establishing a root node in a tree representing a home base and comprising a capacity of a corresponding delivery vehicle;
setting an index to an initial value, the index representing a level of the tree;
adding one or more unassigned delivery points as a child node of the root node if a path to the corresponding unassigned delivery point is feasible;
setting the index to the initial value plus one;
adding a next level delivery point as a child node of a node in a tree level index if the delivery point is unassigned and a path to the next level delivery point is feasible, the adding step being repeated for each combination of unassigned delivery point and node in the tree level index ;
incrementing the index; and
repeating the adding a next level delivery point and the incrementing until the index is greater than a count of delivery points.
20 . The non-transitory machine-readable storage medium of claim 19 , wherein an unvisited delivery point m has an arrival time window of [LS n +T nm , LE n +T nm ] and a feasible arrival time window of
[ AS m ,AE m ]=[LS n +T nm ,LE n +T nm ]∩[TS m −TW,TE m ],
where LS n is a start of a feasible time window for node n in the tree;
LE n is an end of the feasible time window for node n in the tree;
T nm is a travel time from point n to point m;
TS m is a start of a required time window for demand point d;
TE m is an end of the required time window for demand point d;
AS m is a start of the feasible arrival time window for node n in the tree;
AE m is an end of a feasible arrival time window for node n in the tree; and
TW is a maximum wait time at a demand point.