A Neighbourhood Search Algorithm for Determining Optimal Intervention Strategies in the Case of Metro System Failures

Two basic patterns of urban land use and transportation systems may be identified worldwide: the Los Angeles and the Manhattan pattern. The former is characterized by a low population density and a large urbanized area. In this context, the private car system is predominant and the most efficient in mobility choices. Likewise, the use of public transport systems is limited to low-income users without the ownership of a private car (or motorbike). Hence, due to the need to adopt low-fare policies in low-density contexts over long distances and with multiple origins/destinations to be covered, implementing public transport systems means high operational costs unlikely to be compensated by ticket revenues. Moreover, the adoption of suitable demand management policies for reducing the use of private vehicles entails only an increase in user travel costs without any significant variation in terms of mobility choices. Hence, the most widely adopted public transport systems are generally buses or, if one or more main routes can be identified, regional trains offering low-frequency services with limited timetables.

The distinctive characteristics of the Manhattan pattern are high population densities and activity concentration. In these contexts, public transport modes are the most sustainable, together with cycling and walking. Indeed, travelling by carrequires a street use of about $10 \mathrm{~m}^2$ per person (with the assumption of 1.25 passengers per car), while $0.2-0.4 \mathrm{~m}^2$ per user is required in the case of the public transport system (both for buses and metros). Moreover, adoption of the private car mode requires additional space for parking, since a car is usually parked for most of the day (the average trip duration is about $2-4 \mathrm{~h} /$ day). Scant availability of parking spaces, combined with appropriate policies (from simple pricing to full restriction of use) and the proneness to public transport use also for high-income passengers, allows the adoption of travel demand management strategies to reduce private vehicle use. Indeed, in such contexts due to the high densities and the concentration of activities (i.e. multiple origins/destinations situated in small areas), high accessibility levels can be ensured by organizing integrated public transport based on metro/rail services as a mobility backbone with high-quality performance (i.e. reduced waiting and travel times) and bus services with feeder functions, increasing the geographical coverage of rail services. Hence, it is possible to achieve high occupancy levels of public transport vehicles with corresponding high ticket revenues without penalizing user mobility choices.

Obviously, in real contexts, as in most European cities, there are urban structures that are intermediate between the two mobility patterns described above. Hence, it is necessary to identify the optimal combination of private car and public transport which maximizes user accessibility, also considering further aspects such as air and noise pollution, and congestion.

Since in both patterns the rail/metro system can be an important element for implementing mobility choices, our proposal is to develop suitable methods for reducing discomfort for public transport users in the event of system disruption. Such strategies can be included in the wider topic of transportation system optimization that is commonly indicated as the Transportation Network Design Problem (TNDP). However, an extensive review of the TNDP can be found in Magnanti and Wong [1], Yang and Bell [2] and Feremans et al. [3]. Generally, the TNDP can be decomposed into a Road Network Design Problem (RNDP) and a Mass Transit Network Design Problem (MTNDP). The RNDP, which consists in designing variables of the private car system, has been widely studied elsewhere. The proposed models may be classified into discrete variable models (Billheimer & Gray [4] and Gao et al. [5]), continuous variable models (Dantzig et al. [6], Cascetta et al. [7], Adacher & Cipriani [8], Caggiani & Ottomanelli [9] and Gallo et al. [10]) and mixed variable models (Cantarella & Vitetta [11] and Cantarella et al. [12]). Likewise, the MTNDP, which consists of designing variables of the public transport system, has been explored by Desaulniers and Hickman [13], Guihaire and Hao [14] and Kepaptsoglou and Karlaftis [15]. The models in question can be classified into service frequency optimization (Salzborn [16], Yu et al. [17] and Gallo et al. [18, 19]), joint design of frequencies and routes (Laporte et al. [20] and Van Nes et al. [21]) or elastic demand approach models (Lee & Vuchic [22] and Marìn & Garcia-Ròdenas [23]). However, there are also several contributions related to specific themes such as the budget reductions of public transport (D'Acierno et al. [24]), the definition of energy-efficient driving profiles (Gallo et al. [25]), effect of information on user choices (Pariota & Bifulco [26] and Bifulco et al. [27]) or safety of transportation systems (Dell'Acqua et al. [28]).

Solving the TDNP requires that suitable models be implemented to provide system performance corresponding to each feasible solution (i.e. alternative project). Generally, these models can be formulated by means of an analytical approach (see, for instance, Cantarella [29], Nguyen et al. [30], Cascetta [31] and D'Acierno et al. [32]). However, since a rail or a metro system has a high degree of complexity due to the extensive interaction among their components (i.e. infrastructure, rolling stock, signalling system, travel demand and planned timetable), performance models are generally based on apposite simulation techniques. In particular, rail simulation models can be classified into macroscopic, mesoscopic or microscopic models, according to the level of network details adopted; stochastic or deterministic, according to the statistical assumption on analysed variables; synchronous or asynchronous, according to the ability to analyse different classes of trains jointly (such as high speed or regional trains). However, details on rail (or metro) simulation models can be found in Kettner and Sewcyk [33], Prinz et al. [34], Marinov and Viegas [35], Nash and Huerlimann [36] and Siefer and Radtke [37].

The aim of this article is to apply a heuristic algorithm to define optimal intervention strategies which minimize user discomfort in the case of a metro system breakdown. Indeed, as widely shown in the literature (see, for instance, Batley et al. [38]), in the case of failures which reduce the quality of the service without interrupting it, users may decide to increase their travel duration (i.e. continue to use the metro system) rather than modify their planned trip (for instance, by choosing an alternative transport mode). Hence, due to the need to model the detailed effects of each intervention strategy on passengers, we propose adoption of a micro-simulation approach (based on the use of OpenTrack ${ }^{\text {® }}$ software (Nash & Huerlimann [36]) appropriately integrated with our tools) for calculating metro system performance.

The article is organized as follows: Section 2 provides the framework for identifying optimal intervention strategies in the case of metro system failures; Section 3 describes the main features of the proposed solution algorithm; Section 4 applies the proposed approach in the case of a real-scale metro line; finally, conclusions and research perspectives are outlined in Section 5.

As widely shown in the literature (see, for instance, Montella et al. [39]), the optimal intervention strategy in the case of metro system failures can be formulated as a multidimensional bi-level optimization problem, that is,

s.t.

where $y$ is the intervention strategy vector, $\hat{y}$ is the optimal value of $y ; S_y$ is the feasibility set of $y ; Z$ is the objective function to be minimized; $f c$ is the failure context vector; $t p$ is the transportation network performance vector; $r p$ is the rail system performance vector; $u f$ is the user flow vector; $\Pi$ is the simulation function; $i^0$ is the rail infrastructure vector in non-perturbed conditions; $r^0$ is the rolling stock vector in non-perturbed conditions; $s^0$ is the signalling system vector in non-perturbed conditions; $p t$ is the planned timetable vector.

As shown by D'Acierno et al. [40, 41], the simulation function (2) can be formulated by means of the interaction among four simulation models: a failure simulation model, which envisages reduction in metro system performance due to the analysed failure context; a service simulation model, which provides real timetables depending on metro system performance, planned timetables and adopted intervention strategies; a supply simulation model, which supplies performance of all transportation systems depending on passenger flows; a demand simulation model, which provides user choices in terms of passenger flows depending on the performance of all transportation systems (including the metro systems). Hence, since relation (2) allows for each failure context and for each feasible intervention strategy to determine all elements for the calculation of the objective function $Z$, the challenge proposed in this article is to apply some algorithms to solve problem (1). However, details in objective function formulation can be found in D'Acierno et al. [42].

The aim of this article is twofold: the classification in a vector framework of all feasible intervention strategies and the formulation of a solution algorithm for solving problem (1).

The first aim cannot be achieved in general terms since it is strongly dependent on the metro network analysed. Hence it is dealt with in the section below. The latter objective is tackled by adopting a Neighbourhood Search Algorithm (NSA) for reducing drastically the number of alternative strategies to analyse (i.e. the number of objective functions to evaluate). Indeed, the use of an exhaustive approach is feasible only in the case of very simple networks (as shown by D'Acierno et al. [43]).

The NSA is a heuristic algorithm for solving discrete optimization problems. In particular, for each vector $y$ it is possible to associate a set of vectors $\mathrm{N}(\mathrm{y}) \subseteq S y$, indicated as the neighbourhood of $y$, where the generic element $y^{\prime} \in \mathrm{N}(\mathrm{y})$ is obtained from $y$ by increasing or reducing only one component of vector $y$ and considering all other components constant.

The most commonly adopted rule for generating the following solution to be analysed is the Steepest Descent Method (SDM). It consists in analysing (i.e. calculating the corresponding objective function value) all elements of the neighbourhood and considering the solution of the lowest objective function value as the following starting point (i.e. the current solution). The algorithm ends when a better solution cannot be obtained (i.e. when the current solution is a local optimum).

In order to reduce computation times further (i.e. reducing the number of solutions to be examined), a different approach may be adopted, such as the Random Descent Method (RDM). It consists in randomly extracting an element of set $\mathrm{N}(\mathrm{y})$ and calculating the corresponding objective function value. If it is lower than the current value, the new element becomes the current solution. Otherwise, another element of the neighbourhood is analysed until a better solution is found. Also in this case, the algorithm terminates when no further improvements are possible.

However, the use of the RDM, especially in the case of non-convex objective functions, could provide different results both in terms of calculation times and objective function improvements (since we may obtain different local minima).

In order to verify its utility, the proposed approach was applied in the case of a real metro line: Line 1 of the Naples metro system (in Italy). The metro line (Figure 1), about 18 km long, consists of 18 stations, four of which (Piscinola, Colli Aminei, Medaglie d'Oro and Garibaldi) are equipped with points and recovery tracks, and two (Vanvitelli and Dante) are equipped only with points.

The proposed application consists in considering that a breakdown occurs on a train during the morning peak-hour: a run after leaving Chiaiano (i.e. the station just after Piscinola) at 7.05 breaks down and is forced to travel at a maximum speed of $45 \mathrm{~km} / \mathrm{h}$, representing a bottleneck for the whole service. In this case, in addition to the 'do nothing' strategy, it is possible to identify 20 feasible intervention strategies based on:

• continuing the service as far as a station equipped with a recovery track and driving the train onto the maintenance track just after unloading passengers on the platform;

• continuing the service until a station equipped with points and driving the train to the depot (located next to Piscinola station) by changing direction just after unloading passengers on the platform;

• recovering the damaged train on a maintenance track or at the depot with or without the use of a spare train for completing the service for the rest of the day.

The intervention strategies, according to problem (1), can be described by vector $\boldsymbol{y}$, of dimensions $(4 \times 1)$, where:

• $y_1$ represents the strategy type implemented, that is, $1=$ recovery on a maintenance track; 2 = changing direction in a station with points;

• $y_2$ represents when the strategy is implemented, that is, $1=$ during the outgoing trip; $2=$ during the return trip;

• $y_3$ represents the station where the strategy is implemented, that is, $1=$ Colli Aminei; $2=$ Medaglie d'Oro; $3=$ Vanvitelli; $4=$ Dante; $5=$ Terminus (i.e. Garibaldi during the outgoing trip or Piscinola during the return trip);

• $y_4$ represents the use of a spare train, that is, $1=$ no spare train; $2=$ spare train.

It is worth noting that the following combinations of values are not feasible:

• changing direction during the return trip, that is, $y_1=2$ and $y_2=2$;

• changing direction at the terminus, that is, $y_1=2$ and $y_3=5$;

• recovering the train in a station without a maintenance track, that is, $y_1=1$ and $y_3=3$, and $y_1=1$ and $y_3=4$.

Application of the above formulation produces 40 combinations, while there are 20 feasible solutions to analyse. Although the simplicity of the analysed network (an isolated metro line with few points and recovery tracks) entails a number of feasible solutions such as to allow an exhaustive approach, in order to show the benefits of using a heuristic algorithm, we applied both versions of the NSA and compared results with a complete analysis of solutions.

In particular, passenger flows, estimated by means of methods described in Ercolani et al. [44], were evaluated according to three travel demand levels (see, for instance, Figure 2): a 50 th percentile corresponding to average conditions, an 85 th percentile which indicates high demand conditions and a 95th percentile which denotes extremely high demand conditions. However, further details on travel demand estimation can be found in Cartenì et al. [45], Caropreso et al. [46] and Di Mauro et al. [47].

Figure 3 provides comparisons between the two proposed approaches of the NSA for different levels of travel demand; Figure 4 contrasts the exhaustive approach with the best approach of the NSA: implementation of the exhaustive approach required 1.92 h, while the use of the NSA-RDM provided the optimal solutions in 0.67 h (50th percentile), 0.68 h (85th percentile) and 0.77 h (95th percentile), with reductions in calculation time, respectively, of $65.29 \%, 64.71 \%$ and $60 \%$. Although such reductions may appear negligible in the case of the simple network analysed, they may instead be very significant in the case of more complex networks, as widely shown in the literature (see, for instance, D'Acierno et al. [43]).

In conclusion, we analysed the problem of identifying the optimal intervention solution in the case of metro system breakdowns, proposing a bi-level constrained optimization problem and a related heuristic solution algorithm for reducing calculation times. A first application was carried out in the case of a real-scale metro line, albeit with a simple framework (an isolated metro line with a limited number of points and recovery tracks), in order to show the feasibility of the proposed approach. Further research would be required to address the case of more complex metro or rail lines (network complexity), different kinds of intervention strategies and different failure severities.