Conflict-free Dynamic Route Multi-AGV Using Hybrid Dijkstra Floyd-Warshall Algorithm With Time Windows

Soli - chudin

Abstract


Autonomous Guided Vehicle is a mobile robot that can move autonomously on a track or lane in an indoor or outdoor environment while performing a series of tasks. Determination of the shortest route on an autonomous guided vehicle is one of the optimization problems in handling the free route that has an influence on the distribution of goods in the manufacturing industry warehouse. The pick-up and pick-drop process in the distribution of AGV goods such as pickup, transportation and delivery of goods with short mileage characteristics is very possible to do simulations with three AGV vehicle unit load type. There are time windows constraints on workstations that limit delivery. The problem of determining the route in this study is deemed necessary as a multi-vehicle routing problem with a time window. This study aims to describe the combination of algorithms written based on dynamic programming to overcome the problem of AGV conflict-free routing using time windows. The combined approach of the dijkstra and floyd-warshall algorithms is applied as an optimization goal to improve algorithm performance.


Keywords


Conflict-free route; Dynamic programming; Hybrid algorithm; Time windows

References


V. Jaiganesh, D. K. J, and J. Girijadevi, “Automated Guided Vehicle with Robotic Logistics System,” in Procedia Engineering, 2014, vol. 97, pp. 2011–2021.

D. Antakly et al., “A Temporised Conflict-Free Routing Policy for AGVs,” IFAC- Pap., vol. 50, no. 1, pp. 1–7, 2018.

S. M. Homayouni, S. H. Tang, N. Ismail, M. K. A. M. Ariffin, and R. Samin, “A Hybrid Genetic-Heuristic Algorithm for Scheduling of Automated Guided Vehicles and Quay Cranes in Automated Container Terminals,” in Conference: 39th Computer and Industrial Engineering (CIE39), 2009, pp. 96–101.

L. Xu, Y. Wang, L. Liu, and J. Wang, “Exact and Heuristic Algorithms for Routing AGV on Path with Precedence Constraints,” Hindawi Publishing Corporation, vol. 2016, Chengdu, China, pp. 1–9, 2016.

E. Gawrilow, “Dynamic Routing of Automated Guided Vehicles in Real-time Dynamic Routing of Automated Guided Vehicles in Real-time ¨ rn Stenzel,” in Mathematics Key Technology for The Future, no. January, Berlin, Germany: ResearchGate, 2008, pp. 165–177.

N. Smolic-rocak, S. Bogdan, Z. Kovacic, and T. Petrovic, “Time Windows Based Dynamic Routing in Multi-AGV Systems,” IEEE Trans. Autom. Sci. Eng., vol. 7, no. 1, pp. 151–155, 2010.

E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numer. Math., vol. 271, no. 1, pp. 269–270, 1959.

R. W. Floyd, “ORDER ARITHMETIC procedure,” Algorithm, vol. 5, no. 6, pp. 344–348, 1962.

Q. I. U. Ling and H. S. U. Wen-jing, “Conflict-free AGV Routing in a Bi-directional Path Layout,” pp. 1–12.

S. Peyer, D. Rautenbach, and J. Vygen, “A generalization of Dijkstra ’ s shortest path algorithm with applications to VLSI routing,” J. Discret. Algorithms, vol. 7, no. 4, pp. 377–390, 2009.

M. Hamzeei, R. Zanjirani, and H. Rashidi-bejgan, “An exact and a simulated annealing algorithm for simultaneously determining flow path and the location of P / D stations in bidirectional path,” J. Manuf. Syst., vol. 32, no. 4, pp. 648–654, 2013.

T. Nishi and Y. Tanaka, “Petri Net Decomposition Approach for Dispatching and Conflict-Free Routing of Bidirectional Automated Guided Vehicle Systems,” in The 4th IEEE International Conference on Automation Science and Engineering, 2012, vol. 42, no. 5, pp. 1230–1243.

D. Lauzon and D. Riopel, “Dispatching , Routing , and Scheduling of Two Automated Guided Vehicles in a Flexible Manufacturing System,” Int. J. Flex. Manuf. Syst., vol. 8, pp. 247–262, 1996.

P. Taylor, C. M. Klei, and J. Kim, “AGV dispatching,” Int. J. Prod. Res., vol. 34, no. September 2013, pp. 37–41, 2007.

E. Gawrilow, M. Klimm, and R. H. Mo, “Conflict-free vehicle routing,” EURO J. Transpot Logist., vol. 1, pp. 87–111, 2012.

U. A. Umar, M. K. A. Ariffin, N. Ismail, and S. H. Tang, “Conflict-Free Automated Guided Vehicles Routing Using Multi-Objective Genetic Algorithm,” Res. J. Appl. Sci. Eng. Technol., vol. 6, no. 14, pp. 2681–2684, 2013.

A. I. Corréa, A. Langevin, and L. Rousseau, “Scheduling and routing of automated guided vehicles : A hybrid approach,” in Computers & Operations Research, 2007, vol. 34, pp. 1688–1707.

W. Malopolski, “A sustainable and conflict-free operation of AGVs in a square topology,” Comput. Ind. Eng., vol. 126, no. October, pp. 472–481, 2018.

E. U. Rotterdam and D. Version, “Positioning automated guided vehicles in a loop layout,” Eindhoven University of Technology, vol. 9731, no. 1997, Rotterdam, Netherlands, pp. 1–19, 2019.

Z. Zhang, Q. Guo, J. Chen, and P. Yuan, “Collision-Free Route Planning for Multiple AGVs in an Automated Warehouse Based on Collision Classification,” in IEEE Access, 2018, vol. 6, pp. 26022–26035.

Y. Akturt, “Scheduling of AGV in decision making hierarchi.pdf,” Int. J. Prod., vol. 34, no. 2, pp. 577–591, 1996.

N. Azi, M. Gendreau, and J. Potvin, “An exact algorithm for a single-vehicle routing problem with time windows and multiple routes,” Eur. J. Oper. Res., vol. 178, pp. 755–766, 2007.

N. A. El-sherbeny, “The Algorithm of the Time-Dependent Shortest Path Problem with Time Windows,” Sci. Res., vol. 5, no. October, pp. 2764–2770, 2014.

Y. Dumas, J. Desrosiers, E. Gelinas, and M. M. Solomon, “An Optimal Algorithm for the Traveling Salesman Problem with Time Windows,” Oper. Res. Proc., vol. 43, no. April 1995, pp. 1–7, 2016.




DOI: http://doi.org/10.11591/ijece.v10i4.pp%25p
Total views : 19 times

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.