The Centre for Transport Network Optimisation is a research centre based at Cardiff University, Wales and represents a collaboration between the Schools of Mathematics and Computer Science.
Our research, partially funded by High Performance Computing Wales (HPC-Wales), is primarily concerned with producing algorithms for the Urban Transit Routing Problem. Our goal is to develop new, highly efficient approaches for public transport network design, considering factors such as routing and scheduling, fleet size, satisfying passenger demand, and minimising costs and carbon footprints.
- Design and build effective and robust multiobjective algorithms for public transit routing and scheduling;
- Provide strong evidence of the success and broad application of these methods on a range of benchmark test data and challenging real-world problems;
- To provide the academic community with a versatile range of real-world problem instances;
- Build robust parallel models to demonstrate scalability of our methods to very large urban conurbations.
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.
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 problem-specific operators in order avoid wasting time generating and testing huge numbers of infeasible solutions.
Once feasible route sets are generated, we then have the difficult and costly 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 across the entire network, and the average number of transfers per person. There could be several different potential paths through the travel network of an individual passenger, and various choices 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. The cost of such calculations indicates a need for high performance computing and/or parallelism to achieve reasonable run times.
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. 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, or exam timetabling problem) the focal point for academic research seems to be weak for the UTRP, and it has been is difficult for researchers to compare their methods with one another.
Here are a number of relevant references, produced by members of CTNO and elsewhere:
- Mumford, C. New Heuristic and Evolutionary Operators for the Multi-Objective Urban Transit Routing Problem. IEEE Congress on Evolutionary Computation, 2013, vol. 1 pp 939-946.
- Fan, L., Mumford, C., and Evans. D. A simple multi-objective optimization algorithm for the urban transit routing problem. IEEE Congress on Evolutionary Computation, pp 1-7, 2009.
- Fan, L. and Mumford, C. A metaheuristic approach to the urban transit routing problem. Journal of Heuristics, vol. 16 (3) 2010 pp 353-372, 2010. .
- Chakroborty, P. Genetic Algorithms for Optimal Urban Transit Network Design, Computer-Aided Civil and Infrastructure Engineering 18 (2003) 184-200.
- Chakroborty, P. and Tathagat Dwivedi, Optimal Route Network Design For Transit Systems Using Genetic Algorithms, Engineering Optimization (2002) vol. 34(1), 83-100.
- Mandl, C. Evaluation and Optimization of Urban Public Transport Networks, European Journal of Operational Research, vol. 5 (1980) 396-404.
- Mandl, C. Evaluation and Optimization of Urban Public Transport Networks, Third Congress on Operations Research, Amsterdam, Netherlands (1979).
- Mandl, C. Applied Network Optimization, Academic Press, London, 1979.
There are currently 5 problem instances that are used with this problem, downloadable here. These have been compiled by Christine Mumford to whom questions should be directed. Each problem instance comprises 3 files: an (x, y) coordinates file; a transit demand matrix; and a transit time matrix. The names of the files are as follows:
- Mandl's Swiss Network (15 Nodes and 21 Links Network). Files: MandlCoords.txt, MandlDemand.txt, and MandlTravelTimes.txt.
- Mumford0 (30 Nodes and 90 Links Network). Files: Mumford0Coords.txt, Mumford0Demand.txt and Mumford0TravelTimes.txt.
- Mumford1 (70 Nodes and 210 Links Network). Files: Mumford1Coords.txt, Mumford1Demand.txt and Mumford1TravelTimes.txt.
- Mumford2 (110 Nodes and 385 Links Network). Files: Mumford2Coords.txt, Mumford2Demand.txt and Mumford2TravelTimes.txt.
- Mumford3 (127 Nodes and 425 Links Network). Files: Mumford3Coords.txt, Mumford3Demand.txt and Mumford3TravelTimes.txt.
Let n denote the number of nodes in a problem instance. The structure of the coordinates files are as follows:
The demand and travel times are stored in 2D matrices, where d_ij gives the demand (or travel times) between nodes i and j. The files are therefore laid out as follows:
d_11 d_12 d_13 ... d_1n
d_21 d_22 d_23 ... d_2n
d_31 d_32 d_33 ... d_3n
d_n1 d_n2 d_n3 ... d_nn
Please note the following:
- The transit time between each pair of nodes is measured in minutes.
- The transit time is recorded as "Ïnf" between nodes that are not directly connected.
- All matrices are symmetric.
- The row and column headings (i.e., node numbers) are not included in the matrices.
- Mandl's Swiss Network was originally published in his book Applied Network Optimization (Academic,London,1979).
Here is some C (C++) source code for checking the validity of a route set. Validity is assessed according to the problem constraints of Urban Transit Routing Problem (Mumford (2013)):
1. The route set must contain all vertices in the underlying transport graph;
2. No route in the route set should contain a cycle;
3. All routes in the route set should contain between MIN and MAX vertices (inclusive), where MIN and MAX are specified by the user;
4. The route set must be connected, allowing all of the demand in the network to be satisfied.
The program can be compiled using both gcc and visual studio. .