A Multi-Objective Ant Colony System-Based Approach to Transit Route Network Adjustment

A transit route network design problem is a vitally important problem in the area of public transit systems. Most of studies on this problem aim to design a new transit network, which is often an infeasible option in practice since it is highly challenging to replace an existing network with a completely new one. In this paper, we propose a Multi-objective Ant Colony System-based Approach (MACSA) to adjust routes of bus lines for an existing transit network, such that transit service quality is improved while making the smallest deviation of the adjusted network from the existing one. First, all the bus lines in a network are sorted according to their performance. Then, a multi-objective ant colony system is adapted to adjust the sorted bus lines one by one. Besides traditional optimization objectives to maximize direct passenger flow and minimize line repetition coefficient, a new optimization objective (metric), termed adjustment degree, is proposed to measure the difference between adjusted bus lines and existing ones. Needleman-Wunsch algorithm is introduced to calculate the adjustment degree. A multi-pheromone updating mechanism is suggested to guide ants to search for better bus lines for each objective. MACSA is applied to benchmark problem instances and a real-world problem and compared with six approaches. Experiments show that MACSA can achieve an adjusted network with higher direct passenger flow, lower repetition coefficient and smaller adjustment degree. The adjustment degree achieved by MACSA is 1.61-53.82% smaller than that of other comparative approaches.