A flow-first route-next heuristic for liner shiping network design

Designing cyclic sailing routes for a fleet of containers is a very complex problem. Due to the increasing awareness for environmental consequences, it has become more important to not only design cost-efficient, but also energy-efficient networks. This paper proposes a flow-first route-next heuristic, which seeks to maximize profit while stimulating so-called slow steaming. This heuristic first creates a backbone ow which will be used to generate initial rotations. These initial rotations are improved using a Variable Neighborhood Search algorithm. Then, sailing speed is minimized such that all routes remain feasible. We perform this procedure two times, once allowing only simple cyclic (general) rotations and once allowing non-simple cyclic rotations, also referred to as buttery rotations. In addition, the rotations are generated and improved in two manners, once assuming design speed and once assuming maximum speed. Our results show that the revenue for owing containers is higher when allowing for buttery rotations. Also, when maximum speed is assumed while generating and improving rotations, the revenue is higher for both the general and buttery algorithm. We see that after subtracting the cost for operating the rotations, no profitable solutions were found. However, the buttery algorithm with maximum speed is the least loss-making algorithm.