A Service Design Problem for a Railway Network

We study the problem of designing a set of highly-profitable freight routes in a railway network, taking into account the capacity of the network and the level of service requested by different goods; in particular the profit achieved by transporting a good is a nonlinear function of the associated transit time. We propose an ILP model which is solved heuristically by column generation and fixing techniques. Computational results on a real network crossing eleven European countries are reported, showing that we can find solutions that are provably close to optimal. Given the large size of our instances, a key issue of our approach is to avoid finding an optimal solution of the continuous relaxation of our model, stopping as soon as near-optimal primal and dual solutions are available.