Methods and apparatus for load and route assignments in a delivery system

Patent metadata

Field	Value
Publication number	US-RE50779-E
Application number	US-202318130226-A
Country	US
Kind code	E1
Filing date	Apr 3, 2023
Priority date	Sep 12, 2018
Publication date	Feb 3, 2026
Grant date	Feb 3, 2026

Abstract

A load and route assignment system is provided and generally includes a computing device and a database. The database may store historical inbound load data and historical outbound load data related to previous inbound and outbound loads. The computing device can obtain and aggregate the historical inbound and outbound load data from the database, and determine an optimal path based on the aggregated historical data. The optimal path, along with load attribute data, may be stored in the database as a tour template for future load executions. The computing device may use the tour templates to determine future load assignments to vehicles. The computing device may also obtain real-time load requests, and match them to one or more of a plurality of tour templates. The computing device may assign the matched real-time load requests to a vehicle for execution in accordance with the corresponding load and tour template.

First claim

What is claimed is:

1 . A computing device comprising:
one or more processors; and a memory configured to store instructions that when executed by the one or more processors cause the computing device to:
aggregate, within a database, historical inbound data related to a plurality of inbound loads based on at least one similar attribute of the plurality of inbound loads to determine and, based on the historical inbound data, generate inbound node data characterizing at least two inbound nodes;
aggregate, within the database, historical outbound data related to a plurality of outbound loads based on at least one similar attribute of the outbound loads to determine and, based on the historical outbound data, generate outbound node data characterizing at least one outbound node;
based on the inbound node data, construct a first determination that there is at least a first pre-defined amount of time to travel between locations associated with the at least two inbound nodes while still satisfying at least a first time window attribute of at least one of the two inbound nodes;
determinegenerate first edge data characterizing at least a first directed edge between the at least two inbound nodes based on the first determination;
based on the inbound node data and the outbound node data, construct a second determination that there is at least a second pre-defined amount of time to travel between locations associated with the at least one outbound node and at least one of the at least two inbound nodes while still satisfying at least a second time window attribute of at least one of the at least one outbound node and the at least two inbound nodes;
determinegenerate second edge data characterizing at least a second directed edge between the at least one outbound node and the at least one of the two inbound nodes based on the second determination;
determinegenerate path data characterizing a plurality of paths between the locations associated with the at least one outbound node and the at least two inbound nodes based on the at least first directed edge and the at least second directed edge; and
determine generate optimal path data characterizing an optimal path based on the path data characterizing the plurality of paths;
generate a tour template based on the optimal path data;
receive, over a network, a live load for delivery;
generate a tour execution that assigns the tour template to the live load; and
store the tour execution within the database.

2 . The computing device of claim 1 , wherein the at least one similar attribute of the plurality of inbound loads comprises an origin, a destination, a destination time window, and a pickup time window, wherein the instructions, when executed by the one or more processors, cause the computing device is further configured to:
determine that the origin is the same;
determine that the designation is the same;
determine that the destination time windows of each of the plurality of inbound loads overlap by a first minimum amount of time; and
determine that the pickup time windows of each of the plurality of inbound loads overlap by a second minimum amount of time.

3 . The computing device of claim 1 , wherein the plurality of paths between the locations associated with the at least one outbound node and the at least two inbound nodes are determined by the application of Dijkstra's algorithm.

4 . The computing device of claim 1 , wherein the plurality of paths between the locations associated with the at least one outbound node and the at least two inbound nodes are determined based on determining that the plurality of paths satisfy at least one rule.

5 . The computing device of claim 4 , wherein the at least one rule comprises determining that the optimal path includes at least a minimum number of inbound and outbound loads, and no more than a maximum number of inbound and outbound loads.

6 . The computing device of claim 1 , wherein the optimal path is determined based on a Key Performance Indicator (KPI) of the plurality of paths.

7 . The computing device of claim 6 , wherein the KPI is an empty miles ratio, wherein the instructions, when executed by the one or more processors, cause the computing device is configuredto determine that the optimal path has the lowest empty miles ratio of the plurality of paths.

8 . The computing device of claim 1 is further configuredwherein the instructions, when executed by the one or more processors, cause the computing device to assign the optimal pathtour execution to a vehicle for execution, and transmit, over the network, the assigned tour execution.

9 . A method by a computing device comprising:
aggregating, within a database, historical inbound data related to a plurality of inbound loads based on at least one similar attribute of the plurality of inbound loads to determine and, based on the historical inbound data, generating inbound node data characterizing at least two inbound nodes; aggregating, within the database, historical outbound data related to a plurality of outbound loads based on at least one similar attribute of the outbound loads to determine and, based on the historical outbound data, generating outbound node data characterizing at least one outbound node; based on the inbound node data, constructing a first determination that there is at least a first pre-defined amount of time to travel between locations associated with the at least two inbound nodes while still satisfying at least a first time window attribute of at least one of the two inbound nodes; determininggenerating first edge data characterizing at least a first directed edge between the at least two inbound nodes based on the first determination; based on the inbound node data and the outbound node data, constructing a second determination that there is at least a second pre-defined amount of time to travel between locations associated with the at least one outbound node and at least one of the at least two inbound nodes while still satisfying at least a second time window attribute of at least one of the at least one outbound node and the at least two inbound nodes; determininggenerating second edge data characterizing at least a second directed edge between the at least one outbound node and the at least one of the two inbound nodes based on the second determination; determining a plurality of paths between the locations associated with the at least one outbound node and the at least two inbound nodes based on the at least first directed edge and the at least second directed edge; and determining generating optimal path data characterizing an optimal path based on the plurality of paths; generating a tour template based on the optimal path data; receiving, over a network, a live load for delivery; generating a tour execution that assigns the tour template to the live load; and storing the tour execution within the database.

10 . The method of claim 9 wherein the at least one similar attribute of the plurality of inbound loads comprises an origin, a destination, a destination time window, and a pickup time window, wherein the method further comprises:
determining that the origin is the same;
determining that the designation is the same;
determining that the destination time windows of each of the plurality of inbound loads overlap by a first minimum amount of time; and
determining that the pickup time windows of each of the plurality of inbound loads overlap by a second minimum amount of time.

11 . The method of claim 9 wherein determining the plurality of paths comprises determining that the optimal path includes at least a minimum number of inbound and outbound loads, and no mo

Assignees

• Walmart Apollo Llc

Inventors

• Fu Mingang
• Pande Pushkar Raj
• Nayak Amritayan
• Deshpande Deepak
• Vasantham Madhavan Kandhadai
• Aman Syed
• Zhang Deyi
• Jain Rohit

Classifications

• G08G1/096816

  where the complete route is transmitted to the vehicle at once · CPC title

• G06Q10/06393

  Score-carding, benchmarking or key performance indicator [KPI] analysis · CPC title

• G01C21/3453

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title

• G01C21/3446 Primary

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/343

  Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047) · CPC title