Our Research on the Urban Transit Routing Problem (Bus Routing)

Lang Fan and Christine Mumford

busRoutes.png

1  Introduction

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 theoretically consist of any number of routes and each route can be of any length. 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 grossly inefficient, cost too much, 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.

2  Main themes of our research

Despite the obvious importance of the UTRP, there has been little fundamental research, since the pioneering work of Christoph Mandl undertaken three decades ago [3,4,5]. With the exception of the inspiring work of Partha Chakroborty and Tathagat Dwivedi [1,2], most other published work has focussed on bespoke systems for specific urban locations. 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. With a lack of common graph theoretical models and benchmark data, it is difficult for researchers to compare their methods with one another.
In our research we have built on the models of Mandl and Chakroborty, and developed a basic heuristic/metaheuristic framework for iterative solution improvement. We recognize that all successful solution improvement methods rely on the following THREE fundamental aspects for their ultimate success:
  1. the quality of the chosen representation,
  2. the effectiveness of the initialization procedures, and
  3. the suitability of the chosen neighbourhood moves.
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 have 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 (the only instance readily available to researchers when the work was carried out). In addition we generated some new test instances and established some simple upper and lower bounds for the UTRP.
Our work culminated in several research papers and, in 2009, a PhD was awarded to Lang Fan.

3  Downloadable Documents

Thesis

A complete record of the work can be found in Lang Fan's thesis.

Papers

Our main published papers are:
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, 2010. (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.

Data

There are TWO data sets in FOUR files consisting of a transit demand matrix and a transit time matrix for the two urban transit routing problem:
  1. Mandl's Swiss Network (15 Nodes and 21 Links Network).
  2. 110 Nodes and 275 Links Network generated based on a bus map for a major British city.
The structure of these matrices we used is shown as follows: 
Node_Number 0   1   2   3   4   5   6   7   8...

0           .   .   .   .   .   .   .   .   .

1           .

2           .

3           .

4           .

5           .

6           .

7           .

8           .
.
.
.
Please note:
  1. The transit time between each pair of nodes is measured by minutes.
  2. The transit time is recorded as "-" between nodes that are not directly connected.
  3. All the matrices are symmetric.
  4. The row and column headings (i.e., node numbers) are not included in the matrix.
Experimental results obtained by testing these networks have been published in our papers listed above.
Mandl's Swiss Network was published in his book [3]. and comparison results for some researchers' experiments on Mandl's network were published in Chakroborty's and Dwivedi's paper [1].
Here is the data:
Transit Demand Matrix for Mandl's Swiss Network
Transit Time Matrix for Mandl's Swiss Network
Transit Demand Matrix for 110 Nodes and 275 Links Network
Transit Time Matrix for 110 Nodes and 275 Links Network

References

[1]
Partha Chakroborty and Tathagat Dwivedi, Optimal Route Network Design For Transit Systems Using Genetic Algorithms, Engineering Optimization (2002) Vol.34(1), 83-100.
[2]
Partha Chakroborty, Genetic Algorithms for Optimal Urban Transit Network Design, Computer-Aided Civil and Infrastructure Engineering 18 (2003) 184-200.
[3]
Christoph E.Mandl, Applied Network Optimization, Academic Press, London, 1979.
[4]
Christoph E.Mandl, Evaluation and Optimization of Urban Public Transport Networks, Third Congress on Operations Research, Amsterdam, Netherlands (1979).
[5]
Christoph E.Mandl, Evaluation and Optimization of Urban Public Transport Networks, European Journal of Operational Research 5 (1980) 396-404.


File translated from TEX by TTH, version 4.03.
On 08 Apr 2012, 07:31.