Modeling of Schedule-Based Path Planning for Automated Vehicles Guided by Uni-Directed Rails

Rei Hino; Hiroki Tsuji

doi:10.20965/ijat.2012.p0228

single-au.php

« previous

IJAT Vol.6 No.2 pp. 228-234

doi: 10.20965/ijat.2012.p0228

(2012)

Paper:

Views over last 60 days: 710

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

Received:

September 27, 2011

Accepted:

January 19, 2012

Published:

March 5, 2012

Keywords:

path planning, schedule, Dijkstra’s algorithm, shortest time path, uni-directional rail

Abstract

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:

R. Hino and H. 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:

References

[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] 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] 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] 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] 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 article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[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.