Researchers Gabriel Homsi, Rafael Martinelli, Thibaut Vidal, and Kjetil Fagerholt have made significant strides in addressing the complexities of maritime logistics with their latest study on industrial and tramp ship routing problems. Their work, titled “Industrial and Tramp Ship Routing Problems: Closing the Gap for Real-Scale Instances,” introduces innovative solutions to challenges that have long plagued the shipping industry.
The study focuses on a general ship routing problem that incorporates a wide array of real-world constraints, including pickups and deliveries, cargo selection, ship-dependent starting locations, travel times and costs, time windows, and incompatibility constraints. These factors collectively present substantial hurdles for both exact and heuristic methods, with some instances involving as few as 18 cargoes remaining unsolved. To tackle these challenges, the researchers developed an exact branch-and-price (B&P) algorithm and a hybrid metaheuristic.
The B&P algorithm is designed to generate elementary routes while leveraging decremental state-space relaxation to accelerate column generation. It also employs heuristic strong branching, along with advanced preprocessing and route enumeration techniques. This method has proven highly effective, optimally solving 239 out of 240 existing instances within a one-hour timeframe. Furthermore, scalability experiments have demonstrated its capability to optimally solve problems involving around 60 ships and 200 cargoes, equating to 400 pickup and delivery services. For the largest cases with up to 260 cargoes, the algorithm achieves optimality gaps of less than 1.04%.
Complementing the B&P algorithm, the researchers developed a sophisticated hybrid metaheuristic. This approach extends the unified hybrid genetic search, utilizing a set-partitioning phase and problem-tailored variation operators to efficiently handle all the problem characteristics. The metaheuristic has outperformed all previous heuristics, producing near-optimal solutions within minutes. This is particularly noteworthy as these instances are comparable in size to the largest problems routinely solved by shipping companies.
The practical applications of this research are substantial. By providing tools that can optimally solve complex routing problems, shipping companies can enhance their operational efficiency, reduce costs, and improve service reliability. The ability to handle real-scale instances means that these solutions can be directly applied to the day-to-day operations of maritime logistics, offering significant benefits to the industry.
In summary, the work of Homsi, Martinelli, Vidal, and Fagerholt represents a significant advancement in the field of maritime logistics. Their innovative algorithms and metaheuristics offer practical, scalable solutions to longstanding challenges, paving the way for more efficient and effective shipping operations. Read the original research paper here.