Marine Traffic Optimization Using Petri Net and Genetic Algorithm
AbstractThe 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.
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
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).