AN EFFICIENT AND PRACTICALLY ROBUST HYBRID METAHEURISTIC ALGORITHM FOR SOLVING FUZZY BUS TERMINAL LOCATION PROBLEMS

摘要

Bus network design is an important problem in public transportation. In practice, some parameters of this problem are uncertain. We propose two models for the bus terminal location problem with fuzzy parameters. In the first formulation, the number of passengers corresponding to each node is a fuzzy number. In the second formulation, an additional assumption of fuzzy neighborhood is considered. These problems being NP-hard, we use a genetic algorithm (GA) and a simulated annealing (SA) algorithm for solving them. We also propose an idea to hybridize these algorithms. In our hybrid algorithm, SA is applied as a neighborhood search procedure of GA on the best individual of the population, which is the best available approximation of the optimal solution, with a varying probability that is gradually increased with the increase in the number of iterations in GA. We then implement GA, SA, our hybrid algorithm, and a recently proposed hybrid algorithm making use of a constant probability for application of SA on all the individuals of the population of GA, and use a nonparametric statistical test to compare their performances on a collection of randomly generated medium to large-scale test problems. Results of computational experiments demonstrating the efficiency and practicability of our proposed algorithm are reported.