Optimal Time Transfer in Bus Transit Route Design Using Genetic Algorithms


Somnuk Ngamchai and David J. Lovell

ASCE Journal of Transportation Engineering, Vol. 129, No. 5, pp. 510-521.


ABSTRACT


This paper is concerned with the design of transit routes and service frequencies. While this topic tends to receive less attention than more short-term planning efforts such as vehicle and crew scheduling, it is a critical component of longer range planning, when that flexibility is available. When optimizing transit route design and the associated service frequencies, the objective is usually to minimize the overall cost, generally a combination of user costs and operator cost. The problem tends to suffer from several forms of mathematical complexity, such as non-linearity and non-convexity of the objective function, and the discrete and multi-objective nature of route design. This paper will investigate the major components and important constraints in bus transit route design. Existing approaches and models are identified and studied, which will suggest the elements of a new model. The properties of the new model which provide particular insight into the problem are demonstrated. The model is developed for optimizing bus transit route configuration and service frequencies on each bus route. It is comprised of three major components, all of which are designed to obtain as efficient a solution as possible. The route generation algorithm is guided by several strategies, including the demand pattern and an insignificantly different load factor search. The route evaluation algorithm designs the service frequency on each route, and applies headway coordination techniques at each transfer point to decrease transfer times between routes if it is possible to reduce the overall cost. This algorithm also calculates the overall network cost as a performance measure. Finally, the route improvement algorithm will modify the existing route configuration, making such alterations as changing the transfer locations in the system and investigating shortest paths between certain origins and destinations to test new components of the routes. The model is solved with a genetic algorithm. It is particularly suited for the route generation and improvement algorithms for designing optimal routes, and to the route evaluation model to consider which routes should be coordinated or integrated in this model. Moreover, effective problem-specific genetic operators are demonstrated to facilitate the search. The model is applied to a set of test networks and performance results are presented.