Designing robust rapid transit networks with alternative routes

Designing robust rapid transit networks with alternative routes Gilbert Laporte 1 , Angel Marı ´n 2 , Juan A. Mesa 3 *and Federico Perea 4 1 Canada Research Chair in Distribution Management, HEC Montre ´al, Canada 2 Departamento de Matema ´tica Aplicada y Estadı ´stica, Universidad Polite ´cnica de Madrid, Spain 3 Departamento de Matema ´tica Aplicada II, Universidad de Sevilla, Spain 4 Departamento de Me ´todos Estadı ´sticos, Universidad de Zaragoza, Spain SUMMARY The aim of this paper is to propose a model for the design of a robust rapid transit network. In this paper, a network is said to be robust when the effect of disruption on total trip coverage is minimized. The proposed model is constrained by three different kinds of flow conditions. These constraints will yield a network that provides several alternative routes for given origin–destination pairs, therefore increasing robustness. The paper includes computational experiments which show how the introduction of robustness influences network design. Copyright #2010 John Wiley & Sons, Ltd. KEY WORDS: rapid transit systems; network design; robustness 1. INTRODUCTION The increased demand for passenger transportation in and around urban areas and the resulting traffic congestion have lead many cities to build rapid transit systems and new conventional railway lines (see, e.g., [1]). Because of the high construction and operating costs of such systems, it is important to pay attention to issues affecting effectiveness and robustness at the planning stage. A crucial part of the planning process is the underlying infrastructure network design which consists of two intertwined problems: the determination of alignments and the location of stops and stations. Because most rapid transit systems are railways, we will use both terms indiscriminately. Design decisions are considered at the strategic level, but they must incorporate the traffic behavior of users. At the upper level the objective is to maximize demand coverage, subject to design and budget constraints. At the lower level the traffic demand decisions are incorporated in the transit network design alternatives, considering the traffic cost of private and public modes, based on the system supply (the network to be constructed) and on assumptions made about the modal traffic costs. The selection and comparison of these alternatives may be carried out by considering that users choose both a path and a travel mode. Several studies have addressed railway or metro network design problems. The location of a single alignment has been dealt with in the papers by Bruno et al. [2,3] and Dufourd et al. [4]. In the first one the weighted travel cost of all the users is minimized, while in the other two the coverage of the population by public network is maximized. The work of Laporte et al. [5], incorporates origin– destination data in order to maximize the trip coverage. The papers of Hamacher et al. [6] and Laporte et al. [7] consider the problem of locating stations on a given alignment in different set-ups. The first one assumes that there already exists a partial alignment on which some stations are located, while the second one considers a discrete set of candidates to locate the stations. Garcı ´a and Marı ´n [8,9] study the mode interchange and parking network design problems using bilevel programing. They address the multimodal traffic assignment problem with combined modes at a lower level. Laporte et al. [10] JOURNAL OF ADVANCED TRANSPORTATION J. Adv. Transp. 2011; 45:54–65 Published online 29 July 2010 in Wiley Online Library (wileyonlinelibrary.com). DOI: 10.1002/atr.132 *Correspondence to: Juan A. Mesa, Departamento de Matema ´tica Aplicada II, Universidad de Sevilla, Spain. E-mail: [email protected] Copyright #2010 John Wiley & Sons, Ltd. extend the previous models by incorporating station location and multiple alignments. Their model maximizes demand coverage, subject to budget constraints. Marı ´n [11] studies the inclusion of a free but bounded number of lines, and each origin–destination (O/D) of the lines is chosen in the rapid transit network design model. In a related field, a number of authors (see, e.g., Fortz and Labbe ´[12], Fortz et al. [13], and Gro ¨tschel et al. [14]) have studied the problem of designing robust low cost communication networks that can survive the failure of some edges. However, telecommunication and transportation networks operate differently. In telecommunication networks the routing of signals is decided by the network managers whereas in transportation networks passengers make their own choices. As a result the same solution methodology cannot apply to both types of problems. Online planning in railway and other transportation networks needs to react in the best possible way to perturbations, and network robustness must be taken into account at the planning stage. Several sources of uncertainty are present in transportation systems. Stochasticity of demand has been addressed by many authors, e.g., Lou et al. [15] and Yin and Lawphongpanich [16]. We are concerned here with uncertainty relative to the network itself (see, e.g., [17]). The review article by Yang and Bell [18] considers link additions and link improvements in network design problems and casts these problems in the general framework of bilevel programing. In the first case robust optimization is considered from a stochastic point of view by Rockafellar and Wets [19] who identify robust decision by discovering similarities among the optimal solutions for different scenarios. A framework for robust optimization is analyzed in Malcolm and Zenios [20] and Mulvey et al. [21]. These papers assess different choices for parameters while penalizing variance of the cost of deviations from feasibility. A serious difficulty in this approach is to strike a proper balance between the terms of the objective function. One must achieve a tradeoff between the mean and variance of the solution, and deviations from feasibility under all scenarios. In the second case one seeks a solution that remains feasible even for worst-case scenario parameters. A bibliography on this topic, with comments on robustness in combinatorial optimization, can be found in Nikulin [22]. This optimization approach considers the robust counterpart of the problem, see for example, Ben-Tal and Nemirovski [23,24] in which a robust solution is sought using ellipsoidal uncertainty sets for data. The over-conservatism of this strategy is unsuitable for many situations in which only a low number of parameters are uncertain simultaneously [25,26]. This is in fact the case of railway network design problems in which robustness is considered according to disruptions to the usual operations [27,28]. In general, the robustness of a system indicates the influence of the perturbations on the usual functioning. The more a system is capable of achieving its aim in adverse conditions, the more robust it becomes. The perturbation on the operations of a railway system can come from internal causes (signals or rolling stock failures, crew problems, coordination and computer problems, etc.) or from external causes (extreme weather conditions, a drop in electrical power, etc.). The occurrence of two or more perturbations at the same time is very infrequent, but since lines use several sections of the network, a disruption on one arc affects the operation on others, causing secondary or knock-on delays. Our goal is to design robust transportation networks. We consider that a railway network is robust when, in the event of arc failures, a high proportion of the passengers will still find the network useful and faster than other means of transportation. Therefore, we will build networks that provide several routes to passengers, thus increasing robustness. Although flow variables are introduced in our models, the reader should note that such variables are used only for modeling purposes, and to define the different routes available to each O/D pair on the RTN, but users always have the final say when it comes to deciding which route to take, in accordance with the first Wardrop principle. In principle, modeling user behavior can be done through the use of variational inequalities or of mathematical programs with a rather large number of equality constraints (see, e.g., [29]). But given the very high computational complexity of these models, we have avoided the use of bilevel programing in the RTND model. This choice is coherent with the assumption that the system capacity is not considered in our model. Nevertheless, our designs will provide users with several possibilities. Some models can be used to design networks that maximize trip coverage under normal conditions, i.e., no disruptions occur. Others maximize trip coverage in the presence of disruptions. We propose a combination of these two objectives, with the aim of providing a near-optimal network both when no failures occur and when an arc is inoperative. Copyright #2010 John Wiley & Sons, Ltd. J. Adv. Transp. 2011; 45:54–65 DOI: 10.1002/atr DESIGNING ROBUST RAPID TRANSIT NETWORKS 55 The remainder of this paper is organized as follows. Section 2 presents the model for the core network design problem. Section 3 is dedicated to the inclusion in the model of the proposed robustness constraints. Section 4 describes computational experiments. The paper ends with some conclusions. 2. A MODEL FOR THE RAPID TRANSIT NETWORK DESIGN PROBLEM In our model for the Rapid Transit Network Design Problem (RTNDP) we assume that the mobility patterns in a metropolitan area are known. This implies that the number of potential passengers from each origin to each destination is given. We also assume that the locations of the potential stations are given. There already exists a different mode of transportation (for example, private cars) competing with the railway. When deciding which mode each demand is allocated to, the comparison between the generalized costs of the travelers is used. The aim of the model is to design a network, i.e., to decide at which nodes to locate the stations and how to connect them, consisting of railway lines, and covering as many trips as possible. Since resources are limited we also impose a budget constraint on construction costs. Similar ILP models have appeared in the literature (see [10,30]). In these models, flow variables on the routes through the RTN are binary, therefore allowing only to decide whether an O/D pair is assigned to the RTN or not. In our model we allow these variables to take any value in [0,1] and add flow variables on the alternative mode. This way we allow that part of the demand of the O/D pair is routed through the RTN and the rest through the alternative mode, thus allowing our model to become robust when providing O/D pairs with different alternative routes in the RTN (see Section 3). 2.1. Data and notation The model uses the following notation: (1) A set N¼{n i :i¼1,2...,n} of potential sites for locating stations. (2) A set A0of feasible (bidirectional) arcs linking the elements in N. Therefore, we have a graph G0¼(N,A0), from which arcs are to be selected to form railway lines. Furthermore, there exists a graph G00 ¼(N,A00) representing the network used by the complementary mode (e.g., the street network). Let G¼(N,A), where A¼A0[A00, be the whole network. Denote by NðiÞ¼fnj:9a2A0;a¼ðni;njÞg the set of nodes adjacent to n i . (3) Every feasible arc a¼ðni;njÞ2A0has an associated length d ij equal to approximate Euclidean distances if the system to be designed is underground, and to street network distances if it is at grade. However, forbidden regions will increase distances, and d ij can also be interpreted as the generalized cost (time) of traversing arc a¼ðni;njÞ2A0. (4) For every node n i and every arc a2A0there is an associated cost of constructing the corresponding infrastructure: c i is the cost of building a station at node n i , and c a is the cost of building link a.A bound C max on the available budget is also given. (5) The demand pattern is given by a vector (g w ): w2W, where Wis the set of ordered O/D pairs: W¼fw¼ðp;qÞ:np;nq2Ng. (6) The generalized cost of satisfying every demand by the railway network and the complementary modes are uRN wand uCOM w, respectively. While the cost of using the complementary mode depends on its network and therefore is an input data, the cost of using the railway depends on the topology of the network to be constructed. The computation of railway costs uRN wcan be done by adding the lengths of the arcs of the path of win the railway network. Let u w be the generalized cost of weither by G0or by G00. The aim of the model is to design a network consisting of a set Lof lines, |L| being a low number. Since constraints on the total cost will be imposed, we will allow some lines of Lto not be included in the designed network. Note that for the model to be meaningful we need to impose technical constraints on the data: both the lengths d ij on A0and the complementary mode cost uCOM wmust satisfy the triangle inequality. Copyright #2010 John Wiley & Sons, Ltd. J. Adv. Transp. 2011; 45:54–65 DOI: 10.1002/atr 56 G. LAPORTE ET AL. 2.2. Variables The following variables will be used in the model: yl i¼1, if node n i is a station of line l; 0 otherwise. xl ij ¼1, if the arc a¼ðni;njÞ2A0belongs to line l2L; 0 otherwise. x ij , if the arc a¼ðni;njÞ2A0belongs to the railway network; 0 otherwise. ~ fw ij denotes the proportion the demand of w2Wgoing through arc (n i ,n j )2A0, from n i to n j , ~ fw ij 2½0;1, if no failure occurs. Note that these variables will define the fastest route for win the network to be built. ~ ’w ij denotes the proportion of the demand of w2Wthrough arc (n i ,n j )2A0, from n i to n j ,~ ’w ij 2½0;1,if no failure occurs. h l ¼1, if line lis included; 0 otherwise. p w ¼1, if the demand of wis allocated to the railway network, that is, if its fastest route in the network takes less time than that of the alternative mode; 0, otherwise. In practice, variables ~ fw ij and ~ ’w ij often take integer values, unless more than one route take equal time. 2.3. Objective function and constraints The objective of our model is to maximize the railway demand coverage when no disruption occurs: z1¼X w¼ðp;qÞ2W gwpw: The constraints are as follows: Budget constraints: X ðni;njÞ2A0;i<j cijxij þX l2LX hi2N ciyl iCmax:(1Þ Alignment location constraints: xl ij yl i;ðni;njÞ2A0;i<j;l2L(2Þ xl ij yl j;ðni;njÞ2A0;i<j;l2L(3Þ xl ij ¼yl ji;ðni;njÞ2A0;i<j;l2L(4Þ xl ij xl ij;ðni;njÞ2A0;i<j;l2L(5Þ xl ij X l2L xl ij;ðni;njÞ2A0;i<j(6Þ X j2NðiÞ xl ij 2;ni2N;l2L(7Þ hlþX ðni;njÞ2A0;i<j xl ij ¼X ni2N yl i;l2L(8Þ 1 2X ðni;njÞ2A0;i<j xl ij þMðhl1Þ0;l2L(9Þ 1 2X ðni;njÞ2A0;i<j xl ij þMhl0;l2L(10Þ X ni2BX nj2B xl ij B jj 1;BN;B jj 2;l2L:(11Þ  Copyright #2010 John Wiley & Sons, Ltd. J. Adv. Transp. 2011; 45:54–65 DOI: 10.1002/atr DESIGNING ROBUST RAPID TRANSIT NETWORKS 57 Routing demand conservation constraints: X ðni;npÞ2A0 ~ fw ip þX ðni;npÞ2A00 ~ ’w ip ¼0;w¼ðp;qÞ2W(12Þ X ðnp;njÞ2A0 ~ fw pj þX ðnp;njÞ2A00 ~ ’w pj ¼1;w¼ðp;qÞ2W(13Þ X ðni;nqÞ2A0 ~ fw iq þX ðni;nqÞ2A00 ~ ’w iq ¼1;w¼ðp;qÞ2W(14Þ X ðnq;njÞ2A0 ~ fw qj þX ðnq;njÞ2A00 ~ ’w qj ¼0;w¼ðp;qÞ2W(15Þ X ðni;nkÞ2A0 ~ fw ik X ðnk;njÞ2A00 ~ fw kj ¼0;if k=2fp;qg;w¼ðp;qÞ2W(16Þ X ðni;nkÞ2A00 ~ ’w ik X ðnk;njÞ2A00 ~ ’w kj ¼0;if k=2fp;qg;w¼ðp;qÞ2W(17Þ ~ fw ij þ~ ’w qj 1;ðni;njÞ2A;w2W:(18Þ Location-allocation constraints: ~ fw ij þpw1X l2L xl ij;ðni;njÞ2A0;w2W:(19Þ Splitting demand constraints: "þuwuCOM wMð1pwÞ0;w¼ðp;qÞ2W:(20Þ where uw¼P ðni;njÞ2A0 dij~ fw ij þP ðni;njÞ2A00 uCOM ij ~ ’w ij ,Mis a large real number, e>0 is a small tolerance, and uCOM ij is the generalized cost of traversing arc (n i ,n j ) by the complementary mode. Constraint (1) is the budget constraint. Constraints (2) and (3) ensure that a link is included in the railway network only if the nodes to which the link is incident are also selected. Constraints (4) allow edges to be used in both directions. Constraints (5) and (6) state that arc (n i ,n j ) is built if and only if a line uses it. Constraints (7) force each node to have at most two associated edges of each line. Constraints (11) ensure that a line does not contain a cyclic subgraph. Note that these constraints along with (8) guarantee that the lines to be constructed will induce paths. However, a line of the network must have at least one edge, which is ensured by constraints (9). If a line lis not considered in the design then it does not have any edge by (10). Constraints (12)–(18) are the flow conservation constraints at each node. The incoming flow equals the outgoing flow for both pairs of variables. We also impose that both outgoing flows and both incoming flows must be equal to 1 at the beginning and at the end of the paths, respectively. Constraints (19) guarantee that an O/D pair demand is routed on an edge only if this edge belongs to the railway network. Finally, constraints (20) force the demand to be assigned to the railway mode if and only if the associated cost of using this network (taking the fastest route) does not exceed the corresponding cost of the complementary mode. The role of ein these constraints is to break ties. For the sake of simplicity mode choice was reduced to a 0–1 decision. However, our model admits a more elaborated mode distribution as that applied in the paper by Marı ´n and Garcı ´a-Ro ´denas [31] where a piecewise linear approximation of a logit function is considered. For computational reasons, transfer costs are not taken into account in this model since the model is already rather heavy. A model in which transfers are considered is provided in Garzo ´net al. [32]. 3. INTRODUCING ROBUSTNESS IN THE MODEL Our model for the design of a railway network does not consider the system capacity. This is consistent with the assumption that public transportation costs are independent of link passenger flows, for which we assume that the available capacity is sufficient. This context is one for which Copyright #2010 John Wiley & Sons, Ltd. J. Adv. Transp. 2011; 45:54–65 DOI: 10.1002/atr 58 G. LAPORTE ET AL. the user-link assignments are all-or-nothing. This leads to concentrating riders for each O/D pair in single routes. Since this type of solution usually implies that some parts of the network are crowded while others are almost empty, the RTNDP model has no robust network solution and any disruption of service, especially in the most crowded sections of the network, involves a large number of passengers. The introduction of the robustness constraints not only provides alternative routes in the event of arc failure, but it also helps avoid congestion on a restricted set of arcs. To incorporate the robustness constraints in the model, we introduce the following variables: fw ij denotes the proportion of the demand of w2Wthat goes through arc (n i ,n j )2A0, from n i to n j , fw ij 2½0;1, if a failure occurs. ’w ij denotes the proportion of the demand of w2Wthat travels through arc (n i ,n j )2A00, from n i to n j , ’w ij 2½0;1, if a failure occurs. These variables are created in order to provide O/D pairs with different alternative routes. They just seem a duplication of the ~ f;~ ’variables, but they are in fact crucial to our definition of robustness. Although the new variables are defined as percentage of the demand of each O/D pair going through certain arcs, they should be seen as alternative routes, since users have the power to decide which route to take. The objective now consists not only of maximizing demand coverage, but it also takes into account the effects of possible failures in the network. Therefore, apart from z 1 , two other customer-oriented criteria are combined in the objective function: The maximization of the railway demand coverage in case of failures: z2¼X w¼ðp;qÞ2W gwX j2NðpÞ;ðnp;njÞ2A0 fw pj 0 @1 A: Note that P j2NðpÞ;ðnp;njÞ2A0 fw pj is the proportion of the demand of the O/D pair w¼(p,q) that will use the railway network. The minimization of the total routing maximal value: zDIST ¼X w2W;ði;jÞ2A0 fw ij dij: The objective function becomes z¼az1þð1aÞz2bzDIST: where bis a positive number close to 0, to keep z 1 and z 2 as primary goals. If a2[0,1] is close to 1, the objective is to maximize the demand coverage when no arc fails. In contrast, if ais close to 0, the objective is to maximize the demand coverage when arcs fail. We add the term z DIST to force the model to choose the shortest of all potential routes (still keeping as primary goal the demand coverage). The model has the same structure as that of Section 2.3, with the following changes. Constraints (12)–(18) become Routing demand conservation constraints: X ðni;npÞ2A0 fw ip þX ðni;npÞ2A00 ’w ip ¼0;w¼ðp;qÞ2W(21Þ X ðnp;njÞ2A0 fw pj þX ðnp;njÞ2A00 ’w pj ¼1;w¼ðp;qÞ2W(22Þ X ðni;nqÞ2A0 fw iq þX ðni;nqÞ2A00 ’w iq ¼1;w¼ðp;qÞ2W(23Þ Copyright #2010 John Wiley & Sons, Ltd. J. Adv. Transp. 2011; 45:54–65 DOI: 10.1002/atr DESIGNING ROBUST RAPID TRANSIT NETWORKS 59 X ðnq;njÞ2A0 fw qi þX ðnq;njÞ2A00 ’w qi ¼0;w¼ðp;qÞ2W(24Þ X ðni;nkÞ2A0 fw ik X ðnk;njÞ2A0 fw kj ¼0;if k=2fp;qg;w¼ðp;qÞ2W(25Þ X ðni;nkÞ2A00 ’w ik X ðnk;njÞ2A00 ’w kj ¼0;if k=2fp;qg;w¼ðp;qÞ2W(26Þ fw ij þ’w ij 1;ðni;njÞ2A;w2W(27Þ Mf w ij ~ fw ij ;ðni;njÞ2A;w2W:(28Þ Constraints (21)–(26) are flow conservation constraints (as for variables ~ fand ~ ’). Constraints (28) state that the fastest route for an O/D pair (defined by variables ~ fand ~ ’) must be among the different alternative routes chosen for that pair. Constraints (19) become: fw ij þpw1X l2L xl ij;ðni;njÞ2A0;w2W: since we must now build the arcs for every possible route. 3.1. Demand-arc flow constraints The first kind of robustness constraints to be introduced are called demand-arc flow constraints (DAF) and allow the demand of every arc to be routed through alternative paths, considering the complementary mode as an alternative. A disadvantage of multi-path routing lies in the fact that the demand is split, and therefore a more expensive but more robust solution arises. The user cost difference between the standard RTNDP and the RTNDP with demand-arc constraints is the price of robustness [26]. These constraints, called demand-arc flow constraints, DAF for short, allow the demand of every arc of every O/D pair wto use at least rw ij different routes. Therefore, fw ij 1 rw ij ;ðni;njÞ2A0 DAF A0;w2WDAF W: where A0 DAF and W DAF are the sets of selected arcs and O/D pairs, respectively. The limitation can be uniform so that rw ij ¼r;8ðni;njÞ2A0 DAF;w2WDAF.Ifris a positive integer, then these constraints impose that each affected O/D pair will have rdifferent alternative routes in the network (if this is allowed by the budget constraint). To illustrate, consider the example of Figure 1 where demand (1,3) takes the direct route f1;3 1;3¼1. If we impose DAF constraints with r¼2, this demand now has two possible routes: directly from n 1 to n 3 , or via node 2 as depicted in Figure 2, that is, f1;3 1;3¼f1;3 1;2¼f1;3 2;3¼0:5. 3.2. Arc flow constraints An interpretation of the arc flow constraints, AF for short, is that only a percentage of the total number of O/D pairs will have their demand routed through the arcs involved. In case of arc failure, only a percentage of the O/D flows will be affected X w2WAF fw ij þX w2WAF fw ji WAF jj rij ;ðni;njÞ2A0 AF A0;WAF W: where r ij plays the same role as rw ij and A0 AF and W AF are the subset of arcs and the subset of O/D pair that will be considered, respectively. A common situation arises when the upper bound is uniform rij ¼r;8ðni;njÞ2A0 AF. Note that this constraint relaxes the constraint on demand-arc flow, and may only affect some arcs, for example, the hub transit network. Another possibility is to consider only a selected group of O/D pairs, for example, O/D pairs with a long distance between the origin and the destination, or pairs without private car availability. Copyright #2010 John Wiley & Sons, Ltd. J. Adv. Transp. 2011; 45:54–65 DOI: 10.1002/atr 60 G. LAPORTE ET AL. 3.3. Arc demand constraints When imposing arc demand constraints, AD for short, only a percentage of the total traffic may be routed through the selected arcs. These constraints imply that the O/D demands are spread over a number of arcs, thus avoiding their concentration and railway congestion. X w2WAD fw ij gwþX w2WAD fw ji gwSw2Wgw rij ;ðni;njÞ2A0 AD A0;WAD W: where A0 AD and W AD are the subset of arcs and the subset of O/D pairs to be considered, respectively. As before, it is often the case that rij ¼r;8ði;jÞ2A0 AD. Also, as for the previous constraints and for the same reason, a selected group of O/D pairs to which the constraints are applied may be selected. It should be stressed that the flow variables fand ware only introduced for computational purposes and to define the different routes on the RTN for each O/D pair, but users are free to choose their route (we assume they will choose the fastest one available). For instance, in Figure 2 the flow from node 1 to Figure 2. Lines of the network and flow from n 1 to n 3 when r¼2 and C max ¼40. Figure 1. Lines of the network and flow from n 1 to n 3 when r¼1 and C max ¼40. Copyright #2010 John Wiley & Sons, Ltd. J. Adv. Transp. 2011; 45:54–65 DOI: 10.1002/atr DESIGNING ROBUST RAPID TRANSIT NETWORKS 61 node 3 is split into two. This does not mean that half of the users go via one route and the other half via the other route, but only that users can choose either alternative, and, if one of them is not available, users can still find the RTN attractive. 4. COMPUTATIONAL EXPERIMENTS Our computational experiments aim to assess to which extent the parameter aaffects the objective function and the resulting network. The model was solved by branch-and-bound, which was implemented in GAMS 22.2 and CPLEX 10.0. The network depicted in Figure 3 was used for the experiments. Each node has an associated construction cost c i , and a pair (c ij ,d ij ) is associated to each edge, where c ij and d ij are the construction cost of the edge and its length. The latter parameter can also represent the generalized cost of traversing the edge using the railway system. The O/D demands g w and the cost uCOM wfor each O/D pair w2Ware given by the following matrices: G¼ 0 9 261913126 6 4 11 0 14 26 7 18 3 7 9 30190302483911 21 9 11 0 22 16 21 18 16 14 14 8 9 0 20 12 18 9 26 1 22 24 13 0 11 28 21 75619151301614 5 9 11161725170 21 6 8 101811201420 0 0 B B B B B B B B B B B B @ 1 C C C C C C C C C C C C A ; uCOM w¼ 01;60;82 1;62;54 3;64;6 200;91;21;52;53;23;54;5 1;51;40 1;30;92 3;32;93;9 1;92 1;90 1;82 2 3;84;1 31;52201;53 2 3 2;12;72;21 1;50 2;53 2;5 3;93;93;9232;50 2;52;5 53;544232;50 2;5 4;64;54 3;53 2;52;52;50 0 B B B B B B B B B B B B @ 1 C C C C C C C C C C C C A ; As usual, subtour elimination constraints (11) where initially relaxed and gradually imposed, except in the case of circular lines. Table I summarizes our results. We have used C max ¼40, and we have imposed the three different robustness constraints separately, over the central arcs, (2,3), (2,4), (3,4), (3,5), (4,5). The resulting networks are: R1¼{(1,3,4,7,6,8), (3,5,6,9)}, and R2¼{(4,6,7), (6,8), (1,2,3,1), (3,5,6,9)}. 4 3 7 2 2 3 Figure 3. Test network. Copyright #2010 John Wiley & Sons, Ltd. J. Adv. Transp. 2011; 45:54–65 DOI: 10.1002/atr 62 G. LAPORTE ET AL.