IJAT Vol.6 No.2 pp. 228-234
doi: 10.20965/ijat.2012.p0228


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

September 27, 2011
January 19, 2012
March 5, 2012
path planning, schedule, Dijkstra’s algorithm, shortest time path, uni-directional rail

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.

Cite this article as:
Rei Hino and Hiroki Tsuji, “Modeling of Schedule-Based Path Planning for Automated Vehicles Guided by Uni-Directed Rails,” Int. J. Automation Technol., Vol.6, No.2, pp. 228-234, 2012.
Data files:
  1. [1] 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.
  2. [2] 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.
  3. [3] 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.
  4. [4] 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.
  5. [5] E. Roszkowska, “Recognizing and Handling the Livelock Problem in AGV Systems,” 2004 IEEE Int. Conf. on Systems, Man and Cybernetics, pp. 1637-1642, 2004.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Mar. 05, 2021