R. van Heffen
Optimal positioning of AGV target points under quay and stacking cranes
Report 2006.TL.7091, Transport Engineering and Logistics.
In a new model for dynamic route planning of AGV's on a container terminal,
the traditional fixed routes defined by transponders embedded in the track
are replaced by arbitrary routes between quay and stack. These routes are
created using the DEFT Model (Dynamic Evasive Free-range Trajectory), which
computes the shortest route for every individual AGV movement between stack
and quay, evading collisions with other vehicles.
The AGV's are parked parallel at the quay and stack areas to wait before they
are handled. Because the DEFT model does not specify the angle at which a
vehicle will reach its destination, it can not be used to enter the quay or
stack parking positions directly. An intermediate target point (TP) must be
used which connects the calculated DEFT route with the final position of the
AGV. The goal of this assignment is to optimize the positioning of this
In literature, many research publications can be found in the field of the
routing of vehicles. In 1957, Dubins  described how any position can be
reached using three movements at maximum, straight or curved. Because no
analytical solution for determining the Dubins paths could be found, it was
decided to construct the paths geometrically. Six different configurations
of Dubins paths exist, and each path is constructed separately. All Subpaths
of these configurations can be constructed with the same calculations. For
the construction of the paths, curves have been assumed to be attained
instantly (infinite steering speed).
The final model calculates the path length between two arbitrary positions.
These positions are first converted into one destination (x, y,
f) with starting point (0, 0, 0). Using the
minimum radius of the vehicle, the path length for every Dubins path can
then be calculated using the standard geometric properties of each path type.
The software implements this model in a program with a user interface. The
user can define the terminal configuration (Target Point, Lane Orientation,
Lane Distance, Number of Lanes, Angle Range, Minimum Radius) and the number
of AGV's that should be sampled in the simulation. The configuration can be
previewed for visual confirmation, and sample paths can be calculated and drawn
to test the model and the configuration.
The simulation part of the program samples a predefined number of AGV's with
an arbitrary starting position and target lane. The shortest path length is
calculated for each AGV and the data is stored. When the simulation is
finished, the average path length for all calculated shortest paths is
presented to the user, and additional data and statistics are available for
further analysis of the simulation results.a
Two experiments have been defined to test the target point optimization
using the program, one typical quay area and one typical stack area. For
each configuration, a grid of possible target points is chosen. For each
target point in the grid, a simulation was done to calculate the average
shortest path length of the target point. Combining these data, the point
with the lowest average path length was selected. This represents the
optimal position for the target point, in terms of path length.
The results of both experiments are shown in Table 1 and Table 2. For each
possible target point position (x, y), the calculated average shortest path
length is shown. The lowest value represents the optimal position and is
printed in bold.
Table 1: Average Shortest Path Lengths of the Quay Area Experiment
|| x = 0
|| x = -1
|| x = -2
|| x = -3
| y = 0
Table 2: Average Shortest Path Lengths of the Stack Area Experiment
|| x = 0
|| x = -0.5
|| x = -1
|| x = -1.5
|| x = -2
|| x = -2.5
|| x = -3
|| x = -3.5
|| x = -4
| y = -2
The results of the experiments show that the optimal target point position
indeed exists and can be found using the program. Points close to the target
require extra path length to reorient the vehicle. Points far away from the
target require extra path length to cover the distance. The optimum position
is located in between.
From additional simulation data it was found that the average shortest path
length of the Quay configuration can be improved by requiring arrival angles
to be positive (not facing away from the target lanes). The Stack configuration
did not show this kind of improvement possibilities.
Other criteria can be used for improvement of target points as well. By
analyzing the standard deviations of the possible target points, positions with
a low average value but some relatively high path lengths can be located and
possibly replaced by a position without the higher path lengths. Although this
would result in a higher average path length, this extra path length can be
subtracted from the DEFT route, and therefore not necessarily has to be a problem.
The influence of the target lanes is another possible improvement of the target
point analysis. Some lanes might require relatively high path lengths. By sorting
the path length data per target lane, inefficient lanes can be excluded or given
a lower priority to improve the general performance of the target point.
Besides the AGV target point optimization, the model for the path synthesis
can be used for the short distance route calculation of any holonomic moving
vehicle in general. By introducing continuous curvature bends (finite
steering speed) the model could be further improved.
Reports on Transport Engineering and Logistics (in Dutch)
, TU Delft