The offshore mobile charging vessel location and electric vessels charging scheduling problem

Electric vessels (EVs) are increasingly adopted in maritime transportation to meet the demands of green shipping due to their zero-emission, low noise, and cost-efficiency. However, EVs face operational challenges due to their limited battery capacity, requiring charging arrangements during voyages to maintain continuous service. Addressing this challenge, this paper investigates the offshore mobile charging vessel location and electric vessel charging scheduling problem (OMCVL-EVCSP). We first formulate the problem as a mixed-integer linear program (MILP). Considering the NP-hard of the problem, we then develop a parallel adaptive large neighborhood search (PALNS) algorithm based on the problem structure. The proposed PALNS utilizes a greedy heuristic method to construct multiple initial feasible solutions, designs some problem-specific destroy and repair operators, and then uses a local search mechanism to improve the solution during each iteration. To evaluate the performance of the proposed PALNS algorithm, we further develop two metaheuristic methods, namely, improved artificial bee colony (IABC) and adaptive genetic algorithm (AGA). Computational experiments on randomly generated instances demonstrate that the proposed PALNS achieves the best performance, outperforming the commercial solver CPLEX and metaheuristic methods in terms of both solution quality and computational efficiency. Besides, we apply the proposed PALNS method to solve a case study, demonstrating its practicality and generating valuable managerial insights for the maritime domain.