A branch-and-price algorithm for solving the single-hub feeder network design problem

Erik Orm Hellsten*, David Sacramento, David Pisinger

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review


In liner shipping, containers are generally transshipped in major hub ports in each region, between larger inter-region vessels and smaller feeder vessels. In this paper, we study the problem of designing the feeder vessel network, transporting containers between a regional hub and the surrounding feeder ports. The problem, as modelled, has many similarities with the split delivery vehicle routing problem, but with additional characteristics such as simultaneous pickups and deliveries and weekly departures. The problem also includes fleet sizing with a heterogeneous fleet and allows demand rejection at a penalty cost. We present a branch-and-price framework to solve the problem, where the subproblem is solved by enumerating vessel routes and subsequently assigning commodities by solving a min-cost flow problem for each commodity. The algorithm is tested on instances with up to 12 ports, which are all solved to optimality. Since the problem is similar to the liner shipping network design problem but without transshipments, we further study selected instances from the LINER-LIB instance suite. The Baltic instance is solved to proven optimality and we find the best known solution to the West Africa instance, significantly improving on what can be found in the literature.
Original languageEnglish
JournalEuropean Journal of Operational Research
Issue number3
Pages (from-to)902-916
Number of pages15
Publication statusPublished - 2022


  • OR in maritime industry
  • Liner Shipping Network Design
  • Network Design
  • Branch-and-price


Dive into the research topics of 'A branch-and-price algorithm for solving the single-hub feeder network design problem'. Together they form a unique fingerprint.

Cite this