Based on passenger mobility knowledge, this research presents a model for the design of passenger-oriented lines for SNCF Transilien (major railway operator for the Parisian suburban mass transit). In the Paris area, the traffic has increased by 30% over the last decade, reaching 3.2 million passengers a day on the network. We have developed a new method that proposes a line planning process aiming at the best quality level for passengers, and at reasonable costs. First, we introduce indicators to characterize the performance of railway services, with the traveler’s and the operator’s points of view. Then, a method to solve a graph theory-based multiobjective model for the Line Planning Problem is presented, minimizing both users’ discomfort and operating costs. This method provides all efficient solutions. Experimental results on SNCF Transilien real instances are presented. Several objective functions are compared and analyzed with regards to the passenger quality of service. These new criteria provide a more accurate outlook of the quality of service.