Patent Description:
<FIG> discloses a typical prior art automated storage and retrieval system <NUM> with a framework structure <NUM> and with container handling vehicles <NUM> operating on the system <NUM>.

The members <NUM>, <NUM> may typically be made of metal, e.g. extruded aluminium profiles.

The framework structure <NUM> of the automated storage and retrieval system <NUM> comprises a rail system <NUM> arranged across the top of the framework structure <NUM>, on which rail system <NUM> a plurality of container handling vehicles <NUM> are operated to raise storage containers <NUM> from, and lower storage containers <NUM> into, the storage columns <NUM>, and also to transport the storage containers <NUM> above the storage columns <NUM>.

The rail system <NUM> comprises a first set of parallel rails <NUM> arranged to guide movement of the container handling vehicles <NUM> in a first direction X across the top of the frame structure <NUM>, and a second set of parallel rails <NUM> arranged perpendicular to the first set of rails <NUM> to guide movement of the container handling vehicles <NUM> in a second direction Y which is perpendicular to the first direction X.

Also shown in <FIG> is a first rail in a first direction X, 110a, a second rail in a first direction X, 110b, a first rail in a second direction Y, 111a and a second rail in a second direction Y, 111b. The container handling vehicles <NUM> move laterally above the storage columns <NUM>, i.e. in a plane which is parallel to the horizontal X-Y plane.

Storage containers <NUM> are stored in the columns <NUM> which define a third direction Z which is orthogonal to the first direction X and the second direction Y. The storage containers <NUM> are accessed by the container handling vehicles <NUM> through access openings <NUM> in the rail system <NUM>, i.e. the rail system <NUM> is arranged on the framework structure <NUM> defining the circumference of each access opening <NUM> on top of each storage column <NUM>. The upright members <NUM> of the framework structure <NUM> may be used to guide the storage containers when these out from and lowering of the containers into the columns <NUM>.

The storage volume of the framework structure <NUM> has often been referred to as a grid <NUM>, where the possible storage positions within storage columns <NUM> in this grid is referred to as a storage cell. Each storage column <NUM> may be identified by a position in an X- and Y- direction, while each storage cell may be identified by a container number in the X, Y and Z- direction.

In the framework structure <NUM>, most of the columns <NUM> are storage columns <NUM>, i.e. columns <NUM> where storage containers <NUM> are stored in stacks <NUM>.

In <FIG>, columns <NUM> and <NUM> are special-purpose columns used by the container handling vehicles <NUM> to drop off and/or pick up storage containers <NUM> so that they can be transferred to an access station (not shown) where the storage containers <NUM> can be accessed from outside of the framework structure <NUM> or transferred out of or into the framework structure <NUM>.

Within the art, columns for transferring a storage container in and out of the storage system is normally referred to as port column <NUM>, <NUM> or a transfer column. A storage container is transferred to and from a port column <NUM>, <NUM> via ports <NUM>', <NUM>' typically located at an opening at an end of the port column <NUM>, <NUM>. i.e. where storage containers are entering or exiting the port columns <NUM>, <NUM>. A port may also be located at other locations such as at a mid-level or ground level of a port column <NUM>, <NUM>.

Transportation and transferring of storage container <NUM> to an access station may be in any direction, that is horizontal, tilted and/or vertical. For example, the storage containers <NUM> may be placed in a random or dedicated column <NUM> within the framework structure <NUM>, then picked up by any container handling vehicle <NUM> and transported to a port column <NUM>,<NUM> for further transportation to an access station.

In <FIG>, the first port column <NUM> may for example be a dedicated drop-off port column where the container handling vehicles <NUM> can drop off storage containers <NUM> to be transported to an access or a transfer station, and the second port column <NUM> may be a dedicated pick-up port column where the container handling vehicles <NUM> can pick up storage containers <NUM> that have been transported from an access or a transfer station.

The access station may typically be a picking or a stocking station where product items are removed from or positioned in the storage containers <NUM>. In a picking or a stocking station, the storage containers <NUM> are normally not removed from the automated storage and retrieval system <NUM> but are returned into the framework structure <NUM> again once accessed. Port columns <NUM>, <NUM> can also be used for transferring storage containers to another storage facility (e.g. to another framework structure or to another automated storage and retrieval system), to a transport vehicle (e.g. a train or a lorry), or to a production facility.

When a specific storage container <NUM> stored in one of the columns <NUM> disclosed in <FIG> is to be retrieved, one of the container handling vehicles <NUM> is assigned and instructed to retrieve the storage container <NUM> from its location and transport it to the port <NUM>' of the port column <NUM>. This operation involves moving the container handling vehicle <NUM> to a location above the storage column <NUM> in which the storage container <NUM> is located, retrieving the storage container <NUM> from the storage column <NUM> using a lifting device (not shown) of the container handling vehicle <NUM> and transporting the storage container <NUM> to the port <NUM>' of the port column <NUM>.

This step, which is sometimes referred to as digging within the art, may be performed with the same container handling vehicle <NUM> that is subsequently used for transporting the target storage container to the drop-off port column <NUM>, or with one or a plurality of other cooperating container handling vehicles <NUM>. Alternatively, or in addition, the automated storage and retrieval system <NUM> may have container handling vehicles <NUM> specifically dedicated to the task of temporarily removing storage containers from a storage column <NUM>. Once the target storage container <NUM> has been removed from the storage column <NUM>, the temporarily removed storage containers <NUM> can be repositioned into the original storage column <NUM>. However, the removed storage containers <NUM> may alternatively be relocated to other storage columns <NUM>.

When a storage container <NUM> is to be stored in one of the columns <NUM>, one of the container handling vehicles <NUM> is instructed to pick up the storage container <NUM> from the port <NUM>' of the port column <NUM> transferring storage containers from an access or a transfer station and transport it to a location above the storage column <NUM> where it is to be stored. After any storage containers positioned at or above the target position within the storage column stack <NUM> have been removed, the container handling vehicle <NUM> positions the storage container <NUM> at the desired position. The removed storage containers <NUM> may then be lowered back into the storage column <NUM> or relocated to other storage columns.

Locations of each storage container <NUM> within the framework structure <NUM> and locations and movements of each container handling vehicle <NUM> operating on the storage and retrieval system are continuously monitored and controlled by a control system <NUM> as well as a reference to the content of each storage container <NUM> so that a desired storage container <NUM> can be delivered to the desired location at the desired time without the container handling vehicles <NUM> colliding with each other.

An example of a typical control system <NUM> is shown in <FIG> and comprises a master controller <NUM>, a database <NUM> keeping track of the storage containers <NUM>, a routing planner <NUM> used for finding optimal routes for the container handling vehicles <NUM> and a transmitter/receiver <NUM> for communicating instructions to each container handling vehicle <NUM>. The control system <NUM> communicates with vehicle controllers <NUM> in each container handling vehicle <NUM> and controls traffic flow of the container handling vehicles <NUM> according to the routing planner <NUM>.

In the description above, separate port columns <NUM>, <NUM> for transferring storage container to and from the storage and retrieval system <NUM> are described. This provides an efficient solution. Only one of the port columns <NUM>, <NUM> may however be used for both transferring storage container to and from the storage and retrieval system.

An automated storage and retrieval system <NUM> is typically operated by two or more container handling vehicles <NUM> serving the same port <NUM>' of a port column <NUM> for transferring storage containers to an access station. Each container handling vehicle <NUM> is assigned and given a task by receiving instructions transmitted from the control system <NUM>. A task may for instance be to get a specific storage container <NUM> from a storage column <NUM> where it is located, drive a set distance in a set direction, deliver a storage container <NUM> at the port <NUM>' etc..

According to prior art, the focus has been to deliver storage containers <NUM> to a port <NUM>' as fast as possible. When several container handling vehicles <NUM> serve the same port <NUM>' for interacting with it, by delivering or retrieving a storage container <NUM> to or from the port <NUM>', they may be at the port <NUM>' or driving towards the port <NUM>' at the same time. This may introduce an inefficiency problem at the port <NUM>'. The container handling vehicles <NUM> may have to wait in queue before they can interact with the port <NUM>', i.e. before delivering or retrieving a storage container <NUM> to/from the port. In this way, the operational capacity of each container handling vehicle <NUM> is not optimally utilized.

To fully utilize the operational capacity of container handling vehicles <NUM> designated to serve the same port <NUM>', each container handling vehicle <NUM> ideally arrive at the port <NUM>' right after another container handling vehicle <NUM> has finished its interaction with the port, i.e. delivering or retrieving a storage container to or from the port <NUM>'.

If a container handling vehicle <NUM> starts to drive towards a port <NUM>' too early, the operational capacity of the container handling vehicle <NUM> may not be optimally utilized since it may have to wait to deliver a storage container <NUM> to the port <NUM>' if other container handling vehicles <NUM> are interacting with the port <NUM>' or moving towards the port <NUM>' for delivering or retrieving storage containers <NUM> at the same time.

The present invention addresses and solves this problem by ensuring that the port <NUM>' is served by a container handling vehicle <NUM> with minimal waiting time at the port <NUM>' thereby reducing the probability that container handling vehicles <NUM> must wait in queue at the port <NUM>'.

Instead of standing still waiting in queue for other container handling vehicles <NUM> to finish interacting with a port, a container handling vehicle <NUM> is in structed to perform other intermediate tasks before delivering or retrieving a storage container <NUM> to and from the port.

NO <CIT> describes an automated storage and retrieval system comprising a control system configured to control and coordinate interaction between drones and container handling vehicles operating respectively below and on top of the automated storage and retrieval system. Different steps are performed by an operational controller in communication with a first type of controller in each container handling vehicle and a second type of controller in each drone, and where timing information is a factor.

According to prior art, the focus has been to deliver storage containers to a port as fast as possible. This may however delay container handling vehicles serving the same port since they may be at the port or driving towards the port at the same time.

Some container handling vehicles may then have to wait in queue at the port before they can interact with it, i.e. before delivering or retrieving a storage container to/from the port. In this way, the operational capacity of each container handling vehicle is not optimally utilized.

According to the invention, the operational capacity of each container handling vehicles designated to serve the same port is better utilized by letting each container handling vehicle arrive at the port preferably just before another container handling vehicle has finished its interaction with the port.

The invention is defined by a method for utilizing operational capacity of container handling vehicles when assigned tasks of delivering or retrieving identified storage containers at same port of an automatic storage and retrieval system comprising a framework structure defining a storage grid for storing storage containers in storage columns, and where the storage containers are handled by the container handling vehicles running on top of the storage grid, and where the port is used for transferring storage containers to and from the storage and retrieval system.

Where a port is located is irrelevant for the solution according to present invention. As mentioned above, a port can be located at a port column that is used for transferring storage containers at a consolidation station. A port can also be located at a consolidation station or picking station. What is relevant for the solution is a deadline a container handling vehicle needs to be at a port.

The method comprises the following steps performed by a control system communicating with a vehicle controller in each container handling vehicle:.

According to one embodiment, the end times and end positions of the container handling vehicles when the assigned tasks without a deadline complete are calculated according to parameters based on one or more of the following:.

According to one embodiment, it is checked if the container handling vehicles can meet the deadline based on the calculated end position and end times of the container handling vehicles after first completing the task without a deadline.

According to one embodiment, container handling vehicles that can meet the deadline are given a bonus point, while container handling vehicles that cannot meet the deadline are given a penalty point and ranking are performed according to points given.

According to one embodiment of the method, where it is calculated that the assigned task without a deadline would cause the container handling vehicle to miss the deadline of the assigned task with a deadline, then ranking the assigned job with the deadline ahead of the assigned job without a deadline thereby first executing the task with the deadline, and subsequently the task without the deadline.

According to one embodiment, assigned but unfinished tasks without a deadline are reassigned to a different container handling vehicle which has capacity within its schedule to complete the reassigned task without a deadline.

The present invention is further defined by a control system for utilizing operational capacity of container handling vehicles when assigned tasks of delivering or retrieving identified storage containers at same port of an automatic storage and retrieval system comprising a framework structure defining a storage grid for storing storage containers in storage columns. The storage containers are handled by the container handling vehicles running on top of the storage grid, and where the port is used for transferring storage containers to and from the storage and retrieval system. The system comprises a control system communicating with a vehicle controller in each container handling vehicle. The control system comprises a processor arranged for running a computer program that when executed performs the method described above.

The invention is further defined by a computer program that when executed by a processor in a control system of an automated storage and retrieval system performs the method described above for utilizing operational capacity of container handling vehicles when assigned tasks of delivering or retrieving identified storage containers at same port of an automatic storage and retrieval system.

The following drawings are appended to facilitate the understanding of the invention.

In the following description, the invention will be explained in more detail with reference to the appended drawings.

A typical prior art automated storage and retrieval system <NUM> with a framework structure <NUM> was described in the background section above with reference to <FIG>.

The framework structure <NUM> can be of any size, and it is understood that it can be considerably wider and/or longer and/or deeper than the one disclosed in <FIG>.

Also, the storage grid <NUM> can be considerably deeper than disclosed in <FIG>. For example, the storage grid <NUM> may be more than twelve grid cells <NUM> deep, i.e. in the Z direction indicated in <FIG>.

The container handling vehicles <NUM> can be of any type known in the art, e.g. any one of the automated container handling vehicles disclosed in <CIT>, in NO<CIT> or in <CIT>.

The rail system <NUM> arranged across the top of the framework structure <NUM> allows the container handling vehicles <NUM> to move horizontally between storage columns <NUM> and first and second ports <NUM>', <NUM>' that they are interacting with, i.e. the ports <NUM>', <NUM>' they are instructed to deliver or retrieve a storage container <NUM> to and from.

When describing the invention below, port <NUM>' is used as an example of the port <NUM>' a set number of container handling vehicles <NUM> are assigned to interact with. The number of vehicles may for instance be <NUM> to <NUM>.

The present invention provides a method and control system for avoiding queue at a port <NUM>' by better controlling each container handling vehicle <NUM> instructed to interact with the same port <NUM>'.

<FIG> is a flowchart illustrating the different steps of the method for utilizing operational capacity of container handling vehicles <NUM> assigned tasks of delivering or retrieving identified storage containers <NUM> at same port of an automatic storage and retrieval system <NUM> comprising a framework structure <NUM>. The framework structure defines a storage grid <NUM> for storing storage containers <NUM> in storage columns <NUM>. The storage containers <NUM> are handled by the container handling vehicles <NUM> running on top of the storage grid <NUM>. In this example, the port <NUM>' is located at an opening of a port column <NUM> which is used for transferring storage containers <NUM> to and from the storage and retrieval system <NUM>. Several steps are performed by a control system <NUM> communicating with a vehicle controller <NUM> in each container handling vehicle <NUM>.

Each container handling vehicle <NUM> is assigned tasks. An assigned task can for instance be to deliver a specific storage container at the port <NUM>' or to move a storage container from one location to another location.

Some tasks have higher priority than others. High priority tasks will be assigned with deadlines while other tasks are assigned without a deadline. A task with a deadline will typically be a task where a specific storage container is requested to be transferred in the port <NUM>'.

A first step of the method <NUM> according to the invention is to assign tasks without and with deadlines <NUM>, <NUM> for the container handling vehicles <NUM>. Which container handling vehicle <NUM> that is assigned to handle a specific storage container <NUM> is based on cost parameters. Examples of cost parameters are distance and driving time from a current location of a container handling vehicle <NUM> to a location of a specific storage container <NUM>; digging time; traffic situation including possible other container handling vehicles <NUM> blocking a path to the location of the storage container <NUM>; time when the container handling vehicle <NUM> is available; battery level of container handling vehicle <NUM>, etc..

Digging time is the time a container handling vehicle <NUM> will use to remove other storage containers <NUM> positioned above a target storage container <NUM> in a storage column <NUM>. Digging can be performed with the same container handling vehicle <NUM> that is used for transporting a target storage container <NUM> to the port <NUM>'. Alternatively, digging can be formed by dedicated container handling vehicles <NUM> used only for digging. In this case, digging time can be disregarded or at least reduced for the container handling vehicle <NUM> that is assigned a task, i.e. to deliver a specific storage container <NUM> at the port <NUM>'.

Based on said cost parameters, the next step is calculating end times and end positions of the container handling vehicles <NUM> when tasks assigned without a deadline are completed <NUM>.

As mentioned, this can be calculated according to cost parameters based on one or more of the following: time elapsed when driving from a current location of container handling vehicles <NUM> to a new location where a task is completed; other traffic influencing the container handling vehicle <NUM> when driving from its current location to the task; time when the container handling vehicles <NUM> is available; battery level of container handling vehicles <NUM>.

The next step of the method is to check if the container handling vehicles <NUM> can complete assigned tasks with a deadline after first finishing the tasks without a deadline. This check is performed by calculating time elapsed for the container handling vehicles <NUM> to perform the task with a deadline when starting from its location after first finishing the task without a deadline.

In one embodiment, checking can result in bonus points or penalty points given to container handling vehicles <NUM>. If the checking concludes that a container handling vehicle <NUM> cannot meet the deadline <NUM>, it is given a penalty point <NUM>. If the checking concludes that a container handling vehicle <NUM> can meet the deadline <NUM>, it is given a bonus point <NUM>.

In one embodiment, assigned but unfinished tasks without a deadline are reassigned to a different container handling vehicle <NUM> which has capacity within its schedule to complete the reassigned task without a deadline. In this way a container handling vehicle <NUM> can prioritize tasks with deadlines.

After this, the next step is ranking tasks assigned to the container handling vehicles <NUM> according to bonus and penalty points as well as estimated arrival times at the port <NUM>. Tasks that can be performed within the deadline, after first finishing a task without a deadline, are ranked first, and further according to arrival times of the container handling vehicles <NUM> at the port <NUM>'. An example is described below with reference to <FIG>.

The last step of the method is executing tasks by communicating instructions to the container handling vehicles <NUM> according to the ranking of tasks. The instructions comprise information of where to pick up a storage container and which storage container <NUM> it is as well as which port it shall be delivered to.

<FIG> is a table showing an example of tasks assigned to container handling vehicles <NUM>. Tasks without a deadline are indicated as <NUM> to <NUM> while tasks with a deadline are indicated as <NUM> to <NUM>. The table further shows if assigned container handling vehicles <NUM> can finish an assigned task without the deadline and still perform a task with the deadline. If yes, the task without a deadline is performed before the task with a deadline. If no, the task with a deadline is performed before the task without a deadline. This is reflected in the task priority column in the figure, e.g. for assigned vehicle <NUM> task <NUM> without deadline is performed before task <NUM> with deadline. The last column shows examples of arrival times at same designated port where storage containers <NUM> shall be delivered, i.e. arrival times at the port <NUM>' before the deadline for the task with deadline for each designated container handling vehicle <NUM>.

<FIG> is a table showing the resulting ranking of tasks and assigned vehicles as the tasks are being executed as instruction to the container handling vehicles <NUM>. The resulting ranking is based on the task priority and arrival times deduced in <FIG>. Container handling vehicles <NUM> arriving at the port <NUM>' first are ranked first, and container handling vehicles <NUM> arriving at the port just before the deadline are ranked last.

Tasks assigned for vehicles are executed and instructions are transmitted to each container handling vehicle <NUM> according to the ranked list. In this way, the operational capacity of each container handling vehicle <NUM> is better utilised since task without a deadline can be performed before tasks with a deadline if a container handling vehicle <NUM> can still perform an assigned task within a set deadline. Container handling vehicles <NUM> assigned to interact with the same port <NUM>' will then less likely to have to wait for each other to finish interacting with the port, i.e. interacting in the terms of delivering or retrieving storage containers <NUM> to or from the port <NUM>'.

The invention is further defined by a control system <NUM> for utilizing operational capacity of container handling vehicles <NUM> when assigned tasks of delivering or retrieving identified storage containers <NUM> at same port <NUM>', <NUM>' of an automatic storage and retrieval system <NUM> as the one described above with reference to <FIG>.

The control system <NUM> is described above with reference to <FIG> and comprises a master controller <NUM>, a database <NUM> keeping track of current locations of storage containers <NUM>, a routing planner <NUM> for finding optimal routes for the container handling vehicles <NUM> based on cost parameters, also described above, and a transmitter/receiver <NUM> for communicating instructions to each container handling vehicle <NUM>, preferably wirelessly. The control system <NUM> further comprises a processor arranged for running a computer program that when executed performs the method described above thereby utilizing operational capacity of container handling vehicles <NUM> when assigned tasks with and without deadlines.

Claim 1:
A method for utilizing operational capacity of container handling vehicles (<NUM>) when assigned tasks of delivering or retrieving identified storage containers (<NUM>) at same port (<NUM>') of an automated storage and retrieval system (<NUM>) comprising a framework structure (<NUM>) defining a storage grid (<NUM>) for storing storage containers (<NUM>) in storage columns (<NUM>), and where the storage containers (<NUM>) are handled by the container handling vehicles (<NUM>) running on top of the storage grid (<NUM>), and where the port (<NUM>') is used for transferring storage containers (<NUM>) to and from the storage and retrieval system (<NUM>), characterised in that the following steps are performed by a control system (<NUM>) communicating with a vehicle controller (<NUM>) in each container handling vehicle (<NUM>):
- assigning tasks without deadlines and with deadlines for the container handling vehicles (<NUM>) to arrive at the port (<NUM>');
- calculating end times and end positions of the container handling vehicles (<NUM>) when the assigned tasks without a deadline complete;
- checking if container handling vehicles (<NUM>) can meet a deadline after first completing a task without a deadline;
- ranking the tasks assigned to the container handling vehicles (<NUM>), where tasks that can meet the deadline, after first finishing a task without a deadline, are ranked first, and further according to arrival times of the container handling vehicles (<NUM>) at the port (<NUM>');
- executing tasks by communicating instructions to the container handling vehicles (<NUM>) according to the ranking of tasks.