Application of A Route Expansion Algorithm for Transit Routes Design in Grid Networks

Document Type: Research Paper

Authors

1 MSc Grad., Department of Civil and Environmental Engineering, Tarbiat Modares University, Tehran, Iran

2 Ph.D Candidate, Department of Civil and Environmental Engineering, Tarbiat Modares University, Tehran, Iran

3 Assistant Professor, Department of Civil and Environmental Engineering, Tarbiat Modares University, Tehran, Iran

4 Professor, Department of Civil and Environmental Engineering, Tarbiat Modares University, Tehran, Iran

Abstract

Establishing a network of transit routes with satisfactory demand coverage is one of the main goals of transit
agencies in moving towards a sustainable urban development. A primary concern in obtaining such a
network is reducing operational costs. This paper deals with the problem of minimizing construction costs
in a grid transportation network while satisfying a certain level of demand coverage. An algorithm is
proposed following the general idea of “constructive algorithms” in related literature. The proposed
algorithm, in an iterative approach, selects an origin-destination with maximum demand, generates a basic
shortest-path route, and attempts to improve it through a route expansion process. The paper reports the
scenarios and further details of the algorithm considered for expanding a transit route in a grid network. A
random 6×10 grid network is applied to report the results. The results support that application of the
proposed algorithm notably reduces the operational costs for various amounts of demand coverage.

Keywords


- Baaj, M. H. and Mahmassani, H. S. (1991) “An AI‐based approach for transit route system planning and design”, Journal of Advanced Transportation, Vol. 25, No. 2, pp. 187-209.

- Baaj, M.H. and Mahmassani, H.S. (1995) “Hybrid route generation heuristic algorithm for the design of transit networks”, Transportation Research C: Emerging Technologies, Vol. 3, No. 1, pp. 31–50.

- Badia, H., Estrada, M. and Robusté, F. (2014) “Competitive transit network design in cities with radial street patterns”, Transportation Research Part B: Methodological, Vol. 59, pp. 161-181.

- Cancela, H., Mauttone, A. and Urquhart, M.E. (2015) “Mathematical programming formulations for transit network design”, Transportation Research Part B: Methodological, Vol. 77, pp. 17-37.

- Ceder, A. and Wilson, N. H. (1986) “Bus network design”, Transportation Research Part B: Methodological, Vol. 20, No. 4, pp. 331-344.

- Farahani, R.Z., Miandoabchi, E., Szeto, W.Y. and Rashidi, H. (2013) “A review of urban transportation network design problems”, European Journal of Operational Research, Vol. 229, No. 2, pp. 281-302.

- Guihaire, V. and Hao, J. K. (2008) “Transit network design and scheduling: A global review”, Transportation Research Part A: Policy and Practice, Vol. 42, No. 10, pp. 1251-1273.

- Ibarra-Rojas, O.J., Delgado, F., Giesen, R. and Muñoz, J.C. (2015). “Planning, operation, and control of bus transport systems: A literature review”, Transportation Research Part B: Methodological, Vol. 77, pp. 38-75.

- Kepaptsoglou, K. and Karlaftis, M. (2009) “Transit route network design problem: review”, Journal of Transportation Engineering, Vol. 135, No. 8, pp. 491–505.

- Kermanshahi, S., Shafahi, Y. and Bagherian, M. (2015). “Application of a new rapid transit network design model to bus rapid transit network design: case study Isfahan metropolitan area”, Transport, Vol. 30, No. 1, pp. 93-102.

- Mandl, C. E. (1980) “Evaluation and optimization of urban public transportation networks”, European Journal of Operational Research, Vol. 5, No. 6, pp. 396-404.

- Mauttone, A. and Urquhart, M. E. (2009) “A route set construction algorithm for the transit network design problem”, Computers and Operations Research, Vol. 36, No. 8, pp. 2440-2449.

- Nie, Y. M. (2016) “NUTREND”, http://translab.civil.northwestern.edu/nutrend/?page_id=53. Accessed 1 February 2016.

- Schöbel, A. (2012) “Line planning in public transportation: models and methods”, OR Spectrum, Vol. 34, No. 3, pp. 491-510.

- Snellen, D., Borgers, A. and Timmermans, H. (2002) “Urban form, road network type, and mode choice for frequently conducted activities: a multilevel analysis using quasi-experimental design data”, Environment and Planning A, Vol. 34, No. 7, pp. 1207-1220.

- Stern, R. (1996) “Passenger transfer system review”, Transportation Research Board, Washington, D.C.

- Zhao, F. and Zeng, X. (2006) “Simulated annealing–genetic algorithm for transit network optimization”, Journal of Computing in Civil Engineering, Vol. 20, No. 1, pp. 57-68.