This thesis tackles the Urban Transit Network Design Problem (UTNDP) which involves determining an efficient set of routes and schedules for public transit networks. The UTNDP can be divided into five subproblems as identified by Ceder and Wilson [24]: i) network design, ii) frequency setting, iii) timetable development, iv) bus scheduling, and v) driver scheduling, with each problem requiring the output of the previous. In this thesis we focus on the first two stages, network design and frequency setting. We identify that evaluation is a major bottleneck for the network design problem and propose alternative approaches with the aim of decreasing the computation time. A multi-objective evolutionary algorithm (MOEA) for the network design problem is then presented that trades-off the passenger and operator costs. A passenger wishes to travel from their origin to destination in the shortest possible time, whereas the network operator must provide an adequate level of service whilst balancing the operational costs i.e. number of drivers and vehicles. The proposed MOEA combines a heuristically seeded population, using a novel construction algorithm, with several genetic operators to produce improved results compared with the state of the art from the literature. We provide an evaluation of the effectiveness of the genetic operators showing that improved performance, in terms of the number of dominating and nondominating solutions, is achieved as the size of the problem instance increases. Four surrogate models are proposed and an empirical evaluation is performed to assess the solution quality versus run trade-off in each case. It is found that surrogate models perform well on large problem instances producing improved Pareto sets compared with the original algorithm due to the increased amount of evolution that is allowed to occur under fixed time limits. Finally we empirically evaluate three multi-objective approaches for the frequency setting problem utilising the route networks produced during our network design procedure. It is shown that a MOEA based on the NSGAII framework provides the best quality solutions due to the cost of evaluation when using a neighbourhood based approach such as multi-objective tabu search. Constraints on vehicle capacity and fleet size are then introduced. It is shown that such constraints vastly reduce the number of solutions from network design that can successfully undergo frequency setting. A discussion is then presented highlighting the limitations of conducting network design and frequency setting separately along with alternative approaches that could be used in the future. We conclude this thesis by summarising our findings and presenting topics for future works.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:709603 |
| Date | January 2016 |
| Creators | John, Matthew P. |
| Publisher | Cardiff University |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://orca.cf.ac.uk/99851/ |
Page generated in 0.0119 seconds