Optimization methods for the planning of rapid transit systems

a Optimization methods for the planning of rapid transit systems Gilbert Laporte a,* , Juan A. Mesa b , Francisco A. Ortega c Centre de recherche sur les transports, Universite de Montreal, C.P. 6128, Succursale Centre-ville, Montreal, Quebec, Canada H3C 3J7 b Departamento de Matem atica Aplicada II, Escuela Superior de Ingenieros, Universidad de Sevilla, Sevilla, Spain c Departamento de Matematica Aplicada I, Escuela Tecnica Superior de Arquitectura, Universidad de Sevilla, Sevilla, Spain Abstract A central question when planning rapid transit systems is the determination of alignments and stations. Operational research methods can help solve these problems and they are also useful for the assessment of the network characteristics. This survey article reviews the main available methods. Keywords: Rapid transit systems; Alignments; Stations; Location 1. Introduction A central question when planning rapid transit systems is the determination of alignments and stations. Yet surprisingly little is known about the analytical tools available for this process. A recent investigation by Gendreau et al. (1995) indicates that rapid transit planning is a complex decision making process involving multiple objectives and constraints, uncertainties, non-quanti®able factors, large capital expenditures and long term commitments. The process is shared by several players such as planners, engineers, users, environmentalists and other interest groups. It is widely recognized that standard network design tools are often inadequate for entirely solving such complex problems (see, e.g., Magnanti and Wong, 1984), but they can play a useful role at a technical level. The planning process usually starts with an analysis of the city structure, including the identi- ®cation of the major business, shopping, industrial, recreational and tourist areas, universities, hospitals and other important buildings, airports, railway stations, bus depots, major arteries, existing transit systems, etc. Origin±destination (O/D) ¯ows are then analyzed and broad corridors for the location of alignments are targeted. Several scenarios are then developed, and evaluated in terms of technical feasibility, cost, coverage and utilization, eciency, impact on land use, real-estate and retail trade (Bay, 1985; Wulkan and Henry, 1985), trac and parking (Schabas, 1988), environment (Blackledge and Humphreys, 1984), * Corresponding author. Tel.: +1 514 343 6143; fax: +1 514 343 7121. E-mail address: [email protected] (Gilbert Laporte). safety (Siegel, 1980; Straus, 1980; Perrin and Benz, 1990), etc. This process usually takes place over a long period and involves the participation of a variety of players. Several iterations may be required as some scenarios are modi®ed or new ones are introduced. A restricted set of promising solutions are then ®ne tuned and a ®nal decision is made. Interesting applications of this process are provided in Blackledge and Humphreys (1984), Lundstr om et al. (1981), Page and Demesky (1985), Perrin and Benz (1990), and Schabas (1988). Analytical methods are routinely used at several stages of the planning process. Engineering techniques are applied to help assess the technical feasibility and construction cost of some potential alignments. Sophisticated simulation tools, like EMME/2 (INRO Consultants, 1998), can help derive trac ¯ows under various system con®gurations. Discrete choice models can now be employed for demand forecasting as a function of a system's attributes and pricing structure. A recent overview by Bierlaire (1998) proposes a model classi®cation under four headings: the decision maker's characteristics, the transportation alternatives, their attributes, and the decision rules. Operational research methods, several of which have only been developed in recent years, can help in three major areas at the planning stage: the generation of interesting alignments, the location of stations, and the assessment of network characteristics. Our focus in this study is strategic or long term planning. We therefore exclude operational aspects such as train scheduling and fare setting. Our paper is organized along these lines. In Section 2, we examine some modeling issues associated with the design of rapid transit networks. In Sections 3 and 4, algorithms for alignment and station location are described. The more global issue of network assessment is addressed in Section 5. 2. Modeling issues The problem of generating a good transit network can be viewed as a network design problem (see, e.g., Ahuja et al., 1995), but even the simplest models belonging to this category are hard to handle by means of analytical methods when the size of the network becomes large. In the context of rapid transit planning, the problem is compounded by the multiciplicity of constraints and objectives, some of which are dicult to state clearly or to measure adequately. We are aware of no analytical method capable of solving the rapid transit network design problem in its entirety. All known methods apply to a single line location. Therefore, the global problem could be tackled piecemeal by locating one alignment at a time, although techniques do exist to evaluate the e- ciency of a complex network. In contexts such as transit line location, analytical methods should be used to procedure several alternative solutions rather than only one. Our preference goes for methods that can generate a family of good solutions with respect to the problem's main criteria. These solutions should then be quanti®ed with respect to other criteria not explicitly considered during the generation phase, and decision makers should choose from among the proposed solutions. The objective of a rapid transit system is to transport a large number of people eciently and eectively (see, e.g., Blackledge and Humphreys, 1984; Bonz, 1983; Fukuyama, 1983; Quqing, 1984). If only one alignment is to be located, this usually translates into maximizing the population covered by the line. If an entire network is to be designed, overall network eciency also has to be taken into account, as we discuss in Section 4. Even in the case of a single alignment, the population maximization objective is not so easy to measure. Some authors (see, e.g., Chapleau et al., 1986; Wirasinghe and Vandebona, 1987) interpret it as the number of people living within a certain distance of the line. A way to measure this is to use a series of embedded corridors along the line. The problem with this approach is that people living close to the line, but relatively far from a station, are less likely to use the system. The population covered by stations is a more adequate measure of demand. To operationalize this measure, Dufourd et al. (1996) and Bruno et al. (1998a, b) use concentric shapes (contour lines) around each potential station, with decreasing weights hifor people leaving within dwalking units from the station (these authors use h01:0, h11:0, h20:5, h30:25, hd0 for dP4). Walking distances can be approximated by an `pmetric, where usually 1 6p62. The case p1 corresponds to the Manhattan distance, while the case p2 correspond to the Euclidean distance. If a Manhattan metric is used to describe walking distances, the contour lines will be diamond shaped. If a Euclidean metric is used, they will be circular. Thus, if Px;yis the population associated with coordinate point x;y, the cover of a station located at sis de®ned as CsX dX x;y:Dx;y;sd hdPx;y;1 where Dx;y;sis the walking distance between x;yand s. The cover CPof a full alignment P s1;...;snis therefore CPPn i1Csi. Other authors (e.g., Gleason, 1975; Current et al., 1985) and a number of transit planners (Hadler and Majumder, 1981; Lutin and Benz, 1992) use similar population coverage measures. This way of de®ning the cover of an alignment may not fully capture its ridership. For example, a person living close to a station on a North±South alignment, but traveling on the East±West axis is unlikely to patronize the system. A better way to measure ridership would be to consider all O/D pairs associated with the stations of an alignment P(Huber and Church, 1985). While this measure is more precise than CP, it requires a substantial amount of data and it is dicult to handle within an optimization algorithm. Moreover, some researchers (e.g., Wulkan and Henry, 1985) argue that population relocations invariably occur once the line is built. Therefore, using observed O/D patterns at the planning stage may not yield increased accuracy. For this reason, a measure such as CPis probably the best and simplest way to measure the coverage of an alignment. Some authors do not consider population coverage as the main objective in transit planning. Rather, they view the construction of a rapid transit system as a catalyst for urban development. For example, Howard (1978) describes how the construction of a light rail system has been bene®cial to the development of the Tyne and Wear area in England. Alsaadi (1983) cites urban development as one of the primary motives behind the construction of the Baghdad metro. However, other authors like Straus (1980) stress that while rapid transit may help support urban renewal programs, it can never be a substitute for integrated planning. There are also some studies that show that the urban growth resulting from the presence of rapid transit can in some cases be minor. Such seems to be the case of the BART in the Bay Area (see, e.g., Fajans et al., 1978; Knight and Trygg, 1977). Several external criteria must be taken into account when locating an alignment. Some of them related with engineering or environmental issues are dicult to take into account within the framework of a generic optimization algorithm. This is not to say that they should be ignored, but it is probably preferable to quantify them once a potential alignment has been generated. Requirements on inter-station spacing must be treated as hard constraints. It is common to impose a minimum spacing `min between any two stations, and a maximum spacing `max between two consecutive stations. As a rule, both these values lie between 0.5 and 2 km. Inner city stations are normally less spaced out than suburban stations (see Bruno et al., 1998a, b). The lower bound ensures that trains will not have to stop frequently. The upper limit means that transit users will not have to walk too far to the closest station and it also acts indirectly as an upper bound on total construction costs. The most frequent version of the rapid transit alignment problem is to locate an alignment P s1;...;snin a given area (or in a restricted corridor), in order to maximize population coverage (as measured by CP, for example), under station interspacing constraints. The number nof stations is usually given or constrained to take a value within a small interval, and some stations of the alignment may be ®xed a priori. 3. Locating an alignment One of the ®rst analytical approaches to the location of rapid transit alignments is contained in 3 DicesareÕs (1970) Ph.D. thesis in which the author models the problem as that of determining a least cost path between an origin and a destination, under a variety of constraints. A simple solution methodology for this problem is suggested by Church and Cliord (1979): (1) superimpose a grid onto the study area; (2) assign a score to each cell for each of the criteria considered by the user; (3) aggregate the various scores into a single objective to be minimized; (4) solve the resulting problem using a shortest path algorithm. One major drawback with this approach is that a cost minimization algorithm is likely to produce a minimal alignment between a given origin and a given destination without consideration for population coverage. If the shortest path algorithm is used to maximize a coverage objective, then the alignment produced will likely criss-cross the entire region. Current et al. (1985) have improved upon this rather crude methodology by incorporating in the model the population covered by the alignment and the connection cost associated with the uncovered population. This yields a covering path model or a median shortest path model, depending on whether one maximizes population coverage subject to constraints on the alignment, or whether one minimizes a combination of the alignment length and of the cost of reaching it. Another model belonging to the same class was recently suggested by Bruno et al. (1998a, b). Instead of maximizing population coverage, the authors work with O/D demands. All the above models can be viewed as pathlocation problems in networks (see Mesa and Boey, 1996 and Labb e et al., 1998), and can be formulated using the notation proposed in the latter reference. Let GV;Ebe an undirected network where Vfv1;...;vngis a set of vertices and Eis a set of edges. Let cij denote the cost (or length) of edge vi;vj, and let dij be the length of a shortest chain between viand vj. For SV, de®ne dSfvi;vj2E;i2S;j62 Sg. A non-negative demand wiis associated with every vertex vi2V. Let wPvi2Vwibe the total demand. In covering problems, for a given rP0, de®ne Sifvj2 V:dij 6rgas the set of vertices that can cover vi. Given a non-negative constant k, we can de®ne several problem classes, using the following binary variables: xij 1 if and only if edge vi;vjbelongs to the solution; yi1 if and only if vertex vibelongs to the solution; zi1 if and only if vertex vi is indirectly covered; zij 1 if and only if vertex vi is assigned to vertex vj. If the objective is cost minimization, it can be written as minimize X vi;vj2E cijxij:2 If total cost is a constraint, then X vi;vj2E cij 6k:3 Similarly, a coverage objective can be expressed as maximize X vi2V wizi4 and the corresponding constraints are X vi2V wiziPk5 and zi6X j2Si yjvi2V:6 Constraints (6) ensure that vertex viis covered only if some vertex vjis on the solution. If kw, then all the demand of the network is covered. If k<w, we talk of indirect cover. In such a case, one may wish to minimize the sum of distances between the path and the demand points not on it: minimize X vi;vj2V wjdji zji 7 or impose a constraint on this sum of distances: X vi;vj2V wjdji zji 6k:8 When using (7) or (8), one must introduce the following technical constraints: X j6i zij yi1vi2V9 and zij 6yivi;vj2V10 which force each vertex vito be on the path or to be assigned to another vertex vj. Whichever set of constraints an objectives is used, constraints must be imposed to ensure that the solution is a path: X vi;vj2E xij X vi2V yiÿ1;11 X vi;vj2dS xij Pykyhÿ1 SV;vk2S;vh62 S;26jSj6nÿ1;12 X vi;vj2dfvig 62yivi2V:13 The diculty in all these models is to introduce constraints to properly control inter-station spacing which is crucial in most practical situations. Such restrictions are best handled through heuristics. In recent years, two heuristics have been proposed for the single alignment location problem under a population coverage objective and station inter-spacing constraints. The ®rst, by Dufourd et al. (1996), uses tabu search, a metaheuristic that iteratively explores the solution space by allowing intermediate deteriorating solutions (for a recent overview of this method, see Glover and Laguna (1997)). The method starts from an initial solution generated as a random walk in the plane. At each iteration, it moves one or several stations to neighbouring locations while preserving feasibility. The second heuristic, by Bruno et al. (1998a, b) gradually extends a partial alignment by locating one location at a time while ensuring that the candidate station can feasibly be linked with the partial alignment. An improvement phase extracts several partial alignments from a known feasible solution and extends them at both ends using the same rules as for the construction phase. Overall this algorithm works better than that of Dufourd et al. (1996). It is much faster and is far less likely to become trapped in a local optimum. A good solution can be produced even from a poor starting alignment. Tests on randomly generated instances show that the Bruno et al. algorithm consistenly generates optimal or near-optimal solutions within insigni®cant computing times. Tests were also carried out using population data from the city of Milan and easily produced an alignment covering the main population centres. There have been fewer studies on the simultaneous location of several alignments. One notable exception is the work of Wirasinghe et al. (1977) who analyze the design of a star shaped con®guration in the context where passengers ®rst use feeder buses to the closest station. The aim of this work is to determine, using analytical formulas, the ideal number of branches in the star and the location of stations. It is based partly on previous results by Vuchic and Newell (1968). 4. Locating stations The methods outlined in Section 3 simultaneously locate an alignment and a set of stations. However, once the alignment has been determined, it often pays to ®ne tune the location of stations by means of an optimization algorithm. At this stage, since the alignment is known, it is prossible to determine more accurately the catchment area of each station and therefore the total ridership of the alignment. A well-known study in this area is the article by Vuchic and Newell (1968) who seek to determine the location of stations in an idealized star shaped system where people commute to a single point. The analysis takes into account passenger distribution along the line, access speed, dynamic characteristic of the train, standing time of the train in stations, and intermodal transfer time at stations. The objective is to minimize overall transportation time to the ®nal destination. Using simultaneous dierence equations, the authors show that for a uniform population distribution along the line, station spacings increase in the direction of passenger cumulation. Laporte et al. (1998) disregard transportation time on the train and seek to maximize the catchment area of a single already located line, by appropriately locating stations on it, subject to inter-station constraints. They ®rst discretize the alignment, but the level of accuracy can be quite high. For example, a discretization step of 0.1 km is quite realistic. Then, as explained in Section 2, concentric iso-distance curves can be built around each station. If the catchment areas Aiand Ajof two adjacent station locations iand joverlap, then an equidistance dividor can be drawn to determine which station the inhabitants of Ai\Ajwill patronize. The next step is to actually determine the size of population living between any two consecutive iso-distance curves in the catchment area of each station. Practically this can be quite dicult since population data are usually associated with census tracts and these do not coincide with isodistance curves. However, precise population counts can be obtained by means of triangulation methods (O'Rourke, 1994) and computational geometry techniques (Laporte et al., 1998). Alternatively, geographic information systems software (Schweiger, 1992) can prove useful if analytical formulae for the iso-distance curves can be incorporated within such systems and if graphical representations of them are available. In practice, determining the population cover of each potential station may be sucient. More accurate estimates of ridership (as opposed to total population) can also be derived by applying an attraction model (see, e.g., Ort uzar and Willumsen, 1990). Once the potential ridership of each potential station has been estimated, the actual choice of station locations can be obtained exactly as the solution of a shortest path problem on a directed graph GV;A, where Vis the set of potential locations and Ais a set of arcs between the vertices of V. An arc i;jis only de®ned if it is feasible, in terms of inter-spacing restrictions, to locate iand j consecutively on the alignment. The cost associated with i;jis Mÿcij, where cij is the expected population (or ridership) in area associated with the segment i;j, and Mis a large constant satisfying MPmaxi;j2Afcijg. The computational feasibility of this approach is demonstrated in Laporte et al. (1998), using data from the city of Sevilla. 5. Assessing transit networks As mentioned, we are not aware of any algorithm capable of producing a full transit network. However, analytical tools exist to assess the quality of a potential or real-life network. This line of research is rooted in the work of Musso and Vuchic (1988) who devised a set of measures to quantify various aspects of a metro network GV;E. These include some simple indices such as the number of stations, the total length of the network, the number of lines, the number of multiple stations, and more sophisticated measures such as the number of minimal cycles (not embedding any other cycle), a network complexity indicator bjEj=jVj,aconnectivity indicator equal to the ratio between jEjand the maximum number of edges that could potentially exist in G, and a directness of service measure equal to the proportion of O/D trips that can be made without transfers. Laporte et al. (1994) have introduced two other measures. The ®rst is the passenger-network eectiveness de®ned as follows. For each path Pbetween viand vjon the network, GV;E, ®rst de®ne the total passenger cost as hijP X vi;vj2P tij rPtfsPÿrPÿ1ts; 14 where tij is the travel time between viand vj,rP and sPare, respectively, the number of transfers and edges on the path, tfis the transfer time and ts is the stopping time. Then the total passenger cost is hX vi;vj2 Vi<j hij;15 where hij minPfhijPg. The passenger-network eectiveness index is then khX vi;vj2E tij: ,16 The second measure is passenger-plane eectiveness, i.e., an index comparing passenger travel cost using the transit network with the cost that would be incurred if travel was made in the plane. Consider an `pnorm describing walking distances. Given the matrices Hhijand Mpmijp, where mijp is the travel time between viand vj computed with an `pnorm, then the passengerplane eectiveness measure is lpkHÿMpk=jVj;17 where, given an rsmatrix Aaij, the Frobenius norm kAkis de®ned as kAk X i1X j1 a2 ij! 1=2 :18 The conclusion of this study is that in circular cities, the cartwheel (Fig. 1(b)) and triangle (Fig. 1(c)) designs yield the best (smallest) measures. In grid cities, the modi®ed grid (Fig. 1(e)) and half-grid (Fig. 1(f)) con®gurations are best in terms in of passenger-network eectiveness, but are inferior to grid con®gurations (Fig. 1(d)) with respect to passenger-plane eectiveness (see Table 1). Star designs (Fig. 1(a)) are the least ecient. It should be noted that the networks of London, Moscow, Tokyo JR, Madrid and Hamburg belong to the cartwheel category, although they are rather more complex than the drawing of Fig. 1. Six basic network con®gurations. Fig. 1. The cities of Prague, Frankfurt, Kiev and St.Petersburg exhibit triangular or quasi-triangular con®gurations. Montreal, Chicago and Toronto have modi®ed grid systems. This analysis only applies to the topological con®guration of the network and assumes that all O/D pairs are equally likely. In a second study, Laporte et al. (1997) have studied passenger/ network eectiveness and passenger/plane eectiveness of some con®gurations by dropping the uniformity assumption and by introducing mode competition. In particular, they make use of a deterrence function (Ort uzar and Willumsen, 1990) to adjust downward the expected travel demand between O/D pairs that are further apart. More speci®cally, consider two points vi and vjlocated on the network in two zones (a circular inner center Z1and an outer annulus Z2), and their respective catchment areas Aiand Aj. The number of trips nij between viand vjis computed as nij bij fij gij;19 where bij takes one of three values b1;b2or b3, with b1b2b31, according to whether viand vj are both in the same zone (Z1or Z2) or in dierent zones (one in Z1, one in Z2). The second factor, fij, is a `friction coecient' representing the total demand between viand vj. It is a deterrence function of the travel time xbetween a point pAiand point qAj, of the form fijxaxeÿbxa;b>020 (see Ort uzar and Willumsen, 1990). Finally, a logit function of the form qij 1eÿlsijÿs0 ijÿ121 is used to re¯ect mode choice, where cis a parameter, and tij,t0 ij are shortest travel times between viand vj, using public transit and all the other transportation modes, respectively. Using suitable values for a;band l, the authors have conducted numerical experiments on a number of idealized networks. These tests essentially con®rm the conclusions of the previous study presented in Laporte et al. (1994). 6. Conclusion The use of operational research methods in the area of rapid transit systems planning is still relatively new. This can be explained partly by the intrinsic diculty of the underlying network design problem, and partly by the complexity of the decision process itself. There are more available analytical tools now than there were ten years ago and this trend is likely to continue in the near future. Powerful local search methods are now capable of producing good quality alignments, exact methods exist for ®ne tuning station location and measures have been proposed to assess the overall quality of a rapid transit con®guration. In the area of algorithmic research, the next step will probably be the design of highly interconnected networks, and a better integration of travel demand functions within the network generation process. There is now a need for decision support systems containing algorithmic and geographic information features, and capable of generating within a short time several good quality scenarios, with a list of quanti®ed attributes. The ultimate choice will always rest with the decisions makers, but we believe better decisions can be made if the alternatives to choose from are superior. Table 1 Comparison of some basic con®gurations for circular and grid cities Con®guration Circular cities Grid cities Star Circle Cartwheel Trianglea Grid Modi®ed grid Half-grid Passenger network eectiveness index 34.17 32.56 25.91 18.47 29.90 27.63 26.26 Passenger-plane eectiveness index p1:5 0.88 0.80 0.53 0.59 0.94 1.02 1.43 Acknowledgements This research was in part supported by the Canadian Natural Sciences and Engineering Research Council under grant OGP0039682 and by Ministerio de Educaci on y Ciencia, Spain, under grant CICYT PB-95-1237-C03-01. This support is gratefully acknowledged. References Ahuja, R.K., Magnanti, T.L., Orlin, J.B., Reddy, M.R., 1995. Applications of network optimization. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (Eds.), Network Models, Handbooks in Operations Research and Management Science 7. North-Holland, Amsterdam, pp. 1± 83. Alsaadi, J.M., 1983. The Baghdad metro 1983. Advanced Tunnelling Technology and Subsurface Use 3, 149±156. Bay, P.N., 1985. Determining cost-eectiveness of transit systems. Transportation Research Board State-of-the-Art Report 2 - Light Rail Transit System Design for CostEectiveness, pp. 9±12. Bierlaire, M., 1998. Discrete choice models. In: Labb e, M., Laporte, M.G., Tanczos, K., Toint, P. (Eds.), Operations Research and Decision Aid Methodologies in Trac and Transportation Management, NATO ASI Series F: Computer and Systems Sciences, Springer, Berlin, 166, pp. 203± 227. Blackledge, D.A., Humphreys, E.M.H., 1984. The West Midland rapid transit study. In: Proceedings of the Planning and Transport Research and Computation, Sussex, pp. 71±84. Bonz, M., 1983. Insertion et r ealisation de l'infrastructure des m etros l egers dans le tissu urbain. 45e Congr es International de l'UITP, Rio de Janeiro. Bruno, G., Gendreau, M., Laporte, G., 1998. A heuristic for the location of a rapid transit line. Publication CRT-98-55, Centre for Research on Transportation, Montreal. Bruno, G., Ghiani, G., Improta, G., 1998b. A multi-modal approach to the location of a rapid transit line. European Journal of Operational Research 104, 321±332. Chapleau, R., Lavigueur, P., Baass, K., 1986. A posteriori impact analysis of a subway extension in Montreal. Publication 503, Centre for Research on Transportation, Montreal. Church, R.L., Cliord, T.J., 1979. Discussion of environmental optimization of power lines, by Economides and Shari®. Journal of the Environmental Engineering Division, ACSE 105, 438±439. Current, J.R., ReVelle, C.S., Cohon, J., 1985. The maximum covering/shortest path problems: A multiobjective network design and routing formulation. European Journal of Operational Research 21, 189±199. Dicesare, F., 1970. A systems analysis approach to urban transit guideway location. Ph.D. dissertation, Department of Electrical Engineering, Carnegie-Mellon University, Pittsburgh, PA. Dufourd, H., Gendreau, M., Laporte, G., 1996. Locating a transit line using tabu search. Location Science 4, 1±19. Fajans, M.H., Dyett, M.V., Dornbusch, D.M., 1978. Study of developments patterns ± BART impact program, land use, and urban development project. John Blayney Associates, David M. Dornbusch and Co., Metropolitan Transportation Commission, Berkeley. Fukuyama,M.,1983.Optimalstationlocationforatwohierarchy transit system. In: Proceedings of the Eighth International Symposium on Transport and Trac Theory, pp. 264±291. Gendreau, M., Laporte, G., Mesa, J.A., 1995. Locating rapid transit lines. Journal of Advanced Transportation 29, 145± 162. Gleason, J.M., 1975. A set covering approach to bus stop location. Omega 3, 605±608. Glover, F., Laguna, M., 1997. Tabu Search, Kluwer, Boston. Hadler, D.K., Majumder, A., 1981. A method for selecting optimum number of stations for a rapid transit system by network approach: An application in Calcutta tube rail. In: Jaiswal, N.K. (Ed.), Scienti®c Management of Transportation Systems, North-Holland, Amsterdam, pp. 97±108. Howard, D.F., 1978. Tyne and Wear metro. Transport Management 11, 9±12. Huber, D., Church, R.L., 1985. Transmission corridor location modelling. Journal of Transportation Engineering 111, 114± 130. INRO Consultants, 1998. EMME/2 Users' Manual, Release 9, Montreal. Knight, R.L., Trygg, L.L., 1977. Land use impacts of rapid transit: Implications if recent experience. De Leuw, Cather and Company, San Francisco. Labb e, M., Laporte, G., Rodr õguez-Mart õn, 1998. Path, tree and cycle location. In: Crainic, T.G., Laporte, G. (Eds.), Fleet Management and Logistics, Kluwer, Boston, pp. 187±204. Laporte, G., Mesa, J.A., Ortega, F.A., 1994. Assessing topological con®gurations for rapid transit networks. Studies in Locational Analysis 7, 105±121. Laporte, G., Mesa, J.A., Ortega, F.A., 1997. Assessing the eciency of rapid transit con®gurations. TOP 5, 95±104. Laporte, G., Mesa, J.A., Ortega, F.A., 1998. Locating Stations on Rapid Transit Lines, Publication CRT-98-22. Centre for Research on Transportation, Montreal. Lundstr om, L., J arvi o, E., Kaitila, K., 1981. The metro system in Helsinki central city area project. In: Proceedings of the International Symposium Subsurface Space, Stockholm, pp. 147±154. Lutin, J.M., Benz, G.P., 1992. Key issues in light rail transit station planning and design. Transportation Research Record 1361, 117±124. Magnanti, T.L., Wong, R.T., 1984. Network design and transportation planning: Models and algorithms. Transportation Science 18, 1±55. Mesa, J.A., Boey, T.B., 1996. A review of extensive facility location in networks. European Journal of Operational Research 95, 592±603.