publication . Thesis

Metaheuristics for designing efficient routes & schedules for urban transportation networks

John, Matthew P.;
Open Access English
  • Country: United Kingdom
Abstract
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...
Subjects
free text keywords: QA75
Related Organizations

3 Literature Review 49 3.1 Vehicle Routing Problems . . . . . . . . . . . . . . . . . . . . . . . 49 3.2 Practical Guidelines for the UTNDP . . . . . . . . . . . . . . . . . . 52 3.3 Methods for tackling the UTNDP . . . . . . . . . . . . . . . . . . . . 54 3.3.1 Mathematical Approaches . . . . . . . . . . . . . . . . . . . 54 3.3.2 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3.3 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.4 Frequency Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.5 Limitations of Published Research . . . . . . . . . . . . . . . . . . . 74 3.6 Commercial Software . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4 An Improved Approach to Network Design 79 4.1 Heuristic Construction . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.2 NSGAII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3 Genetic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.3.1 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.3.2 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.4 Measuring Population Diversity . . . . . . . . . . . . . . . . . . . . 90 4.5 Experimental Method . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.7 Genetic Operator Analysis . . . . . . . . . . . . . . . . . . . . . . . 98

5 Surrogate Models for Network Design 113 5.1 Overview of Surrogate-assisted Optimisation . . . . . . . . . . . . . 114 5.2 Proposed Management Strategies . . . . . . . . . . . . . . . . . . . . 115 5.3 Proposed Surrogate Models . . . . . . . . . . . . . . . . . . . . . . . 116 5.4 Experimental Method for Surrogate Models . . . . . . . . . . . . . . 119 5.5 Experimental Results for Surrogate Models . . . . . . . . . . . . . . 120 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

6 Frequency Setting 135 6.1 Preliminary Investigation . . . . . . . . . . . . . . . . . . . . . . . . 136 6.2 Evaluation with Frequencies Considered . . . . . . . . . . . . . . . . 140 6.3 Problem Instance Demand Scaling . . . . . . . . . . . . . . . . . . . 144 6.4 Variable Fleet Size . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.4.1 NSGAII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6.4.2 Multi-objective First Descent . . . . . . . . . . . . . . . . . . 149 6.4.3 Multi-objective Tabu Search . . . . . . . . . . . . . . . . . . 150 6.4.4 Neighbourhood Operators . . . . . . . . . . . . . . . . . . . 152 6.4.5 Candidate Solution Selection . . . . . . . . . . . . . . . . . . 153 6.4.6 Population Generation . . . . . . . . . . . . . . . . . . . . . 155 6.4.7 Experimental Method . . . . . . . . . . . . . . . . . . . . . . 156 6.4.8 Experimental Results . . . . . . . . . . . . . . . . . . . . . . 156 6.5 Constrained Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.5.1 Experimental Method . . . . . . . . . . . . . . . . . . . . . . 160 6.5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . 160 6.6 Constrained Capacity & Fleet Size . . . . . . . . . . . . . . . . . . . 162 6.7 Discussion: Alternative Approaches to Frequency Setting . . . . . . . 163 6.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

7 Conclusions & Future Work 169 7.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 2.3 A connected (a) and unconnected graph (b) . . . . . . . . . . . . . . 17 2.4 A directed weighted graph. . . . . . . . . . . . . . . . . . . . . . . . 18 2.5 A sample representation of a transport network (a) with examples of an invalid (b) and valid (c) route network . . . . . . . . . . . . . . . . . 20 2.6 (a) Route network - road network with three routes overlaid (b) Transit network - network used for evaluation . . . . . . . . . . . . . . . . . 23 2.7 An example transport network (a), route set (b) and resultant route network (c) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.9 Route network extract with two routes. . . . . . . . . . . . . . . . . . 36 2.10 An example transit network with three routes, each with three identical transfer vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.11 Removal of the intermediate overlapping transfer vertices in the transit network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 [39] Georges A Croes. A method for solving traveling-salesman problems. Operations research, 6(6):791-812, 1958.

[54] Lang Fan and Christine L Mumford. A metaheuristic approach to the urban transit routing problem. Journal of Heuristics, 16(3):353-372, 2010.

[55] Lang Fan, Christine L Mumford, and Dafydd Evans. A simple multi-objective optimization algorithm for the urban transit routing problem. In 2009 IEEE Congress on Evolutionary Computation, pages 1-7. IEEE, 2009.

[93] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671-680, 1983. [OpenAIRE]

[94] Joshua Knowles and David Corne. On metrics for comparing nondominated sets. In Evolutionary Computation, 2002. CEC'02. Proceedings of the 2002 Congress on, volume 1, pages 711-716. IEEE, 2002.

[95] A. L. Kok, C. M. Meyer, H. Kopfer, and J. M. J. Schutten. A dynamic programming heuristic for the vehicle routing problem with time windows and european community social legislation. Transportation Science, 44(4):442-454, 2010.

[107] Héctor Martínez, Antonio Mauttone, and María E Urquhart. Frequency optimization in public transportation systems: Formulation and metaheuristic approach. European Journal of Operational Research, 236(1):27-36, 2014.

[109] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6):1087-1092, 1953. [OpenAIRE]

[119] Miloš Nikolic´ and Dušan Teodorovic´. Transit network design by bee colony optimization. Expert Systems with Applications, 40(15):5945-5955, 2013. [OpenAIRE]

[146] Christine L Valenzuela. A simple evolutionary algorithm for multi-objective optimization (seamo). In Congress on Evolutionary Computation (CEC), pages 717-722, 2002.

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue