US-12626211-B2 - Systems and methods for last-mile delivery assignment

US12626211B2US 12626211 B2US12626211 B2US 12626211B2US-12626211-B2

Abstract

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.

Inventors

Xi Chen
Minghui Liu
Yiren Ye
Hengchao Wang
Yuan Wang
Jing Huang
Mingang Fu
Mohit Agarwal

Assignees

WALMART APOLLO, LLC

Dates

Publication Date: 20260512
Application Date: 20221230

Claims (20)

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.

Description

TECHNICAL FIELD This application relates generally to route assignment and, more particularly, to assignment engines configured to generate optimized assignments. BACKGROUND Driver matching for deliveries generated by an automated delivery system requires selection of the “right” driver for an order such that the driver accepts the order and completes the order. Some delivery management systems allow a customer to select a delivery window specifying a range of time when the goods may be delivered. Similarly, some delivery management systems allow delivery drivers to operate in a crowdsourced, or “gig,” arrangement in which delivery drivers can choose when to be available for deliveries and can select only those deliveries they wish to perform. Current systems use a cascading assignment method that provides potential orders to potential drivers using various mechanism based on, for example, time remaining until a delivery window. However, such systems do not ensure drivers will select presented deliveries or minimize travel distances for all drivers. Failure to provide desired deliveries or optimal solutions can result in, for example, goods spoiling before delivery or delivery delays due to vehicles being selected that do not provide an optimal solution for routing current deliveries. This may have a cascading effect on subsequent deliveries, potentially missing promised delivery windows on other orders on the delivery schedule. SUMMARY In various embodiments, a system including 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, and an adjustment engine configured, and a route optimization engine are disclosed. The adjustment engine is 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. The weight is determined based on at least one driver-trip feature, at least one driver feature, and at least one trip feature. The route optimization engine is 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 and 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. 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. In various embodiments, a computer-implemented method includes steps of: 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; 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; and 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. The weight is determined based on at least one driver-trip feature, at least one driver feature, and at least one trip feature. 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. In various embodiments, a non-transitory computer-readable medium having instructions stored thereon is disclosed. The instructions, when executed by at least one processor, cause a device to perform operations including: 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; 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; and 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. The weight is determined based on at least one driver-trip feature, at least on