This research focuses on designing transportation plan for SNCF Transilien (French rail-way operator for the Parisian suburban mass transit). The objective is to develop methods and decision support tools to propose a timetable adapted to the passenger demand in the Parisian mass transit system, including comfort and reliability criterias. This paper aims to present the first step of this research. We propose a graph theoretic ILP formulation for the Line Planning Problem, minimizing both travelers travel time and operating cost. We furthermore develop a multi-objective method to solve this problem. This method offers a pool of solutions in order to let the final designer choose the solution. We report computational results on real world instances provided from SNCF Transilien.@en