Modeling of Schedule-Based Path Planning for Automated Vehicles Guided by Uni-Directed Rails
Rei Hino and Hiroki Tsuji
Department of Mechanical Science and Engineering, Graduate School of Engineering, Nagoya University, Furo-cho, Chikusa-ku, Nagoya 464-8603, Japan
The aim of this paper is to construct a specialized method of path planning for transportation in a conveyance system composed of automated vehicles running on uni-directional rails in a manufacturing factory. In the conveyance system, there exist redundant rails in addition to the rails that directly connect any two production resources. Every vehicle is permitted to run on roundabout rails to avoid other vehicles stopped on the rail in front of the production resource, thus allowing it to arrive at its destination in a shorter time. The adoption of roundabout rails creates multiple candidates for the transportation path between two resources, and the performance of the conveyance system depends on the path that is selected. In the present paper, a new set of formulations is defined to describe the movements of the vehicles, and the conveyance plans are represented on a Gantt chart as a future schedule for all vehicles. The defined formulations give the exact scheduled time at both edges of the rail, i.e., they neglect the status of the vehicles between nodes. We also explain a practical path-planning procedure to generate an appropriate path through the adoption of Dijkstra’s algorithm, referring to the times represented on the Gantt chart, and the validity of the procedure is examined by computational simulation.
-  L. Qiu, W. J. Hsu, S.-Y. Huang, and H.Wang, “Scheduling and routing algorithms for AGVs: a survey,” Int. J. Production Research, Vol.40, No.3, pp. 745-760, 2002.
-  C. W. Kim and J. M. A. Tanchoco, “Conflict-free shortest-time bidirectional AGV routing,” Int. J. of Production Research, Vol.29, No.12, pp. 2377-2391, 1991.
-  D. J. Bertsimas and D. Simchi-Levi, “A new generation of vehicle routing research: robust algorithms, addressing uncertainty,” Operations Research, Vol.44, No.2, pp. 286-304, 1996.
-  T. Ganesharajah, N. G. Hall, and C. Sriskandarajah, “Design and operational issues in AGV-served manufacturing systems,” Annals of Operations Research, Vol.76, pp. 109-154, 1998.
-  E. Roszkowska, “Recognizing and Handling the Livelock Problem in AGV Systems,” 2004 IEEE Int. Conf. on Systems, Man and Cybernetics, pp. 1637-1642, 2004.