Dynamic traffic based routing algorithm

Details Dynamic traffic based routing algorithm Dynamic traffic based routing algorithm

2000-06-30

2001-09-04

Cuchlinski, Jr., William A. (Department: 3661)

Data processing: vehicles, navigation, and relative location

Navigation

Employing position determining equipment

C701S200000, C340S992000, C073S17800T

Reexamination Certificate

active

06285951

ABSTRACT:

S
TATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT N/A
BACKGROUND OF THE INVENTION
Electrically powered vehicles are often used in manufacturing and warehouse environments for transporting and manipulating articles of manufacture. Such vehicles are desirable in such environments due to their clean operation and low noise. Often such vehicles are propelled along a fixed rail or track, allowing precise control of movement along a predetermined path.
In particular, computer controlled materials transport systems are known for moving materials among various work stations of a facility. Such systems are employed, as an example, in semiconductor fabrication facilities for moving semiconductor wafers to successive work stations. In such a wafer transport system, a monorail track is routed past the work stations and a plurality of electric vehicles are mounted on the track and moveable therealong for delivering wafers to successive work stations and for removing wafers therefrom after requisite processing operations have been accomplished. The track is composed of interconnected track sections that usually include one or more routing sections or modules that are operative to provide plural paths along the track. In general a node is a location where a vehicle is stopped, loaded, unloaded, or redirected. Thus, a node can be a workstation that a vehicle must pass through or an intersection of one or more tracks where the vehicle may be redirected.
The vehicles on the track can operate in two modes—connected or semi-independent. In connected operation, a central controller, usually a computer, assigns destinations to vehicles and monitors operation of the whole system even when the vehicles are not at a station.
In the past, the central controller has assigned a route to a vehicle based on a static routing algorithm that typically attempts to find the vehicle having the minimum distance from the destination node. This distance may include a static penalty referred to as a “node crossing value” for each node that the vehicle must pass through on the route to the destination node. However, the static routing algorithms are unable to adjust to exigent circumstances that may exist within the materials transport systems such as traffic congestion and other delays due to equipment. In addition, many computer controlled materials transport systems have at least two levels, or zones. These different levels or zones often have a limited capability for transporting vehicles therebetween. For example, in a two level system the two levels may be connected by a single vertical switch, which due to its height and speed may create an area of traffic congestion.
It would therefore be desirable to be able to compute a vehicle route using a dynamic routing algorithm that is able to respond to exigent circumstances within the materials transport system and that is able to minimize the vehicle traffic between different levels or zones.
BRIEF SUMMARY OF THE INVENTION
In accordance with the present invention, a method and system is disclosed for dynamically routing a material transport vehicle using traffic based parameters. A controller is directed to allocate a material transport vehicle to a particular node, and the controller selects the material transport vehicle that is physically closest to the particular node. The controller identifies the possible routes between the initial node of the material transport vehicle and the destination node. The controller analyzes each of the nodes within each identified route according to a metric function, and selects the route for the material transport vehicle having the smallest metric function value. The metric function may include data associated with each of the nodes in the material transport system including a node-to-node distance parameter, a node crossing parameter, and the number of material transport vehicles in a queue at each node within the route. In one embodiment, the metric function is:
M
=
∑
i
=
1
N
⁢
[
L
i
+
D
i
⁡
(
1
+
V
i
)
]
.


REFERENCES:
patent: 5283739 (1994-02-01), Summerville et al.
patent: 6078865 (2000-06-01), Koyanagi

Affiliated with

Also associated with

Rating

Dynamic traffic based routing algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic traffic based routing algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic traffic based routing algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2547823