System and method for generating a delivery plan for multi-tier delivery schemes

• US 10,255,577 B1
• Filed: 12/22/2011
• Issued: 04/09/2019
• Est. Priority Date: 12/22/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Steves, Andrea C., Lehmann, Sebastian
• Primary Examiner(s): Chen, George
• Application Number:
  US13/335,758
• Time in Patent Office: 2,665 Days
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/646 Following a predefined trajectory, e.g. a line marked on the floor or a flight path
• CPC Class Codes: G06Q 10/083 Shipping
• CPC Class Codes: G06Q 10/08355 Routing methods

Abstract

Various embodiments of a system and method for generating a delivery plan for multi-tier delivery schemes are described. Embodiments may include generating a delivery plan for a region including multiple delivery locations. The delivery plan may specify at least one agent delivery route within the region. The delivery route may include at least one shipment acquisition location coinciding with an expected travel route of a vehicle conveying shipments. The agent delivery route may be traversed by an agent that is to deliver a specific group of shipments acquired from the vehicle at the shipment acquisition location. Embodiments may include selecting the specific group of shipments for delivery on the delivery route. The selecting is based on a time constraint for delivering the group of shipments to respective delivery locations along the delivery route, and historical delivery time information for previous deliveries to the delivery locations along the delivery route.

Claims

1. A computer-implemented method, comprising:

generating a final segment delivery plan for a region including multiple delivery locations, wherein the final segment delivery plan comprises;

an expected vehicle travel route of a vehicle conveying shipments within the region; and

at least one agent delivery route within the region, wherein the agent delivery route includes at least one shipment acquisition location coinciding with the expected vehicle travel route, wherein said agent delivery route is distinct from the expected travel route of the vehicle, and is a final segment of a larger delivery route, and wherein said agent delivery route is to be traversed by a robotic agent that is to deliver a specific group of shipments acquired from the vehicle at said shipment acquisition location, wherein the robotic agent'"'"'s traversal of the agent delivery route is specified to be performed during at least a portion of the vehicle'"'"'s traversal of the expected vehicle travel route;

selecting the specific group of shipments for delivery on a segment of said agent delivery route, wherein said selecting is based on;

a time constraint for delivering the group of shipments to respective delivery locations along said segment of the agent delivery route, and

historical delivery time information for previous deliveries to the delivery locations along said segment of the agent delivery route;

transmitting one or more instructions associated with the generated final segment delivery plan to the robotic agent via network communication over one or more networks, wherein the one or more instructions direct the robotic agent to traverse the at least a portion of the specified agent delivery route while the vehicle traverses at least a portion of the specified expected vehicle travel route;

calculate, based on a robotic agent rendezvous time at the vehicle and one or more delivery times at one or more points of delivery along the agent delivery route obtained from the robotic agent, delivery time information associated with the agent delivery route;

for a next delivery plan;

select a subsequent group of shipments for delivery on said segment of said agent delivery route based on;

a time constraint for delivering the subsequent group of shipment to respective delivery locations along said segment of the said agent delivery route, and

the calculated delivery time information associated with said agent delivery route; and

transmit instructions, via a network communication over one or more networks to the robotic agent, that direct the robotic agent to traverse said agent delivery route to deliver the subsequently-selected group of shipments while the vehicle traverses at least a portion of the specified expected vehicle travel route.

2. The computer-implemented method of claim 1, wherein said time constraint is a constraint based on an expected time of a subsequent acquisition of additional items, wherein said subsequent acquisition includes the agent acquiring another group of shipments from a delivery vehicle at another shipment acquisition location on said agent delivery route.

3. The computer-implemented method of claim 1, wherein said specific group of shipments originate from a merchant, wherein the method comprises selecting said specific group of shipments based on delivery destinations for shipments of that group having shorter historical delivery times than delivery destinations of other shipments sent by the merchant.

4. The computer-implemented method of claim 3, wherein the method comprises selecting said specific group of shipments based on the historical delivery times in order to maximize the quantity of shipments to be delivered on the agent delivery route.

5. A computer-implemented method, comprising:

generating a delivery plan for a region including multiple delivery locations, wherein the delivery plan comprises;

an expected vehicle travel route of a vehicle conveying shipments within the region; and

at least one agent delivery route within the region, wherein the agent delivery route includes at least one shipment acquisition location coinciding with the expected vehicle travel route, wherein said agent delivery route is distinct from the expected travel route of the vehicle, and wherein said agent delivery route is to be traversed by a robotic agent that is to deliver a specific group of shipments acquired from the vehicle at said shipment acquisition location;

wherein generating the delivery plan includes generating a delivery plan that specifies that the robotic agent is to traverse at least a portion of the specified agent delivery route while the vehicle traverses at least a portion of the specified expected vehicle travel route;

selecting the specific group of shipments for delivery on a segment of said agent delivery route, wherein said selecting is based on;

a time constraint for delivering the group of shipments to respective delivery locations along said segment of the agent delivery route, and

historical delivery time information for previous deliveries to the multiple delivery locations along said segment of the agent delivery route; and

transmitting one or more instructions associated with the generated delivery plan to the robotic agent via network communication over one or more networks, wherein the one or more instructions direct the robotic agent to traverse the at least a portion of the specified agent delivery route while the vehicle traverses at least a portion of the specified expected vehicle travel route;

calculating, based on a robotic agent rendezvous time at the vehicle and one or more delivery times at points of delivery along the agent delivery route obtained from the robotic agent, delivery time information associated with the agent delivery route;

for a next delivery plan;

selecting a subsequent group of shipments for delivery on the segment of said agent delivery route based on;

a time constraint for delivering the subsequent group of shipments to respective delivery locations along said segment of the agent delivery route, and

the calculated delivery time information associated with the agent delivery route; and

transmitting instructions, via network communication over one or more networks to the robotic agent, that direct the robotic agent to traverse the agent delivery route to deliver the subsequently-selected group of shipments while the vehicle traverses at least a portion of the specified expected vehicle travel route.

6. The computer-implemented method of claim 5, wherein said time constraint is a constraint based on an expected time of a subsequent acquisition of additional items, wherein said subsequent acquisition includes the agent acquiring another group of shipments from a delivery vehicle at another shipment acquisition location on said agent delivery route.

7. The computer-implemented method of claim 5, wherein said specific group of shipments originate from a merchant, wherein the method comprises selecting said specific group of shipments based on delivery destinations for shipments of that group having shorter historical delivery times than delivery destinations of other shipments sent by the merchant.

8. The computer-implemented method of claim 7, wherein the method comprises selecting said specific group of shipments based on the historical delivery times in order to maximize the quantity of shipments to be delivered on the agent delivery route.

9. The computer-implemented method of claim 5, wherein said vehicle comprises multiple different groups of shipments to be delivered by agents on respective agent delivery routes;

wherein the method comprises generating an egress sequence for each of those groups of shipments, the egress sequence specifying an order in which the groups of shipments are to be removed from the delivery vehicle by agents at respective shipment acquisition locations.

10. The computer-implemented method of claim 9, wherein the method comprises, for each given group of shipments, generating a delivery sequence for that group of shipments, wherein said delivery sequence specifies the order in which shipments of that group are to be delivered to delivery destinations by the agents.

11. The computer-implemented method of claim 10, wherein the method comprises conveying the delivery sequence of each given order to a mobile device possessed by the respective agent.

12. The computer-implemented method of claim 5,

wherein the method comprises selecting said specific group of shipments based on one or more of:

travel distances of the agent delivery route or physical configurations of delivery locations on the agent delivery route.

13. The computer-implemented method of claim 5, wherein said vehicle is tasked with delivering other shipments distinct from the specific group of shipments.

14. The computer-implemented method of claim 5, wherein the method comprises regenerating the delivery plan in response to detecting an event.

15. The computer-implemented method of claim 14, wherein said event comprises one or more of:

a personnel status change, a weather event, or a traffic event.

16. The computer-implemented method of claim 5, wherein the selection of the specific group of shipments is additionally based on a restriction on one or more of:

an aggregate size for the specific group of shipments, an aggregate weight for the specific group of shipments, or an aggregate value for the specific group of shipments.

17. A system, comprising:

a memory; and

one or more processors coupled to the memory, wherein the memory comprises program instructions executable by the one or more processors to;

generate a delivery plan for a region including multiple delivery locations, wherein the delivery plan comprises;

an expected vehicle travel route of a vehicle conveying shipments within the region; and

at least one agent delivery route within the region, wherein the agent delivery route includes at least one shipment acquisition location coinciding with the expected vehicle travel route, wherein said agent delivery route is distinct from the expected travel route of the vehicle, and wherein said agent delivery route is to be traversed by a robotic agent that is to deliver a specific group of shipments acquired from the vehicle at said shipment acquisition location;

wherein to generate the delivery plan for the region, the program instructions are executable to generate a delivery plan that specifies that the robotic agent is to traverse at least a portion of the specified agent delivery route while the vehicle traverses at least a portion of the specified expected vehicle travel route;

wherein to select the specific group of shipments for delivery on a segment of said agent delivery route, the program instructions are executable to select that group based on;

a time constraint for delivering the group of shipments to respective delivery locations along said segment of the agent delivery route, and

historical delivery time information for previous deliveries to the delivery locations along said segment of the agent delivery route;

transmit one or more instructions associated with the generated delivery plan to the robotic agent via network communication over one or more networks, wherein the one or more instructions direct the robotic agent to traverse the at least a portion of the specified agent delivery route while the vehicle traverses at least a portion of the specified expected vehicle travel route;

calculate, based on a robotic agent rendezvous time at the vehicle and one or more delivery times at points of delivery along the agent delivery route obtained from the robotic agent, delivery time information associated with the agent delivery route;

for a next delivery plan;

select a subsequent group of shipments for delivery on the segment of said agent delivery route based on;

a time constraint for delivering the subsequent group of shipments to respective delivery locations along said segment of the agent delivery route, and

the calculated delivery time information associated with the agent delivery route; and

transmit one or more instructions, via network communication over one or more networks to the robotic agent, that direct the robotic agent to traverse the agent delivery route to deliver the sub sequently-selected group of shipments while the vehicle traverses at least a portion of the specified expected vehicle travel route.

18. The system of claim 17, wherein said time constraint is a constraint based on an expected time of a subsequent acquisition of additional items, wherein said subsequent acquisition includes the agent acquiring another group of shipments from a delivery vehicle at another shipment acquisition location on said agent delivery route.

19. The system of claim 17, wherein said specific group of shipments originate from a merchant, wherein the program instructions are configured to select said specific group of shipments based on delivery destinations for shipments of that group having shorter historical delivery times than delivery destinations of other shipments sent by the merchant.

20. The system of claim 19, wherein the program instructions are configured to select said specific group of shipments based on the historical delivery times in order to maximize the quantity of shipments to be delivered on the agent delivery route.

21. The system of claim 17, wherein said vehicle comprises multiple different groups of shipments to be delivered by agents on respective agent delivery routes;

wherein the program instructions are configured to generate an egress sequence for each of those groups of shipments, the egress sequence specifying an order in which the groups of shipments are to be removed from the delivery vehicle by agents at respective shipment acquisition locations.

22. The system of claim 21, wherein the program instructions are configured to, for each given group of shipments, generate a delivery sequence for that group of shipments, wherein said delivery sequence specifies the order in which shipments of that group are to be delivered to delivery destinations by the agents.

23. The system of claim 22, wherein the program instructions are configured to convey the delivery sequence of each given order to a mobile device possessed by the respective agent.

24. The system of claim 17, wherein the program instructions are configured to select said specific group of shipments based on one or more of:

travel distances of the agent delivery route or physical configurations of delivery locations on the agent delivery route.

25. The system of claim 17, wherein said vehicle is tasked with delivering other shipments distinct from the specific group of shipments.

26. A non-transitory computer-readable storage medium, storing program instructions computer-executable on a computer to:

generate a delivery plan for a region including multiple delivery locations, wherein the delivery plan comprises;

an expected vehicle travel route of a vehicle conveying shipments within the region; and

at least one agent delivery route within the region, wherein the agent delivery route includes at least one shipment acquisition location coinciding with the expected vehicle travel route, wherein said agent delivery route is distinct from the expected travel route of the vehicle, and wherein said agent delivery route is to be traversed by a robotic agent that is to deliver a specific group of shipments acquired from the vehicle at said shipment acquisition location;

wherein to generate the delivery plan the instructions are executable to generate a delivery plan that specifies that the robotic agent is to traverse at least a portion of the specified agent delivery route while the vehicle traverses at least a portion of the specified expected vehicle travel route;

wherein to select the specific group of shipments for delivery on a segment of said agent delivery route, the program instructions are executable to select that group based on;

a time constraint for delivering the group of shipments to respective delivery locations along said segment of the agent delivery route, and

historical delivery time information for previous deliveries to the delivery locations along said segment of the agent delivery route;

transmit one or more instructions associated with the generated delivery plan to the robotic agent via network communication over one or more networks, wherein the one or more instructions direct the robotic agent to traverse the at least a portion of the specified agent delivery route while the vehicle traverses at least a portion of the specified expected vehicle travel route;

calculate, based on a robotic agent rendezvous time at the vehicle and one or more delivery times at points of delivery along the agent delivery route obtained from the robotic agent, delivery time information associated with the agent delivery route;

for a next delivery plan;

select a subsequent group of shipments for delivery on the segment of said agent delivery route based on;

a time constraint for delivering the subsequent group of shipments to respective delivery locations along said segment of the agent delivery route, and

the calculated delivery time information associated with the agent delivery route; and

transmit one or more instructions, via network communication over one or more networks to the robotic agent, that direct the robotic agent to traverse the agent delivery route to deliver the subsequently-selected group of shipments while the vehicle traverses at least a portion of the specified expected vehicle travel route.

27. The non-transitory computer-readable storage medium of claim 26, wherein said time constraint is a constraint based on an expected time of a subsequent acquisition of additional items, wherein said subsequent acquisition includes the agent acquiring another group of shipments from a delivery vehicle at another shipment acquisition location on said agent delivery route.

28. The non-transitory computer-readable storage medium of claim 26, wherein said specific group of shipments originate from a merchant, wherein the program instructions are configured to select said specific group of shipments based on delivery destinations for shipments of that group having shorter historical delivery times than delivery destinations of other shipments sent by the merchant.

29. The non-transitory computer-readable storage medium of claim 28, wherein the program instructions are configured to select said specific group of shipments based on the historical delivery times in order to maximize the quantity of shipments to be delivered on the agent delivery route.

30. The non-transitory computer-readable storage medium of claim 26, wherein said vehicle comprises multiple different groups of shipments to be delivered by agents on respective agent delivery routes;

wherein the program instructions are configured to generate an egress sequence for each of those groups of shipments, the egress sequence specifying an order in which the groups of shipments are to be removed from the delivery vehicle by agents at respective shipment acquisition locations.