Solving bus terminal location problems using evolutionary algorithms

Bus terminal assignment with the objective of maximizing public transportation service is known as bus terminal location problem (BTLP). We formulate the BTLP, a problem of concern in transportation industry, as a p-uncapacitated facility location problem (p-UFLP) with distance constraint. The p-UFLP being NP-hard (Krarup and Pruzan, 1990), we propose evolutionary algorithms for its solution. According to the No Free Lunch theorem and the good efficiency of the distinctive preserve recombination (DPX) operator, we design a new recombination operator for solving a BTLP by new evolutionary and memetic algorithms namely, genetic local search algorithms (GLS). We also define the potential objective function (POF) for the nodes and design a new mutation operator based on POF. To make the memetic algorithm faster, we estimate the variation of the objective function based on POF in the local search as part of an operator in memetic algorithms. Finally, we explore numerically the performance of nine proposed algorithms on over a thousand randomly generated problems and select the best two algorithms for further testing. The comparative studies show that our new hybrid algorithm composing the evolutionary algorithm with the GLS outperforms the multistart simulated annealing algorithm.