CONFLICT-FREE SHORTEST-TIME BIDIRECTIONAL AGV ROUTEING

被引：151

作者：

KIM, CW

TANCHOCO, JMA

机构：

[1] School of Industrial Engineering, Purdue University, West Lafayette, IN

来源：

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH | 1991年 / 29卷 / 12期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1080/00207549108948090

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

This paper presents an efficient algorithm for finding conflict-free shortest-time routes for automated guided vehicles moving in a bidirectional flow path network. The proposed algorithm is based on Dijkstra's shortest-path method. It maintains. for each node, a list of time windows reserved by scheduled vehicles and a list of free time windows available for vehicles to be scheduled. We introduce the concept of time window graph in which the node set represents the free time windows and the arc set represents the reachability between the free time windows. Then the algorithm routes the vehicles through the free time windows of the time window graph instead of the physical nodes of the flow path network. It requires o(nu-4n2 computations in the worst case, where nu is the number of vehicles and n is the number of nodes.

引用

页码：2377 / 2391

页数：15

共 7 条

[1]

Broadbent A.J., Besant C.B., Premi S.K., Walker S.P., Free ranging AGV systems: Promises, problems and pathways, Proc. 2Nd Int. Conf. On Automated Materials Handling, (1985)

[2]

Dukstra E.W., A note on two problems in connexion with graphs, Numerische Mathematik, 1, pp. 269-271, (1959)

[3]

Egbelu P.J., Tanciioco J., Characterization of automatic guided vehicle dispatching rules, Int. J, Prod. Res, 22, 3, pp. 359-374, (1984)

[4]

Fujii S., Sandoh H., Hohzake R., A routeing control method of automated guided vehicles by the shortest path with time-windows, Presented in 10Th Int. Conf. On Prod. Res., (1989)

[5]

Huang J., Palekar U.S., Kapoor S.G., A labelling algorithm for the navigation of automated guided vehicles, Advances in Manufacturing Systems Engineering (Proc. Winter Annual Meeting of the ASME, 37, pp. 10-15, (1989)

[6]

Nilsson N., Principles of Artificial Intelligence, (1980)

[7]

Taghaboni F., Tanchoco J., A LISP-based controller for free-ranging automated guided vehicle systems, Int. J. Prod. Res, 26, 2, pp. 173-188, (1988)

← 1 →