# A Variable Neighbourhood Search-Based Algorithm for the Transit Route Network Design Problem
## 1 Introduction  
Sustainability calls for a behavioural shift to public transport, as the increased reliance on automobiles has deteriorated traffic conditions and air quality. In this context, the level of service provided by the transit system is crucial, offering a competitive alternative compared to other transportation modes available to passengers. Reasonably, the level of service provided is directly linked to the design of the transit network, which should account for user preferences while trying to ensure a profitable operation for the transit agency. The transit operator aims to minimise costs while meeting the service standards expected by transit users. Operational costs usually depend on the number of routes, the fleet size, the length of the routes, and the hours of operation. Buses are, perhaps, the most popular means of public transport due to their flexibility, relatively low fixed cost, and ability to transport a high number of passengers. Undenably, bus transit networks must offer high-quality service to passengers to effectively compete with private or other public modes. The quality of a transit route may be measured in terms of network parameters, such as route directness, service coverage, network efficiency, and the number of transfers required [1]. The latter is perhaps one of the most crucial parameters that influence the perceived quality of the transportation service provided by transit modes, as most transit riders are only willing to transfer once per trip. This means that transit ridership could be fostered by optimising route networks to minimise transfers and increase route directness. The associated problem has been widely referred to as the Transit Route Network Design Problem (TRMDP), with several optimisation techniques developed to produce routes that satisfy certain planning criteria. However, there is no uniformly adopted method for planning transit networks, and there are significant differences among the various methods developed over the years in terms of solution quality, with newer methods consistently outperforming earlier implementations. Generally, the problem of designing a transportation network deals with the maximisation or the minimisation of an objective function value that represents the planning goaland is subject to a variety of constraints, which reflect the performance requirements and the physical and resource limitations of the network. From its nature, the general network design problem is a highly complex and multiply-constrained problem that belongs to the class of NP-hard problems [2]. This means that it cannot be solved for large instances in polynomial time, as the computational cost increases exponentially with the size of the problem. Thus, planners and researchers turned to combinatorial optimisation techniques and algorithms to deal with the complexity of the problem. There is rich literature concerning the design of transit networks. Multi-step heuristic algorithms were presented in the early studies of [PERSON] [3], [PERSON] [4], and [PERSON] [5]. Another branch of the literature considered analytical methods aimed at determining network structures for transit services by determining some of the physical characteristics. However, analytical methods, such as those proposed by [PERSON] [6], [PERSON] [7], and [PERSON], [8] optimise only parameters such as route spacing and length rather than determining the actual routes in a given network [9]. Additionally, there have been attempts to formulate the TRNDP as a mathematical programming problem [10; 11]. These formulations, however, do not determine the routes through their mathematical program but construct them to achieve some desirable features, which are reflected by the objective function and the constraints. During the last few decades, metaheuristic approaches emerged as promising alternatives for solving the TRNDP [12]. Among such implementations, genetic algorithm variants (GAs) have been widely applied for the TRNDP [9; 13; 14; 15; 16; 17; 18; 19; 20; 21].