Marine Traffic Optimization Using Petri Net and Genetic Algorithm

Gudelj, Anita; Kezić, Danko; Vidačić, Stjepan · 1970 · Crossref

DOI: 10.7307/ptt.v24i6.1199

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the optimization of marine traffic control and job scheduling within marine canal traffic systems (MCTS). The primary research problem involves managing vessel movement through shared resources, such as canals and locks, to ensure safe passage, resolve conflicts, avoid deadlocks, and minimize total completion times. The authors identify this as a discrete event dynamic system (DEDS) problem that is NP-hard due to resource constraints, precedence relations, and the need for simultaneous conflict and deadlock avoidance. The motivation stems from the need to balance the vessel owners' desire for quick movement with the economical utilization of limited resources. To solve this, the authors propose a novel integration of Petri Net (PN) modeling with a Genetic Algorithm (GA). Specifically, they utilize the MRF1PN class, a subclass of flowline system Petri nets designed for analyzing multi-class re-entrant flowline systems. This class allows for a matrix-based formal description of the system structure, which facilitates integration with GA. The methodology employs P-timed Petri nets to model the system dynamics, including resource availability and job durations. The GA serves as the optimization engine, using indirect encoding where chromosomes represent project priorities, delay times, and resource release dates. A schedule generator decodes these chromosomes into parameterized active schedules, which are then checked for conflicts and deadlocks using the PN structural analysis. The fitness function for the GA is the minimum makespan. The approach is verified through a computer simulation in a MATLAB environment using a specific case study of a marine canal system. The system consists of three shared canals and four directional basins with defined capacity constraints. The Petri net model includes places for resources, jobs, and control supervisors to prevent forbidden states. The simulation demonstrates the algorithm's ability to generate conflict-free and deadlock-free schedules. The evolutionary process uses an elitist strategy, copying the best 20% of individuals, mutating the worst 30%, and using crossover for the remainder. The results confirm that the integrated PN-GA framework can effectively handle multi-project, multi-constrained scheduling problems with shared resources. The significance of this work lies in providing a rigorous, automated method for optimizing marine traffic systems that are traditionally difficult to manage due to complex resource dependencies. By combining the structural analysis capabilities of Petri nets with the global search efficiency of Genetic Algorithms, the authors offer a solution that ensures safety (deadlock avoidance) while optimizing efficiency (minimizing makespan). This approach is applicable not only to marine traffic but also to other flexible manufacturing systems and resource-constrained scheduling problems where real-time control and optimization are required.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• gap acceptance