Systems and methods for last-mile delivery assignment
Systems and methods of route optimization are disclosed. An adjustment engine receives a plurality of driver-trip pairs each including a driver selected from a plurality of drivers and a trip selected from a plurality of trips and determines a weight for each of the driver-trip pairs. The weight is determined based on at least one driver-trip feature, at least one driver feature, and at least one trip feature. A route optimization engine selects a set of optimal driver-trip pairs based on a bipartite matching process including the weight for each of the driver trip pairs. The set of optimal driver-trip pairs minimizes total estimated time of arrival to a pickup location for each trip in the plurality of trips. Trip data is transmitted to a corresponding device associated with a corresponding driver paired with each trip in the set of optimal driver-trip pairs.
1 . A system, comprising:
a non-transitory memory;
a transceiver configured to receive potential assignment data comprising data representative of a plurality of drivers and a plurality of trips;
an adjustment engine configured to:
receive a plurality of driver-trip pairs each including a driver selected from the plurality of drivers and a trip selected from the plurality of trips; and
determine a weight for each of the driver-trip pairs, wherein the weight is determined based on respective weights of at least one driver-trip feature, at least one driver feature, and at least one trip feature, wherein:
the at least one driver-trip feature includes driver affinity score based, in part, on a driver probability to accept a respective trip,
the at least one driver feature including real-time driver behavior features representative of driver declined trips relative to maximum declined trips in a predetermined time period, and
the at least one trip feature includes a trip priority feature; and
a route optimization engine configured to:
select a set of optimal driver-trip pairs from the plurality of driver-trip pairs based on a bipartite matching process including the weight for each of the driver-trip pairs, wherein the set of optimal driver-trip pairs minimizes a total estimated time of arrival to a pickup location for each trip in the plurality of trips;
transmit trip data for each trip in the plurality of trips to a corresponding device associated with a corresponding driver paired with each trip in the set of optimal driver-trip pairs;
receive from the corresponding device an indication of either acceptance or non-acceptance for each trip in the set of optimal driver-trip pairs; and
in response to receiving an indication of non-acceptance for a subset of the set of optimal driver-trip pairs that is provided after a predetermined time limit, automatically:
providing the subset of the set of optimal driver-trip pairs to the adjustment engine, and
broadcasting corresponding trip data to devices of the plurality of drivers.
2 . The system of claim 1 , wherein the adjustment engine is configured to generate a trip-specific weight component of the weight based on the trip priority feature.
3 . The system of claim 1 , wherein the adjustment engine is configured to generate a driver-specific weight component of the weight based on the real-time driver behavior features.
4 . The system of claim 3 , wherein the adjustment engine is configured to implement a trained real-time behavior model to determine the driver-specific weight component.
5 . The system of claim 1 , wherein the adjustment engine is configured to generate a driver-trip weight component of the weight based on the driver affinity score.
6 . The system of claim 5 , wherein the adjustment engine is configured to implement a trained driver affinity model to generate the driver affinity score.
7 . The system of claim 1 , wherein the weight for each of the driver-trip pairs is defined as:
W
T
,
D
=
f
1
dt
(
ETA
)
+
f
2
dt
(
)
+
f
3
dt
(
S
d
,
S
T
)
+
f
4
dt
(
n
rej
)
+
f
5
dt
(
g
)
+
f
6
dt
(
x
,
p
)
where
f
1
dt
(
ETA
)
is an estimated time or arrival from a current location associated with the driver to a pickup location associated with the trip,
f
2
dt
(
p
dt
^
)
is a predicted probability of a driver d accepting a trip t,
f
3
dt
(
S
d
,
S
T
)
is a best-fit vehicle function,
f
4
dt
(
n
rej
)
is real-time activity function,
f
5
dt
(
g
)
is a driver performance function, and
f
6
dt
(
x
,
p
)
is a trip function.
8 . The system of claim 7 , wherein
f
2
dt
(
p
dt
^
)
is defined as:
f
2
dt
(
)
=
c
max
(
s
-
0
.
5
)
3
(
⌊
n
t
4
⌋
e
p
d
t
∑
t
e
p
d
t
-
0
.
5
)
3
where c max a control parameter configured to control the weight and n t is a number of expired or rejected trips for the driver in a predetermined time period.
9 . The system of claim 7 , wherein
f
4
dt
(
n
rej
)
is defined as:
f
4
dt
(
n
)
=
{
c
max
1
-
(
1
-
n
n
max
)
2
,
n
≤
n
max
c
max
,
n
>
n
max
where n is a number of expired or rejected trips for the driver in a predetermined time period, c max a control parameter configured to control the weight, and n max a maximum number of expired or rejected trips in a predetermined time period.
10 . The system of claim 7 , wherein
f
5
dt
(
g
)
is defined as:
f
5
dt
(
g
)
=
c
g
where g is a priority group and c g maps the priority group to a weight value.
11 . A computer-implemented method, comprising:
receiving, via a transceiver, potential assignment data comprising data representative of a plurality of drivers and a plurality of trips;
receiving, at an adjustment engine, a plurality of driver-trip pairs each including a driver selected from the plurality of drivers and a trip selected from the plurality of trips;
determining, by the adjustment engine, a weight for each of the driver-trip pairs, wherein the weight is determined based on respective weights of at least one driver-trip feature, at least one driver feature, and at least one trip feature, wherein:
the at least one driver-trip feature includes driver affinity score based, in part, on a driver probability to accept a respective trip,
the at least one driver feature including real-time driver behavior features representative of driver declined trips relative to maximum declined trips in a predetermined time period, and
the at least one trip feature includes a trip priority feature;
selecting, by a route optimization engine, a set of optimal driver-trip pairs from the plurality of driver-trip pairs based on a bipartite matching process including the weight for each of the driver-trip pairs, wherein the set of optimal driver-trip pairs minimizes a total estimated time of arrival to a pickup location for each trip in the plurality of trips;
transmitting, via the transceiver, trip data for each trip in the plurality of trips to a corresponding device associated with a corresponding driver paired with each trip in the set of optimal driver-trip pairs;
receiving, via the transceiver, from the corresponding device an indication of either acceptance or non-acceptance for each trip in the set of optimal driver-trip pairs; and
in response to receiving an indication of non-acceptance for a subset of the set of optimal driver-trip pairs that is provided after a predetermined time limit, automatically
providing the subset of the set of optimal driver-trip pairs to the adjustment engine, and
broadcasting corresponding trip data to devices of the plurality of drivers.
12 . The computer-implemented method of claim 11 , wherein the adjustment engine is configured to generate a trip-specific weight component of the weight based on the priority feature.
13 . The computer-implemented method of claim 11 , wherein the adjustment engine is configured to generate a driver-specific weight component of the weight based on the real-time driver behavior features.
14 . The computer-implemented method of claim 13 , wherein the adjustment engine is configured to implement a trained real-time behavior model to determine the driver-specific weight component.
15 . The computer-implemented method of claim 11 , wherein the adjustment engine is configured to generate a driver-trip weight component of the weight based on the driver affinity score.
16 . The computer-implemented method of claim 15 , wherein the adjustment engine is configured to implement a trained driver affinity model to generate the driver affinity score.
17 . A non-transitory computer-readable medium having instructions stored thereon, wherein the instructions, when executed by at least one processor, cause a device to perform operations comprising:
receiving, via a transceiver, potential assignment data comprising data representative of a plurality of drivers and a plurality of trips;
receiving, at an adjustment engine, a plurality of driver-trip pairs each including a driver selected from the plurality of drivers and a trip selected from the plurality of trips;
determining, by the adjustment engine, a weight for each of the driver-trip pairs, wherein the weight is determined based on respective weights of at least one driver-trip feature, at least one driver feature, and at least one trip feature, wherein:
the at least one driver-trip feature includes driver affinity score based, in part, on a driver probability to accept a respective trip,
the at least one driver feature including real-time driver behavior features representative of driver declined trips relative to maximum declined trips in a predetermined time period, and
the at least one trip feature includes a trip priority feature;
selecting, by a route optimization engine, a set of optimal driver-trip pairs from the plurality of driver-trip pairs based on a bipartite matching process including the weight for each of the driver-trip pairs, wherein the set of optimal driver-trip pairs minimizes a total estimated time of arrival to a pickup location for each trip in the plurality of trips;
transmitting, via the transceiver, trip data for each trip in the plurality of trips to a corresponding device associated with a corresponding driver paired with each trip in the set of optimal driver-trip pairs;
receiving, via the transceiver, from the corresponding device an indication of either acceptance or non-acceptance for each trip in the set of optimal driver-trip pairs; and
in response to receiving an indication of non-acceptance for a subset of the set of optimal driver-trip pairs that is provided after a predetermined time limit, automatically
providing the subset of the set of optimal driver-trip pairs to the adjustment engine, and
broadcasting corresponding trip data to devices of the plurality of drivers.
18 . The non-transitory computer-readable medium of claim 17 , wherein the weight for each of the driver-trip pairs is defined as:
W
T
,
D
=
f
1
dt
(
ETA
)
+
f
2
dt
(
)
+
f
3
dt
(
S
d
,
S
T
)
+
f
4
dt
(
n
rej
)
+
f
5
dt
(
g
)
+
f
6
dt
(
x
,
p
)
where
f
1
dt
(
ETA
)
is an estimated time of arrival from a current location associated with the driver to a pickup location associated with the trip,
f
2
dt
(
p
dt
^
)
is a predicted probability of a driver d accepting a trip t,
f
3
dt
(
S
d
,
S
T
)
is a best-fit vehicle function,
f
4
dt
(
n
rej
)
is real-time activity function
f
5
dt
(
g
)
is a driver performance function, and
f
6
dt
(
x
,
p
)
is a trip function.
19 . The non-transitory computer-readable medium of claim 18 , wherein
f
2
dt
(
p
dt
^
)
is defined as:
f
2
dt
(
)
=
c
max
(
s
-
0
.
5
)
3
(
⌊
n
t
4
⌋
e
p
d
t
∑
t
e
p
d
t
-
0
.
5
)
3
where c max a control parameter configured to control the weight and n t is a number of expired or rejected trips for the driver in a predetermined time period.
20 . The non-transitory computer-readable medium of claim 18 , wherein
f
4
dt
(
n
rej
)
is defined as:
f
4
dt
(
n
)
=
{
c
max
1
-
(
1
-
n
n
max
)
2
,
n
≤
n
max
c
max
,
n
>
n
max
where n is a number of expired or rejected trips for the driver in a predetermined time period, c max a control parameter configured to control the weight, and n max a maximum number of expired or rejected trips in a predetermined time period.