M. van der Zee
Dynamic free range routing for automatic guided vehicles
Masters thesis,
Report 2005.TL.6969, Transport Engineering and Logistics.
In this thesis an algorithm is presented that allows for dynamic free
range route planning of automatic guided vehicles (AGVs). This routing
algorithm is based on the route choice methodology from the NOMAD
microscopic pedestrian behavioral model.
When designing AGV systems, six design issues can be distinguished, namely
vehicle design, facility layout, fleet size, idle vehicle management, control
system design and operational procedure design. This thesis focuses on one of
these operational procedures.
Operational procedure design consists of defining procedures for dispatching,
scheduling and routing. Dispatching is the process of assigning a
transportation job to an AGV, where scheduling is the process of dispatching a
set of AGVs to a batch of transportation jobs. Routing is the process of
determining routes for a set of AGVs to fulfill their respective transportation
jobs. In this thesis, a new AGV routing methodology is presented. A routing
procedure can be static or dynamic. In the case of dynamic routing, input
information is used that evolves real-time, whereas in static routing
information is assumed to be fixed and known throughout route execution.
Routes can be determined for all AGVs in the system at one central location or
locally at each AGV. Routing procedures that combine local and central routing
are termed distributed.
Up until now, AGVs use a map of predefined, fixed paths that are combined
to obtain routes along which they move from origin to destination point.
The problem of scheduling and routing is addressed as a vehicle routing
problem (VRP). Using fixed paths was historically defined, but also allows
for reliable automation of vehicles with limited maneuverability.
The use of fixed paths posts some problems. Routes are unnecessary long,
which leads to high transportation times and low system throughput. Path
segments are shared between routes for multiple vehicles, which leads to
congestion and deadlocks during route execution. Furthermore, the routing
process is vulnerable to disruptions, for example if path segments cannot
be used during operation due to vehicle break down.
Using dynamic information (on planned vehicle routes) and free range route
determination might provide solutions to these problems. It is expected
that the use of a dynamic free range routing process will result in better
facility area utilization and decreased route length with respect to the
fixed path routing case. Furthermore, it is expected that use of dynamic
information on AGV movements combined with free range movement
capabilities will allow for more flexible deadlock and congestion
avoidance mechanisms and smaller differences between planned and realized
arrival times. In the field of robotics, the problem of free range motion
planning for car-like mobile robots is addressed. Difficulty in this field
of motion planning is the fact that car-like mobile robots are in general
not capable movement perpendicular to their direction of movement. This
constraint on movement is termed a nonholonomic constraint. Solution
methods are developed that allow for motion planning for mobile robots
with nonholonomic constraints.
NOMAD is a microscopic pedestrian behavioral model, which is used to aid
in the design public places by predicting pedestrian traffic flows. It
assumes pedestrians to be economists that choose their walking
trajectories, activity areas, activity completion times and activity order
such as to minimize an expected cost function that reflects their personal
preferences.
In the NOMAD model a strategic, tactical and operational level are
distinguished. At the strategic level the activity choice of pedestrians is
modeled. The tactical level is concerned with scheduling of these activities,
route and destination choice and activity time choice. At the operational
level, the determined routes are executed. Of specific interest to this thesis
is the (free range) route choice mechanism.
A study of the NOMAD model has suggested that it might be useful for AGV
routing. When applied to AGV routing, it is not used as a predictive pedestrian
simulation tool, but as an optimized AGV control tool. The NOMAD model could be
interesting to dynamic free range routing of AGVs, because it allows for time
dependent determination of free ranging trajectories. Other interesting aspects
are the fact that the model uses a layered structure that is quite similar to
the structure for AGV system control adapted at the AGV laboratory and the fact
that it allows for the implementation of AGV specific behavior. Problems that
will have to be addressed are the fact that pedestrians are taken to be points
in space in the NOMAD model, which does not apply to AGVs. Furthermore, AGVs
have kinematic constraints that do not apply to pedestrians. Finally, AGVs put
strict requirements on their orientation at the start and end of their
trajectories.
An AGV routing algorithm is designed that makes use of the free range
route choice mechanism of the NOMAD model. As starting point for this
routing algorithm, an approach to AGV system control is used that
distinguishes a strategic, tactical and operational level. In this thesis,
the routing part of the tactical level is addressed.
Adapted AGV system control approach
The routing algorithm dynamically determines free ranging trajectories
that are optimized regarding arrival time, the avoidance of static
obstacles and the planned trajectories of other AGVs.
The routing algorithm was implemented in a software component in Object
Pascal for Borland Delphi 7. This component was found to be able to
determine free range trajectories with sufficient accuracy within
computation times that allow for real time local application on AGVs.
To evaluate the routing algorithm, the component was implemented in a
simulation. This simulation showed that free range trajectories were
determined that on average are 19% shorter than routes determined using a mesh
routing algorithm and 53% shorter than routes determined using a loop routing
algorithm. The simulation showed that the routing algorithm effectively takes
static obstacles and other vehicles into account. A reliable method for time
window arrival was implemented. Moreover, up to a certain fleet size,
trajectories were shown to have admissible midsections that do not violate the
nonholonomic constraints on the vehicle.
It is recommended that the routing algorithm is further tested by
implementing a suitable operational controller. This way, the influence of
the routing algorithm on system throughput, safety and reliability can be
investigated under stochastic (operational) influences. Finally
suggestions are made with regard to the possibility of saving computation
time and with regard to additional features that could be implemented in
the routing algorithm.
Reports on Transport Engineering and Logistics (in Dutch)
Modified: 2005.07.07;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.