Patent ID: 11948109
Assignee: AMAZON TECHNOLOGIES, INC.
Field: IT methods for management (Electrical engineering)
Classification: CPC G | IPC G

Claim 0:
1. A computer system comprising:
one or more processors; and
one or more memories storing computer-readable instructions that, upon execution by the one or more memories, configure the computer system to:
determine, by at least querying a data store during a time window prior to a start of a planning horizon, a demand for item transportation expected during the planning horizon;
determine, by at least querying the data store during the time window, first information about first delivery drivers available during the planning horizon and second information associated with second delivery drivers, wherein each one of the first delivery drivers is associated with a pre-planned delivery service for the planning horizon, wherein each pre-planned delivery service is associated with a pre-defined cost that is independent of actual usage of the pre-planned delivery service, wherein each one of the second delivery drivers is associated with an on-demand delivery service, and wherein the second information indicates a use cost that depends on actual use of on-demand delivery services;
determine, by at least executing program code of an optimization model, (i) blocks each having a corresponding time length and assignable to one of the delivery drivers, (ii) tours each assignable to one of the blocks and usable to transport a different portion of the demand, (iii) a first assignment of a first block to a first delivery driver of the first delivery drivers and a first assignment of a first tour to the first block, (iv) a remaining portion of the demand to be transported using the on-demand delivery services, and (v) a second assignment of an item from the remaining portion to a second tour and a second assignment of the second tour to a second block, wherein:
the optimization model is configured to perform an iterative search that optimizes, by at least solving a restricted master problem (RMP) that jointly considers resource information and tour information by combining at least two variables into a single variable such that the iterative search is computationally reduced and completed by the computer system before an end of the time window, an overall item transportation cost, the RMP solved by at least using the demand, the first information, the second information, and pre-defined costs of the pre-planned delivery services as inputs to the program code and exploring variables that include candidate blocks and candidate tours per candidate block, and
the block and the tour are one of the candidate blocks and one the candidate tours respectively;
store, in the data store, a first output and a second output, the first output indicating the first assignment of the first block and the first assignment of the first tour, the second outputting indicating the remaining portion of the demand, the second assignment of the item, and the second assignment of the second tour;
cause by at least sending the first output to a first computing device of the first delivery driver over a data network, the first computing device to present, at a first user interface, the first assignment of the first block as a schedule and to present the first assignment of the first tour, the first output sent based at least in part on the first delivery driver being associated with the corresponding pre-planned delivery service;
determine, by at least querying the data store at a predefined time prior to the end of the time window, an update to the demand;
determine, by at least re-executing the program code of the optimization model based at least in part on the update and in which the iterative search is skipped, a change to the first tour;
cause the first computing device to present the schedule and the change to the first tour;
receive, over the data network from a second computing device of a second delivery driver of the second delivery drivers, a request for delivery information; and
cause, by at least sending the second output to the second computing device over the data network in response to the request, the second computing device to present, at a second user interface, an availability of the of the second block and the second assignment of the second tour, the second output sent based at least in part on the second delivery driver being associated with the corresponding on-demand delivery service.