Convex Formulation of the Maritime Fleet Size and Mix Problem Considering Battery Electric Ships

This paper focuses on the problem of determining a minimum-cost fleet of battery electric ships for a given liner shipping operation. The problem is strongly nonlinear and includes integer-valued decision variables, which make it intractable for most real-world instances. The conventional approach in the literature is to formulate a linear approximation by restricting available ship types to a small number of predetermined alternatives. Contrary to the conventional linearization approach, this paper models the nonlinearities directly. We show that the problem exhibits a hidden convex structure uncovered by changes of variables. Computational experiments show that our convex formulation achieves 15.1\% lower fleet cost on average and reduces the solve time by at least 10x compared to the linear formulation. The solve time advantage is attributed to the elimination of binary variables associated with ship type selection. Our implementation is available at https://users.aalto.fi/~aritari/convex_ESFSMP.html.