Abstract:

As the emergencies such as traffic congestion may interfere with vehicles to complete a trip on time and may further result in the failure of relevant bus scheduling scheme,it is highly necessary to establish a high-reliability scheme which adapts to the traffic environment change. In this paper,based on the assumption that the delay time caused by uncertain factors follows the normal distribution and that the regional bus scheduling problem can be regarded as a set-partitioning problem of“part of trips are completed by a vehicle”,the concept of reliability is introduced to formulate the regional bus scheduling scheme as a multi-objective programming problem with the minimum cost of vehicles as the previous objective and with the maximum reliability as the secondary objective. Then,the constraint method is used to convert the secondary objective into the corresponding constraint,which makes the model to be a single-objective programming problem. Moreover,an improved genetic algorithm,which redesigns a chromosome coding,a fitness function,a heuristic procedure for population initialization and the crossover /mutation operation according to the features of bus scheduling,is designed to solve the problem. An example is finally given to show the correctness and effectiveness of the proposed model and algorithm.

Key words: regional bus scheduling, multi-objective programming, reliability, improved genetic algorithm