A GRASP-based multi-objective approach for the tuna purse seine fishing fleet routing problem
针对金枪鱼围网船队航线规划问题，提出两种双目标混合整数线性规划模型，并用多目标贪婪随机自适应搜索算法求解，发现协作策略可显著降低油耗（17.3%）和海上时间（10.1%）。
Nowadays, the world’s fishing fleet uses 20% more fuel to catch the same amount of fish compared to 30 years ago. Addressing this negative environmental and economic performance is crucial due to stricter emission regulations, rising fuel costs, and predicted declines in fish biomass and body sizes due to climate change. Investment in more efficient engines, larger ships and better fuel has been the main response, but this is only feasible in the long term at high infrastructure cost. An alternative is to optimize operations such as the routing of a fleet, which is an extremely complex problem due to its dynamic (time-dependent) moving target characteristics. To date, no other scientific work has approached this problem in its full complexity, i.e., as a dynamic vehicle routing problem with multiple time windows and moving targets. In this paper, two bi-objective mixed linear integer programming (MIP) models are presented, one for the static variant and another for the time-dependent variant. The bi-objective approaches allow to trade off the economic (e.g., probability of high catches) and environmental (e.g., fuel consumption) objectives. To overcome the limitations of exact solutions of the MIP models, a greedy randomized adaptive search procedure for the multi-objective problem (MO-GRASP) is proposed. The computational experiments demonstrate the good performance of the MO-GRASP algorithm with clearly different results when the importance of each objective is varied. In addition, computational experiments conducted on historical data prove the feasibility of applying the MO-GRASP algorithm in a real context and explore the benefits of joint planning (collaborative approach) compared to a non-collaborative strategy. Collaborative approaches enable the definition of better routes that may select slightly worse fishing and planting areas (2.9%), but in exchange for a significant reduction in fuel consumption (17.3%) and time at sea (10.1%) compared to non-collaborative strategies. The final experiment examines the importance of the collaborative approach when the number of available drifting fishing aggregation devices (dFADs) per vessel is reduced. • This paper formulates and solves for the first time the dynamic vehicle routing problem with multiple time windows and moving targets. • A multi-objective greedy randomized adaptive search procedure (MO-GRASP) algorithm is proposed and tested with fishing fleets real world data. • The collaborative strategy yields a substantial reduction in fuel consumption (17.3%) and time at sea (10.1%) compared to the non-collaborative strategy. • This study demonstrates that optimizing the routes of a fleet can lead to a win-win strategy that reduces cost to industry and emissions to the environment.