Keywords: genetic algorithm, routing, scheduling, bus, behavioural response, transfers.

This paper describes the concurrent optimisation of bus network routes and schedules by means of a Genetic Algorithm (GA). Particular emphasis is placed on the development of an accurate and comprehensive objective function that best represents the value of the network. Specific genetic operators have been developed to satisfactorily drive the GA towards the optimal solution.

Bus networks are an intrinsic part of most urban public transportation systems. The effectiveness and efficiency of a bus network is dependent on many factors, including comfort, reliability, convenience, routeing, scheduling and socio- economic factors. All things being equal, as in the situation of a given fleet servicing a particular area, the two factors with the greatest impact on the merit of a bus network are routeing and scheduling. Therefore this paper concentrates on the application of a GA to discerning the optimal combination of these two factors.

Many existing bus networks are the result of ad hoc or heuristic alterations and adjustments over long periods of time, rather then a formulated design process. Analytical approaches often fail to describe the problem in a realistic and accurate manner and often sacrifice geographical accuracy and realism of demand in order to obtain a solution. Frequently, analytical methods are applied to idealised situations at the aggregate level or restricted to optimising particular sections of the network without evaluating the network in its entirety. Many of the complexities that make the problem unsuitable to traditional optimisation and search techniques are easily overcome by the GA, as it is ideally suited to solving non-linear, discontinuous, multi objective problems.

The objective function definition is the overriding constituent of any solution. In this paper the objective function described incorporates properties and constraints which have been neglected in previous studies. It includes provision for passenger transfer, dynamic origin-destination demand matrix, overlapping routes and the conflicting components of user and operator requirements. Information on behavioural response to change in public transportation systems, collated by the TCRP [1], has been adapted and incorporated into the objective function.

Problem specific genetic operators have been developed and are described in this paper. In particular, crossover is implemented at two levels, crossover between networks and between individual routes. Methods of mutation have been formulated in order to expand the area of the solution space the GA examines. The effect of the genetic operators on a sample network configuration is described and the results of the corresponding objective function evaluation are shown. The GA is applied to a standardised network that has been studied previously (Mandl [2], Baaj and Mahmassani [3], Krishna Rao et al [4]).

1

TCRP Web Document 12, "Traveler Response to Transportation System Changes, Interim Handbook", Available from: http://gulliver.trb.org/publications/tcrp/tcrp_webdoc_12.pdf (11 Feb 2003)

2

C.E. Mandl, "Evaluation and Optimisation of Urban Public Transport Networks", European Journal of Operational Research, 6, 31-56, 1980.

3

M. Hadi Baaj and Hani S. Mahmassani, "An AI Based Approach for Transit Route System Planning and Design", Journal of Advanced Transportation, ASCE 25(2), 187-210, 1991.

4

K.V. Krishna Rao, S. Muralidhar and S.L. Dhingra, "Public Transport Routing and Scheduling Using Genetic Algorithms", Proc. 8th International Conference on Computer-Aided Scheduling of Public Transport (CASPT-2000), Berlin, Germany, 21-23 June, 2000.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £82 +P&P)