Systems and methods for compressing shortest path matrices for delivery route optimization

Patent metadata

Field	Value
Publication number	US-10248925-B2
Application number	US-201615370081-A
Country	US
Kind code	B2
Filing date	Dec 6, 2016
Priority date	Dec 6, 2016
Publication date	Apr 2, 2019
Grant date	Apr 2, 2019

Abstract

Systems and methods including one or more processing modules and one or more non-transitory storage modules storing computing instructions configured to run on the one or more processing modules and perform an act of preparing an initial shortest path matrix including a plurality of elements, an initial number of a plurality of map intersection nodes, and a plurality of full shortest paths between an origination map intersection node and a destination map intersection node. Each element can include a full shortest path, and each full shortest path can include one or more map intersection nodes. The one or more processing modules also can be configured to compress the initial shortest path matrix to form a compressed shortest path matrix that includes a compressed number of the plurality of map intersection nodes that is fewer than the initial number of the plurality of map intersection nodes.

First claim

What is claimed is:

1. A system comprising:
one or more processors; and
one or more non-transitory storage devices storing computing instructions configured to run on the one or more processors and perform acts of:
preparing an initial shortest path matrix comprising a plurality of elements, an initial number of a plurality of map intersection nodes, and a plurality of full shortest paths between an origination map intersection node and a destination map intersection node, wherein each element of the plurality of elements comprises a full shortest path of the plurality of full shortest paths, and each full shortest path of the plurality of full shortest paths comprises one or more map intersection nodes of the plurality of map intersection nodes;
obtaining a first set of compression rules for compressing, using the one or more processors, the initial shortest path matrix by reducing the plurality of map intersection nodes in the initial shortest path matrix;
using the first set of compression rules and the one or more processors to compress the initial shortest path matrix to form a compressed shortest path matrix comprising a compressed number of the plurality of map intersection nodes that is fewer than the initial number of the plurality of map intersection nodes;
receiving a first delivery order for delivery of a first order at a first location; and
determining a shortest path delivery route for the first delivery order at the first location using the compressed shortest path matrix,
wherein:
using the first set of compression rules and the one or more processors to compress the initial shortest path matrix to form the compressed shortest path matrix comprises using the first set of compression rules and the one or more processors to compress the initial shortest path matrix to form a first compressed shortest path matrix by replacing the full shortest path between the origination map intersection node and the destination map intersection node in each element of the plurality of elements with a single map intersection node of the plurality of map intersection nodes;
the compressed number of the plurality of map intersection nodes that is fewer than the initial number of the plurality of map intersection nodes comprises a first compressed number of the plurality of map intersection nodes that is fewer than the initial number of the plurality of map intersection nodes;
the single map intersection node for a respective element of the plurality of elements comprises a next map intersection node in the full shortest path of the respective element of the plurality of elements; and
determining the shortest path delivery route for the first delivery order at the first location using the compressed shortest path matrix comprises determining the shortest path delivery route using the first compressed shortest path matrix.

2. The system of claim 1 , wherein:
one or more full shortest paths of the plurality of full shortest paths of the initial shortest path matrix comprise multiple map intersection nodes of the plurality of map intersection nodes; and
the one or more non-transitory storage devices storing the computing instructions are configured to run on the one or more processors and perform an act of:
using the first set of compression rules and the one or more processors to compress each of the one or more full shortest paths of the plurality of full shortest paths comprising the multiple map intersection nodes of the plurality of map intersection nodes in the initial shortest path matrix to form the single map intersection node of the plurality of map intersection nodes in the first compressed shortest path matrix.

3. The system of claim 1 , wherein:
the one or more non-transitory storage devices storing the computing instructions are configured to run on the one or more processors and perform acts of:
obtaining a second set of compression rules for compressing, using the one or more processors, the first compressed shortest path matrix by reducing the plurality of map intersection nodes in the first compressed shortest path matrix;
using the second set of compression rules and the one or more processors to compress the first compressed shortest path matrix to form a second compressed shortest path matrix comprising a second compressed number of the plurality of map intersection nodes that is fewer in number than the first compressed number of the plurality of map intersection nodes by compressing adjacent elements of the plurality of elements in a row in the first compressed shortest path matrix to form a single interval comprising a single interval map intersection node of the plurality of map intersection nodes when the adjacent elements comprise identical map intersection nodes of the plurality of map intersection nodes; and
storing the second compressed shortest path matrix in random access memory cache; and

determining the shortest path delivery route for the first delivery order at the first location using the compressed shortest path matrix comprises determining the shortest path delivery route using the second compressed shortest path matrix.

4. The system of claim 1 , wherein the one or more non-transitory storage devices storing the computing instructions are configured to run on the one or more processors and perform an act of storing, in a random access memory cache, a small distance matrix associated with the first location and retrieved from the compressed shortest path matrix after receiving the first delivery order, the small distance matrix being smaller than the compressed shortest path matrix.

5. The system of claim 4 , wherein the one or more non-transitory storage devices storing the computing instructions are configured to run on the one or more processors and perform acts of:
receiving an additional delivery order for an additional delivery at the first location; and
determining an additional shortest path delivery route for the additional delivery at the first location using the small distance matrix stored in the random access memory cache.

6. The system of claim 1 , wherein:
one or more full shortest paths of the plurality of full shortest paths of the initial shortest path matrix comprise multiple map intersection nodes of the plurality of map intersection nodes;
the one or more non-transitory storage devices storing the computing instructions are configured to run on the one or more processors and perform acts of:
using the first set of compression rules and the one or more processors to compress each full shortest path of the plurality of full shortest paths comprising the one or more map intersection nodes of the plurality of map intersection nodes in the initial shortest path matrix to form the single map intersection node of the plurality of map intersection nodes in the first compressed shortest path matrix;
obtaining a second set of compression rules for compressing, using the one or more processors, the first compressed shortest path matrix by reducing the plurality of map intersection nodes in the first compressed shortest path matrix;
using the second set of compression rules and the one or more processors to compress the first compressed shortest path matrix to form a second compressed shortest path matrix comprising a second compressed number of the plurality of map intersection nodes that is fewer in number than the compressed number of the plurality of map intersection nodes by compressing adjacent elements of the plurality of elements in a row in the first compressed shortest path matrix to form a single interval comprising a single interval map intersection node of the plurality of map intersection nodes when the adjacent elements comprise identical map intersection nodes of the plurality of map intersection nodes;
storing the s

Assignees

• Wal Mart Stores Inc
• Walmart Apollo Llc

Inventors

• Fu Mingang
• Deshpande Deepak
• Seetharaman Prakash
• Pattathil Devadas

Classifications

• G06Q10/083 Primary

  Shipping · CPC title

• G01C21/3446

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