The Optimal Arrangement of Boats in a Coastal Maritime Passenger Lines System Using Graph Theory

This paper presents research in the field of optimization in maritime passenger traffic that can ensure the long-term sustainability of coastal maritime passenger lines system. For the purpose of the research contained in this paper, it has been hypothesized that the optimal arrangement of boats within a coastal maritime passenger lines system will reduce the consumption of propulsion energy, the emission of harmful gasses and operating costs. The aim of this paper is to present an efficient algorithm for a reduction in propulsion energy consumption in coastal maritime passenger lines systems by reassigning boats to lines that they service. The problem is modeled using a bipartite graph and the solution is obtained by searching for optimal matching using Edmonds’ algorithm. The authors apply, for the first time, Edmonds’ algorithm to the problems of the optimization of assignments of boats to lines. The research results were confirmed by tests on a representative example. The optimization results on only 10 ships in the given example show yearly savings of 91,097.30 L of fuel (lowering costs by EUR 69,233.95) and reducing CO 2 by 243.59 tons, which proves that this algorithm found a much more efficient arrangement that could result in a significant reduction in propulsion energy consumption, thus providing economic and ecological benefits.