By now, the continuous increase in freight transport demand has clearly put into evidence that road networks can not constitute the unique way to manage freight transportation. In this framework, an alternative to road transportation, indicated, after the European Union definition, as Motorways of the Sea (MoS), has to be investigated in order to understand its potential performance from the point of view of economic costs, travelling times, environmental impact, and so on. Then, the aim of this paper is to design a MoS network model, essentially consisting of a graph, able to take into account both ground and maritime links among a set of seaports, and to identify the cost functions characterising the links, as well the non-additive costs characterising the paths, so as to state and solve a shortest path problem on such a complete network. Finally, a case study relevant to the Mediterranean Sea is presented.