Exact and heuristic approaches for the ship-to-shore problem
研究了灾后海军使用小型船只和直升机（连接器）将物资从船运到岸的问题，提出了包含资源集的数学规划模型，并开发了精确分支定价算法和贪心启发式算法，实验显示84%的实例在一小时内求解，贪心算法在三分之二实例中找到最优解。
After a natural disaster such as a hurricane or flooding, the navy can help by bringing supplies, clearing roads, and evacuating victims. If destinations cannot be reached over land, resources can be transported using smaller ships and helicopters, called connectors. To start aid on land as soon as possible this must be done efficiently. In the ship-to-shore problem, trips with their accompanying resources are determined while minimising the makespan. Limited (un)loading capacities, heterogeneous connector characteristics and constraints posed by priority of the resources and grouping of the resources (resource sets) all require that the connector trips are carefully coordinated. Despite the criticality of this coordination, existing literature does not consider resource sets and has only developed heuristics. We provide a formulation that incorporates resource sets and develop (i) an exact branch-and-price algorithm and (ii) a tailored greedy heuristic that can provide upper bounds. We find that 84% of our 98 practical instances terminate within an hour in on average 80 s. Our greedy heuristic can find optimal solutions in two-thirds of these instances, mostly for instances that are very constrained in terms of the delivery order of resources. When improvements are found by the branch-and-price algorithm, the average gap with the makespan of the greedy solution is 40% and, in most cases, these improvements are obtained within three minutes. For the 20 artificial instances, the greedy heuristic has consistent performance on the different types of instances. For these artificial instances improvements of on average 35% are found in reasonable time.