Systems and methods for combinatorial resource optimization

Patent metadata

Field	Value
Publication number	US-2019228352-A1
Application number	US-201816007913-A
Country	US
Kind code	A1
Filing date	Jun 13, 2018
Priority date	Jan 19, 2018
Publication date	Jul 25, 2019
Grant date	—

Abstract

Horizontally-scalable systems and methods for scheduling and optimizing deliveries are described herein. At least one scheduler is configured to receive a request to schedule a delivery for an origination location. The request includes a desired time slot. The request is compared to a persistent delivery snapshot for the origination location to determine availability of the desired time slot. An interim delivery snapshot including the requested delivery is generated when the persistent delivery snapshot has an available time slot corresponding to the desired time slot. At least one optimizer is configured to receive the interim delivery snapshot and generate an updated persistent delivery snapshot by applying an optimization process to the interim delivery snapshot.

First claim

What is claimed is:

1 . A system, comprising:
a computing device configured to:
define at least one scheduler configured to:
receive a request to schedule a delivery for an origination location, wherein the request includes a desired time slot;
compare the request to a persistent delivery snapshot for the origination location to determine availability of the desired time slot;
generate an interim delivery snapshot including the requested delivery when the persistent delivery snapshot has an available time slot corresponding to the desired time slot; and

define at least one optimizer configured to:
receive the interim delivery snapshot;
generate an updated persistent delivery snapshot by applying an optimization process to the interim delivery snapshot.

2 . The system of claim 1 , wherein the at least one optimizer comprises a stateless optimizer configured to provide the updated persistent delivery snapshot to one of the plurality of schedulers that generated the interim delivery snapshot.

3 . The system of claim 1 , wherein the at least one optimizer comprises a stateful optimizer configured to associate a unique ID with the updated persistent delivery snapshot, wherein the optimizer is configured to store the updated persistent delivery snapshot in a database.

4 . The system of claim 1 , wherein the computing device is configured to define an optimization queue, wherein the at least one scheduler is configured to provide the interim delivery snapshot to the optimization queue, and wherein the at least one optimizer is configured to receive the interim delivery snapshot from the optimization queue.

5 . The system of claim 4 , wherein the at least one optimizer is configured to apply an incremental optimization process to the updated persistent delivery snapshot.

6 . The system of claim 4 , wherein the at least one optimizer is configured to apply a batch optimization process to the persistent delivery snapshot.

7 . The system of claim 1 , wherein the at least one optimizer is configured to:
receive at least one delta event; and modify the updated persistent delivery snapshot based on the at least one delta event.

8 . The system of claim 1 , wherein the computing device is configured to define at least one geospatial engine configured to generate mapping data, wherein the at least one geospatial engine is configured to receive distance and time matrix queries from the at least one scheduler and the at least one optimizer.

9 . The system of claim 8 , wherein the at least one geospatial engine is configured to provide distance and time queries for off-road travel.

10 . A method comprising:
defining a plurality of schedulers and a plurality of optimizers; receiving, at a selected one of the plurality of schedulers, a request to schedule a delivery for predetermined first origination location, wherein the request includes a desired time slot; comparing, by the selected one of the plurality of schedulers, the request to a persistent delivery snapshot for the first origination location to determine availability of the desired time slot; generating, by the selected one of the plurality of schedulers, an interim delivery snapshot including the requested delivery when the persistent delivery snapshot has an available time slot corresponding to the desired time slot; receiving, at a selected one of the plurality of optimizers, the interim delivery snapshot; generating, by the selected one of the plurality of the optimizers, an updated persistent delivery snapshot by applying an optimization process to the interim delivery snapshot.

11 . The method of claim 10 , wherein the selected one of the plurality of optimizers comprises a stateless optimizer configured to provide the updated persistent delivery snapshot to the selected one of the plurality of schedulers.

12 . The method of claim 10 , wherein the selected one of the plurality of optimizers comprises a stateful optimizer configured to associate a unique ID with the updated persistent delivery snapshot, wherein the selected one of the plurality of optimizers is configured to store the updated persistent delivery snapshot in a database.

13 . The method of claim 10 , comprising:
defining an optimization queue; providing, by the selected one of the plurality of schedulers, the interim delivery snapshot to the optimization queue; and receiving, by the selected one of the plurality of optimizers, the interim delivery snapshot from the optimization queue.

14 . The method of claim 13 , wherein the selected one of the plurality of optimizers is configured to apply an incremental optimization process to the updated persistent delivery snapshot.

15 . The method of claim 13 , wherein the selected one of the plurality of optimizers is configured to apply a batch optimization process to the updated persistent delivery snapshot.

16 . The method of claim 10 , comprising:
receiving, at the selected one of the plurality of optimizers, at least one delta event; and modifying, by the selected one of the plurality of optimizers, the updated persistent delivery snapshot based on the at least one delta event.

17 . The method of claim 10 , comprising defining a plurality of geospatial engines configured to generate mapping data, wherein each of the geospatial engines is configured to receive distance and time matrix queries from one or more of the plurality of schedulers and/or one or more of the plurality of optimizers.

18 . A non-transitory computer readable medium having instructions stored thereon, wherein the instructions, when executed by a processor cause a device to perform operations comprising:
defining a plurality of schedulers and a plurality of optimizers; receiving, at a selected one of the plurality of schedulers, a request to schedule a delivery for predetermined first origination location, wherein the request includes a desired time slot; comparing, by the selected one of the plurality of schedulers, the request to a persistent delivery snapshot for the first origination location to determine availability of the desired time slot; generating, by the selected one of the plurality of schedulers, an interim delivery snapshot including the requested delivery when the persistent delivery snapshot has an available time slot corresponding to the desired time slot; receiving, at a selected one of the plurality of optimizers, the interim delivery snapshot; generating, by the selected one of the plurality of the optimizers, an updated persistent delivery snapshot by applying an optimization process to the interim delivery snapshot.

19 . The non-transitory computer readable medium of claim 18 , wherein the instructions, when executed by the processor cause the device to perform operations comprising:
defining an optimization queue; providing, by the selected one of the plurality of schedulers, the interim delivery snapshot to the optimization queue; and receiving, by the selected one of the plurality of optimizers, the interim delivery snapshot from the optimization queue.

20 . The non-transitory computer readable medium of claim 18 , wherein the instructions, when executed by the processor cause the device to perform operations comprising:
receiving, at the selected one of the plurality of optimizers, at least one delta event; and modifying, by the selected one of the plurality of optimizers, the updated persistent delivery snapshot based on the at least one delta event.

Assignees

• Walmart Apollo Llc

Inventors

• Nayak Amritayan
• Seetharaman Prakash
• Fu Mingang
• Pande Pushkar Raj
• Deshpande Deepak
• Malyala Kumar

Classifications

• G06F17/30088

  Physics · mapped topic

• G06F9/546

  Message passing systems or structures, e.g. queues · CPC title

• G06F17/30002

  Physics · mapped topic

• G06Q10/047 Primary

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G06Q10/083

  Shipping · CPC title