Cooperative liner shipping network design by means of a combinatorial auction

Cooperation in the ocean liner shipping industry has always been important to improve liner shipping networks (LSN's). As tight cooperations like alliances are challenged by antitrust laws, looser forms of cooperation among liner carriers might become a reasonable way to increase efficiency of LSN's. Our goal is to facilitate a loose form of cooperation among liner carriers. Therefore, we introduce a coordination mechanism for designing a collaborative LSN based on a multi round combinatorial auction. Via the auction, carriers exchange demand triplets, i.e. orders which describe the transport of containers between ports. A standard network design problem which includes ship scheduling and cargo routing decisions is used as isolated network design problem of an individual carrier. A carrier has to solve this isolated problem repeatedly during the auction so that the carrier is able to decide which demand triplets to sell, on which demand triplets to bid, and what prices to charge. To solve these problems we propose a variable neighborhood search based matheuristic. The matheuristic addresses the isolated planning problem in four phases (construct ship cycles, modify cycles, determine container flow, and reallocate ships to cycles). Our computational experiments on a set of 56 synthetic test instances suggest that the introduced combinatorial auction increases profits on average compared to isolated planning significantly by four percent. The more diverse the original assignment of demand triplets and ships to carriers is, the higher the potential for collaboration; for 18 diverse instances, the profits increase on average by ten percent.