# A Variable Neighbourhood Search-Based Algorithm for the Transit Route Network Design Problem
## 2 Materials and Methods  
### The TRNDP Problem  
The TRNDP refers to the construction of routes for a fleet of public transport vehicles subject to operational and other constraints. As explained in Section 2, there is no commonly accepted mathematical programming formulation of the problem due to its inherent complexity and discrete nature. Indeed, the design of a route structure for a network of realistic size is \"a non-convex (even concave) optimisation problem, for which no simple procedure exists short of direct comparison of various local optima\" [57]. [PERSON] and [PERSON] [10] attributed the difficulty of the problem to its discrete nature, as well as the difficult-to-calculate objective function, which create difficulties in obtaining a solution through traditional optimisation techniques. In the respective literature, though, specific quantitative criteria that characterise a desirable route set have been accepted [38]. [PERSON] [14] defined the characteristics of an efficient route set as the lack of unsatisfied demand, the high percentage of demand satisfied through direct trips, and a low amount of average travel time per user. Accordingly, the problem may be stated as follows [19; 29]:  
We consider a road network, denoted by the graph \(G=(N,A)\), where \(N\) is the set of nodes representing the bus stops and \(A\) is the set of links representing the street segments. A route used by the transit passengers is described by a path in the graph. We assume that the given road network is connected and undirected. We have a demand matrix denoted by \(d_{ij}\), which represents the number of trips per time unit between node \(i\) and node \(j\). We also denote by \(D\) the origin-destination matrix (O-D matrix) as follows:  
\[D=\left\{d_{ij}|i,j\in[1,2,\ldots,|N|]\right\} \tag{1}\]  
We also know the travel time matrix for the road network denoted by \(tt_{ij}\), which represents the in-vehicle travel time between node \(i\) and node \(j\). By \(TT\), we denote the travel time matrix as follows:  
\[TT=\left\{tt_{ij}|i,j\in[1,2,\ldots,|N|]\right\} \tag{2}\]  
Thus, the problem may be defined in the following way: For a given set of nodes \(N\), a demand matrix \(D\) and a travel time matrix \(TT\), we must determine a set of routes \(RS\) that ensure all passengers are able to travel from their origins to their destinations in an efficient way. A very simple form of the objective function is used:  
\[Z=ATT_{RS} \tag{3}\]  
where \(ATT_{RS}\) denotes the Average Travel Time per passenger for the specific route set \(RS\). This metric is considered the most informative, as it incorporates transfer penalties and thus implicitly reflects direct demand coverage as well [38]. Our objective is to find a set of routes \(RS\) such that \(Z\) is minimised. Additionally, the solution must satisfy the following real-world constraints [38]:* The length of each route should be higher than a minimum predefined value but should not exceed a maximum number of nodes which reflects practical considerations such as scheduling and shift duration;
* The route set must be connected, so that all passengers can get to their destinations;
* A specific number of routes are offered by the transit provider due to budget limitations. As such, a high-level mathematical formulation can be given as follows.