The urban transit routing problem (UTRP) involves devising routes for public transport systems: for example, buses or trains. It is a highly complex NP-Hard problem, and solving it invariably involves a cycle of generating and testing “candidate” route sets.
Unlike better known vehicle routing problems (such as the travelling salesman problem, or the capacitated vehicle routing problem) the UTRP is difficult to formulate mathematically. In many ways, there is much more freedom in constructing the routes. A particular node (e.g., bus stop or train station) or set of nodes can appear on many different routes, and individual routes can be long or short (or even circular). A route set can contain few or many routes. The design of the optimum route set will vary according to certain factors, including vehicle capacity (how many passengers it can carry), vehicle frequency (i.e., the schedule or timetable), and the demand between each pair of nodes (i.e, the numbers of passengers wishing to travel from node A to node B). In practice, the evaluation of automatically generated candidate route sets can prove both time consuming and challenging, with huge numbers of potential solutions rejected because they are infeasible, i.e., they fail to meet demand or perhaps they leave some passengers stranded without connections. Heuristic and metaheuristic methods are clearly appropriate for NP-Hard problems such as this, but the solution methods need to be very carefully designed, and incorporate a level of “intelligence” or knowledge about the problem, to control the amount of “randomness” involved, to avoid wasting time generating and testing huge numbers of infeasible solutions.
Once feasible route sets are generated, we then have the difficult issue of evaluation, which requires choosing an appropriate path through the travel network for each passenger, and using this information to calculate statistics, such the average travel time over all demand on the network, and the average number of transfers per person. There may be several different potential paths through the travel network of an individual passenger, and various decision have to be made, such as whether it is better to transfer vehicles and change routes if it saves time, or stay on an vehicle to avoid the inconvenience of making transfers. In our work so far we have adopted the relatively simple model published by Chakroborty et al ([1, 2] to determine the assignment of travel paths, using an all-pairs-shortest-path approach with 5 minutes penalty for each person-transfer that is made.
For further reading, two recent review articles are recommended, [3, 4]. The book written by Christoph Mandl (1979) is well worth reading. It is a pioneering text which introduces many of the important ideas. Another good introductory read is a report from the University of Texas  published in 1994.
Despite the obvious importance of the UTRP, progress is hampered by a lack of text-book style models and benchmark problems. The only publicly available benchmark with all necessary information is Mandl’s 15 node Swiss Road Network Problem, which is very small indeed. Published work that goes beyond Mandl’s data tends to focus on bespoke systems for specific urban locations, where the necessary data is not provided for other researchers. Compared with other important NP-Hard problems (such as the travelling salesman problem, the examination timetable problem, the job-shop scheduling problem, and many more), the “focal point” for academic research seems to be weak for the UTRP, and it is difficult for researchers to compare their methods with one another.
In this work research Lang Fan and Christine Mumford built on the work of Mandl and Chakroborty et al and developed a basic heuristic/metaheuristic framework for iterative solution improvement. We recognized that all successful solution improvement methods rely on the following THREE fundamental aspects for their ultimate success:
Regardless of whether the method eventually chosen is tabu search, simulated annealing, evolutionary algorithms, variable neighbourhood search, or some other heuristic/metaheuristic method, these fundamental issues of representation, initialization and neighbourhood moves are key. We concentrated on building a successful framework incorporating a suitable representation and simple but effective initialization procedures and neighbourhood moves. Avoiding the time-consuming evaluation of vast numbers of weak or infeasible solutions, is probably the main challenge we encountered during our research. We tested our framework using simple hill-climbing and simulated annealing algorithms, and beat previously best published results for Mandl’s benchmark problem. In addition we generated some new test instances (which unfortunately are now lost) and established some simple upper and lower bounds for the UTRP.
Our work culminated in two research papers [7, 8] and, in 2009, a PhD was awarded to Lang Fan.
A couple of year after the completion of Lang Fan’s PhD, Christine Mumford began to slowly advance the work, because of its fascination and obvious global importance. A great debt to Lang is owed, his work provided some sound foundations to upon which to move forward. Everything was newly coded from scratch using MATLAB, with a few C routines linked in for speedup (for example, Floyd Warshall all pairs shortest paths). New data sets were created, because unfortunately our previous data was either miss-labelled or lost. All code was thoroughly and carefully tested during development.
The new work involved the development of a multiobjective evolutionary algorithm with new heuristics, mutation and crossover operators. Results have recently been published in .
This project was partially funded by HPC Wales and ran from the beginning of October 2013 to the end of September 2014. The team working on the project are listed below:
The project focussed on:
Two publications have resulted from this work, one directly covering the parallel models , and the other relates more to the PhD work of Matthew John, . Recently a paper has been submitted by Matthew John, Christine Mumford, Rhyd Lewis and Jonathan O’Connell to IEEE Transactions on Evolutionary Computation covering Surrogate Models, GPU speedup and some detailed experiments to evaluate the contributions of various genetic operators to our multi-objective evolutionary algorithm for bus routing.
There are currently 15 data files.
These were files were contributed by Christine Mumford (C.L.Mumford@cs.cardiff.ac.uk) to whom questions should be directed
There are five data sets in fifteen files consisting of an (x, y) coordinates file, a transit demand matrix and a transit time matrix for each of the five urban transit routing problem:
The structure of the coordinates files are as follows:
The structure of the Demand and Travel Times files are 2D matirces:
Mandl’s Swiss Network was published in his book: (C.E.Mandl,Applied Network Optimization,Academic,London,1979)
Experimental results for the networks have been published in my paper 
Click here to access to download a zip file with this data plus an explanatory document and some timing experiments.
Click here to use an online evaluation tool for evaluating your own route sets, according to the constraints we use in our papers defined in Table 1. All our results assume a 5 minute waiting time / transfer penalty. Please note that there is a runtime limit of 30 seconds on the website, so this program will only work on relatively small instances. For example, it will work on route sets for Mandl, Mumford0 and Mumford1, but probably time out for route sets derived from larger networks (e.g., Mumford2 and Mumford3). (A Python program for download is in preparation and will be posted soon). The evaluation software gives researchers the opportunity to ensure that their results are comparable with ours. Over a period of time we have found that errors in the evaluations procedure can be very tricky to detect, and we believe that we have now ironed them all out. This has been achieved by different researchers independently coding the evaluation procedure, followed by cooperation to debug and validate.
Click here to download Mandl test files to try out the program (TravelTimes, Demand and a 6 route solution).
LBop = Minimum
|Nodes and Links||Routes||/Route||R(L) (mins)|
|Mandl||15 & 20||4-8||2-8||10.0058||63|
|Mumford0||30 & 90||12||2-15||13.0121||94|
|Mumford1||70 & 210||15||10 - 30||19.2695||345*|
|Mumford2||110 & 385||56||10 - 22||22.1689||864*|
|Mumford3||127 & 425||60||12 - 25||24.7453||982*|
 Guihaire, V. and Hao, J.K., Transit network design and scheduling: A global review. Transportation Research Part A: Policy and Practice, 42(10), pp.1251-1273, 2008.
 Ibarra-Rojas, O. J., F. Delgado, R. Giesen, and J. C. Muoz. Planning, operation, and control of bus transport systems: A literature review. Transportation Research Part B: Methodological 77 (2015): 38-75.
 Shih, Mao-Chang and Mahmassani, Hani S., A Design Methodology for Bus Transit Networks with Coordinated Operations. Report SWUTC/94/60016-1, Southwest Region University Transportation Center, University of Texas at Austin, 1994.
 Fan, Lang, and Mumford, Christine.L. A metheuristic approach to the urban transit routing problem . Journal of Heuristics, Vol 16 (3) 2010 pp 353-372. (Also first published on line in 2008). DOI Link.
 Fan, Lang Mumford, Christine L, Evans, Dafydd. A simple multi-objective optimization algorithm for the urban transit routing problem. IEEE Congress on Evolutionary Computation, pp 1-7, 2009. DOI Link.
 Mumford, Christine L, New heuristic and evolutionary operators for the multi-objective urban transit routing problem, Evolutionary Computation (CEC), 2013 IEEE Congress on , vol. 1, pp.939,946, 20-23 June 2013. DOI Link.
 Cooper, Ian, John, Matthew P., Lewis, Rhydian, Mumford, Christine Lesley and Olden, Andrew. Optimising large scale public transport network design problems using mixed-mode parallel multi-objective evolutionary algorithms. Evolutionary Computation (CEC), 2014 IEEE Congress on. IEEE, 2014.
 John, Matthew P., Christine L. Mumford, and Rhyd Lewis. An improved multi-objective algorithm for the urban transit routing problem. Evolutionary Computation in Combinatorial Optimisation. Springer Berlin Heidelberg, 2014. 49-60.