# A Variable Neighbourhood Search-Based Algorithm for the Transit Route Network Design Problem
## 1 Introduction
Recent efforts have developed various evolutionary algorithms to solve both the transit route network design and the frequency setting problem (TRNDFSP), including single-objective [22] and multi-objective genetic algorithms [23; 24], Differential Evolution [25], heuristic-aided Stochastic Beam Search [26], as well as memetic algorithms [27]. Apart from evolutionary algorithms, swarm intelligence has been recognised as a promising tool in solving the TRNDP. Artificial bee colony algorithms (BCO) were presented in [PERSON] [28] and [PERSON] [29], while ant colony optimisation (ACO) has been also explored [30; 31]. In a similar context, [PERSON] and [PERSON] [32] and [PERSON] et al. [33] proposed PSO-based algorithms, while multi-objective PSO variants coupled with integer programming were proposed in [PERSON] and Kepaptsoglou [34; 35] and [PERSON] et al. [36] to design transit networks operated by electric buses and allocate charging infrastructure. Other metaheuristic approaches include simulated annealing [37; 38], cat swarm optimisation [39], and tabu search [40; 41]. Hybrid metaheuristic methodologies have been proposed as well, combining different metaheuristics [42; 43; 44; 45]. Apart from metaheuristics, in a notable approach, [PERSON], [PERSON], and [PERSON] [46] proposed the use of hyper-heuristics, which combine and control different low-level heuristics for solving the problem. To the authors' knowledge, these results, along with those in [PERSON] et al. [26], constitute the state-of-the-art for the TRNDP. The interested reader is referred to the review papers by [PERSON] and [PERSON] [47], [PERSON] and [PERSON] [48], [PERSON] et al. [49], and [PERSON] et al. [50] for more information on the various problem aspects and associated solution methods. More recently, [PERSON] et al. [12] reviewed metaheuristic applications on the TRNDP and compared their relative performance on [PERSON]'s benchmark network. The latter is the most widely used instance for testing the performance of several of the existing algorithms in the respective literature. Despite the extensive literature on the TRNDP, the overview of the literature shows that, interestingly, VNS has not been applied to the problem at hand. In this context, this study proposes a Variable Neighbourhood Search (VNS)-based algorithm for the TRNDP. The motivation for this work is straightforward; as to the authors' knowledge, this is the first study to apply a VNS-based methodology to the TRNDP, despite the vast literature on the problem. Interestingly, VNS implementations have achieved very satisfactory results on Vehicle Routing Problem (VRP) variants [51; 52; 53; 54; 55]. Moreover, neighbourhood moves are considered crucial in designing efficient algorithms for the TRNDP [38]. The proposed algorithm is simple and effective, exploiting a storage structure to speed up solution evaluation, yielding superior results or matching state-of-the-art approaches. In fact, the potential of VNS for the TRNDP is corroborated by our results on [PERSON]'s Swiss benchmark network [4], which is widely perceived as the basis for comparison among different algorithms [12]. In two cases, the algorithm has matched the existing best solutions, while in the remaining cases, it has outperformed other approaches. Interestingly, the proposed VNS-based algorithm has produced results that compare favourably to much more elaborate approaches, which require a lot more modelling effort, such as hyper-heuristics. Experiments on a larger benchmark by [PERSON] [56] also demonstrated the potential of the algorithm. The remainder of the paper is organised as follows: Section 2 reviews the related literature and presents the TRNDP problem Section 3 presents the solution methodology and the experimental results. Conclusions and suggestions are given in Section 4.