Optimizing Maritime Passenger Transfer in Rich Vehicle Routing Problem Using a Hybrid Genetic Algorithm

Abstract

Ship routing is a fundamental component of maritime passenger logistics, involving the careful planning of sea routes to facilitate the efficient and comfortable transportation of passengers. However, the ship routing problem presents unique challenges in the transit network design, encompassing various Vehicle Routing Problem (VRP) variants. These challenges arise from complex characteristics including multiple depots, ship types, and asymmetric distances between ports. This study aims to minimize passenger transfers in ship routing by incorporating constraints on maximum distance and travel time. To address these challenges, we propose a two-step approach: a hybrid Genetic Algorithm (GA) that incorporates the Fixed Radius Near Neighbor (FRNN) heuristic method alongside GA optimization. Moreover, a comparison was conducted between our proposed hybrid GA and both the standalone FRNN and conventional GA. The comparative analysis demonstrated that the hybrid GA outperformed both the FRNN and the standard GA in the reduction of passenger transfers and attainment of optimal fitness values. This highlights the significance of incorporating various optimization methodologies to enhance performance. Subsequent studies should investigate the mechanisms underlying the success and suitability of hybrid GA in practical maritime logistics scenarios.

Keywords

• VRP
• multi-depot
• asymmetric
• heterogeneous
• ship routing
• passenger transit