Dynamic Truck Route Planning Between Automated Facilities

• US 20190066041A1
• Filed: 12/15/2017
• Published: 02/28/2019
• Est. Priority Date: 08/28/2017
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Hance, Chris, Vrevin, Thibault
• Granted Patent: US 10,787,315 B2
• Time in Patent Office: Days
• CPC Class Codes: B65G 1/137 with arrangements or automatic control means for selecting which articles are to be removed
• CPC Class Codes: B65G 1/1373 for fulfilling orders in warehouses
• CPC Class Codes: B65G 67/04 Loading land vehicles loading or unloading boats to or from land vehicles B60P3/10
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G05D 1/021 specially adapted to land vehicles
• CPC Class Codes: G05D 1/0297 by controlling means in a control room
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/083 Shipping
• CPC Class Codes: G06Q 10/0833 Tracking
• CPC Class Codes: G06Q 10/08355 Routing methods
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

A method includes providing a first route for a delivery vehicle that is associated with a first deadline to reach a first location. The method also includes receiving a cargo delivery request. The method further includes determining a second route for the delivery vehicle that includes a stop at an automated warehouse. The method additionally includes determining, based on scheduling information for robots at the warehouse, a projected availability time for cargo that satisfies the cargo delivery request to be available for pickup at the warehouse. The method also includes determining that the delivery vehicle is expected to reach the first location by the first deadline after traveling on the second route and picking up the cargo from the warehouse. The method further includes providing the second route to the delivery vehicle and causing a robot at the warehouse to prepare the cargo for pickup at the warehouse.

Claims

1. A method comprising:

providing a first route for a delivery vehicle, wherein the first route is associated with a first deadline to reach a first location;

subsequently receiving a cargo delivery request;

determining a second route for the delivery vehicle, wherein the second route includes a stop at an automated warehouse before the first location;

determining, based on scheduling information for a plurality of robots at the automated warehouse, a projected availability time for cargo that satisfies the cargo delivery request to be available for pickup at the automated warehouse;

determining, based on the projected availability time for the cargo, that the delivery vehicle is expected to reach the first location by the first deadline after traveling on the second route and picking up the cargo from the automated warehouse;

subsequently providing the second route to the delivery vehicle; and

causing at least one robot at the automated warehouse to prepare the cargo for pickup at the automated warehouse.

2. The method of claim 1, further comprising:

determining an arrival time by which the delivery vehicle is expected to reach the automated warehouse from a current location of the delivery vehicle on the first route; and

determining the projected availability time based on the arrival time.

3. The method of claim 2, wherein determining the arrival time comprises using mapping software that accounts for one or more constraints of the delivery vehicle.

4. The method of claim 1, wherein the scheduling information for the plurality of robots comprises ordered queues of tasks assigned to each of the plurality of robots.

5. The method of claim 1, wherein determining the projected availability time for the cargo comprises running a software simulation based on positions of the plurality of robots in the automated warehouse and based on a position of the cargo in the automated warehouse.

6. The method of claim 1, wherein the projected availability time for the cargo comprises a future time at which the at least one robot is expected to move the cargo to a loading dock of the automated warehouse.

7. The method of claim 1, further comprising determining, based on the scheduling information for the plurality of robots at the automated warehouse, a projected load time by which one or more of the plurality of robots are expected to have loaded the cargo onto the delivery vehicle, wherein determining that the delivery vehicle is expected to reach the first location by the first deadline after traveling on the second route and picking up the cargo from the automated warehouse is further based on the projected load time.

8. The method of claim 7, further comprising assigning a number of robots of the plurality of robots to load the cargo onto the delivery vehicle based on the scheduling information for the plurality of robots, wherein the projected load time is based on the assigned number of robots.

9. The method of claim 1, wherein the automated warehouse is a first automated warehouse, wherein the plurality of robots is a first plurality of robots and wherein the cargo delivery request is for a delivery from the first automated warehouse to a second automated warehouse having a second plurality of robots, the method further comprising:

determining, based on scheduling information for the second plurality of robots at the second automated warehouse, a projected unload time by which one or more of the second plurality of robots are expected to have unloaded the cargo from the delivery vehicle, wherein determining that the delivery vehicle is expected to reach the first location by the first deadline after traveling on the second route and picking up the cargo from the automated warehouse is further based on the projected unload time.

10. The method of claim 9, further comprising:

determining one or more metrics of the cargo from at least one sensor on the at least one robot that prepares the cargo for pickup at the automated warehouse, wherein the projected unload time by which the one or more of the second plurality of robots are expected to have unloaded the cargo from the delivery vehicle is based on the one or more metrics of the cargo.

11. The method of claim 1, wherein the automated warehouse is a first automated warehouse, wherein the plurality of robots is a first plurality of robots and wherein the cargo delivery request is for a delivery from the first automated warehouse to a second automated warehouse having a second plurality of robots, the method further comprising:

determining projected future workloads for each of the first automated warehouse and the second automated warehouse;

identifying, based on the projected future workloads, a robot of the first plurality of robots to relocate to the second automated warehouse using the delivery vehicle; and

loading the identified robot onto the delivery vehicle while the delivery vehicle is stopped at the first automated warehouse.

12. The method of claim 11, wherein the identified robot has a fixed base, the method further comprising causing an autonomous fork truck at the first automated warehouse to load the identified robot on the delivery vehicle by lifting the fixed base of the identified robot with one or more tines on the autonomous fork truck.

13. The method of claim 1, further comprising:

determining dimensions of the cargo based on sensor data from at least one sensor on one of the plurality of robots; and

determining that the delivery vehicle has a sufficient amount of free space to accommodate the dimensions of the cargo before providing the second route to the delivery vehicle.

14. The method of claim 1, wherein the cargo delivery request is received from a software application running on a computing device.

15. The method of claim 1, wherein providing the second route to the delivery vehicle comprises causing the second route to be displayed on a user device in the delivery vehicle.

16. The method of claim 1, wherein the delivery vehicle is an autonomous truck, wherein providing the second route to the autonomous truck comprises causing the autonomous truck to autonomously navigate to the automated warehouse by the projected availability time.

17. A non-transitory computer readable medium having stored therein instructions executable by one or more processors to cause the one or more processors to perform functions comprising:

providing a first route for a delivery vehicle, wherein the first route is associated with a first deadline to reach a first location;

subsequently receiving a cargo delivery request;

determining a second route for the delivery vehicle, wherein the second route includes a stop at an automated warehouse before the first location;

determining, based on scheduling information for a plurality of robots at the automated warehouse, a projected availability time for cargo that satisfies the cargo delivery request to be available for pickup at the automated warehouse;

determining, based on the projected availability time for the cargo, that the delivery vehicle is expected to reach the first location by the first deadline after traveling on the second route and picking up the cargo from the automated warehouse;

subsequently providing the second route to the delivery vehicle; and

causing at least one robot at the automated warehouse to prepare the cargo for pickup at the automated warehouse.

18. A system comprising:

an automated warehouse, comprising a plurality of robots; and

a control system configured to;

provide a first route for a delivery vehicle, wherein the first route is associated with a first deadline to reach a first location;

subsequently receive a cargo delivery request;

determine a second route for the delivery vehicle, wherein the second route includes a stop at the automated warehouse before the first location;

determine, based on scheduling information for the plurality of robots at the automated warehouse, a projected availability time for cargo that satisfies the cargo delivery request to be available for pickup at the automated warehouse;

determine, based on the projected availability time for the cargo, that the delivery vehicle is expected to reach the first location by the first deadline after traveling on the second route and picking up the cargo from the automated warehouse;

subsequently provide the second route to the delivery vehicle; and

cause at least one robot at the automated warehouse to prepare the cargo for pickup at the automated warehouse.

19. The system of claim 18, wherein the automated warehouse is a first automated warehouse, wherein the plurality of robots is a first plurality of robots, wherein the system further comprises a second automated warehouse having a second plurality of robots, and wherein the cargo delivery request is for a delivery from the first automated warehouse to the second automated warehouse.

20. The system of claim 19, wherein the control system is further configured to:

determine, based on scheduling information for the second plurality of robots at the second automated warehouse, a projected unload time by which one or more of the second plurality of robots are expected to unload the cargo from the delivery vehicle; and

determine, based on the projected unload time, that the delivery vehicle is expected to reach the first location by the first deadline after traveling on the second route and picking up the cargo from the first automated warehouse and dropping off the cargo at the second automated warehouse.