Marine Traffic Optimization Using Petri Net and Genetic Algorithm

  • Anita Gudelj
  • Danko Kezić
  • Stjepan Vidačić
Keywords: marine traffic system, optimization, deadlock avoidance, genetic algorithm, Petri net

Abstract

The paper deals with the traffic control and job optimization in the marine canal system. The moving of vessels can be described as a set of discrete events and states. Some of these states can be undesirable such as conflicts and deadlocks. It is necessary to apply adequate control policy to avoid deadlocks and blocks the vessels’ moving only in the case of dangerous situation. This paper addresses the use of Petri net as modelling and scheduling tool in this context. To find better solutions the authors propose the integration of Petri net with a genetic algorithm. Also, a matrix based formal method is proposed for analyzing discrete event dynamic system (DEDS). The algorithm is developed to deal with multi-project, multi-constrained scheduling problem with shared resources. It is verified by a computer simulation using MATLAB environment.

References

Degre, T.: The Management of Marine Traffic: A Survey of Current Future Measures, Journal of Navigation, Vol. 48, 1995, pp. 53-69

Kezić, D., Perić, N., Petrović, I.: A Petri Net Approach of Deadlock Prevention in Marine Traffic System, In Proceeding of the IEEE International Symposium on Industrial Electronics, Croatia, Vol. 1, 2005, pp. 217–222

Kezić, D., Gudelj, A.: Design of River System Deadlock Avoidance Supervisor By Using Petri Net, PROMET, Vol. 22, No. 3, 2010, pp. 215-221

Blazewicz, J., et al.: Scheduling Subject to Resource Constraints: Classification and Complexity, Discrete Applied Mathematics, Vol. 5, 1983, pp. 11-24

Kofjač, D., Kljajić, M.: Application of Genetic Algorithms and Visual Simulation in a Real-Case Production Optimization, Transactions on System and Control, Vol. 3, No. 12, 2008, pp. 992-1001.

Yoshikawa, M., Terai, H.: Genetic Algorithm Engine for Scheduling Problems, WSEAS Transactions on Circuits and Systems, Vol. 5, No. 3, 2006, pp. 397-402

Ezpeleta, J., et al.: A Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems, IEEE Trans. on Robotics and Automation, Vol. 11, No. 2, 1995, pp. 173-184

Lautenbach, L., Ridder, H.: The Linear Algebra of Deadlock Avoidance – A Petri Net Approach, Research Report of Institute for Computer Science, Germany, 1996.

Lewis, F., et al.: Analysis of Deadlocks and Circular Waits Using A Matrix Model for Discrete Event Systems, Automatica, Vol. 34, No. 9, 1998, pp. 0-19

Tricas, F., et al.: An Iterative Method For Deadlock Prevention In FMS, in Proceeding of 5th Workshop Discrete Event System, Belgium, 2000, pp. 139 – 148

Murata, T.: Petri Nets: Properties, Analysis, and Applications, In Proceedings of the IEEE, Vol. 77, No. 4, 1989, pp. 541 – 580

Bogdan, S., Lewis, F.L., Kovačić, Z., Mireles, J.: Manufacturing Systems Control Design – A Matrix-Based Approach, Springer London, U.K., 2006, pp. 1290–1292.

Mireles, J., Lewis, F.: Deadlock Analysis and Routing on Free-Choice Multipart Re-entrant Flow Lines Using a Matrix-Based Discrete Event Controller, In Proceedings of the IEEE International Conference on Decision and Control, Vol. 1, 2002, pp. 793-798

Holland, J.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975.

Cavalieri, S.: Petri Nets and Genetic Algorithms to Increase Productivity in FMS, In Proceedings of 2nd Conf. on Knowledge-Based Intelligent Electronic Systems, Australia, 1998.

Chen, J.H., Fu, L.C., M.H. Lin, Huang, A.C.: Petri-Net and GA-Based Approach to Modelling, Scheduling, and Performance Evaluation for Wafer Fabrication, IEEETransactions on Robotics and Automation, Vol. 17, No. 5, 2001, pp. 619-636

Bogdan, S., Lewis, F.L.: Matrix Approach to Deadlock Avoidance of Dispatching in Multi-Class Finite Buffer Re-entrant Flow Lines, Intelligent Control, in Proceedings of IEEE International Symposium, No. 16-18, 1997, pp. 397–402

Goncavles, J.F., Mendes, J.M., Resende, M.G.C.: A Hybrid Genetic Algorithm for the Job Shop Scheduling Problem, European Journal of Operational Research, Vol. 167, 2005, pp. 77-95

Leon, V.J., et al.: Strength and Adaptability of Problem-Space Based Neighbourhoods for Resource Constrained Scheduling, Operations Research Spectrum, Vol. 17, 1995, pp. 173–182

How to Cite
1.
Gudelj A, Kezić D, Vidačić S. Marine Traffic Optimization Using Petri Net and Genetic Algorithm. PROMET [Internet]. 1 [cited 2019Dec.8];24(6):469-78. Available from: http://traffic.fpz.hr/index.php/PROMTT/article/view/1199
Section
Articles