Optimization of the Urban Line Network Using a Mathematical Programming Approach

Optimization of the Urban Line Network Using a Mathematical Programming Approach

L. Jánošíková M. Koháni M. Blaton D. Teichmann 

Department of Transportation Networks, University of Žilina, Slovak Republic

Institute of Transport, VŠB-Technical University of Ostrava, Czech Republic

30 September 2012
| Citation



The paper deals with the line-planning problem related to urban public transport. Given the transportation network in a city, the origin–destination matrix of travel demands, and the fl eet of available vehicles, the goal is to design the routes and frequencies of lines. The proposed solution method is a combination of the exact mathematical programming algorithm and a trip assignment procedure. The solution process consists of three stages: (i) initialization, (ii) designing the line network and setting the initial frequencies of selected lines, (iii) solution improvement. In the fi rst stage, an initial set of feasible lines is proposed. In the second stage, an optimal subset of candidate lines is selected and initial frequencies of lines are computed by solving a mathematical programming model of the line-planning problem. The problem is formulated as a multiple criteria optimization problem, where the criteria refl ect travelers’ demand for a high quality service, operator’s interest in an effective service, and the environmental impact of the vehicles. The solution of this problem specifi es the number of vehicles of the given mode and type operating on the lines. The lines which are not assigned a vehicle will not operate. The assigned number of vehicles determines the frequency of a given line. At the same time, the solution specifi es optimal passengers’ routes in the line network. The third stage consists of an iterative process, which computes new line frequencies with regard to in-vehicle and waiting times, transfers, and passengers’ behavior in a situation when they have multiple travel alternatives. The approach has been verifi ed using real transportation data of a middle-sized city in the Slovak Republic. The paper presents the results of the case study.


 discrete choice model, line-planning problem, mathematical programming, multiple criteria optimization


[1] Cede r, A. & Wilson, N.H., Bus network design. Transportation Research Part B, 20(4), pp. 331–344, 1986. doi: http://dx.doi.org/10.1016/0191-2615(86)90047-0

[2] Borndörfer, R., Grötschel, M. & Pfetsch, M.E., A column-generation approach to line plan-ning in public transport. Transportation Science, 41(1), pp. 123–132, 2007. doi: http://dx.doi. org/10.1287/trsc.1060.0161

[3] Erlander, S. & Schéele, S., A mathematical programming model for bus traffi c in a network. Proc. of the 6th Int. Symposium On Transportation and Traffi c Theory, ed. D.J. Buckley,  Elsevier: New York, London, Amsterdam, pp. 581–605, 1974.

[4] Blatonˇ, M., Vícekriteriální optimalizace linek MHD. Proc. of the Seminar Discrete Optimisation Problems in Transportation. University of Pardubice: Pardubice, Czech, 2009.

[5] Cerný, J. & Kluvánek P., ˇ Základy matematickej teórie dopravy, VEDA: Bratislava, Slovak, 1991.

[6] Peško, Š., Podpora  metód operaˇcného výskumu pri navrhovaní systému liniek. Proc. of the 6th Int. Conf. On Urban Transportation Infrastructure. University of Žilina: Žilina, Slovak, 2008.

[7] Surovec, P., Provoz a ekonomika silnicˇní dopravy I. Vysoká škola bánˇská: Ostrava, Czech, 2000.

[8] Teichmann, D., O nˇekolika modifi kacích matematického modelu pˇridˇelování vozidel linkám v mˇestské hromadné dopravˇe. New Railway Technique, 17(1), pp. 20–23, 2009.

[9] Fan, W. & Machemehl, R.B., Optimal Transit Route Netwo rk Design Problem: Algorithms, Implementations, and Numerical Results. Report No. SWUTC/04/167244-1. Center for Transportation Research: University of Texas at Austin, 2004. 

[10] Jánošíková, L., Blatonˇ, M. & Teichmann, D., Design of urban public transport lines as a multiple criteria optimisation problem. Proc. of the 16th International Conference on Urban Transport and the Environment – Urban Transport XVI, eds A. Pratelli & C.A. Brebbia, WIT Press: Southampton, pp. 137–146, 2010.

[11] Ehrgott, M. & Wiecek, M.M., Multiobjective programming (Chapter 17). Multiple Criteria Decision Analysis: State of the Art Surveys, eds J. Figueira, S. Greco & M. Ehrgott, Springer: New York, 2005.

[12] Fiala, P., Modely a metody rozhodování. Oeconomica: Praha, Czech, 2006.

[13] Koppelman, F.S. & Bhat, C., A Self Instructing Course in Mode Choice Modeling: Multinomial and Nested Logit Models, 2006, available at http://www.civil.northwestern.edu/people/koppelman/PDFs/LM_Draft_060131Final-060630.pdf

[14] Fan, W. & Machemehl, R.B., Characterizing bus transit passenger waiting times. 2nd Material Specialty Conference of the Canadian Society for Civil Engineering. Canadian Society for Civil Engineering: Montreal, 2002.