Implications of the computational complexity of transit route network redesign for metaheuristic optimisation systems

Author(s): J.J. Blum and T.V. Mathew
DOI: 10.1049/iet-its.2011.0021

For access to this article, please select a purchase option:

Buy article PDF

Buy Knowledge Pack

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership

Recommend Title Publication to library

IET Intelligent Transport Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Author(s): J.J. Blum ¹ and T.V. Mathew ²
- Affiliations: 1: Computer Science and Mathematical Sciences, Penn State University, Harrisburg, USA
  2: Department of Civil Engineering, Indian Institute of Technology, Bombay, India
Source: Volume 6, Issue 2, June 2012, p. 124 – 131
DOI: 10.1049/iet-its.2011.0021 , Print ISSN 1751-956X, Online ISSN 1751-9578

The transit route network design problem is a computationally intractable optimisation problem that seeks a set of bus routes and frequencies that minimises the operator cost while maximising passenger utility. Previous attempts to optimise this problem have used metaheuristic and heuristic techniques to find solutions that allow for a complete redesign of the transit network. In reality, however, a complete redesign of the network may encounter political resistance from existing transit users if the routes that they use are eliminated. Here, an intelligent agent optimisation system is used to optimise the transit route network redesign (TRNR) problem, which is subject to the additional constraint that existing routes in the network remain, although perhaps serviced with lower frequency. When applied to the transit network in Mumbai, India, the optimisation system found significant improvement in the route network, even when subject to these constraints. In a scenario in which the current routes were maintained with frequency of stops reduced by no more than 50%, operator cost could be improved by 18.1% while maintaining the current level of passenger utility. On the other hand, passenger utility could be improved by 5.5% at current levels of operator cost.

References

1. 1)
  - S. Ngamchai , D.J. Lovell . Optimal time transfer in bus transit route network design using a genetic algorithm. J. Transp. Eng. , 510 - 521
2. 2)
  - M.-C. Shih , H.S. Mahmassani , M.H. Baaj . Planning and design model for transit route networks with coordinated operations. Transp. Res. Rec. , 16 - 23
3. 3)
  - C.E. Mandl . Evaluation and optimization of urban public transportation networks. Eur. J. Oper. Res. , 396 - 404
4. 4)
  - J. Agrawal , T. Mathew . Transit route network design using a parallel genetic algorithm. J. Comput. Civil Eng. , 248 - 256
5. 5)
  - Tom, V.M.: `Urban transit route network design using genetic algorithm', 1999, PhD, Indian Institute of Technology, Department of Civil Engineering, Madras, India.
6. 6)
  - Lui, H., Yang, X.: `Bus transit route network design using genetic algorithm', Int. Conf. on Transportation Engineering, 2007, p. 1135–1141.
7. 7)
  - Fan, W., Machemehl, R.B.: `Optimal transit route network design problem: algorithms', Report no. SWUTC/04/167244-1, 2004.
8. 8)
  - J.J. Blum , A. Sridhar , T.V. Mathew . Origin–destination matrix generation from boarding–alighting and household survey data, transportation research record. J. Transp. Res. Board , 1 - 8
9. 9)
  - W. Fan , R.B. Machemehl . Using a simulated annealing algorithm to solve the transit route network design problem. J. Transp. Eng. , 122 - 132
10. 10)
  - F. Zhao , I. Ubaka . Transit network optimization: minimizing transfers and optimizing route directness. J. Publ. Transp. , 1 , 63 - 81
11. 11)
  - F. Zhao , X. Zeng . Simulated annealing-genetic algorithm for transit network optimization. J. Comput. Civil Eng. , 1 , 57 - 68
12. 12)
  - A. Ceder , N.H.M. Wilson . Bus network design. Transp. Res. B , 331 - 344
13. 13)
  - W. Fan , R.B. Machemehl . Optimal transit route network design problem with variable transit demand: genetic algorithm approach. J. Transp. Eng. , 40 - 51
14. 14)
  - S.B. Pattnaik , S. Mohan , V.M. Tom . Urban bus transit route network design using genetic algorithms. J. Transp. Eng. , 368 - 375
15. 15)
  - Lei, D., Yan, X.: `Urban transit route network design problem using tabu search algorithm', Int. Conf. on Transportation Engineering, 2007, p. 3929–3934.
16. 16)
  - M. Bielli , M. Caramia , P. Carotenuto . Genetic algorithms in bus network optimization. Transp. Res. C , 19 - 34
17. 17)
  - S. Chien , Z. Yang , E. Hou . A genetic algorithm approach for transit route planning and design. J. Transp. Eng. , 200 - 207
18. 18)
  - M.H. Baaj , H.S. Mahmassani . Hybrid route generation heuristic algorithm for the design of transit networks. Transp. Res. C , 31 - 50
19. 19)
  - J. Blum , T. Mathew . Intelligent agent optimization of urban bus transit system design. J. Comput. Civil Eng. , 5 , 357 - 369
20. 20)
  - B.R. Marwah , R. Parti , P.K. Kalra . Optimal planning of transit routes for large cities.

Implications of the computational complexity of transit route network redesign for metaheuristic optimisation systems

Implications of the computational complexity of transit route network redesign for metaheuristic optimisation systems

Buy article PDF

Buy Knowledge Pack

Thank you

References

Related content