We consider the problem of designing lines in a public transport system, where we include user-optimal route choice. The model we develop ensures that there is enough capacity present for every passenger to travel on a shortest route. We present two different integer programming formulations for this problem, and discuss exact solution approaches. To solve large-scale line planning instances, we also implemented a genetic solution algorithms. We test our algorithms in computational experiments using randomly generated instances along realistic data, as well as a realistic instance modeling the German long-distance network. We examine the advantages and disadvantages of using such user-optimal solutions, and show that our algorithms sufficiently scale with instance size to be used for practical purposes.