This talk discusses an application of planning support in designing a sea-transport system. Increased pressure on the road network and increasing transport needs make companies look for new transport solutions. This spurred an initiative to create a new liner shipping service. The initiative came from a group of Norwegian companies who need transport between locations on the Norwegian coastline and between Norway and The European Union. While few producers on the Norwegian coast have sufficient load to support a cost efficient; high frequency sea-transport service; they can reduce costs and decrease transport lead-time by combining their loads on common ships. They agreed upon a tender (transport offer) which was proposed to a number of shipping companies. The tender specifies the number of cargos per week and time constraints for pickup and delivery. It also states the requirements regarding ship types and loading and unloading techniques. For rapid handling; all goods must be transported in containers. Finally the tender specifies the yearly payment each company will make to be part of this transportation system. Today there are neither ships nor harbour facilities to support the proposed solution. Thus; major investments are necessary. Estimates indicate that investments in ships alone; can amount to about 150 mill US dollars. We present a model which calculates a near optimal fleet and corresponding routes to satisfy the requirements in the tender. The problem is a variant of the general pickup and delivery problem with multiple time windows. In addition; it includes requirements for recurring visits; separation between visits and limits on transport lead-time. The problem is formulated as a set partitioning model and solved by a heuristic branch-and-price algorithm.