Faculty Mechanical, Maritime and Materials Engineering

Transport Technology

Computer program, 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 Target Point.

In literature, many research publications can be found in the field of the routing of vehicles. In 1957, Dubins [3] 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.

x = 0
| x = -1
| x = -2
| x = -3
| |

y = 0 | 6.75 | 6.41 | 5.70 | 5.42 |

-1 | 5.99 | 5.41 | 4.76 | 5.00 |

-2 | 4.02 | 3.56
| 4.11 | 4.96 |

-3 | 4.14 | 4.29 | 4.77 | 5.46 |

x = 0 | x = -0.5 | x = -1 | x = -1.5 | x = -2 | x = -2.5 | x = -3 | x = -3.5 | x = -4 | |

y = -2 | 6.95 | 7.13 | 6.85 | 5.70 | 4.90 | 4.04 | 3.56
| 3.98 | 4.43 |

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)

Modified: 2006.11.10; logistics@3mE.tudelft.nl , TU Delft / 3mE / TT / LT.