The Memetic algorithm for the optimization of urban transit network

• The Memetic algorithm to optimize the urban transit network is proposed.
• Four types of local search operators to improve the performance are designed.
• The proposed algorithm is tested to improve the performance to other algorithms.
• Some interesting issues for the transit network are analyzed and discussed.

This paper employs the Memetic algorithm (MA) to optimize the urban transit network. Aiming at the optimal route configuration and service frequency for the urban transit network, the objective function of the proposed mathematical model is to minimize the passenger (user) cost and to reduce the unsatisfied passenger demand at most. MA is one of the recent growing evolutionary computation algorithms. It is imbedded with the local search operator based on the classical genetic algorithm (GA) to improve the computational performance. We represent the solution with two single link lists (SLL), and design four types of local search operators: 2-opt move (Type A), 2-opt move (Type B), swap move and relocation move to obtain the better chromosomes for the GA. At the same time, an effective try-an-error procedure for verifying the local search operator is presented to increase the search efficiency. The algorithm has been tested with benchmark problems reported in the existing literatures. Comparing the results obtained by our algorithm and traditional algorithms which have been proved to be efficient, it demonstrates that the proposed algorithm could improve the computational performance relative to other algorithms.