A Review Of Urban Transportation Network Design Problems

Transcript

European Journal Journal of Operational Research Research 229 (2013) (2013) 281–30 281–302 2 Contents lists available at SciVerse ScienceDirect ScienceDi rect European Journal Journal of Oper Operati ation onal al Resea Research rch journal homepage:  www.elsevier.com/locate/ejor Invited Review A review of urban transportatio transportation n network network design problems problems Reza Zanjirani Farahani a, , Elnaz Elnaz Miandoabc Miandoabchi hi b, W.Y. W.Y. Szeto zeto c, Hannane Hannaneh h Rashidi Rashidi d ⇑ a Department of Informatics and Operations Management, Management, Kingston Business School, Kingston University, UK  Logistics and Supply Supply Chain Research Group, Institute for Trade Trade Studies and Research (ITSR), (ITSR), Tehran, Iran c Departmen Departmentt of Civil Engin Engineerin eering, g, The Universit University y of Hong Kong, Kong, Hong Kong, Kong, China d Department of Industrial Engineering, Mazandaran University of Science and Technology, Iran b a r t i c l e i n f o a b s t r a c t  Article history: Received 7 March 2012 Accepted 2 January 2013 2013 Available online online 9 January 2013 2013 This paper presents a comprehensive comprehensive review of the definitions, definitions, classifications, classifications, objectives, constraints, network topology topology decision variables, variables, and solution methods methods of the Urban Transportation Transportation Network Network Design Problem (UTNDP), (UTNDP), which includes includes both the Road Network Design Problem (RNDP) (RNDP) and the the Public Transit Network Design Problem (PTNDP). (PTNDP). The current current trends trends and gaps gaps in each class of of the problem problem are discussed discussed and future directions directions in terms of both modeling modeling and solution approaches approaches are given. This review intends intends to provide a bigger picture of of transportation transportation network network design problems, problems, allow comparisons comparisons of formulation formulation approaches approaches and and solution methods methods of different problems problems in various classes of UTNDP, and encourage encourage cross-fertilization between the RNDP and PTNDP research. Crown Copyright Copyright  2013 Published Published by Elsevier B.V. All rights rights reserved. reserved. Keywords: Transportation Urban transportation network design problem Road network design Transit network design and frequency setting problem Multi-modal network design problem 1. Introductio Introduction n Transportation Transportation is important important in the sense sense that it allows people to to take take part in human human activit activities. ies. With With an increasi increasing ng popul populatio ation, n, the demand demand for transportation transportation is also increasing. increasing. More and more more traffic is on roads, which in turn creates more and more mobility-relate mobility-related d problem problemss such such as conges congestion tion,, air polluti pollution, on, noise noise pollutio pollution, n, and acciden accidents; ts; especiall especially y in city city cent center erss whe where re the the level level of of huma human n activit activities ies is high. high. Gover Governm nment entss need to plan plan transpor transportt networks networks properly properly and control control urban traffic traffic movement movementss to ensure mobility mobility and mitigate mobility related problems simultaneously. simultaneously . A higher popula population tion also also leads leads to more more expensiv expensive e land, land, especial especially ly in city centers and hence hence more more people living in in new towns towns or suburbs, suburbs, thereby requiring new transportation infrastructures for serving new towns towns or improving existing transportation structures structure s to cope cope with the increasing increasing population population in the suburbs. suburbs. These planning planning,, design and management management issues are tradition traditionally ally addressed addressed in UTNDP. UTNDP. This problem can actually include the design problems in suburban areas in addition addition to those in urban areas, because the methodo methodology logy involved involved is basically the the same. Moreover, Moreover, this problem problem can involve involve transit network networkss in addition addition to road networks, networks, since transportatio transportation n includes both public and private transport. UTNDP has has been continuously studied during the last five five decades, and the number number of related publication publicationss has grown over over time, probably probably because the problem problem is highly complicat complicated, ed, theoretical theoretically ly ⇑ Corresponding Corresponding author. author. Tel.: +44 020 8517 8517 5098; fax: +44 020 8417 8417 7026. (R.Z. Farahani). Farahani). E-mail address: [email protected] (R.Z. 0377-2217/$ 0377-2217/$ - see front matter matter Crown Crown Copyright Copyright http://dx.doi.org/10.1016/j.ejor.2013.01.001  interes interestin ting, g, practica practicall lly y import important ant,, and multid multidisci isciplin plinary. ary. Review Reviewss have been published by Boy Boyce ce (1984), (1984), Ma Magna gnanti nti and and Wong Wong (1984), (19 84), Frie Friesz sz (198 (1985), 5), Mig Migdala dalass (1995), (1995), Yan Yang g and and Bell Bell (1998 (1998a), a), Desaulniers and Hickman (2007), Guihaire and Hao (2008) (2008),, and and recently by Kepaptsoglou and Karlaftis (2009). (2009). Some Some of these these review reviewss deal with general network design problems, problems, but some some focus specifspecifically on on urban network network design design or or on one part part of urban transportatransportation networ networks. ks. For exampl example, e, the first five review reviewss only only focu focuss on RNDP, RNDP, while while the the last last three three review reviewss only only focus focus on PTNDP. PTNDP. As a result, the similarities similarities and differenc differences of the formulation formulation approaches approaches and solution methods methods between RNDP and PTNDP cannot be addressed in these reviews, reviews, and this this does not not encourage encourage the the crossfertilization fertilizati on of the two two research research areas. areas. Moreov Moreover, er, the proble problem m that considers the interaction between road and public transit network designs designs has been ignored in these reviews. reviews. This paper paper attempts attempts to provide provide a holistic view view of UTNDP UTNDP and its its classifications classifications by uniting uniting the decisions decisions for improvin improving g transportatransportation networ networks. ks. With regard to this, the current current paper covers both problem categories, categories, and presents presents a third problem category for the joint decisions decisions in road and public public transit networks networks with at least two modes, modes, which considers considers the interactions interactions of of these modes. modes. This paper also contains contains updated updated literature literature for both fields to early 2011. This contrasts contrasts to the last review review paper paper on RNDP which which was pubpublished in the late 1990s, 1990s, and the previous previous reviews of of PTNDP PTNDP which cover cover the litera literatur ture e until until 2007. 2007. The main main aim of this paper paper is to cover problems related to urban transportation network network topology and its its configur configuratio ation. n. In this rega regard, rd, only only the strategic  level and a number of  tactical level decisions related to network topology are 2013 Published by Elsevier B.V. B.V. All rights reserved. 282 R.Z. Farahani Farahani et al./ European European Journal Journal of Operation Operational al Research Research 229 (2013) (2013) 281–302 281–302 covered in this paper; paper; those papers not related related to to network network topoltopology decisions, decisions, such as operational operational level decisions decisions and tactical decidecisions that are not related to network network topology, topology, will not be covered covered unless they are considered together with network topology decisions. sions. Problem Problemss such such as traffic traffic signal signal setti setting, ng, parking parking pricing pricing,, toll setting, and public transit ticket pricing are important important sub-probsub-problems of of UTNDP UTNDP and even some of these have a long history with many important features and developments. developments. These sub-problems sub-problems deserve deserve to be examined examined and and reviewed reviewed in a compre comprehen henssive manner in future review review papers and hence hence are excluded from from this paper. Traffic signal setting has the strongest relevancy with network configurati figuration on decisio decisions, ns, as the networ network k topology topology directly directly affects affects the flow pattern and the the conflict conflict points at intersect intersections. ions. This sub-probsub-problem has has been studied extensively extensively and and there there is a relatively relatively large body of literature literature (e.g. (e.g. Ca Cant ntare arella lla et al. al.,, 19 1991 91;; Me Mene negu guzz zzer er,, 19 1995; 95; Wong Wo ng an and d Yang Yang,, 199 1999; 9; We Wey, y, 20 2000 00;; Ca Casce scett tta a et al. al.,, 20 2006 06). ). Moreover, Moreover, this review focuses on determini deterministic stic transport networks and deterministic deterministic travel travel dem demand and.. That That is, we focus focus on papers papers that assume no supply and demand demand uncertain uncertainty. ty. For example, example, there there is no random randomn ness in travel demand and road capacity considered in the reviewed reviewed papers. papers. Nevertheles Nevertheless, s, we can still still identify identify curcurrent trends trends and gaps gaps as shown later, and highlight highlight new new research research directio directions ns in this this field field as shown shown in in the last section section.. Other than reviewing reviewing UTND UTNDP, P, we also also rev revie iew w the the solu soluti tion on methods. methods. This allows comparisons comparisons of solution solution methods methods of different problems problems in various various classes of UTNDP UTNDP and proposes proposes new algoalgorithmic research directions. directions. This algorithmic algorithmic review review and the new directions directions are particularly important, important, given that these these methods methods are required required to solve practical practical design problems, problems, and their problem problem sizes have become become larger and larger. Real case studies are also reviewed to give insight about the size of the network networkss for each each problem catalogue currently considered and give some hints on the future future requirement requirement of the solution solution methods methods for practical practical problems. The rest rest of the paper paper is organi organized zed as follows follows:: Section Section 2 explains the key definitio definitions, ns, classific classificatio ations, ns, and general general formulat formulations ions of  UTNDP; UTNDP; Section 3 reviews reviews the specific problem studied in the literature; ature; Section Section 4 depicts the solution solution methods methods used in the literature ture;; Secti Section on 5 describes the the application application to real case scenarios; scenarios; and Section 6 presents presents an overall view of of the research developm developmen entt of UTNDP. UTNDP. Finally, the summary summary and further further research directions directions are presented presented in Section 7. 2. Definition Definitions, s, general general formulatio formulations ns and classific classificatio ations ns of  UTNDP  2.1. Definitions of UTNDP There There are are at at least least three three differen differentt defini definitio tions ns of UTNDP UTNDP in the literature: 1. UTNDP UTNDP is concerned concerned with with building building new new streets streets or expanding expanding the the capacity of of existing streets streets (Dan (Dantzig tzig et al., 197 1979 9). This definition definition is quite common common in in the literature, literature, but most studies use other other names names for this problem catalogue catalogue such as the Road Network Network Design Problem Problem (RNDP), (RNDP), the transportation transportation network network design design problem, problem, and the network network design problem. problem. 2. UTNDP UTNDP is to determi determine ne the optima optimall lo locati cations ons of faciliti facilities es to to be added added into a transp transport ortatio ation n network network,, or to determ determine ine the optioptimal mal capacity capacity enhance enhancemen ments ts of existing existing facilit facilities ies in a networ network k (Fr Fries iesz, z, 19 1985 85). ). In this this defi defini nitio tion, n, the the faci facilit lities ies may may be be repr repreesente sented d by eithe eitherr node nodess o orr links. links. There Therefo fore, re, this this defin definiti ition on is wider than the the first one. 3. UTNDP UTNDP deals deals with with a complet complete e hiera hierarch rchy y of of decision decision--making processes processes in in transportation transportation planning, planning, and includes includes strategic, strategic, tactical and operational decisions (Magnanti (Magnanti and Wong, 1984). Strategic decisions are long-term decisions related to 1984). the infrastructures infrastructures of of transportation transportation networks, networks, including including both both transit and road networks; tactical decisions are those concerned concerned with the the effective utilization of infrastructures and resources resources of  existing urban transportation transportation netw networ orks ks;; and and operational decidecisions, which are mostly mostly related to trafsions are short-term decisions, fic flow control control,, demand demand mana managem gemen entt or schedul scheduling ing prob problem lemss. Fig ig.. 1 gives examples examples of strategic, strategic, tactical and and operational operational decidecisions in UTNDP: UTNDP: the shaded shaded items items are related to network network topoltopology. This definition definition has the widest widest scope scope among among the three, three, since it includes the managem managemen entt aspect aspect at the tacti tactical cal and and operaoperational levels in addition addition to the planning planning aspect aspect at the strategic strategic level. In order order to to create create a compre comprehen henssive and integrated collection of  classifications classifications under a single umbrella, umbrella, this paper adopts adopts the third definition definition of UTNDP, UTNDP, but mainly limits itself to the decisions decisions specspecified ified in the the seco second nd defi defini nitio tion n – the the decis decision ion relat related ed to to netw networ ork k topology. topology. Actu Actuall ally, y, we belie believe ve tha thatt this this defi defini nitio tion n encom encompa passe ssess both the Road Network Design Problem (RNDP) (RNDP) and the Public Tran(PTNDSP) SP) in which which the sit Network Design and Scheduling Problem (PTND term ‘public’ ‘public’ will be omitted omitted in the rest of paper paper for for the the sake sake of  brevity, that determines determines the the optimal optimal transit routes, frequencies, frequencies, and time-tables, time-tables, because transport transport networks include both transit and road road netw networks orks.. In additio addition, n, we believe believe that that this this defin definitio ition n includes cludes two big big classes classes of UTNDP: UTNDP: (1) the proble problem m of develo developin ping ga new network network via via adding adding links, which is related to strategic decisions and (2) the problem of improving improving or managing managing the current current network, network, which is is related to the tactical tactical and operation operational al decisions decisions.  2.2. General framework of UTNDP UTNDP UTNDP differs from network network design problems problems in other disciplines such as telecommun telecommunicati ication, on, because because the the reaction reaction of traveltravelers has to be taken into account account when designing designing a transportation transportation network. network. Moreover, Moreover, designing designing a network network is is associated with certain transport transport policy. Regarding Regarding these two facts, facts, analyzing analyzing and modelmodeling in in UTNDP UTNDP involves involves two issues: (1) policy-making policy-making for networ network k improvement improvement and (2) predicting predicting the network network user behaviors behaviors in response to the formulated formulated design policies. The rest of this section will discuss the problem from the mentioned aspects.  2.2.1. General mathematical mathematical model for UTNDP The problem problem is usually usually formu formulate lated d as as a bi-level bi-level problem problem or a leader-follower leader-fol lower problem. problem. The upper upper level problem problem is the leader’s leader’s prob problem lem,, the the desig design n prob problem lem,, or the the proble problem m of the the decis decision ion-maker, maker, (e.g. (e.g. the govern governmen mentt), who plans or or manages manages the the transport transport networ network. k. This This upperupper-le leve vell pro proble blem m is relate related d to to the the poli policy cy discussion in practice and includes includes the measurable measurable goal (e.g. reducing total total tra trave vell time), time), restr restrict iction ionss (e.g. (e.g. polit politica ical, l, physi physical cal,, and and environmental environmental constraints) constraints) and and the the desig design n decis decisio ions ns to be made made (e.g. new roads to to be built). This upper-le upper-level vel problem problem assumes assumes that the leader can predict the behavior behavior of the travelers. travelers. The lower-level lower-level problem is the followers’ followers’ problem or the problem problem of travelers travelers who who decide decide wheth whether er to travel, travel, and if so, their their travel travel modes modes and and routes. routes. The bi-level structure allows the decision-maker decision-maker to cons consid ider er the the reaction of the travelers travelers and improve improve the network network to influence influence the trave travell choice choice of travele travelers rs but has has no direct direct contro controll on their their choice. This structure structure does does not allow allow the travelers travelers to to predict the decision decision of of the leader leader,, but only only allows allows them them to to determ determine ine their their choice after after knowing knowing the decision decision of the leader. leader. Mathematic Mathematically, ally, the problem problem can be be represented represented as as follows: ðU 0Þ min u st : : F ðu ; Gðu ; ðuÞÞ ð1Þ ðuÞÞ 6 0 ð2Þ v  v  R.Z. Farahani Farahani et al./ European European Journa Journall of Operatio Operational nal Research Research 229 (2013) (2013) 281–302 281–302 Determining the Orientation of One-way Streets Building New Streets Determining the Allocation of Lanes in Two-way Streets Expanding Existing Streets Determining Transi Determining Transitt Schedule Scheduling of Repairs on Urban Streets Determining Transit Service Frequency Strategic Scheduling Traffic Lights Allocating Exclusive Bus Lanes Designing Bus Routes 283 Operational Tactical Fig. Fig. 1. Examples Examples of decisions decisions in UTNDP. UTNDP. where  v (u) is implicitly implicitly determin determine ed by: ðL0Þ min v  st : :  f ð  f ðu ; g ðu ; Þ ð 3Þ Þ60 ð 4Þ v  v  F  and u are respectively, respectively, the objecti objective ve function function and and (networ (network k design) decision variable vector of the upper upper level level problem problem (U0) (U0),, G is a vector vector function function in the upper upper level level constrain constraint, t,  f  and v  are respectively, the objective function and and decision variable variable (flow) (flow) vector of  the lower level level problem (L0), (L0), and g  is a vector vector function function in the lower lower level constraint. constraint. v (u) is called called the the reactio reaction n or respons response e functio function, n, which which depic depicts ts the user user reaction reaction in terms of of a flow pattern for each network network design Since v (u function that that cannot cannot be shown explicitly, explicitly, u. Since (u) is an implicit function it is depi depicte cted d by by L0. L0. In each each netw networ ork k desi design gn prob problem lem,, v (u) is an optima optimall solution solution of L0. In fact, fact, the objecti objective ve of the bi-leve bi-levell network network design design proble problem m is to find an optima optimall decision decision vector vector u to optimi optimize ze the objective function F  subject to the network network design constraint constraint (2) as well well as the user user react reaction ion cons constrai traints nts (3) (3) and (4). (4). The above above lower lower-lev -level el proble problem m can be express expressed ed as a variavariational inequality; inequality; in this case the bi-level bi-level network network design problem problem can be formu formulate lated d as a mathematical mathematical program with with equilibrium equilibrium conUTNDP then becomes becomes single-le single-level vel but conceptua conceptually, it is straints. UTNDP bi-level bi-level with two different different types of games games involved, involved, name namely ly the the leader-follower leader-follo wer game and the non-cooperative non-cooperative Nash Nash game. game. Solving a bi-level network design problem using exact solution metho methods ds is very very difficult difficult because because the the probl problem em is NP-har NP-hard. d. BenAyed Ay ed et al al.. (1 (198 988) 8) studied bi-level problems and concluded that even a simple bi-level bi-level problem with bot both h linear upper-level upper-level and lower-level lower-level problems problems is also NP-hard NP-hard.. Another Another reason reason is the nonconvex convexity ity of bi-leve bi-levell network network design design problem problems. s. Even Even if both both the upper and and lower level level problems problems may be convex, convex, the convexity convexity of  the bi-level bi-level problem cannot cannot be guaranteed guaranteed (Lu (Luo o et al al., ., 19 1996 96). ). The presented mathematical model mostly corresponds to RNDPs, RNDPs, while due to the comple complexity xity of of TNDSPs TNDSPs only only in some cases is form formul ulat ating ing the TNDSP as a bi-level network network design design problem problem possible. Most of the TNDPs TNDPs are single level level problems problems where where the reactio reactions ns of users users are simplifi simplified. ed. As mention mentioned ed by Chakroborty (2003),, it is diffic (2003) difficult ult to form formul ulate ate a TNDS TNDSP P as a math mathem emati atical cal problem, lem, since since it is inh inhere erently ntly discre discrete te and and concept conceptss such as as transfers and route continuity are hard hard to represe represent. nt. Finally Finally,, Baaj and Mahmassani (1991) discussed the complexity complexity of this problem problem arising arising from its combinatorial, combinatorial, nonnon-lin linear earity ity,, nonnon-con conv vexity and multiobjective objective nature. nature. They also also depicted depicted the the difficulties difficulties in formulating formulating as a mathe mathemat matical ical model, model, and in definin defining g accepta acceptab ble spatial spatial route route layouts.   2.2.2. Classifications of upper level problems or design problems in UTNDP  UTNDP UTNDP can be classified into problem problemss which arise from from a variety of possible network network design policies policies and decisions. Traditional Traditionally, ly, UTNDP UTNDP is is separately separately considered considered in two main catalogues, catalogues, namely RNDP and and TNDSP. RNDP mainly mainly considers considers street networks networks and does not not distinguish distinguish the flow of public transit transit vehicles vehicles and other other private private vehicles. vehicles. RNDP usually supposes supposes all traffic flows as homoghomogenous. enous. Based Based on the nature nature of the decisio decisions ns consider considered, ed, RNDP RNDP can be furth further er classi classifie fied d in three three grou groups: ps: (1) (1) Discrete Network Design (DNDP), which only deals deals with with discrete design decisions Problem (DNDP), such as constru constructi cting ng new roads, roads, adding adding new lanes, lanes, determ determinin ining g the directions directions of one-way one-way streets, streets, and determ determining ining the turning turning restrictions restrictio ns at intersec intersection tions, s, (2) (2) Continuous Network Design Problem (CNDP) (CNDP),, which which is only only concerned concerned with with continuous design decisions such as expanding expanding the capacity of streets, scheduling scheduling traffic lights, and determin determining ing tolls tolls for some some specific streets, and (3) Mixed Net(MNDP),, which which conta contains ins a combin combinatio ation n of  work Design Problem (MNDP) continuous continuous and discrete discrete decision decisions. s. If the demand demand,, land-u land-use, se, or netnetwork changes over the planning horizon are also considered, RNDP can be further further classified into DNDP-T, DNDP-T, CNDP-T, CNDP-T, and MNDP-T, MNDP-T, which are respectively respectively the time-depen time-dependent dent extension extensionss of DNDP, DNDP, CNDP and MNDP. TNDSP mainly mainly considers the topology of the public transit network works, s, as well well as servi service ce frequ frequen enc cy and time timetabl tables. es. This This problem problem can be classified classified into five five types types based on the decisio decisions ns address addressed: ed: (1) (1) The The Transit Network Design Problem (TNDP) (TNDP) exclusively exclusively attends to design routes routes of transit lines lines including the the origins and destinadestinations tions of the transi transitt routes routes and and the sequ sequence ence of of links links visited. visited. (2) The Transit Network Design and Frequency Setting Problem (TNDFSP) determines determines the service frequency frequency of each bus bus line in addition to rout route e desig design. n. (3) (3) The The transit network frequencies setting problem purely deals with frequency setting given the route structure. structure . (4) The transit network timetabling problem deals with the timetable issues given the the service frequency frequency and routes. routes. (5) The transit network frequency and and timeta timetable ble scheduling problem considers both the frequency decisions given the route structure. Nearly all RNDP studies deal with improvements improvements in the existing road networks, networks, as most decision decision variables variables are related to the manipmanipulation of the existing existing network. network. Moreover, Moreover, new city constructi constructions ons rarely rarely occur occur in the real world. world. In contras contrast, t, TNDSP TNDSP studies studies (espe (espe-cially those with topological decisions) decisions) mostly deal deal with new trantransit netw network ork configu configurat ration ions, s, or complet complete e recon reconfigu figurati ration on of of the existing transit networks. networks. A common common characterist characteristic ic of RNDP RNDP and and TNDSP TNDSP is that they they consider consider only a single mode (i.e. private private or public transit mode), mode), and also are often often limited limited to the network network for the the mode studied (i.e. focus on single tier or level network). network). In reality, there are multiple multiple modes modes and their demands demands are are interre interrelate lated. d. The Multi-Modal Multi-Modal Network Network Design Design Problem Problem (MMNDP) can be a suitabl suitable e title for for another another categ category ory,, which which encom encompas passe sess at least least two two differ differen entt mode modess for UTN UTNDP DP.. Traffi Traffic c flow flow in MMND MMNDP P can cover automobiles, automobiles, taxi taxis, s, vans vans,, buse buses, s, bicy bicycl cles es,, motor otorcy cycl cles es,, metro, metro, etc. The speci special al case of MMND MMNDP P is the Bi-Modal Network De(BMNDP), which considers considers only two modes. modes. Decisions Decisions sign Problem (BMNDP), considered considered in MMNDP MMNDP can be decisions concerning concerning a single mode mode 284 R.Z. Farahani Farahani et al./ European European Journal Journal of Operation Operational al Research Research 229 (2013) (2013) 281–302 281–302 (i.e. (i.e. road, road, transit, transit, etc.), etc.), or combin combinatio ations ns of variou variouss decision decisionss for the the modes under under focus. focus. In fact, the multi-m multi-modal odal problem problem arises when when at least two modes are considered considered and simulated, simulated, even if design decisions are are related to only one one of the modes. modes. The multi-m multi-modality odality in urban transportati transportation on networ networks ks is capture captured d in several several forms forms in the literature:    this case, case, the the No interacti interactions ons between between flows of different different modes: modes: In this networks networks of different different modes modes are not related related to to each other, other, and thuss the flows thu flows of one mode mode do not have have any any effect effect on the flows flows of the other other mode modes. s. For example, example, in an autom automobil obile-m e-metro etro problem or or in an autom automobil obile-b e-bus us proble problem m where where buse busess move move in exclusiv exclusive e lanes, transit transit flows flows are physical physically ly separated separated from from automobile flows. Interactio Interactions ns between between flows of differen differentt modes: When buses share the same same roads roads with automobiles, automobiles, the flows flows of buses and and autoautomobiles mobiles affect each other. other. In such problem problems, s, road and and bus bus networks are are related related to each other other in terms of of both nodes nodes and and arcs. multi-modal prob prob-Interrelations Interrelations in flows flows and and in deci decisi sion ons: s: Most multi-modal lems only only consider consider flow interactio interactions, ns, while while in problem problemss with with mode related topographic topographic decisio decisions, ns, the effects effects of decisio decisions ns of  one mode mode on on the other other are are address addressed. ed. For exam example, ple, in an autoautomobile-bus mobile-bus mode mode problem, problem, converting converting a two-way two-way street into a one-way one-way street will affect the bus route on that street. MMNDPs usually consider multi-level or multi-tier multi-tie r networ networks ks in which the road network and different public transit networks are conside considered red to be sub-net sub-netwo worrks of the urban urban transpor transportati tation on netnetworks. Another Another dimension dimension of MMNDPs MMNDPs is the number number of modes modes involved in travelling travelling between between two points. points. There are are two cases in this dimensi dimension: on: first, first, traveler travelerss can only only choose choose a one mode mode;; and secsecond, ond, travele travelers rs can choose choose a combina combination tion of modes modes to finish finish their their trips trips and the num number ber of modes modes invol involved ved is greate greaterr than one. one. In the latter, latter, the trips trips are called combined-mode example e combined-mode trips. One exampl is that that of a traveler traveler who who drive drivess to a metro metro station station and then then takes takes a metro metro to his/her his/her destin destinatio ation. n.  2.2.3. Classification of lower level problems in UTNDP The lower lower level problem problem has different different forms, forms, depending depending on the choice dimensions considered and the assumptions for the travelers used. The lower lower level problems problems in the road networ network k category category are different different from those of the transit network network category. category. The road network network problems problems deal deal with vehicles vehicles as flow units, but transit transit network problem problemss consider consider passengers passengers as flow units. The former former allocates the the vehicle vehicle flows to road networks networks under under a specific transport transport policy scenario, while the latter latter allocates allocates the passenge passengers rs to the public transit vehicles after considering considering a fixed fixed flow flow of publ public ic tran tran-sit vehicles resulting from the the specific transit design scenario. scenario. The most prevalent form of the lower level problem considers the rout route e choice choice of the users, users, which which is called called the the trip assignment  assignment  common form form of problem occurs when when a single mode mode  problem. This common is under focus in pure road road or transit network network design problem problems. s. The problem determines determines the the flow pattern of the transport transportation ation netnetwork for a network network design scenario. scenario. Since there there are two types types of  networks, networks, namely namely road networks and transit networks networks,, ther there e are are two types of trip assignment assignment,, name namely ly traffic traffic assignme assignment  nt  and transit  determinin ining g the flow flow pattern patternss in road road and trans transit it assignment , for determ networks respectively. respectively. Trip assignment assignment usually assumes assumes some sort of behavior behavior principles principles to depict the the route choice choice behavior. behavior. The tratraditional one is Wardrop’s (1952) principle, principle, which states that that the traveler selects selects the shortest route. This principle principle assumes that all travelers are non-cooperative non-cooperative and know the the actual travel travel time for each route. route. This principle principle can be easily extended extended to consider consider tolls, parking costs and excess excess time costs. costs. The resulting resulting flow pattern is is called the user-equilibrium (UE) pattern pattern,, which which is the patte pattern rn such such user-equilibrium (UE) that that no traveler travelerss have any any incentive incentive to switch switch to other other routes, routes, as if  they they switch switched ed rout routes, es, their their trave travell time time woul would d be higher higher.. This This assignm assignment ent is called called UE assignm assignment ent.. The The exte extens nsion ion of UE assig assignnment ment is the stochastic user equilibrium assignment (Daganzo equilibrium (SUE) assignment and Sheffi, Sheffi, 1977 1977), ), which assumes assumes that travelers select routes based on perceived perceived travel time. time. This equilibrium equilibrium assumes assumes that travelers travelers may not not know know the trav travel el time time precisel precisely. y. Opposit Opposite e to the UE UE assumption, assumption, if the travelers travelers are are assumed assumed to behave cooperativel cooperatively, y, the resulting resulting assignment assignment is called system optimal optimal (SO) assignment. assignment. In all the above traffic assignment assignment problem problems, s, the congestion congestion effect is normal normally ly conside considered red (i.e. (i.e. the trave travell costs do depend depend on the traffic traffic flows) flows) but in some some cases, cases, the congest congestion ion effect effect is ignore ignored. d. This leads to congested and uncongested assignment respectively. respectively. In particul particular, ar, if the cong congesti estion on effec effectt is ignore ignored d and UE is assumed assumed,, the conventio conventional nal UE UE traffic assignment assignment becomes becomes an all-or-nothin g  (AON (AON)) assign assignme ment nt in which which all all the the dema demand nd is assig assigne ned d to the the shortest route. route. Moreove Moreover, r, if SUE SUE is assum assumed ed inste instead ad,, then then it is a stostochastic assignm assignment ent problem, problem, which is called stochastic uncongested uncongested assignment  assignment . The transit assignment problem can also be divided into categories of  congested and uncongested transit assignment prob problem lems. s. In uncongested uncongested transit transit assignmen assignmentt no passenger passenger capacity capacity is considered for transit vehicles. The congested transit assignment considers the transit passenger capacity restrictions restrictio ns.. In both both prob problem lems, s, different criteria and different passenger behaviors are assumed, which which leads leads to variou variouss approache approachess of allocati allocation on of passeng passenge er demands mands to transit paths. Similar to trip assignm assignment ent,, a stochas stochastic tic verversion exists for both categories categories of transit assignment assignment.. Traditional Traditional trip assignment assignment problems problems treat all classes of traffic flow flow as a single single unifie unified d traffi traffic c flow. flow. Anot Anothe herr import importan antt extensi extension on to traffic traffic assignm assignment ent is to disting distinguish uish betwe between en differen differentt classes classes of  travelers travelers or vehicles. vehicles. The multiclass trip assignment considers different demands and travel cost functions for each user class. Travelers may be classified classified by their their vehicle vehicle owner ownership ship,, trip purpose purposess, and socioeconomic socioeconomic attribu attributes tes such as income income.. Vehicles Vehicles can be classifie classified d into diffe differen rentt vehicle vehicle types types such such as private private cars, cars, taxis, taxis, trucks, trucks, and motorcycles. motorcycles. On the other other hand, the lower lower level problem problem can allow the the users to have more more than than one travel travel choice choice other than route route choice. choice. In such cases, cases, if both destinatio destination n and route choices are are considered, considered, it becom becomes es a trip distribution-assi gnment ulti-m -mod oda al  gnment problem. In multi problems, problems, the lower level level problem has has to tackle more more than one travel mode. mode. If both mode mode choice choice and route choice are are considered considered then the problem becomes the modal split-traffic assignment problem. lem. If all all dest destin inat atio ion, n, mode, ode, and and rout route e choi choice ces, s, as well ell as the the choice of whether whether to travel or not are are incorporate incorporated, d, the lower lower level level problem becomes the combined travel choice problem . Depe Depend ndin ing g on the model model assumption, assumption, users may select different different travel travel choices sequentially sequentially or simul simultan taneo eou usly. In the above above problem problems, s, demand demand (for (for each mode mode)) between between each each origi origin– n–de dest stina inatio tion n (OD) (OD) pair pair can be be fixed fixed or elasti elastic, c, based based on on the the assumptions assumptions of the main model. Basically, Basically, it is call calle ed fixed demand when the the demand demand for the the mode considered considered is unchanged. unchanged. When the demand demand for travel is dependent dependent on on various various factors such as travel time time of the mode mode considered considered or other system performance performance attributes, attributes, it is call calle ed elastic demand. Elastic Elastic deman demand d can be found found in two forms forms;; first when when the deman demand d between between each each OD pair is is varvariable (i.e. simple elasticity is considered), considered), and second second when when the the total dema demand nd betw between een each OD pair is fixed fixed but the share share of each mode mode for for the the total total demand demand is variabl variable. e. The first first case is defined defined for circumstances circumstances where where trav traveler elerss decide decide to give give up their their trave travell when the the travel cost is too high or or they change change their destination destination,, but the second second case is for circumstanc circumstances es where where travelers travelers only decide to to change change their their mode mode of of travel. travel. Moreo Moreover ver,, the secon second d case is is often found in MMNDP where the total demand is divided between various various modes modes of of travel. Nevertheless, Nevertheless, these lower level problems problems implicitly consider more than one travel choice. R.Z. Farahani Farahani et al./ European European Journa Journall of Operatio Operational nal Research Research 229 (2013) (2013) 281–302 281–302 3. Specific Specific Urban Urban Transport Transporta ation Network Design Problems (UTNDPs) Tables 1–6 summarize the problems studied and solution methods used in each publication. publication. In the following following sections, sections, the specific problem problem being being studi studied ed in in each class of UTNDP UTNDP is review reviewed. ed. Section 3.1 focuses on RNDP, Section 3.2 focuses on TNDP and TNDFSP, TNDFSP, Section 3.3 focuses on MMNDP, MMNDP, and Section 4 focuses on the solusolution method. method. For each each class class of problems, problems, the literatur literature e is presented presented in tables which summa summarize rize the problem attribut attributes es discussed in the current current section, and the solution solution methods methods are addressed addressed in Section 4.  3.1. Studies of the Road Network Design Problem (RNDP) General Generally, ly, the inputs inputs of RNDP RNDP are as follows follows:: (1) the networ network k topolo topology; gy; (2) the trav travel el demand demand betw between een each each OD pair pair for a specific cific time time inter interva vall in terms terms of a matr matrix ix or or a func functio tion; n; (3) the the charcharacterist acteristics ics of streets streets such such as the capaci capacity, ty, the num number ber of lanes, lanes, the free flow flow travel time, and the the specification specificationss of the travel travel time time funcfunction; (4) the upper upper and lower lower bounds bounds of decision variables variables for handling physical or political considerations considerations such as the maximu maximum m allowable allowable increase increase in capacity and the the maximu maximum m toll toll level; (5) the set set of candida candidate te project projectss for networ network k improve improveme ment; nt; (6) the availab available le budge budget; t; and (7) the cost cost of of each candida candidate te projec project. t. For some problem problemss such as scheduling scheduling traffic traffic light and and determining determining road tolls, inputs (4)–(7) are not not necessary. necessary. The upper level constraints of RNDP may include the following: following: (1) the simple upper upper and lower bound constraints for the decision variabl variables; es; (2) the budget budget constra constraint int;; and (3) the definiti definitiona onall conconstraints straints such as capacity constrain constraintt and cycle time time constraint. constraint. The capacity capacity constraint constraint is included included in the upper upper level problem problem in in order to prevent prevent the street flow from exceeding exceeding the street capacity. capacity. This constraint constraint is not necessary necessary when the traffic traffic assignment assignment problem has considered capacity capacity constraints. constraints. The cycle time constraint constraint is used to ensure that the the sum of of green times and and all loss times times for all approaches equals cycle time.  3.1.1. Studies of Continuous Network Design Problem (CNDP) The studies on CNDP are summarized summarized in Table 1. 1. They are categocategorized based based on the objectives objectives used, number number of objectives objectives, travel travel dedemand mand (fixed (fixed or elastic), elastic), traffic traffic assignm assignment ents, s, decision decisions, s, and solu solution tion methods methods involved. involved. As reflectedin Table 1, 1, a significa significant nt body body of of RNDP RNDP research has focused focused on CNDP. CNDP. One reason reason for this this may be the continuousness tinuousness of variables, variables, which allows allows for many different modeling modeling approaches and solution methodologies as shown in Table 1. 1. In terms of objectives objectives and and decisions, decisions, travel time related objectives and street capacity expansion have received the most attention. tion. Capa Capacit city y decisi decision onss are supp suppose osed d to be cont contin inuo uou us. Som Some studies also consider both the link capacity decision with the decisions on road tolls tolls (e.g. Yan Yang, g, 1997 1997)) and traffi traffic c lights lights (e.g. (e.g. Ziyou and Yifan Yi fan,, 20 2002 02;; Ch Chiou iou,, 20 2008 08)) simult simultane aneou ously. sly. Table 1 also shows that that most studies studies on CNDP assume assume fixed demand mand (denoted (denoted by F). However However,, some some studies studies (e.g. Yan Yang, g, 1997 1997)) conconsider sider elastic demand demand (denot (denoted ed by E). Moreov Moreover, er, most most studies studies only have a single objective (denoted (denoted by S) and limited studies consider multi-objectives multi-objectives (denot (denoted ed by M). M). MultiMulti-obje objec ctive problems are all handled handled by the weight weighted ed sum approac approach h (denoted (denoted by W). Furthe Furtherrmore, more, most studies studies focus on DUE traffic traffic assignment assignment and total total travel time.  3.1.2. Studies of discrete and mixed network design problems (DNDP  and MNDPs) A summ summar ary y of DNDP DNDP stu studie diess is given given in Table 2. 2. The The body body of  DNDP literature literature is somewhat somewhat smaller smaller than than that that of CNDP, CNDP, probably probably 285 because of the complexity complexity resulting resulting from the presence presence of discrete variables. variables. These DNDP DNDP studies have been investigated investigated in three distinct tinct groups. groups. The first first group group of studies studies is similar similar to the classica classicall literature erature on CNDP in in the sense that that they focus focus on strategic strategic decisions such as constru constructin cting g new new streets streets,, or increasi increasing ng the the capaci capacity ty of  existing streets streets as yes-no type type decisions. decisions. The second second group of of studies considers tactical decisions such as determining the orientation of one-way one-way streets, streets, allocating allocating lanes lanes in two-way two-way streets, streets, and changing some two-way two-way streets into one-way streets. The last group considers both strategic and tactical decisions. Compared Compared with CNDP, CNDP, additional additional objectives objectives such as minimizing minimizing the sum sum of total networ network k cost and total total flow entropy entropy (where (where the entro entropy py of the the link link flow flow prov provide idess a measu measure re of of flow flow balan balance ce of  the link: link: the larger larger the the flow entrop entropy, y, the more more unsy unsymm mmetri etrical cal the flow), and minimizing total travel distance have been considered. ered. Howeve Howeverr, maxi maxim mizing izing cons consum umer er surplu surplus, s, which which is used in the elastic demand demand case, case, has not been consider considered. ed. Moreover, Moreover, nearly all problems problems considered considered single single objective objective with fixed demand. demand. The only exception exception is the work of  of Xiong Xiong and Schneider (1992) in which which a bi-objective bi-objective problem problem was considered considered and Pareto-set Pareto-set (denoted (denoted by P) was generate generated d as the outp output ut of of the problem problem.. Some Some work work can can be done for the multi-objective multi-objective or elastic demand demand case. case. A review review of the studies studies of of MNDP MNDP is is shown shown in in Table 3. 3. As show shown n from this table, these studies involve involve decisions decisions that are combinations tions of those those found found in CNDP CNDP and DNDP DNDP.. More More impor importan tantly, tly, only only a few studi studies es in this field field have have been accom accomplis plished hed in the last last decade. ade. It seems seems that that a lot lot of of work work could could be done done in this this area area (for (for example, example, considering considering lane allocations allocations in two-way two-way streets or considering multiple objectives with environmental concerns).  3.1.3. Time-dependent Time-dependent studies of Road Network Design Problem (RNDP) Because demand and land use use change over time, this consideration on the planning planning horizon horizon is important important in strategic strategic decisiondecisionmaking making.. Howeve However, r, there there are are only only a few time-d time-depe epend ndent ent studies of RNDP RNDP,, which which can be classi classifie fied d into into two two gro group ups, s, name namely ly the the time-dependent time-dependent Continuous Continuous and Discrete Discrete Network Network Design Problems (refe (referre rred d to as CNDP CNDP-T -T and and DNDP DNDP-T -T respe respecti ctive vely) ly) as show shown n in Table 4. 4. All these groups groups deal with determinin determining g the sequence of the decisions decisions to be made within the modeling modeling horizon horizon.. Their bi-level models models can can be viewed viewed as an extensio extension n of the bi-lev bi-level el networ network k design model model (1)–(4) and time indices indices appear in the resulting resulting model as shown shown below: below: ðU 1Þ min u st : : F ðu1  . . . uT  ;  ; ; Gðu1  . . . uT  ;  ; ; v 1 ðu1 Þ  . . . ; v 1  ; ðu1 Þ  . . . ;  ; ðuT ÞÞ ð5Þ ðuT ÞÞ 6 0 ð6Þ v T  v T  where  v t (ut ) is implicitly implicitly determin determine ed by: ðL1Þ min v  st : :  f ð  f ðu1  . . . uT  ;  ; ; g ðu1  . . . uT  ;  ; ; v 1 ;  . . . v 1 ;  ;  . . .  ; Þ ð7Þ Þ60 ð8Þ v T  v T  where u = [ut ] and and v  = [v t ], and the the modeling modeling horizo horizon n is [1,T ]. If  v   v t  is not equal to v t  1, then then a project project should should start start at at time t . In this this way, way, the project project phasing phasing is captured. captured.   3.2. Studies of Transit Network Design Problems and Transit Network Design and Frequency Frequency Setting Problems (TNDPs and TNDFSPs) Usually Usually,, the main main input inputss to TNDP TNDP includ include: e: (1) the netw network ork of  available infrastructure, infrastructure, which might might consist consist of the urban urban road netnetwork work (with (with or withou withoutt dedicat dedicated ed faciliti facilities es such such as bus stops stops), ), rail structures structures (e.g (e.g.. tram tramwa way ys); and (2) the estimated estimated travel demand. demand. Depend Depending ing on on the type type of problem problem,, TNDPs TNDPs may may includ include e various various combination combinationss of of inpu inputs ts such such as (3) (3) the the ava avail ilab able le budg budget et;; (4) (4) 2    8    6    Table 1 A summary of the studies studies of continuous continuous network network design design problems. problems. Reference Reference Objective Max. Max. Min. consumer reserve total surplus capacity capacity vehicle miles Single/ multiple Min. Min. Min. Min. total total optimization travel + construction construction travel time/ construction cost cost cost Traffic Demand Decision Solution Solution method assignment Determining Scheduling Street road tolls traffic traffic light capacity expansion Steenbrink (1974a) d S SO F d Abdulaal and LeBlanc (1979) d S DUE F d Dantzig Dan tzig et al. (19 (1979) 79) d S SO F d Marcotte (1983) d S DUE F d d d LeBlanc and Boyce (1986) Marcotte (1986) d S S DUE DUE F F d d Ben-Ayed Ben -Ayed et al. (198 (1988) 8) d S SO F d Suh and Kim (1992) Friesz Fri esz et al. (19 (1992 92)) d S S DUE DUE F F d d Marcotte and Marquis (1992) d S DUE F d M+W S DUE SUE F F d S S S S M+W S S S S S S DUE DUE DUE DUE DUE DUE DUE DUE DUE DUE DUE E F F F F F F F F F F S S DUE DUE F F Friesz et al. (19 Friesz (1993 93)) Davis (1994) Yang (1997) Yang and Bell (1998b) Meng Me ng et al. (20 (2001 01)) Meng and Yang (2002) Yang and Wang (2002) Ziyou and Yifan (2002) Chiou (2005) Gao et al. (2 (2007 007)) Chiou (2008) d d d d d d d d d d d d d d d d Xu et al al.. (2 (200 009) 9) d Mathew and Shrama (2009) Wang and Lo (2010) d Iterative-Optimization-Assignment Iterative-Optimization-Assignment Algorithm Algorithm Powell’s Powell’s Method Method,, Hooke Hooke and Jeeves Jeeves Method Iterative Decompositio Decomposition, n, Lagrangian Multiplier Exact Algorithm Algorithm Based on Constraint Accumulatio Accumulation, n, Heuristic Heuristic Bard’s Algorithm Four Heuristics Heuristics based on Iterative Iterative Optimization Assignment Algorithms The authors only discuss discuss on the the possible possible solution approaches Bi-level Descent Algorithm Simulated Annealing + BertsekasGafni’s projection method Two Heuristics Heuristics based on on Iterative Optimization Assignment Algorithms Simulated Annealing Generalized Reduced Gradient Method, Method, Sequential Quadratic Programming Sensitivity Sensitivity Analysis Based Method Nil Augmented Augmented Lagrangian Method Simulated Annealing Simulated Annealing Sensitivity Sensitivity Analysis Based Method Four Gradient-based Gradient-based Methods Gradient-based Gradient-based Method Hybrid Approach for Simultaneously Simultaneously Solving Solving the Two Problems Genetic Genetic Algorithm Algorithm,, Simulated Simulated Annealing Genetic Genetic Algorithm Algorithm Transformation Transformation into a Mixed Integer Linear Program d d d d d d d d d d d d d d d d d d d R   .Z   . F   a  r   a   h   a   n  i    e   t    a   l     .  /   E   u r   o   p  e   a   n  J    o   u r   n  a   l     o   f    O   p  e  r   a   t    i    o   n  a   l    R   e   s   e   a  r   c   h  2  2   9   (   2   0  1   3   )   2   8  1  –  3   0  2   Table 2 A summary summary of the studies studies of discrete discrete network network design design problems. problems. Reference Objective Max. Min. reserve network capacity travel cost + flow entropy Min. total travel distances DNDP with strategic decisions Steenbrink (1974b) Min. total societal cost Min. Min. construction travel + cost construction cost DUE DUE F F d S SUE F d d M+P DUE F d d S S DUE DUE F F d Poorzahedy and Abulghasemi (2005) Poorzahedy and Rouhani (2007) d d DNDP with tactical decisions Lee and Yang (1994) Drezner and Wesolowsky (1997) d d Drezner and Salhi (2000) Drezner and Salhi (2002) d d Zhang and Gao (2007) Wuet al al.. (2 (200 009) 9) Long Lon g et et al. (20 (2010) 10) DNDP with both strategic and tactical decisions Making New street Street some constructing capacity streets expansion oneway S S d d Solution method Lane allocation in twotwoway streets F d Xiong and Schneider (1992) Traffic Demand Decision assignment Turning restrictions optimization at intersections SO d Chen and Alfa (1991) Single/ multiple S d Leblanc (1975) Poorzahedy and Turnquist (1982) Yang and Bell (1998b) Gao et al. (20 (2005) 05) Min. total travel time/ cost d d d d d d d d d d S S DUE DUE F F S S DUE AON F F d S S AON AON F F d S SUE F S SUE F S SUE F d d d d d d d d d Iterative Decomposition Algorithm Branch and Bound Branch and Backtrack Heuristics Branch and Bound+ Stochastic Increment Assignment Cumulative Genetic Algorithm Nil Generalized Benders Decomposition Method with Support Function Ant Systems Hybrids of Ant Systems, Systems, Ant Colony with Genetic Algorithm, Algorithm, Simulated Simulated Annealing, Annealing, Tabu Search Search Simulated Annealing Branch and Bound, Heuristics, Heuristics, Simulated Simulated Annealing Tabu Search Genetic Algorithm, Simulated Annealing Particle Swarm Optimization Chaotic Optimization Algorithm Branch and Bound with Sensitivity Analysis Based R   .Z   . F   a  r   a   h   a   n  i    e   t    a   l     .  /   E   u r   o   p  e   a   n  J    o   u r   n  a   l     o   f    O   p  e  r   a   t    i    o   n  a   l    R   e   s   e   a  r   c   h  2  2   9   (   2   0  1   3   )   2   8  1  –  3   0  2   Table 2 A summary summary of the studies studies of discrete discrete network network design design problems. problems. Reference Objective Max. Min. reserve network capacity travel cost + flow entropy Min. total travel distances DNDP with strategic decisions Steenbrink (1974b) Min. total societal cost Min. Min. construction travel + cost construction cost Single/ multiple Traffic Demand Decision assignment Turning restrictions optimization at intersections Min. total travel time/ cost SO F S S DUE DUE F F d S SUE F d d M+P DUE F d d S S DUE DUE F F d d Chen and Alfa (1991) d Xiong and Schneider (1992) d Yang and Bell (1998b) Gao et al. (20 (2005) 05) d Poorzahedy and Abulghasemi (2005) Poorzahedy and Rouhani (2007) d d DNDP with tactical decisions Lee and Yang (1994) Drezner and Wesolowsky (1997) d d Drezner and Salhi (2000) Drezner and Salhi (2002) d d Zhang and Gao (2007) d Wuet al al.. (2 (200 009) 9) d Long Lon g et et al. (20 (2010) 10) d DNDP with both strategic and tactical decisions Drezner and Wesolowsky (2003) Miandoabchi and Farahani (2010) Making New street Street some constructing capacity streets expansion oneway S d Leblanc (1975) Poorzahedy and Turnquist (1982) Solution method Lane allocation in twotwoway streets d d d d d d d d d S S DUE DUE F F S S DUE AON F F d S S AON AON F F d S SUE F S SUE F S SUE F S AON F S DUE F d d d d d d d d d d Ant Systems Hybrids of Ant Systems, Systems, Ant Colony with Genetic Algorithm, Algorithm, Simulated Simulated Annealing, Annealing, Tabu Search Search Simulated Annealing Branch and Bound, Heuristics, Heuristics, Simulated Simulated Annealing Tabu Search Genetic Algorithm, Simulated Annealing Particle Swarm Optimization Chaotic Optimization Algorithm Branch and Bound with Sensitivity Analysis Based d d Iterative Decomposition Algorithm Branch and Bound Branch and Backtrack Heuristics Branch and Bound+ Stochastic Increment Assignment Cumulative Genetic Algorithm Nil Generalized Benders Decomposition Method with Support Function d d R   .Z   . F   a  r   a   h   a   n  i    e   t    a   l     .  /   E   u r   o   p  e   a   n  J    o   u r   n  a   l     o   f    O   p  e  r   a   t    i    o   n  a   l    R   e   s   e   a  r   c   h  2  2   9   (   2   0  1   3   )   2   8  1  –  3   0  2  Descent Algorithm, Simulated Annealing, Tabu Search, Search, Genetic Algorithm Hybrid of of Simulated Simulated Annealing and Genetic Algorithm, Algorithm, Evolutionary Evolutionary Simulated Annealing 2    8   7   2    8    8    Table 3 A summary summary of the studies studies of mixed mixed network network design problem problems. s. Reference Objective Traffic assignment Demand Decisio Decision Solution method Discrete Continuous Making some streets oneway Yang and Bell (1998a) Cantarell Cant arella a et et al. (200 (2006) 6) Dimitriou Dimitrio u et al. (200 (2008a) 8a) Zhang and Gao (2009) Gallo Gal lo et al. (2 (201 010) 0) General weighted sum multi-objective Min. Min. total total travel time DUE F DUE F Max. profit Min. Min. total total travel cost + constr construction uction cost Min. Min. total total travel time SUE DUE E F SUE Street capacity expansion Constructing new streets Orienting sequences of  streets Traffic light setting d Street capacity expansion Road tolls setting Enumeration Enumerati on Scheme with with Other Methods Methods d d d d d d F d d Hill Climbing, Climbing, Simulated Annealin Annealing, g, Tabu Tabu Search, Search, Genetic Genetic Algori Algorithm, thm, Hybrids Hybrids of Tabu Tabu Search Genetic Algorithm Gradient Based Method with Penalty Function Functio n Scatter Search d  Table 4 A summary of time-dependent time-dependent network network design design studies. studies. Reference Objective Traffic assignment Demand Decisio Decision Constructing new streets CNDP-T  Lo and Szeto (2004) Szeto and Lo Lo (2005, 2008) Szeto and and Lo (2006) Solution method Discrete Continuous Street capacity expansion Street capacity expansion Road tolls setting Max. consumer consumer surplus Max. discounted social surplus DUE DUE E E d d Generalized Reduced Gradient Method Generalized Reduced Gradient Method DUE E d d Generalized Reduced Gradient Method Lo and Szeto (2009) Max. discounted social surplus max. max. intergeneration equity Max. discounted consumer surplus DUE E d d Generalized Reduced Gradient Method DNDP-T  O’Brien and Szeto Max. discounted consumer surplus DUE E d Generalized Reduced Gradient and d d R   .Z   . F   a  r   a   h   a   n  i    e   t    a   l     .  /   E   u r   o   p  e   a   n  J    o   u r   n  a   l     o   f    O   p  e  r   a   t    i    o   n  a   l    R   e   s   e   a  r   c   h  2  2   9   (   2   0  1   3   )   2   8  1  –  3   0  2  2    8    8    Table 3 A summary summary of the studies studies of mixed mixed network network design problem problems. s. Reference Objective Traffic assignment Demand Decisio Decision Solution method Discrete Continuous Making some streets oneway Yang and Bell (1998a) Cantarell Cant arella a et et al. (200 (2006) 6) Dimitriou Dimitrio u et al. (200 (2008a) 8a) Zhang and Gao (2009) Gallo Gal lo et al. (2 (201 010) 0) General weighted sum multi-objective Min. Min. total total travel time DUE F DUE F Max. profit Min. Min. total total travel cost + constr construction uction cost Min. Min. total total travel time SUE DUE E F SUE Street capacity expansion Constructing new streets Orienting sequences of  streets Traffic light setting d Street capacity expansion Road tolls setting Enumeration Enumerati on Scheme with with Other Methods Methods d d d d d d F d d Hill Climbing, Climbing, Simulated Annealin Annealing, g, Tabu Tabu Search, Search, Genetic Genetic Algori Algorithm, thm, Hybrids Hybrids of Tabu Tabu Search Genetic Algorithm Gradient Based Method with Penalty Function Functio n Scatter Search d  Table 4 A summary of time-dependent time-dependent network network design design studies. studies. Reference Objective Traffic assignment Demand Decisio Decision Constructing new streets CNDP-T  Lo and Szeto (2004) Szeto and Lo Lo (2005, 2008) Szeto and and Lo (2006) Lo and Szeto (2009) DNDP-T  O’Brien and Szeto (2007) Solution method Discrete Continuous Street capacity expansion Street capacity expansion Road tolls setting Max. consumer consumer surplus Max. discounted social surplus DUE DUE E E d d Generalized Reduced Gradient Method Generalized Reduced Gradient Method Max. discounted social surplus max. max. intergeneration equity Max. discounted consumer surplus DUE E d d Generalized Reduced Gradient Method DUE E d d Generalized Reduced Gradient Method Max. discounted consumer surplus DUE E d Generalized Reduced Gradient and Branch and Bound d d R.Z. Farahani Farahani et al./ European European Journa Journall of Operatio Operational nal Research Research 229 (2013) (2013) 281–302 281–302 R   .Z   . F   a  r   a   h   a   n  i    e   t    a   l     .  /   E   u r   o   p  e   a   n  J    o   u r   n  a   l     o   f    O   p  e  r   a   t    i    o   n  a   l    R   e   s   e   a  r   c   h  2  2   9   (   2   0  1   3   )   2   8  1  –  3   0  2  289  Table 5 A summary summary of TNDP and and TNDFSP studie studies. s. Reference TNDP studies Patz (1925) Sonntag (1977) Mandl (1980) Pape Pap e et al. (19 (1992 92)) Constraints Objective(s) Solution method – Bus capacity capacity – Demand Demand Restricted Restricted set of possible possible lines Min. number number of empty empty seats Heuristic Heuristic – Min. average average travel travel time – Min. Min. numb number er of transf transfers ers – Min. travel travel time time – Max. route route directness directness – Min. number number of lines – Max. number number of direct direct passen passengers gers – Min. total travel time – Min. Min. unsat unsatisfi isfied ed deman demand d – Max. number number of passengers passengers,, who travel travel with at most two two transfers – Min. number number of transfers transfers – Max. route route directness directness – Max. area coverage coverage Heuristic Heuristic – Constant Constant frequency frequency – Area coverage coverage Area coverage coverage Chakroborty and Dwivedi (2002) Route feasibility Zhao and Gan (2003) – Predefined Predefined routes routes and areas – The number number of lines and stops stops – Route Route and network network directnes directnesss – deviation from main routes routes – Route length – The length length of lines – Route Route directness directness Zhao and Ubaka (2004) Yu et al al.. (2 (200 005) 5) Guan Gu an et al. (20 (2006) 06) – The link capacity capacity – The length length of line – Number Number of transfers transfers Zhao and Zeng (2006) – Route Route directness directness feasibility feasibility – Min. total total number number of transfers transfers – Min. maximu maximum m passenger passenger flow in each route – Min. total total length length of routes routes – Min. Min. total total numbers numbers of routes routes taken taken by passengers – Min. total total distances distances traveled traveled by passengers – Min. average average number number of transfers transfers servic Heuristic Heuristic Heuristic Heuristic Genetic algorithm Greedy Greedy search, search, hill climbing climbing,, hybrid hybrid of tabu search, search, simulated annealing, and greedy search Greedy search, fast hill climb search Parallel Parallel ant colony colony Mathema Mathematical tical method method Hybrid Hybrid metaheu metaheuristic risticss R.Z. Farahani Farahani et al./ European European Journa Journall of Operatio Operational nal Research Research 229 (2013) (2013) 281–302 281–302 289  Table 5 A summary summary of TNDP and and TNDFSP studie studies. s. Reference TNDP studies Patz (1925) Sonntag (1977) Mandl (1980) Pape Pap e et al. (19 (1992 92)) Constraints Objective(s) Solution method – Bus capacity capacity – Demand Demand Restricted Restricted set of possible possible lines Min. number number of empty empty seats Heuristic Heuristic – Min. average average travel travel time – Min. Min. numb number er of transf transfers ers – Min. travel travel time time – Max. route route directness directness – Min. number number of lines – Max. number number of direct direct passen passengers gers – Min. total travel time – Min. Min. unsat unsatisfi isfied ed deman demand d – Max. number number of passengers passengers,, who travel travel with at most two two transfers – Min. number number of transfers transfers – Max. route route directness directness – Max. area coverage coverage Heuristic Heuristic – Constant Constant frequency frequency – Area coverage coverage Area coverage coverage Chakroborty and Dwivedi (2002) Route feasibility Zhao and Gan (2003) – Predefined Predefined routes routes and areas – The number number of lines and stops stops – Route Route and network network directnes directnesss – deviation from main routes routes – Route length – The length length of lines – Route Route directness directness Zhao and Ubaka (2004) Yu et al al.. (2 (200 005) 5) Guan Gu an et al. (20 (2006) 06) – The link capacity capacity – The length length of line – Number Number of transfers transfers Zhao and Zeng (2006) Barra Bar ra et al. (20 (2007 07)) Yang Yan g et al. (2 (2007 007)) – Route Route directness directness – Route Route feasibility feasibility – Numb Number er of routes routes – Route Route length – Budge Budgett – Travel demand satisfaction – Budge Budgett – Service Service level level The length length of routes routes Mauttone and Urquhart (2009) Fan and Mumford (2010) Travel demand satisfaction Curtin and Biba (2011) The length length of routes routes TNDFSP studies Lampkin and Saalmans (1967) Silman Silm an et al. (19 (1974) 74) The number of lines Fleet size Budget Budget Dubois et al. (19 Dubois (1979) 79) Hasselströ Hasse lström m (19 (1979, 79, 198 1981) 1) Budget Budget Budget Ceder and Wilson (1986) – Minimum Minimum frequency frequency Van Nes et al. (198 (1988) 8) – Fleet size – Route Route length Fleet size Shih and Mahmassani (1994) and Shih et al. (199 (1998) 8) Nil Baaj and Mahmassani (1995) – Headway Headway – Fleet size – Capacity Capacity – Number Number of transit transit vehicles vehicles – Frequency Frequency – Line and vehicle capacity – Headway Headway – Load factor factor – Demand satisfaction Bussieck (1998) Pattnaik Patt naik et al. (19 (1998) 98) Carrese and Gori (2004) – Routes Routes length length – Number Number of transfers transfers – total total travel time time – Fleet size – Min. total total number number of transfers transfers – Min. maximu maximum m passenger passenger flow in each route – Min. total total length length of routes routes – Min. Min. total total numbers numbers of routes routes taken taken by passengers – Min. total total distances distances traveled traveled by passengers – Min. average average number number of transfers transfers – Max. service service coverage coverage Heuristic Heuristic Heuristic Heuristic Genetic algorithm Greedy Greedy search, search, hill climbing climbing,, hybrid hybrid of tabu search, search, simulated annealing, and greedy search Greedy search, fast hill climb search Parallel Parallel ant colony colony Mathema Mathematical tical method method Hybrid Hybrid metaheu metaheuristic risticss Min. total length of routes Mathematical Mathematical method – Max. number number of direct direct travelers travelers per unit length – Min. number of routes – Min. total total travel travel time time – Min. total travel time – Min. total total numb number er of transfers transfers – Max. the sum of arc and node node service service values Parallel ant colony – Max. number number of direct direct passengers passengers – Min. total total travel travel time time – Min. fleet size – Min. journey journey time time – Min. overcrow overcrowding ding Min. total travel time – Min. number number of transfers transfers – Max. Max. numb number er of passen passenger gerss – Min. excess excess travel travel time, time, transfer transfer and waiting time – Min. vehicle vehicle costs costs – Max. demand satisfaction – Max. Max. numb number er of direct direct trips trips – Min. travel travel time time – Max. demand demand satisfact satisfaction ion – Min. Min. fleet fleet size size – Max. number number of direct direct trips – Min. waiting waiting time, time, transfer transfer time Heuristic Hill-climbing, simulated annealing Heuristic Heuristic Heuristic Heuristic Heuristic Heuristic Mathema Mathematical tical method method Heuristic Mathematical Mathematical method + heuristic Heuristic Heuristic Heuristic Heuristic – Max. number number of direct direct passengers passengers – Min. operator operator costs Mathema Mathematical tical method method – Min. operator operator costs – Min. Min. passengers passengers’’ travel time time – Min. users waiting time and excess time compared to the minimum minimum path – Min. operator operator costs Genetic Genetic algorithm algorithm Heuristic (continued continued on next page) page) R.Z. Farahani Farahani et al./ European European Journal Journal of Operation Operational al Research Research 229 (2013) (2013) 281–302 281–302 290  Table 5 (continued) continued) Reference Constraints Objective(s) Solution method Bielli et al. (2 Bielli (2002 002)) Fusco Fu sco et al. (20 (2002 02)) Max. 24 criteria of network performance Min. Min. overall overall cost Genetic algorithm Heuristic Heuristicss Tom and Mohan (2003) Nil Wan and Lo (2003) – Service Service frequenci frequencies es of lines lines – Bus capacity capacity – Frequenc Frequency y – Load factor Route Route length length – Min. operator operator and users costs costs – Min. fleet size – Min. cost of waiting and traveling – Min. Min. fleet fleet size size or fleet fleet cost cost – Min. operation costs – Min. total total travel travel time time Min. Min. operation operation costs costs Heuristic Heuristic Ngamchai and Lovell (2003) Using predetermined predetermined lines – Level of service service – Satisfi Satisfied ed demand demand – Lines configuration configuration – Frequenc Frequency y – Route Route length length – Deviation Deviation from shortest shortest path Area coverage Ceder (2003) Agrawal and Mathew (2004) Fan and Machemehl (2004) Hu et al al.. (2 (200 005) 5) Zhao (2006) Zhao and Zeng (2007) Bornd Bo rndörf örfer er et al. (20 (2008 08)) Pacheco Pach eco et al. (200 (2009) 9) Szeto and Wu (2011) Cipriani Cipr iani et al. (201 (2012) 2) – Rout Route e leng length th – Average Average transfer transfer times, times, station station stopping times and headways Route Route directnes directnesss – Headway Headway bound bound – Fleet size – Route Route length length – Load factor factor Demand satisfaction – Number Number of routes routes – Fleet size – Location Location of of the bus bus stops stops – Fleet size – Number Number of of transit transit stops stops – Frequenc Frequency y – Route Route length length – Bus capacity – Frequenc Frequency y – Route Route length length – Min. operator operator and users cost – Min. time time of waiting, waiting, traveling, traveling, and walking – Min. Min. fleet fleet size size – Min. Min. cost cost of unsat unsatisfi isfied ed deman demands ds – Max. Max. the the nons nonsto top p pass passen enge gerr flow flow – Min. Min. sum of passen passenger gers’ s’ and and operato operatorr costs – Min. Min. total total no. of transfers transfers – Max. demand demand coverage coverage Min. Min. weighted weighted sum of users’ users’ and operator operator cost – Min. operation cost – Min. total total travel travel time time Min. Min. total total time of waiting waiting and traveling traveling Genetic algorithm Genetic algorithm MIP solver solver in CPLEX CPLEX Heuristic Heuristic,, parallel parallel Genetic algorithm Genetic algorithm Gene Geneti tic c algo algori rith thm m, ant ant colo colony ny Simulate Simulated d annealin annealing g Heuristics, simulated annealing Column Column generation Local search, search, tabu search Min. Min. weighted weighted sum of the number number of  transfers and network travel time Genetic algorithm Min. sum of operator and user costs Heuristic, parallel genetic algorithm capacity capacity of buses; buses; (5) maximu maximum m or desired desired numbe numberr of bus lines; lines; (6) set of predefi predefined ned possibl possible e bus lines; lines; (7) maximu maximum m and minim minimum um allowab allowable le round round trip trip time of of bus lines; lines; (8) frequen frequency cy of bus lines; lines; (9) maximu maximum m number number of bus stops; stops; (10) (10) minimu minimum m coverag coverage e area by the bus networ network k as the percent percentage age of demand demand that that can be served; served; and (11) maximu maximum m number number of transfer transfers. s. For TNDFSP TNDFSP,, addiadditional information information is required required such such as as fleet size, and the minimum minimum service frequency. As stated stated in in Guihaire and Hao (2008), (2008), the typical consideratio considerations ns for TNDP TNDP are normally normally the the following: following: (1) dependency dependency on the existexisting routes; routes; (2) area covera coverage; ge; (3) route route and and trip trip direc directne tness; ss; (4) demand satisfaction; satisfaction; (5) the num number ber of of lines lines or total total length length of routes; routes; and (6) (6) the overal overalll shape shape of the netw network. ork. For TND TNDSFP SFP,, additio additional nal considerations considerations such as as the number number of runs and frequency frequency bounds bounds for each line are usually usually included. included. Depending Depending on the decision-madecision-maker’s policy for transit networks, networks, these these consi considera deration tionss can be reflect flected ed in cons constr trai ain nts or obje object ctiv ive e fu functi nctio ons by sett settin ing g a boundary for the measure or optimizing the measure measure respectively. For example, example, route length length can appear in the objective function function (e.g. Barr Ba rra a et al. al.,, 20 2007 07)) and route route constrain constraints ts (e.g. (e.g. Szeto and Wu, Wu, 2011 2011). ). For the former, former, the total route route length length is minimize minimized d whereas whereas for the the latter, the route route length length of of each transit transit line line cannot cannot be be exceeded by a user-predetermined user-predetermined value. Regarding Regarding the the numerous numerous studies on TNDFSP TNDFSP and TNDP, a summary mary is present presented ed in Table 5. 5. The The studi studies es in these these two two field fieldss are very diverse diverse and and different different in terms of objectives, objectives, their constrain constraints, ts, and the solution solution methods methods used. The problems problems are usually usually approached proached by multiple multiple criteria to consider consider the interests interests of the public public sectors, line operators operators and and the users, users, but normally normally a weighted weighted sum objective function function is eventually eventually used. used. Also, most of them assume assume a very simplified simplified passenge passenger behavior behavior that that leads to a single-level single-level optimization problem. In most of the existing existing bus bus network network design design problems, problems, any flows flows on the road road network network other than buses such as cars, taxis, and bicycles were generally ignored, ignored, and hence the interactions interactions between between these flows flows and bus flows flows were not not taken into into account. account.  3.3. Studies of the Multi-Modal Multi-Modal Network Design Problem Problem (MMNDP) (MMNDP) A summar summary y of the studies studies of MMNDP MMNDP is provide provided d in Table 6. 6. The The lower-level lower-level problem of these studies is formulat formulated ed as the the moda modall split-traffic split-traffic assignment assignment problem to capture the interaction interaction of the demand demand between between modes. modes. As we can see, these these studies studies can be divided into into two groups. groups. The first group covers covers the studies studies in allocating exclusive exclusive lanes lanes to specific transportation transportation modes. modes. There are are few studies in this group; group; most of which analyze some restricted scenarios as decision-ma decision-making king options, options, and there there is just one one case dealdealing with mathematical modeling. The second group encompasse encompassess the studies which only deal with transit network design decisions. The third group covers studies that simultaneously consider various strateg strategic ic and tactica tacticall decision decisionss of UTNDP. UTNDP. Again, Again, there there are a limite limited d numb number er of of studie studiess in this this grou group. p. More Moreov over er,, these these two two groups assume that that travelers can reach their destinations by using one mode and combined mode trips such as bus-metro trips and trips are not not consid considere ered. d. Indeed Indeed,, there there is a third third group group Park’n’Ride trips that further considers the operational operational decisions of RNDP and TNDP (e.g. Cl Cleg egg g et al al., ., 20 2001 01;; Be Bell llei ei et al al., ., 20 2002 02;; Ha Hamd mdou ouch ch et al al., ., 20 2007 07;; 292 R.Z. Farahani Farahani et al./ European European Journal Journal of Operation Operational al Research Research 229 (2013) (2013) 281–302 281–302 Wu et al al., ., 20 2011 11). ). We do not cite them them here, here, as they they fall fall outsid outside e the the scope scope of this paper. paper. 4. Review Review of solution solution techniqu techniques es to Urban Urban Transport Transportati ation on Network Design Problem (UTNDP) The solution methods noted in Tables 1–6 can be classifie classified d into three categories: categories: (1) (1) exact exact or math mathem emati atical cal meth method odss; (2) (2) heuri eurisstics; tics; and and (3) (3) metah metaheu euris risttics. Exact Exact meth methods ods such as the branch branch and bound method, method, branch-backtr branch-backtrack ack based algorithms algorithms or mathemathematical programming techniques techniques rely rely on on som some math mathem emat atic ical al prop proper ertie tiess to solv solve e the pro proble blem m to at least least local local opt optim imali ality. ty. Although Although some some of them, them, such as mathematical mathematical program programming ming techtechniques for for solving linear linear and nonlinear nonlinear problems, problems, can be used to solve realistic, realistic, large networks networks efficiently, efficiently, others for integer integer proprogramming gramming problems, problems, such as the branch branch and bound method, method, are inapplicable inapplicable for medium medium or large sized network networkss because of computational inefficiency. Heuristics are usually developed developed from from the the insigh insightt of the probproblem but but there may not be convergence. convergence. However, However, they are are always always more efficient efficient than the branch branch and bound bound method method and can be be applied to large network networks. s. Metaheuristics Metaheuristics such as Simulated Simulated Annealin Annealing g (SA) (SA) and the use of  4.1. Solution techniques techniques to the Road Network Design Design Problem (RNDP) The literature on Continuous Network Network Design Problem (CNDP encompasses encompasses a variety variety of solution solution techn technique iques, s, given given the differen differen-tiability of the continuous continuous variables. variables. This diversity diversity is very noticeable in in studies studies from from the the 1970s 1970s and and 1980s 1980s.. For Discr Discrete ete and and Mixed Network Network Design Problem Problemss (DNDP and MNDP), MNDP), discrete variables make these problems NP-hard and non-convex so that exact methods such as the branch and bound method method cannot solve these problems problems efficiently. efficiently. We have noted noted that that due to to the intrinsic intrinsic comcomplexity plexity of these these problem problems, s, the diversi diversity ty of solution solution algor algorithm ithmss is somewhat somewhat limited. limited. A large amount amount of of solution solution algorithm algorithmss belong belong to the metaheurist metaheuristics ics category and the few remaining algorithms are from exact and heuristic type methods. methods. For time-depende time-dependent nt problems, problems, very limited solution solution algorithms algorithms have been develope developed d as the problems problems are relatively relatively new. As expected expected,, the solut solution ion techni techniqu ques es for RNDP RNDP can can be categocategorized into exact methods, methods, heuristic heuristic methods and metaheuristics metaheuristics,, since since RNDP RNDP belon belongs gs to to UTNDP. UTNDP. Exact Exact meth methods ods such as branch branch and bound bound can be found found mostly mostly in DNDP. DNDP. Examples Examples of the use of such meth methods ods includ include e LeBlanc (1975), Chen and and Alfa (1991), (1991), Drezner and Wesolowsky Wesolowsky (1 (199 997) 7),, an and d Lo Lon ng et al al.. (2 (20 010 10)). They developed developed the branch branch and bound bound algorithm algorithm to directly solve solve their (upper (upper)) problem problems. s. LeB LeBlan lanc c (197 (1975) 5) an and d Long Long et al. (2 (201 010) 0) solved the 24-nodes 24-nodes and 76-links Sioux Falls network, and Chen and Alfa (1991) solved four networks, networks, the largest largest of of them them being being the 41- R.Z. Farahani Farahani et al./ European European Journal Journal of Operation Operational al Research Research 229 (2013) (2013) 281–302 281–302 292 Wu et al al., ., 20 2011 11). ). We do not cite them them here, here, as they they fall fall outsid outside e the the scope scope of this paper. paper. 4. Review Review of solution solution techniqu techniques es to Urban Urban Transport Transportati ation on Network Design Problem (UTNDP) The solution methods noted in Tables 1–6 can be classifie classified d into three categories: categories: (1) (1) exact exact or math mathem emati atical cal meth method odss; (2) (2) heuri eurisstics; tics; and and (3) (3) metah metaheu euris risttics. Exact Exact meth methods ods such as the branch branch and bound method, method, branch-backtr branch-backtrack ack based algorithms algorithms or mathemathematical programming techniques techniques rely rely on on som some math mathem emat atic ical al prop proper ertie tiess to solv solve e the pro proble blem m to at least least local local opt optim imali ality. ty. Although Although some some of them, them, such as mathematical mathematical program programming ming techtechniques for for solving linear linear and nonlinear nonlinear problems, problems, can be used to solve realistic, realistic, large networks networks efficiently, efficiently, others for integer integer proprogramming gramming problems, problems, such as the branch branch and bound method, method, are inapplicable inapplicable for medium medium or large sized network networkss because of computational inefficiency. Heuristics are usually developed developed from from the the insigh insightt of the probproblem but but there may not be convergence. convergence. However, However, they are are always always more efficient efficient than the branch branch and bound bound method method and can be be applied to large network networks. s. Metaheuristics Metaheuristics such as Simulated Simulated Annealin Annealing g (SA) (SA) and the use of  a Genetic Genetic Algo Algorith rithm m (GA) (GA) were were propos proposed ed based based on analogi analogies es to physi physical cal,, chemi chemical cal,, or biolog biologica icall proce processe sses. s. They They do do not not requ require ire any mathematical mathematical property property of the problem problem to solve for for solutions solutions and can be used for obtaining obtaining nearly nearly global optimal optimal solutions. solutions. The computation computation speed speed of these methods methods is much faster faster than exact methods for integer programming programmin g prob problem lemss in gene genera rall but at the the expense of solution accuracy. Fig. 2 summarizes summarizes the applications applications of some some metaheu metaheuristics. ristics. This figure figure shows that GAs GAs and SAs have have been mostly mostly used to solve UTNDP, UTNDP, probably probably because they they are classical metaheuristics. metaheuristics. Some other common common method methodss such as Tabu Search Search (TS), (TS), Scatter Scatter Search Search (SS), (SS), Ant Colony Colony (AC), (AC), Ant Systems Systems (AS), and Particle Particle Swarm Optimiz Optimiza ation (PSO) (PSO) have have been been used used in a few studies. Also, some studies have developed developed hybrid hybrid (H) metaheuristics heuristics to achieve a better solution solution quality quality than than non-hybrid non-hybrid metaheuristics. metaheuristics. This This figure figure also reve reveals als that that metahe metaheu uristics have been mostly mostly appl applied ied to TNDFSP TNDFSP,, DNDP, DNDP, and MMN MMNDP, DP, mainly mainly bebecause of of the presence presence of discrete decision variables variables in these probproblems and their non-convexit non-convexity y which causes causes a comput computatio ational nal burden if exact methods methods were were used. More More discu discussio ssion n of of solution solution techniq techniques ues to RNDP, RNDP, TNDP TNDP and and TNDF TNDFSP SP,, and and MM MMNDP wil willl be be give given n in in Sect Sectio ion ns 4.1–4.3 4.1–4.3,, respectively. respectively. 10 CNDP 9 DNDP MNDP 8 MMNDP   s   n 7   o    i    t   a 6   c    i    l   p   p 5    A    f 4   o  .   o    N 3 TNDP TNDFSP 2 1 0 SA GA TS AS, AC PSO SS Methods Fig. Fig. 2. A summary summary of metaheuristics used for for UTNDP. UTNDP. H 4.1. Solution techniques techniques to the Road Network Design Design Problem (RNDP) The literature on Continuous Network Network Design Problem (CNDP encompasses encompasses a variety variety of solution solution techn technique iques, s, given given the differen differen-tiability of the continuous continuous variables. variables. This diversity diversity is very noticeable in in studies studies from from the the 1970s 1970s and and 1980s 1980s.. For Discr Discrete ete and and Mixed Network Network Design Problem Problemss (DNDP and MNDP), MNDP), discrete variables make these problems NP-hard and non-convex so that exact methods such as the branch and bound method method cannot solve these problems problems efficiently. efficiently. We have noted noted that that due to to the intrinsic intrinsic comcomplexity plexity of these these problem problems, s, the diversi diversity ty of solution solution algor algorithm ithmss is somewhat somewhat limited. limited. A large amount amount of of solution solution algorithm algorithmss belong belong to the metaheurist metaheuristics ics category and the few remaining algorithms are from exact and heuristic type methods. methods. For time-depende time-dependent nt problems, problems, very limited solution solution algorithms algorithms have been develope developed d as the problems problems are relatively relatively new. As expected expected,, the solut solution ion techni techniqu ques es for RNDP RNDP can can be categocategorized into exact methods, methods, heuristic heuristic methods and metaheuristics metaheuristics,, since since RNDP RNDP belon belongs gs to to UTNDP. UTNDP. Exact Exact meth methods ods such as branch branch and bound bound can be found found mostly mostly in DNDP. DNDP. Examples Examples of the use of such meth methods ods includ include e LeBlanc (1975), Chen and and Alfa (1991), (1991), Drezner and Wesolowsky Wesolowsky (1 (199 997) 7),, an and d Lo Lon ng et al al.. (2 (20 010 10)). They developed developed the branch branch and bound bound algorithm algorithm to directly solve solve their (upper (upper)) problem problems. s. LeB LeBlan lanc c (197 (1975) 5) an and d Long Long et al. (2 (201 010) 0) solved the 24-nodes 24-nodes and 76-links Sioux Falls network, and Chen and Alfa (1991) solved four networks, networks, the largest largest of of them them being being the 41nodes and 73-links Winnipeg Winnipeg netw networ ork. k. Drezner and Wesolowsky Wesolowsky (1997) solved small and medium sized networks, networks, the the larg larges estt being a 40-nodes 40-nodes and 99-links randomly randomly made network. network. Some studies transformed RNDP into a single level problem and used exact methods methods to solve the resultan resultantt problem. problem. For example, example, Gao Ga o et al. (2 (200 005) 5) transformed transformed DNDP DNDP to a nonlinear nonlinear programm programming ing problem using the support function concept and solved the nonlinear problem by existing nonlinear nonlinear programm programmin ing g techn techniqu iques. es. Gao et al al.. (2 (200 007) 7) developed developed a gradient-ba gradient-based sed method for CNDP using the lower-level problem’s optimal-value optimal-value function. Zhang and Gao (2009) reformulated reformulated MNDP MNDP as CNDP, CNDP, and solved the bi-level bi-level model by the use use of the optim optimal-v al-val alue ue function function of the lower-level lower-level model in a grad gradien ientt-ba based sed method. Other studies studies directly formulated formulated RNDP into a mathematica mathematicall program program with equilibrium equilibrium constraints, constraints, and then then used exact exact methods methods to solve the resultant resultant problem. problem. Not many many studies studies have have adopted this approach. approach. For For CNDP CNDP,, Lo and Szet Szeto o (20 (2004, 04, 200 2009) 9) and Szet Sz eto o an and d Lo (2 (200 005, 5, 20 2006 06,, 20 2008 08)) adopted the generalize generalized reduced gradient gradient based method method to solve the resultant resultant nonlinear nonlinear program, program, while for MMND MMNDP, P, Sz Szet eto o et al al.. (2 (201 010) 0) used the branch and bound algorithm algorithm to the mixed-integ mixed-integer er problem and the the generalized reduced reduced gradient based method method was employed to solve the relaxed problem. The second category category is heuristics heuristics.. There There exists exists a wide wide variety variety of  heuristics for RNDP and especially for CNDP. CNDP. Before applying heuheuristics, ristics, a number number of of studies studies of of RNDP RNDP use the the indirect indirect appr approach oach,, in which which the propose proposed d bi-level bi-level model model is first transfor transforme med d to a single single level optimization optimization model model or a mathematica mathematicall program program with equilibrium constraints, constraints, and then the resultant resultant model model is solved. For instance, Steenbrink (1974b) approximated user optimal flows with system optimal optimal flows and solved DNDP DNDP using the iterative iterative decomposition decomposition method. Abdulaal and LeBlanc (1979) reformulated reformulated their their problem problem as an uncons unconstra traiined optimiz optimization ation and solved it by a direct search method. Marcotte (1983) transformed CNDP into a single level equivalent differentiable differentiable optim optimiza izati tion on prob problem lem and and solved solved it using using a constra constrain intt accumulation accumulation algorithm. algorithm. Poorzahedy and Turnquist Turnquist (1 (198 982) 2) approximated approximated the bi-leve bi-levell prob problem lem to a single level problem, problem, using the the objective objective function function of the lower-level lower-level problem problem as the objec objectiv tive e functio function, n, and all all constra constraint intss of upper upper and lower-leve lower-levell problems problems as the constraints constraints set, and then then used R.Z. Farahani Farahani et al./ European European Journa Journall of Operatio Operational nal Research Research 229 (2013) (2013) 281–302 281–302 two branch-backtr branch-backtrack ack based algorithms algorithms to solve the Sioux Falls network. Davis (1994) transformed transformed CNDP CNDP into a single level problem by including including constraints constraints to represent represent the SUE condition condition and solved it using sequential sequential quadratic programmin programming g and generalized generalized reduced gradient methods. LeBlanc and Boyce (1986) reformulated reformulated CNDP into a single level linear model with with combined lower lower and upper-level objective functions and solved it using Bard’s method. method. Marcotte Marco tte (1986) and Marcotte Marcotte and Marquis Marquis (1992) (1992) both transformed formed the UE conditions conditions into variational inequalities inequalities and developed heuristics heuristics for CNDP CNDP based on the iterative iterative optimization optimization assignment method. Me Meng ng et al. (20 (2001 01)) developed developed an augmented augmented Lagrangian method in which the DUE conditions were represented by a single single constra constraint int in terms terms of the margin marginal al functio function. n. Finally Finally,, Wang and Lo (2010) transformed CNDP into a mixed integer linear program program and solved it using CPLEX. CPLEX. The other group group of RNDP studies studies has developed developed heuristics to directly solve solve the bi-level bi-level model model of the problem. problem. They mostly mostly used descent search methods and exploit the derivative information informat ion of  the implicit response function of  v (u) that that can can be obtaine obtained d from from the lower lower-lev -level el problem problem.. Most Most of these these studies studies are of of the CNDP CNDP type. type. For example example,, Suh and Kim (1992) used a bi-leve bi-levell descent descent algorithm algorithm based on variation variational inequality inequality sensitivity sensitivity analysis. Yang (1997) applied the sensitivity sensitivity analysis analysis based method to set road tolls. Ziyou and Yifan (2002) used the sensitivity sensitivity analysi analysiss based based method method to determine determine signal setting and link expansion. expansion. To solve CNDP, Chiou (2005) employed four gradient-based gradient-based methods, methods, namely Rosen’s gradient projection method, the conjugate gradient gradient projection projection method, method, the quasi-Newt quasi-Newton on project projection ion metho method, d, and Rosen’s gradient projection method with the techniques techniqu es of para parall llel el tangents tangents (PARTAN), (PARTAN), with the use use of derivative derivative information. information. Chiou (2008) proposed proposed a hybrid approach approach to iteratively iteratively solve solve the two bi-level bi-level models (one for reserved capacit capacity y maximization maximization and one for delay-minimizatio delay-minimization) n) and used projected quasi-Newt quasi-Newton on in part part of it. Again, the sensitivity sensitivity analysis analysis based method method was was also incorpoincorporated to find the gradien gradientt informatio information n. There are a few studies from th the e 1970s that develope developed d single single level models models because of using system optimiz optimization ation for the traffic traffic assignment, assignment, and directly directly solving them them by using heuristic heuristic methods. methods. For instance, Dan Dantzig tzig et al. (197 (1979) 9) developed developed an iterative iterative decomposition method and Steenbrink (1974a) used iterative-optimizationiterative-optimizationassignment. assignment. The third third category of of solution solution methods methods belongs belongs to metaheu metaheurisristics. tics. In almost almost all all of the propo proposed sed meta metaheu heurist ristics, ics, the lower lower level level problem is solved for for each newly newly generated generated solution solution to to calculate the objective objective function function value. The application application of this type of solution method method is prevalently prevalently found in DNDP and and MNDP as mentioned mentioned earlier. lier. Therefo Therefore, re, many many studies studies availabl available e in the literat literature ure (as (as shown shown in Tab Tables les 2 and 3) rely rely on meta metahe heu uristics or or their hybrids. hybrids. CNDP has the fewest fewest applications applications of of metaheuristics, metaheuristics, with few applications applications of SA and GA. The budget budget limit limit as the main constraint constraint of CNDP has has been considered considered as the penalty penalty for the objective objective function by Meng and Yang (2002) and Yang and Wang (2002) in SA and by Mathew and Sharma (2009) in GA. In contra contrast, st, DNDP DNDP has has a variety variety of metahe metaheuri urist stics ics and their hybrids, and these solution techniques usually handle constraints directly within within the algorithmic algorithmic steps. steps. For DNDP DNDP with strategic strategic decisions, decisions, AS and its hybrids hybrids have been been applied. applied. For DNDP DNDP with tactactical tical decisions, decisions, classical classical metahe metaheuri uristics stics such such as SA, GA, and TS have have been proposed for orientation orientation of one-way one-way streets streets and PSO has been used to to solve the the lane lane allocation allocation problem problem.. In DNDP with strategic strategic and tacti tactical cal decisio decisions, ns, a numbe numberr of classical classical meta metaheu heurist ristics ics and two hybrid metaheurist metaheuristics ics of of GA have have been been develop developed. ed. The conconstruction struction budget budget in DNDP is tackled inside inside the algorithmic algorithmic steps steps rather rather than than by penalti penalties es in the objec objective tive func function tion.. For instan instance, ce, Poorzahedy and Abulghasemi (2005) (2005) and Poorzahedy and Rouhani Rouhani (2007) considered budget feasibility after new solutions were gen- 293 erate erated d by by the the ant ants. s. In Miandoabchi and Farahani (2010), (2010) , budg budget et feasibility feasibility was maintained maintained when perturbati perturbation on was performed performed or it was repaired repaired when generating generating new solutions solutions (e.g. (e.g. by a crossover crossover operat operator or in GA). GA). In DNDP DNDP when when includin including g tactical tactical decision decisions, s, some some constraints constraints are related to street orientations orientations (e.g. connectivity connectivity between tween OD pairs) pairs) or lanes lanes configu configurat ration ions. s. These These are eithe eitherr considconsidered ered in the the mov move e gen gener erati ation on phase phase (e.g. (e.g. in SA), SA), or are are check checked ed after generatin generating g new solutions solutions (e.g. in GA) and the the infeasible infeasible solutions are discarded discarded.. Only in the lane allocation allocation problem by Zhang and Gao (2007), (2007), were the the out out of bound bound lane allocations allocations resulting resulting from the solution solution update update by PSO repaired. repaired. For For MND MNDP, P, vario various us meta metahe heur urist istics ics such such as as SA, SA, TS, TS, GA and and SS SS have been been used used to solve the the problems. problems. Signal timing timing constrain constraints ts are sometimes imposed in problems with signal setting decisions (e.g. Ca Cant ntar arel ella la et al al., ., 20 2006 06;; Ga Gall llo o et al al., ., 20 2010 10). ). Signal timings timings are are obtained before solving the lower level model for each network design scenario. 4.2. Solution techniques techniques to the Transit Network Design Design Problem and the Transit Network Design and Frequency Frequency Setting Problem (TNDP (TNDP and TNDFSP) As in DNDP DNDP and and MND MNDP, P, the the NP-h NP-hard ard natu nature re of of TNDF TNDFSP SP and and TNDP requires requires developing developing innovative innovative solution solution methods methods to get nearly optimal optimal solutions solutions efficiently for practical sized problems problems.. For this reason, reason, heuristics heuristics and metaheuristics metaheuristics were always always used and sometimes parallel computing computing strate strategi gie es were were incorpo incorporate rated d (e.g. Ag Agra raw wal an and d Mat ath hew ew,, 20 200 04; Yu et al al., ., 20 2005 05;; Ya Yang ng et al al., ., 2007 20 07;; Ci Cipr prian ianii et al. al.,, 20 2012 12), ), although not many studies were found to apply parallel parallel computing computing strategies. They usually include include methods to generate candidate routes using using heuristic algorithms and to define the configu configuration ration of routes using heuristics heuristics or metaheurismetaheuristics (e.g. Cha Chakro krobor borty ty and and Dwived Dwivedi, i, 200 2002; 2; Zha Zhao o and Zeng Zeng,, 200 2006; 6; Patt Pa ttna naik ik et al al., ., 19 1998 98;; Bi Biel elli li et et al al., ., 20 2002 02;; To Tom m and and Moh ohan an,, 20 2003 03;; Agrawal Agraw al and Math Mathew, ew, 2004; Lee and and Vuchic, Vuchic, 2005; Fan and and MachMachemehl, em ehl, 200 2004; 4; Zha Zhao o and Zeng Zeng,, 200 2007 7). Other methods methods constru construct ct a set of routes and then then try try to improve improve them them usually usually by by metaheu metaheuristics ristics (e.g. Hu et al al., ., 20 2005 05;; Ya Yang ng et al al., ., 20 2007 07;; Mau autt tton one e and and Ur Urqu quha hart rt,, 2009). 2009 ). The genera generation tion of candid candidat ate e routes routes is usually usually done done using using shortest-path-ba shortest-path-based sed algorithm algorithmss which which add add nodes nodes or links to the route, until some some sort sort of defined constraints constraints for route length, length, travel time time or etc. are viola violated ted.. The configu configurati ration on of routes routes is usually usually defined fined by selectin selecting g and and improv improvin ing g the generated generated routes which is accompanied accompanied by line frequency frequency determination determination where where required. Assignmen Assignment of passe asseng nge er dema demand nd valu values es to to the the netw networ ork k is perperform formed ed at at this this stag stage. e. Accor Accordi ding ng to to Kepaptsoglo Kepaptsoglou u an and d Ka Karla rlafti ftiss (2009),, the proced (2009) procedure ure for for route route configur configuratio ation n can be categor categorized ized based on the algorithms algorithms used (such as mathematica mathematicall programm programming, iterative iterative heuristic heuristic procedures, procedures, local search search heuristics, heuristics, or metaheumetaheuristic ristic proced procedure ures), s), and on whethe whetherr freque frequenc ncies ies and routes are determined determined sequentially or simultaneousl simultaneously y. Althou Although gh a large large collec collection tion of metahe metaheu uristic applications applications to these these problem problemss can be found found in the litera literatur ture, e, the applic applicatio ations ns are limited to very few numbers numbers of classical and non-classi non-classical cal metaheurist metaheuristics. ics. Classica Classicall metah metaheu euri rist stic icss such such as GA and and SA are are most prevalent among the other classical and non-classical methods ods such such as as TS and and AC. AC. Amon Among g these these four four meth method ods, s, GA has has the the greatest greatest number number of applications, applications, especially in TNDFSP. TNDFSP. Further Further research on testing the the efficiency and solution solution quality quality of metaheurismetaheuristics that have not been been applied to TNDP and and TNDFSP TNDFSP could be done. There are limited studies that have employed mathematical methods methods for obtaining solutions. solutions. For example, Bussieck (1998) applied a relaxation, relaxation, branch and bound bound method method in combination combination with with commercial commercial solvers solvers to obtain solutions. solutions. Wan and and Lo (20 (2003) 03) used the MIP solver in CPLEX to solve their mixed mixed integer problem. problem. Guan et al al.. (2 (20 006 06)) employed employed a standard standard branch and bound bound method method to 294 R.Z. Farahani Farahani et al./ European European Journal Journal of Operation Operational al Research Research 229 (2013) (2013) 281–302 281–302 solve their problem. Ba Barr rra a et al. (2 (200 007) 7) applied the constraint programming gramming technique technique for their problem. problem. Although Although these solution methods methods are exact, they can normally normally obtain solutions solutions for small networks. 4.3. Solution Solution techniqu techniques es to the Multi-Moda Multi-Modall Network Network Design Problem Problem (MMNDP) Given the the relatively relatively small body body of the literature literature in MMNDP, MMNDP, the solut solution ion techn techniqu iques es pro propo posed sed in in this this field field are few few.. In fact, fact, to the the best of our knowle knowledge dge,, only only Me Mesba sbah h et et al. (20 (2008 08)) obtained exact solutions using simple enumeration for the exclusive lane allocation prob problem lem,, which which belong belong to the first first group group of problem problemss. Almo Almost st all of the studie studiess in the second second and and third grou group p of MMNDP MMNDP,, which which include includess various various combinat combination ionss of UTNDP UTNDP decision decisions, s, develop developed ed metaheuristics metaheuristics to to solve solve the the proble problem. m. This This is becau because se of the the high high complexity arising from the problem structure. The only exception is Sze Szeto to et al. (20 (2010) 10) which applied a generalized generalized reduced gradient gradient method together with the branch and bound algorithm. A wide wide varie variety ty of metahe metaheu uristic risticss suc such h as SA, SA, TS, GA, GA, and and nonnonclassical hybrid hybrid metaheuristics metaheuristics such as as hybrids of SA with PSO, clonal selection algorithms and a harmony search have been proposed to solve solve the problem problems. s. For examp example, le, Miandoabch Miandoabchii et al al.. (2 (20 012 12a, a,b) b) applied SA as an improved improved heuristic heuristic to the new new solutions solutions generate generated d by PSO, PSO, a clonal clonal selection selection algor algorithm ithm and and a harmon harmony y search. search. In other other multi-modal multi-modal network network design design problems, problems, the values values of non-topolog non-topolog-ical decision decision variables, variables, such as signal timings timings or bus line line frequenfrequencies, are determ determine ined d after after a new solution solution is generat generate ed by the metaheuristic metaheuristics. s. In such such pro probl blem emss, the the valu values es of of these these vari variabl ables es are obtained after after solving the lower lower level problem to calculate the value value of the objective objective function function (e.g. Cantarella and Vitetta, 2006 20 06;; Be Beltr ltran an et al. al.,, 20 2009 09). ). Howeve Howeverr, parallel computin computing g strategies have not been implemented. implemented. 4.4. Solution Solution techniques techniques to lower-lev lower-level el problems problems The lower-le lower-level vel problem problemss in RNDP are always always in the form form of of a pure traffic traffic assignment assignment problem. problem. The most most prevalent prevalent forms forms of traffic assignment assignment in these problems problems are the DUE assignment assignment with SUE SUE and AON assignme assignments nts as the other forms. forms. These lower lower level problems are often solved many times in some solution methods such as metahe metaheuri urist stics, ics, and hence hence the computati computation on burden burden of the overoverall solution method method can be due to solving these these problems problems too often. The most common common method method to solve DUE assignmen assignmentt in the literature is the convex-com convex-combinat bination ion method (the Frank and Wolfe (1956) method) method) and its variants. variants. A few different different solution methods methods can also also be found, found, such as as the method method of successive averages averages based on the flow averaging averaging proposed proposed by Powell and and Sheffi (1982) (1982),, orcost orcost averaging proposed by Cantarell Cantarella a et al. (2006). The most most common common algorithm algorithm applied applied in the literature literature to solve the the SUE problem problem is is the Method Method of Successive Averages Averages (MSA) (e.g. Che Chen n and Alfa, Alfa, 199 1991; 1; Zhan Zh ang g and and Gao, Gao, 20 2007 07;; Ga Gall llo o et al al., ., 20 2010 10;; Lo Long ng et et al al., ., 20 2010 10)) base based d on flow flow aver averag agin ing. g. Transit assignment assignment in TNDP and TNDFSP TNDFSP is mostly based on on uncongested uncongested transit transit assignment assignment which is considered considered as constraints constraints of math mathem emat atica icall mode models ls (if any) any) or in comp comput utati ation on steps steps of the the algor algorith ithms ms.. In such such assig assignm nmen entt problem problems, s, concep concepts ts of shor shorte test st path assignment assignment are used. Transit assignment assignment models models with the hyperpath concept of Spiess of  Spiess and Florian (1989) are absent absent in TNDP and can can scarcely scarcely be be found found in TNDFSP TNDFSP.. For instan instance, ce, Cip Ciprian rianii et al. (2012) solved a TNDFSP TNDFSP considering considering the concept of the hyperpath; hyperpath; although although they did not note how to solve the transit assignment assignment model, model, it is believed that they adopted adopted Spiess Spiess and and Florian’ Florian’ solution solution strategy. In MMNDP, MMNDP, the modal-sp modal-split lit and trip assignme assignment nt problem problem is solved using various approaches. Some have used simulation soft- ware packages packages such as NETSIM NETSIM (S (Seo et al. l.,, 2005) and and VISS VISSIM IM (El Elsh shafe afei, i, 20 2006 06)) to solve solve the the lower-l lower-leve evell proble problem, m, whilst whilst others others have considered mode split and assignment in separate steps. Cantarella and Vitetta (2006) solved the mode mode split split problem, problem, then equilibrium equilibrium traffic traffic assignm assignment ent and and conside considered red fixed fixed travel travel times times for a transit network. network. Me Mesba sbah h et al. (2 (200 008) 8) solved the mode split problem problem,, traffic traffic assignm assignment ent and and transi transitt assignm assignment ent in in iterativ iterative e steps until convergence convergence was was met, met, and Be Beltr ltran an et al. (2 (200 009) 9) solved the mode split and equilibrium equilibrium traffic and transit transit assignment assignment probproblems in two iteration iterations. s. Transit assignment assignment was was solved using the hyperpath hyperpath approach. approach. Moreover, Moreover, some studies studies used used logit formula formula for mode split, and then solved the assignment problems for one or all modes. The others others considered the the joint mode split and traffic traffic assignment problem. Li an and d Ju Ju (2 (200 009) 9) proposed proposed a heuristic heuristic algoalgorithm rithm,, and and Miandoabch Miandoabchii et al al.. (2 (201 012a 2a,b ,b)) used the diagonalization diagonalization algorithm algorithm to solve their joint joint problem. 4.5. Conclusion Conclusionss for soluti solution on techni techniques ques to UTNDP UTNDP From the investigation investigatio n of solut solution ion techn techniqu iques, es, many many con conclu clu-sions sions on metah metaheur euristic isticss can be drawn drawn.. For example example,, it can be conconcluded that most metaheuristic metaheuristic tech techni niqu ques es developed developed for UTNDP UTNDP belong to the category category of classic metaheu metaheurist ristics. ics. Althou Although gh a numnumber of studies attempted attempted to use some some newer newer techniqu techniques, es, none none of  them have explored the application of the more recent metaheuristics in UTNDP. UTNDP. Furthe Furthermo rmore, re, even even though though some version versionss of hybrid hybrid metaheuristics metaheuristics have been proposed proposed for many many other problems, problems, no such applications applications are are present present in CNDP, CNDP, and only only one one such study can be found found for for TNDFSP TNDFSP.. Anothe Anotherr point point is that that most most propos proposed ed metaheurist metaheuristics ics in UTNDP UTNDP are are of the conve conventi ntiona onall type, type, and very very few of them have have used parallelizi parallelizing strateg strategie iess to improv improve e the comcomputational putational efficiency. efficiency. Similarly Similarly,, multi-objectiv multi-objective e type metaheu metaheurisristics are rarely used in UTNDP UTNDP and most studies studies have used the conventional conventional weighted-sum weighted-sum approa approach ch to to obtain obtain a single single objec objective tive function and then applied single objective type metaheuristics to obtain solution solutions. s. Another Another observation observation from the the literature literature is that the branch and bound algorithm and metaheuristics metaheurist ics have been used separately separately from each other other and no attempt attempt has been made to combine combine them. them. Finally, the above above discussions discussions suggest suggest that most efforts to solve UNTDP are directed towards towards metaheuristic methmethods and little attention has been devoted to non-metaheuristics. non-metaheuristics. In additio addition, n, two point pointss can be address addressed ed concern concerning ing solut solution ion techniques techniques for the lower-level lower-level problem problem.. One point point is that the the studies that used SUE or transit assignment assignment mostly mostly rely on the method method of successive averages, averages, which is not fast enough enough to solve such such probproblems. Another Another point is that nearly all studies studies have used the convenconventional tional algorit algorithm hm to to solve solve the lower lower level level proble problem, m, which which is the most important important source of computationa computationall effort. effort. No study has attempted tempted to speed up up the solution solution process of lower level problem problemss using other approaches, other than solving every single lower level problem. Lastly, Lastly, we find that that that that descent descent search search method methods, s, such as SAB which are prevalen prevalentt in RNDP, RNDP, have not been used in TNDSP TNDSP and and MMNDP. MMNDP. This observati observation on together together with conclusions for metaheumetaheuristics and solution methods for the lower-level problem give us hints for future research directions. 5. Applicatio Application ns in real-world real-world case studies studies In this section, section, some real-world real-world case studies in the literature literature of  UTNDP UTNDP are reviewed. reviewed. The aim is to provide provide information information about about real real world examples examples solved in the studies and give insight insight about the size of the netwo networks rks for each each proble problem m catalog catalogues ues to be handled handled in the future future.. As UTNDP UTNDP is a practica practicall prob problem lem,, some some studi studies es have have applied their developed developed models models to design realistic realistic city networks networks.. R.Z. Farahani Farahani et al./ European European Journa Journall of Operatio Operational nal Research Research 229 (2013) (2013) 281–302 281–302 Table 7 summarizes summarizes the real world networks studied in RNDP publication lications. s. The city names, names, countr countries ies,, and and numb numbers ers of node nodess and and links of the network networkss are reported reported if they are are present present in the publipublications. Tab Tables les 8 and 9 summarize real-world real-world case studi studies es of TNDP, TNDP, TNDFS TNDFSP, P, and MMN MMNDP, DP, includi including ng city city names, names, countr countries, ies, and attri attri-butes of the basic network network of infrastructures infrastructures for for designing designing public public transit transit netwo networks. rks. As we can see, see, the size size of the netwo network rk varies varies substantially from study to study even under under the same problem catalogue, logue, probably probably because the scope scope of the study varies varies from one one to another. another. Some require more nodes to cover more locations locations or larger areas areas but some some do not. When When we compar compare ed the num number ber of of papers papers with with case case studies studies with those without without as shown in Tables 1–6, 1–6, we can can con concl clu ude that that most most of UTNDP UTNDP paper paperss do not includ include e a case study study.. Eighteen Eighteen out of 47 studies studies for transit transit netwo networks rks review reviewed ed in in this this paper paper have solved solved real world world cases. The case studies studies in RNDP are are fewer 295 than than that that in TNDP TNDP and and TNDFSP TNDFSP,, and only only six six out out of 51 studies studies cited here have reported reported case case studies. studies. CNDP, CNDP, with 29 cited studies, constit constitute utess a major major part part of of RNDP RNDP literatu literature, re, but only only one one rerecent cent cas case e stud study y can can be foun found d in this this cat categ egor ory. y. This This is is a good good indication indication of the non-practica non-practicality lity of continuous continuous street expansion expansion decisions. decisions. For For DND DNDP, P, thre three e out out of 17 stud studie iess h hav ave e use used d rea reall world problems problems and this this is limited to DNDP with only only strategic strategic decisions. decisions. For For MND MNDP, P, two two out out of five five stud studie iess h hav ave e cite cited d rea reall problems, problems, in which which the the decis decision ionss are traffi traffic c light light sett setting ingss and street orientations. orientations. Again, continuous continuous street expansion expansion decisions decisions with case study application applicationss are abs absen entt in MNDP MNDP.. Fina Finally lly for for MMND MMNDP, P, four four out of nin nine e studies studies have have reported reported case case studies. studies. We believe believe that that most most of the studies studies do not include include a case study study because because their their focu focuses ses may may be be on develop developing ing efficien efficientt solutio solution n methods methods for practical practical problems problems and the authors authors have no real data data to show show the applica application tionss of the meth method. od.  Table 7 A summary summary of case studies studies in RNDP. Proble Problem m Refere Referenc nces es City, City, count country ry No. No. of nodes nodes No. No. of links links No. No. of OD pairs pairs CNDP (continuous) Mathew and Shrama (2009) Pune, India 273 1131 4083 DNDP (discrete) Steenbrink (1974b) Chen and Alfa (1991) Poorzahedy and Rouhani (2007) Part of the Netherlands Road Network Winnipeg, Canada Mashhad, I.R. Iran Not reported 41 1298 73 1726 23 Not reported Cantarella Cant arella et al. (20 (2006) 06) Barcellona Pozzo di Gotto, Italy Villa San Giovanni, It I taly Melito Porto Salvo, It I taly Benevento, Benevento, Italy 176 88 96 104 510 225 189 175 650 380 342 1260 MNDP (mixed) Gallo Gal lo et al. (20 (2010 10))  Table 8 A summary summary of case studi studies es in TNDP and and TNDFSP. TNDFSP. Problem References City, country Size of the basic network TNDP (transit network) Mandl (1980) Zhao and Zeng (2006) Swiss Swiss Network Network Miami-Dade Miami-Dade County, County, USA Yu et al al.. (2 (200 005) 5) an and d Yang Yang et et al al.. (2 (200 007) 7) Guan Gu an et al. (20 (2006) 06) Mauttone and Urquhart (2009) Curtin and Biba (2011) Dalian, China The Hong Kong Mass Transit Railway, Railway, Chin China a Rivera, Uruguay Richardso Richardson, n, TX, USA 14 nodes nodes and 20 links links 4300 street segments, 2804 nodes and 120,000 OD pairs 3200 links, 2300 nodes and 1500 bus stops 9 nodes nodes and 36 OD pairs pairs Dubois Dub ois et al. (19 (1979) 79) Ten towns towns in France France Shih et al. (19 Shih (1998 98)) and Baaj and Mahmassani (1995) Carrese and Gori Gori (2004) and Cipriani et al al.. (2 (201 012) 2) Pattnaik Patt naik et al. (19 (1998) 98) Bielli Bie lli et al. (20 (2002 02)) Austin, USA For town town of Niece: Niece: 700 nodes, nodes, 250 zones zones and 5400 5400 links. No data provided for the all all towns 177 bus stops Rome, Italy 1300 nodes and 7000 unidirectional links A part part of Madra Madras, s, India India Parma, Parma, Italy Agrawal and Mathew (2004) Hu et al al.. (2 (200 005) 5) Zhao (2006) New Delhi, India Changch Changchun, un, Chin China a The Hong Kong Mass Transit Railway, Railway, Chin China a Miami-Dade Miami-Dade County, County, USA 25 nodes nodes and 35 links links 459 bus stops stops + A network network of 99 centroid centroidss and 685 pedestrian nodes 1332 bus stops with 4076 links No data provided provided for number number of bus stops stops or railway railway stations Pacheco et al. (200 Pacheco (2009) 9) Szeto and Wu (2011) Burgos, Spain Tin Shui Wai, Hong Hong Kong, Kong, Chin China a TNDFSP (transit network and and frequency) 84 nodes and 143 links not reported reported 4300 street segments, and 2804 nodes 120,000 OD pairs 382 bus stops 23 nodes nodes (zones), (zones), and 28 bus stops stops  Table 9 A summary summary on case studies studies in MMNDP. References City, country Network attributes Seo et al. (20 (2005 05)) Elshafei (2006) Cantarella and Vitetta (2006) Beltran Belt ran et al. (200 (2009) 9) Gallo Gal lo et al. (20 (2011 11)) Two arterial roads in Seoul, South Korea A single single roadway roadway in Washing Washington, ton, USA Crotone, Crotone, Italy Rome, Italy Campani Campania, a, Italy – – 254 nodes, nodes, 449 links, links, 21 origins origins and 21 destinati destinations ons 1300 nodes and 7000 unidirectional unidirectional links 262 road nodes, nodes, 43 rail nodes, nodes, 764 road links, links, 98 rail links, links, and 91 centroid centroidss 296 R.Z. Farahani Farahani et al./ European European Journal Journal of Operation Operational al Research Research 229 (2013) (2013) 281–302 281–302 6. An overvi overview ew to to the lite literat ratur ure e of UTNDP NDP The literature literature of UTNDP UTNDP can be dated back back to the second second decade of the 20th 20th centur century, y, when when moder modern n cities cities started started to emerg emerge e and their design issues and the related complexities complexities gradua gradually lly grew grew over time. time. RNDP proposed proposed in the 1970s 1970s and 1980s focused focused on both continuous and discrete decisions for street expansion or construction. tion. The comp complexi lexity ty of the bi-lev bi-level el model model led to the use use of the SO concept concept in in the desig design n model model,, resultin resulting g in a single single level level model. model. The resultant resultant model was solved by branch and bound bound methods methods and heuristics heuristics that did not not rely on derivatives. derivatives. In the 1970s 1970s both DNDP DNDP and CNDP were researched, but later CNDP became more more common since since it was was easier easier to to solve solve.. In the the 1980s 1980s,, follo followi wing ng the the tren trend d in using derivative based heuristic methods and their applicability applicability to bi-leve bi-levell mode models, ls, the use of the SO concept concept in CNDP CNDP and DNDP DNDP became nearly nearly abandoned abandoned and the concept of DUE was incorpoincorporated into into CNDP CNDP and and DNDP. DNDP. In the 1990s 1990s the orientati orientatio on of oneway streets was proposed which further increased the complexity of DNDP DNDP.. This This led led to the the use of of newl newly y emer emergi ging ng met metah aheu euris risttic meth method odss at that that time time,, such such as SA. SA. On the the other other hand hand,, the the studie studiess of CNDP commonly commonly used used descent descent search methods methods and and SA to obtain solutions. The availability availability of various various metaheuristics metaheuristics and the development development of comput computing ing technol technology ogy in the 2000s 2000s resulted resulted in an increase increased d number number of DNDP DNDP with variant variant decisions which which was solved by metaheuristic metaheuristics. s. In the the late late 200 2000s 0s,, lane lane allo alloca cati tion on in twotwo-wa way y streets and turning turning restrictions restrictions at intersect intersections ions were proposed as new decisions. decisions. Heuristic Heuristic methods methods were not applied for solving solving DNDP in the 2000s 2000s except for a new street street construction construction problem problem which possessed possessed speci specific fic attri attribu butes tes that that made made it possi possible ble to be solved solved by such a method method.. Also, Also, a branch branch and bound bound method method was used for solving the turning restriction restrictio n design design probl problem, em, which which belongs to DNDP. DNDP. Inclusion Inclusion of movement movement direction decisions decisions such as street orientation orientation leads to new problem problemss and applicati applications ons of metametaheuristics. heuristics. SUE traffic traffic assignment assignment was used in the lower level level problem of DNDP DNDP in a limited limited number number of of studies studies since since it increase increased d the the computation computation complexity complexity of of the bi-level bi-level problem problem by introducing introducing more paths paths than DUE DUE traffic assignment assignment.. SUE SUE traffi traffic c assig assignm nmen entt has been considered considered in three studies studies in the late 2000s 2000s which used metaheuristics metaheuristics to determine determine the solutions. solutions. A separate separate line line of of RNDP RNDP was was proposed proposed in 2000s 2000s based based on decidecision-making sion-making over a time horizon. horizon. This line does not not restrict the choice of design variables variables but increases the complexity complexity of the problem since the user equilibrium equilibrium problem in each time time period have have to be considered considered simultaneous simultaneously ly.. The first study of MNDP MNDP was was proposed proposed in the 1990s, 1990s, while it was not studied until until the mid-2000s. mid-2000s. These studies used various combinations binations of decisions decisions and nearly nearly all of of them were solved solved by metaheuristics heuristics because of their high high degree degree of complexity. complexity. Unlike RNDP, RNDP, TNDP and and TNDFSP TNDFSP have have such a high complexi complexity ty that exact methods methods or local search heuristics heuristics have rarely been applied to them. them. These problems problems have have been studied since since the 1920s. Research Researchers ers seem seem to be more more intere interested sted in in TNDFS TNDFSP P than than TNDP, TNDP, probably probably because transit transit network network configuratio configuration n with a frequency frequency setting setting is more more reali realistic stic.. The numbe numberr of of TNDFSP TNDFSP studied studied in the 2000s 2000s is almost almost 1.6 times times of that that of of TNDP. TNDP. The develop developme ment nt of  computing technology in recent years have facilitated the application of advanced advanced computing computing strategies strategies such as parallelized parallelized comcomputing puting in in metahe metaheuri uristic stics, s, and a number number of of recent recent studi studies es of TNDP TNDP and TNDFSP TNDFSP have have deployed them them to develop develop more efficient efficient solution methods. MMNDP was studied after the mid-2000s mid-2000 s and all of them them used used some some form of modalmodal-spli splitt traffic traffic assignm assignment ent in in the lower lower level level model. model. There are three three main main groups groups of studies and the the first group is related to exclusive exclusive bus lanes. Although Although exclusive exclusive bus lanes lanes have have been used since the 1930s, this problem had not not been studied thoroughly oughly until the 2000s. All exclusive bus lane allocation problems problems were studied studied as MMNDP. MMNDP. The researchers researchers have used scenario scenario comparisons parisons to determine determine solutions solutions or developed developed a model model that utilized utilized the enumeration method. The second group encompasses the studies that that only only focus focus on transit network network design design decisions. decisions. All of the studies studies in this this group group use use the total total trave travell time, time, or total total costs costs as the single objective objective function function of their problems problems.. The third third group group covers studies that simultaneously simultaneously consider various strategic and tactical decisions decisions of UTNDP. UTNDP. The inclusion inclusion of various various combinati combinations ons of road and public transit transit network network decisions decisions led to the considerconsideration of of various various criteria for the users of of both networks networks and for the the comm commun unity ity in the the secon second d grou group. p. For For this this reaso reason, n, all of  of  MMND MMNDPs Ps in the third third group group are are multimulti-obje objectiv ctive. e. Also, Also, due to the high complexity complexity of the above problems, problems, only metaheurist metaheuristic ic methods have been applied. In conclus conclusion ion,, the develop developmen mentt trends trends in UTNDP UTNDP are are related related to the development development of comput computer er technol technology ogy,, the cumula cumulative tive knowl knowl-edge on the solution solution methods methods and travel behav behavior, ior, and the hot policies icies topic topical al at the the time. time. In the the past, past, comp comput uter er techn technolo olog gy was limited so big problem problemss could not be be solved quickly or exactly by a compu computer ter.. Ther Therefo efore re,, to solve solve for for solut solution ionss at that that time time,, high highly ly simplifi simplified ed design design probl problems ems were were cons consider idered. ed. Very Very often, often, linear linear functions and continuous continuous variabl variables es were used used as an approx approxima imattion of the nonline nonlinear ar and and discrete discrete variables variables and a single-le single-level vel transit network network design problem was was studied with the consideration consideration of a simplifi simplified ed passeng passenge er choice choice behav behavior. ior. With With the deve developm lopmen entt of  new solution solution methods, methods, such as the branch branch and cut cut method method and metaheuristics, metaheuristics, and the the advance advance of computer computer technolog technology, y, more design problems including integer decision variables could be solved efficiently efficiently for at least nearly nearly optimal optimal solutions, solutions, and the approxim approximaation of continuous continuous variables variables by by discrete variables variables may not be be necessarily essarily.. Moreov Moreover, er, the problem problem to be solved solved becam became e bigger bigger and and bigger, and more more design decisions decisions can simultaneous simultaneously ly be incorpoincorporated into the design problem. As time time goes, goes, more more underst understand andin ing g on trav travel el beha behavio viorr is obobtained and more realistic travel behavior was included in the lower level problem. problem. Hence, the design problems problems became more more complicomplicated but but could still be solved efficiently efficiently due to the improve improvement ment in computer computer technology technology and solution methods. methods. Furthermor Furthermore, e, hot policy discussion discussion in the past past led to new design problems problems or at least new objective functions and constraints. constraints. From the above above discusdiscussion, it seems that the existing existing network network design design studies studies try to find a balance between between the computer computer technology technology available, cumulative cumulative knowledge knowledge on the solution methods methods and travel behavior, behavior, and the hot policy topic topic at that time. time. 7. Out Outloo look k After reviewing reviewing the major publications publications of UTNDP, UTNDP, we realized that there are some gaps in the literature which need more studies. This section proposes proposes future future directions directions that are believed believed to be able to lead to essential essential improvem improvements ents over over the the existing existing literature, literature, because the suggested suggested directions directions are related to two major major needs: first, first, the need need to define define problem problemss that are are more more realistic realistic in terms terms of policy policy (or design) design) require requiremen mentt and traveler travelers’ s’ behavio behavior; r; and secsecond, the need for more more efficient solution solution methods methods after taking into into account the development and the limitations limitatio ns of comp comput utin ing g tech tech-nology, nology, and the applicability applicability of of solution methods methods in practice. We have categorized categorized our future future suggestions suggestions for each each problem problem type and for solution methods methods separately. This categorization categorization reflects flects the three three axes axes of of UTNDP, UTNDP, namely namely policy policy discus discussion sionss in the upper level problem problemss (problem (problem approach, approach, decision types, objective objective functions, functions, etc.), and lower lower level problems problems and solution solution methods methods R.Z. Farahani Farahani et al./ European European Journa Journall of Operatio Operational nal Research Research 229 (2013) (2013) 281–302 281–302 (for the whole whole problem and for lower lower level problems). problems). The future future research suggestions are summarized in Table 10 and elaborated in Sections Sections 7.1–7.4.  7.1. Future research for Road Road Network Design Design Problem (RNDP) 7.1.1. Objective functions functions and constraints constraints   Most studies of CNDP and DNDP have only one objective and very very often the the objective objective is related related to travel travel time. time. This implie impliess that that much much empha emphasis sis is on conges congestion tion.. Moreov Moreove er, ther there e is is only only one research research in MNDP MNDP (Cantarell (Cantarella a an and d Vitet Vitetta, ta, 20 2006 06)) that that conconsiders CO emissions emissions minimiza minimization as one of the proble problem m objecobjective functions. functions. Environmen Environmental tal objectives objectives should should be considered considered in these problems since there are usually usually tradeoffs between difdifferent objectives and the environmental environm ental impact impact and this is one of the the hot hot topic topicss of today today.. Optim Optimizi izing ng one one obje objecti ctive ve is at the the expense expense of others. others. Moreo Moreover ver,, the impact impact of emissio emissions ns on health health and global warming has been received recent attention. attention. Henc Hence, e, more studies studies of RNDP with with environmenta environmentall concerns can be proposed and studied studied in the future. future.  297 Minimization Minimization of total travel time/cost is the most prevalent prevalent form of objective objective function function in RNDPs. RNDPs. This objective accounts accounts for the aggregate aggregate network network congestion congestion,, and this this may may lead to unbalanc unbalanced ed congestion levels throughout the network and hence some OD pairs can be benefit more than the the others others in terms of travel time. time. Using equity measures in the objective function can ensure more that equitable equitable benefit benefit is introduce introduced d to each each OD OD pair pair.. Most studies studies in RNDP only only consider consider travel travel times in street segsegments, and ignore ignore the delays delays incurred incurred at intersections intersections (e.g. (e.g. signalized or priority priority related related intersection intersections). s). Interse Intersectio ction n delays delays may significantly significantly contribute contribute to the trip time and inclusion inclusion of  intersection intersection delays delays in the objective objective function function can lead to more realistic travel travel times. However, However, there are only only few related studstudies in DNDP and MNDP. MNDP. For example, example, Lee and Yang (1994) considered intersection delay for the street orientation network design problem; Can anta tare rell lla a et al al.. (2 (200 006) 6) an and d Gal allo lo et al al.. (2010) included included signal setting in the network network design decisions. Intersection Intersecti on delays can be included included in other CNDPs CNDPs and DNDPs. DNDPs. Nearly all RNDPs have adopted determinist deterministic ic modeling. However, travel demands demands or link capacities capacities are are stochastic stochastic in nature. nature. Robustness Robustness and reliability reliability in transportation transportation network networkss have thus  Table 10 Summary of future research research directions for the UTNDP. Problem/solution Problem/solution techniques Subject category Possible extension Road Ne Network De Design Pr Problem (RNDP) Objective functions and constraints Using environmental environmental related objective functions such as pollutions with traditional traditional objective functions functions (for all RNDPs) RNDPs) Using objective functions functions that consider equity equity (for all RNDPs) Including delays incurred in intersections in the travel times (for Continuous Continuous and Discrete NDPs) Using reliability reliability and robustness concepts in objective functions functions or in the constraints constraints (for all RNDPs) RNDPs) Considering operational decisions such as signal setting together with network topology decisions Considering elastic demand (for Discrete NDPs) Using the SUE assignment problem problem (for Continuous Continuous NDPs) Using multiclass user equilibrium assignment assignment problems Using dynamic dynamic traffic traffic assignment problems (for all RNDPs) RNDPs) Decisions Demand Lower-level problem Transit Network Design Problem Problem (TNDP) (TNDP) and Transit Network Design and Frequency Setting Problem (TNDFSP) Multi-Mo Multi-Modal dal Network Network Design Design Problem Problem (MMNDP (MMNDP)) Objective functions Decisions Lower-level problem Decision Decisionss Multi-modality Multi-modality Inter-modal connectivity Lower-level problem Solution techniques Metaheuristics Hybrid methods and nonmetaheuristics Lower-level problem solution methods Using environmental environmental related related objective objective functions functions such as pollutions with traditional objective functions functions (for all problems) problems) Using the time dependent design approach (for both problems) Adopting more more realistic passenger behaviors that consider consider the effects of advanced passenger information information system, system, real time transit transit information, information, and seat availability availability Using Using the time-dep time-depende endent nt design approach approach (for problem problemss with strategic strategic decision decisions) s) Including fixed public transit networks with no effects on private vehicle flows, considering elastic demands and the related objective functions for each mode (for RNDPs) Including a fixed bus network network on the existing road road network that share the the roads with private vehicle, considering the rest restrictions rictions on road network network improvement improvement decisions and using elastic demands and the related objective functions for each mode (for RNDPs) Defining new combinations combinations of multi-modal multi-modal decisions to define MMNDPs MMNDPs Considering inter-modal inter-modal connection connection issue in combined mode trips (e.g. bus + metro networks, networks, road + metro metro networks) networks) Modeling travel behavior in dynamic multi-modal multi-modal networks networks Using recently proposed metaheuristics metaheuristics and comparing their performance with genetic algorithm. Using various hybrids of recent and conventional conventional metaheuristics Using parallelizing and and distributed computing computing to enhance the efficiency efficiency of  metaheuristics For multi-objective multi-objective problems, developing metaheuristics metaheuristics that use Pareto frontier in the solution process rather than those relying on the weighted sum objective objective functions Incorporating SAB heuristic into TNDSP and MMNDP Using hybrids hybrids of of BB method and metaheuristics metaheuristics Developing heuristic methods for problems with discrete decisions Using self-regulated method method to solve SUE or transit assignment assignment problems Using approximation approximation schemes such such as neural networks networks to solve traffic assignment problems 298 R.Z. Farahani Farahani et al./ European European Journal Journal of Operation Operational al Research Research 229 (2013) (2013) 281–302 281–302 drawn attention. attention. Nevertheles Nevertheless, s, up to now now, only only a few few stu studies dies have incorporated these dimensions dimensio ns in UTND UTNDPs Ps.. For For exam exampl ple, e, Ukku Uk kusur surii et et al. (20 (2007 07)) considered considered robustness robustness in the objective objective function, function, and Dim Dimitri itriou ou et al. (20 (2008b 08b)) developed developed CNDP with tratravel time reliability constraints. constraints. These These two two concept conceptss can be adopted adopted for other problems problems in RNDP. RNDP. 7.2.2. 7.2.2. Decisions Decisions  7.1.2. 7.1.2. Decisions Decisions  As shown in this review, review, network network topology topology decisions decisions are seldom considered considered with operation operational al decisions such as as signal setting setting simultaneously. simultaneously. Indeed, Indeed, traffic traffic signal signal setting setting has has the strong strongest est relevancy relevancy with network network configu configuration ration decisions, decisions, as the network network topology topology directly affects affects the flow pattern and and the conflict points at inte interse rsecti ction ons. s. Althoug Although h traffic traffic signal signal settin setting g proble problem m has has been studied studied extensivel extensively y and it has a relatively relatively large body body of literature (e.g. Cantarell Cantarella a et al al., ., 19 1991 91;; Men eneg eguz uzze zerr, 19 199 95; Wong and an d Ya Yang ng,, 19 1999 99;; Wey ey,, 20 2000 00;; Ca Casc scet etta ta et al al., ., 20 2006 06), ), not not man many y network design papers considered both signal setting and network work topolog topology y decision decisions. s. Hence, Hence, more more work work could could be done done in this direction in the future. future. Similar conclusions conclusions can can be be applied to other operationa operationall decisions such as road pricing and and scheduling of of repairs repairs of urban urban streets streets.. 7.1.3. 7.1.3. Demand Demand  For DND DNDP, P, elastic elastic demand demand can can be studied studied in the futur future e given given that that no studi studies es can can be foun found d on this this so far. far. 7.2.3. Lower-level problems    Although Although the SUE problem problem has been used in several DNDPs, DNDPs, its appl applicat ication ion in CNDPs CNDPs is is limited limited to only only a very very few few studi studies es (e.g. Dav avis is,, 19 1994 94;; Lo Lon ng et al al., ., 20 2010 10). ). Its Its applica applicatio tion n in CNDP CNDPss can prov provide ide more more reali realistic stic beha behavio viorr of the users users in in these these problems. Almost all user equilibrium problems consider only single class users. users. While While multiclas multiclass-user s-user equilibrium problems have been discussed in many studies, they have been rarely applied in RNDP RNDPs. s. The The inclu inclusio sion n of of multi multipl ple e use userr class classes es is is a possi possible ble extension. All RNDPs RNDPs in this this review review conside considered red traffi traffic c assignm assignment ent or its time-dependent time-dependent extens extension ion in the lower lower level level problem. problem. These These traffic assignment assignment problem problemss assume assume that the traffic traffic condition condition is in a stea steady dy sta state te in in whic which h the the traf traffic fic cond condit itio ion n doe doess not not vary vary with with time time.. Hence, Hence, they they are not suitable suitable to analyze analyze the traffic traffic conges congestion tion effect effect at the fine-gr fine-grain ained ed tempor temporal al level. level. To exam examin ine e this this effe effect ct,, it is more ore appr approp opri riat ate e to ado adopt Dynamic Dynamic Traffic Traffic Assignment Assignment (DTA). (DTA). This problem problem can provide provide a higher higher degree degree of realism and capture changing changing traffic traffic conditions tions.. It is also also essen essentia tiall for for desig designi ning ng dyna dynami mic c tolls tolls,, since since these these chan change gess due due to traffi traffic c condit condition ions. s. Howe Howeve ver, r, most most of  the existing existing UTNDPs UTNDPs rarely capture capture DTA in the lower lower level problem and very few studies (Ukk (Ukkusu usuri ri and Walle Waller, r, 200 2007 7) did did capt captur ure e it. it. Henc Hence, e, more more rese researc arch h coul could d be done done in this this direction. 7.3.1. 7.3.1. Decisions Decisions  7.2.1. 7.2.1. Objective Objective functions functions  Similar to to RNDP, environmen environmental tal objectives objectives are largely largely ignored ignored in these these problem problems. s. More More focus focus can can be be put on address addressing ing the environmen environmental tal cost in this field. The time-dependent time-dependent approach for MMNDP has not been considered and and could could be a future future exten extension sion for for this this field. field. Howeve However, r, it adds to to the comple complexity xity of of the problem problem.. 7.3.2. 7.3.2. Multi-moda Multi-modallity    7.2. Future research for transit transit network and Transit Transit Network Design Design and Frequency Setting Problem (TNDP (TNDP and TNDFSP) TNDFSP) Most existing studies of TNDP or TNDFSP TNDFSP assume assume simplified simplified passengers’ passengers’ line choice behavior when when designing transit transit routes. This can lead to a single level TNDSP, TNDSP, which is easier to solve but are not too realistic. realistic. For those studies studies with consideratio consideration n of  transit passengers’ passengers’ behavior, behavior, they usually adopt adopt classic assumptions for boardin boarding g and alighting, alighting, and ignore ignore the effect effect of  advanced passenger information information system, real time transit information, mation, and seat seat availability availability on their choice. choice. More realistic paspassenger senger behavio behaviorr should should be capture captured d in this field field in the futur future. e. 7.3. Future research research for Multi-Modal Multi-Modal Network Network Design Design Problem (MMNDP) 7.1.4. Lower-level problems  The time-dependent time-dependent approach approach mentione mentioned d in Section 3.1.3 has not been considere considered d in TNDSP, TNDSP, which also also involves involves long-term, long-term, strategic strategic decisions. decisions. Therefore, Therefore, one future direction could be to develop time-dependent time-dependent models models for TNDP and TNDFSP. TNDFSP. However, this adds adds to the complexity complexity of the problem problem and needs needs fast and efficient efficient solution procedures procedures to handle this. As previously previously mentioned mentioned,, the issue issue of of multimulti-mo modality dality has been largely ignored ignored in road and transit transit network network design problems. problems. In fact, the literature literature of MMNDP MMNDP is very limited, limited, while a number number of  future directions directions are possible possible in this field field by extending extending the the single mode problems problems to include various various forms forms of multi-mo multi-modality. dality. Multi-modalit Multi-modality y with no interact interaction ion betwee between n flows of differen differentt modes. modes. In RNDP, RNDP, public public transit transit modes modes such as buses buses in exclusiv exclusive e lanes, trams, or metro can be be considered considered such such that that they they have have no effects effects on vehicle vehicle flows flows on roads. roads. The dema demand nd shares shares will will vary vary as road networ network k configurati configurations ons change and consequen consequentl tly y disisutility levels of modes modes compare compared d to each each oth other er will will chan change ge.. The existence existence of private private and public public transit modes modes in the probproblem can imply the multi-objective multi-objecti ve natu nature re of the the pro probl blem em because because of the existe existence nce of differen differentt objectiv objectives es that can be be related related to individ individual ual modes modes,, all traveler travelers, s, the commu communi nity ty,, etc. etc. The only two two existing studies studies in this field are Cantarella and Vitetta (2006) for multi-objective multi-objective signal setting and one-way street orientation orientation problem problem with a fixed travel time bus network, network, and Sz Szet eto o et et al. (2 (201 010) 0) for lane additions additions and toll setting. setting. New problem problemss can be propos proposed ed by conside consideri ring ng other road network network improvemen improvementt deci decisi sion ons, s, in the the pre prese senc nce e of of a tram tram or a metro etro network. Such problems may have multiple objective functions (e.g. (e.g. total total user bene benefit, fit, demand demand shar share e of metro metro or tram, tram, air polpollution, lution, etc.). etc.). Multi-modalit Multi-modality y with inter interacti actions ons betwe between en flows flows of differen differentt modes. modes. In an existing existing fixed bus netw network ork that that shares shares the the same same roads with other vehicles, the road network network improvement decisions must take into account account the restrictions restrictions caused by the bus network, network, the changes changes in mode demand demand shares, shares, and both bus bus and non-bus travel times. Different objective functions and various constraints constraints are required required in these problems problems to consider consider multiple multiple performance performance criteria criteria such such as as the dem demand and shar share e of each mode, mode, total total user bene benefit, fit, travel travel cost cost by bus mode mode,, etc. R.Z. Farahani Farahani et al./ European European Journa Journall of Operatio Operational nal Research Research 229 (2013) (2013) 281–302 281–302  Multi-modality Multi-modality with interrelations interrelations betwee between n flows flows of differen differentt modes and and in decisions. decisions. Although Although this this issue has been been recently recently studied by some researchers researchers (e.g. (e.g. Miandoabch Miandoabchii et al., 2012a, b), more new problem problemss can be proposed proposed along along this direction direction.. For example, example, the turn-restric turn-restriction tion problem (Lo (Long ng et et al al., ., 20 2010 10)) has been proposed but the impact impact of turn-restrictions turn-restrictions on transit routes has been been ignored ignored.. One new problem can be to simultasimultaneously design design the turn restrictions and transit routes. Besides, the previous previous studies only only consider changes changes in the routes routes of  existing bus lines between terminal stations. Another extension could be designing designing the whole bus network network in combination combination with various RNDP and MMNDP decisions. decisions.  7.3.3. 7.3.3. Inter-moda Inter-modall connectiv connectivity ity   MMNDP traditional traditionally ly assumes assumes single mode trips trips and ignore the possibility of combined combined mode mode trips such as Park’n’Ride. Comombined mode mode trips trips (i.e. multi-moda multi-modall trip trips) s) resu result lt in the the int inter er-modal connection connection issue. issue. This has been considered considered in the literature for some some operational operational level decisions decisions such as pricing, pricing, but no network network topology topology design problem has has yet considered this. In such problems, problems, an impo import rtan antt issu issue e for for trav travel eler erss is to be able able to transfer transfer convenie convenientl ntly y from from one one mod mode e to to anot anothe herr to to finish finish their trips. trips. This means means that that the network network of of each transit transit mode mode must must be be connec connected ted in the best way to provid provide e an integr integrated ated and connected public transit network. This integration can only become possible under the condition that when designing the transit transit networ network k of one mode mode,, the locati locations ons of transit transit stops stops of  other modes are explicitly considered. Another extension would would be an RNDP RNDP that consid considers ers an existin existing g metro metro networ network k (for carmetro travel) travel) and accounts accounts for the allocation allocation of of parking spaces spaces in the proxim proximity ity of metro metro station stations, s, such that that trave travelers lers can access the metro metro network network by their cars in the most most convenie convenient nt way.  7.3.4. 7.3.4. Lower-lev Lower-level el proble problems ms  In the lower lower level problem problem of MMNDP, MMNDP, only classical classical behavioral behavioral principles principles such as the UE UE principle principle or its extensions extensions were were used, used, and some realistic factors such as the time-varying w waiting aiting time and transfer transfer penalty are rarely rarely considered considered in the behavioral behavioral component component of the formula formulattion. ion. Hence, Hence, one future future directio direction n is to focus focus on on the behavio behavioral ral modeli modeling ng of travele travelers rs in dynami dynamic c multi-modal multi-modal networ networks ks..  7.4.1. 7.4.1. Metaheur Metaheuristics istics The metaheuristics metaheuristics shown in Fig. 2 are actually the classic or well-known metaheuristics metaheuristics that have also been applied applied to other problems. problems. It was observed that genetic genetic algorithm and and simulated annealing are the most prevalent metaheuristics metaheurist ics among the others. Furthermor Furthermore, e, applicat application ionss of a number number of recently recently develdeveloped methods methods such as artificial bee colony, colony, swarm particle optioptimization, mization, harmonic harmonic search, search, and clonal clonal selection algorith algorithm m can be found in some studies. studies. Although Although genetic genetic algorithm algorithm have been been proved to give better better results results than other algorith algorithms ms in several studies, it is not clear clear whether whether other recently recently developed developed metaheuristics heuristics can outperfor outperform m them. them. Instances Instances of such algorithm algorithmss are the the differential differential evolution evolution method, method, firefly algorithm, algorithm, cuckoo search, artificial artificial immune immune systems, systems, and generaliz generalized ed evolutionary evolutionary walk algorithm (Gend (Gendreau reau and Potvin Potvin,, 2010; Koziel and Yang, 2011 20 11;; Ya Yang ng,, 20 2011 11). ). Therefo Therefore, re, one futu future re direct direction ion coul could d be to compare the performance performance of recently recently developed developed heuristics heuristics with with genetic algorithm and the most commonly used algorithms to solve UTNDP. Each metaheuristic metaheuristic has its own strength and each problem has its own own propertie properties. s. It is therefore therefore importan importantt to identify and analyze the problem properties, properties, and develop develop tailor tailored ed solutio solution n methods methods for the problem. problem. Solution Solution methods methods can be develope developed d for new and existing network design problems based on hybrids of differe different nt metah metaheu euristics. ristics. Most hybridization hybridization research in UTNDP has been done with simulated annealing and tabu search with genetic genetic algorithm algorithm and a number number of metaheuristics metaheuristics.. While other possibilities possibilities still still remain remain to hybridize hybridize recently recently developed developed metahe metaheuri uristics stics or to incorpo incorporate rate the the strength strength of varvarious well-known metaheuristics metaheuristics to solve UTNDP. UTNDP. Computation Computational al complex complexity ity of of many classes of UTNDP UTNDP is a major barrier to the efficiency of conventional conventional metaheuristics. metaheuristics. Parallelizing strategies and distributed computing can improve the efficiency but there there are few application applicationss in TNDP and TNDFSP TNDFSP (e.g. Ag Agra rawa wall an and d Mat athe hew, w, 20 2004 04;; Yu et al al., ., 20 2005 05;; Ya Yang ng et al al., ., 2007; 200 7; Cip Ciprian rianii et al., 201 2012 2) and they have never never been considered considered in RNDP RNDP and and MMND MMNDP P to the best best of of our knowle knowledge dge.. Hence, Hence, the incorporation of these considerations into solution algorithms is definitely definitely one future future direction. direction. Most studies studies of TNDSP and and most multi-object multi-objectiive analy analyses ses of  RNDP consider more than one objective but the resultant problems problems are usually formulat formulated ed as a single objective objective problem problem using a weighted weighted sum sum objective objective function. function. This approach approach can actually simplify the problem but we need to predeterm predetermine ine the weight weight for each objective objective function. function. Consequentl Consequently y, this method method precludes precludes some Pareto Pareto solutions. solutions. Alternativel Alternatively y, we can avoid presetting the weight and solve the multi-objective multi-obj ective problem directly using existing multi-objective multi-objecti ve metahe metaheu uristics to determine determine the Pareto frontier frontier and the the modeler can then then determine determine the best solution in the frontier. frontier. This alternative alternative is rarely rarely conside considered red in TNDSP TNDSP and should should be conside considered red in the future. 7.4.2. Hybrid methods and non-metaheuristics non-metaheuristics 7.4. Future research research for solution solution techniques techniques  299   For UTNDP with discrete variables, these were usually solved by metaheuristics metaheuristics or the branch branch and bound method. method. Metaheur Metaheurisistics can give nearly optimal solutions quickly whereas the branch and bound bound method method can be global optimal optimal solutions at the expense expense of comput computati ation on tim time. To make ake a good ood trad tradee-of offf between between solution solution speed speed and and qualit quality, y, a hybrid hybrid of of the branch branch and bound method and metaheurist metaheu ristics ics could could be develop develope ed, where the metaheu metaheuristics ristics are used to find good upper upper and lower lower bounds, bounds, whereas whereas the branch and and bound bound method method is used to check for global optimality. The SAB heuristic heuristic has been used for finding descent directions directions of RNDP but the heuristic has rarely been extended and applied to solve solve TNDSP TNDSP or MMNDP MMNDP with with a bi-leve bi-levell structu structure, re, probab probably ly because there there are few TNDSPs or MMNDPs MMNDPs with a bi-level bi-level structure. Incorporating the SAB heuristic heuristic into TNDSP and MMNDP MMNDP should surely speed up the compu computation tation process and is one potent potential ial resear research ch direct direction ion.. Oth Other er speed speeding ing up up strateg strategie iess should also be considered. considered. As reflect reflected ed in Secti Section on 4.1 4.1,, most most of studies studies of of RNDP RNDP are direc directed ted towards towards finding finding more more efficien efficientt non-m non-metah etaheur euristic istic solution methods for continuous variable problems. There are few studies which have attempted attempted to develop develop efficient non-metahe non-metaheurisuristic solution procedure proceduress to solve discrete discrete variable problems problems.. It seems that that more effort could could be put on developing developing faster faster and better heuristics for RNDP. 300 R.Z. Farahani Farahani et al./ European European Journal Journal of Operation Operational al Research Research 229 (2013) (2013) 281–302 281–302 7.4.3. Solution procedures procedures for lower level problems   When solving the the SUE problem or the transit assignment problem in UTNDP, UTNDP, curren currentt method methodss rely on the meth method od of successuccessive aver average ages, s, which which has has a slow conv converg ergence ence rate. rate. To speed speed up the computation computation process, process, one could employ employ the newly developed self-regulated method proposed by Liu et al. (2 (200 009) 9).. This This method method could be integrated integrated with existing existing solution methods methods for solving bi-level UTNDP. Solving the the lower-level lower-level problem is often the major major source of the comput computatio ational nal burde burden n in UTNDP. UTNDP. This This could be done done by devisdevising faster faster solution solution methods, methods, or by incorporating incorporating approximatio approximation n methods methods such as neural networks networks (see Xiong and Schneider, 1992; 19 92; We Weii an and d Sch Schon onfel feld, d, 19 1993; 93; Do Dong ng an and d Wu Wu,, 20 2003 03;; Ch Chow ow et al al., ., 20 2010 10)) to obtain obtain the travel travel time time or flow values. values.  Acknowledgements  Acknowledgements The authors are grateful to the comments from two anonymous referees. The third author was jointly supported supported by a grant from the Central Policy Unit of the Governmen Governmentt of the Hong Kong Special Administrative Administrative Region Region and and the Resear Research ch Grant Grantss Counci Councill of the Hong Kong Special Administrat Administrative ive Regio Region, n, China China (Pro (Projec jectt No. No. HKU 7026-PPR-12), 7026-PPR-12), a Grant (20090217200 (200902172003) 3) from the Hui Oi Chow Trust Fund and two Grants (201001159008 (201001159008 and 201011159026) 201011159026) from the University Research Committee Committee of the Uni Univer versity sity of Hong Hong Kong. References Abdulaal, Abdulaal, M., LeBlanc, LeBlanc, L.J., 1979. 1979. Continu Continuous ous equilib equilibrium rium netwo network rk design design models. models. Transpor Transportatio tation n Research Research Part B 13 (1), 19–32. 19–32. Agraw Agrawal, al, J., Mathew Mathew,, T.V., T.V., 2004. 2004. Transi Transitt route route design design using using parall parallel el geneti genetic c algorithm algorithm.. Journal Journal of Computi Computing ng in Civil Engin Engineerin eering g 18 (3), 248–25 248–256. 6. Baaj, M.H., M.H., Mahmass Mahmassani, ani, H.S., 1991. 1991. An AI-based AI-based approach approach for transit transit route route system system planning planning and design. design. Journal Journal of Advanced Advanced Transport Transportatio ation n 25 (2), 187–21 187–210. 0. Baaj, M.H., Mahmassani, Mahmassani, H.S., 1995. Hybrid route generation heuristic algorithm for the design design of transit transit networks networks.. Transpor Transportatio tation n Research Research Part Part C 3 (1), 31–50. 31–50. Barra, Barra, A., Carvalho Carvalho,, L., Teypaz, Teypaz, N., Cung, Cung, V.D., V.D., Balassian Balassiano, o, R., 2007. 2007. Solving Solving the transit transit network design design problem with constraint constraint programming. programming. In: Paper Presented at the Proceedin Proceeding g of 11th 11th World Conferen Conference ce on Transpor Transportt Research, Research, pp. 24–28. 24–28. Bellei, Bellei, G., Gentile, Gentile, G., Papola, Papola, N., 2002. 2002. Network Network pricing pricing optimiza optimization tion in multi-u multi-user ser and multimodal multimodal context with elastic demand. demand. Transportation Research Research Part B 36 (9), (9), 779– 779–79 798. 8. Beltra Beltran, n, B., Carres Carrese, e, S., Cipria Cipriani ni,, E., Petrel Petrelli, li, M., M., 2009. 2009. Transi Transitt netwo network rk desig design n with with allocation allocation of green vehicles: vehicles: a genetic genetic algorithm algorithm approach. approach. Transpor Transportatio tation n Research Research Part C 17 (5), 475–48 475–483. 3. Ben-Ayed Ben-Ayed,, O., Boyce, Boyce, D.E., D.E., Blair III, C.E., C.E., 1988. 1988. A general general bilevel bilevel linear linear programm programming ing formulation of the network network design problem. problem. Transportation Transportation Research Part Part B 22 (4), 311–31 311–318. 8. Bielli Bielli,, M., Caram Caramia, ia, M., M., Carote Carotenu nuto, to, P., 2002 2002.. Geneti Genetic c algori algorith thms ms in bus bus netwo network rk optimiza optimization tion.. Transport Transportatio ation n Research Part Part C 10 (1), 19–34. 19–34. Borndörfe Borndörfer, r, R., Grötsche Grötschel, l, M., Pfetsch, Pfetsch, M.E., M.E., 2008. 2008. Models Models for line planning planning in public public tran transp spor ort. t. In: In: Hick Hickma man, n, M., M., Mirc Mircha hand ndan ani, i, P., P., Voß, Voß, S. (Eds (Eds.) .),, Comp Comput uter er-A -Aid ided ed Systems Systems in Public Public Transpor Transport. t. Springer, Springer, Berlin, Berlin, Heidelber Heidelberg, g, pp. 363–37 363–378. 8. Boyce, D.E., 1984. Urban transportation network-equilibrium network-equilibrium and design models: recent achievements achievements and future future prospects. Environment Environment and Planning Planning A 16 (1), 1445–1474. Bussie Bussieck, ck, M.R., M.R., 1998 1998.. Optim Optimal al Lines Lines in Publi Public c Rail Rail Transp Transport ort.. Braun Braunsch schwe weig ig University University of Technolo Technology, gy, Germany. Germany. Cantarell Cantarella, a, G., Vitetta, Vitetta, A., 2006. 2006. The multi-c multi-criteri riteria a road network network design design problem problem in an urban urban area. area. Transport Transportation ation 33 (6), 567–58 567–588. 8. Cant Cantar arel ella la,, G.E. G.E.,, Impr Improt ota, a, G., G., Sforz Sforza, a, A., A., 1991 1991.. Road Road netw networ ork k signa signall sett settin ing: g: equili equilibri brium um conditi condition ons. s. In: Papage Papageorg orgio iou, u, M. (Ed.) (Ed.),, Conc Concise ise Encyclo Encycloped pedia ia of  Traffic Traffic and Transporta Transportation tion Systems. Systems. Pergamo Pergamon n Press, pp. 366–37 366–371. 1. Cantar Cantarell ella, a, G.E., G.E., Pavon Pavone, e, G., Vitett Vitetta, a, A., 2006. 2006. Heuris Heuristic ticss for urba urban n road road netw network ork design: design: lane layout layout and and signal signal settin settings. gs. European European Journal Journal of Operation Operational al Research 175 (3), (3), 1682–1695. 1682–1695. Carrese, Carrese, S., Gori, Gori, S., 2004. 2004. Chapter Chapter 11: an urban urban bus network network design procedur procedure. e. In: Patr Patrik ikss sson on,, M., M., Labb Labbé, é, M. (Eds (Eds.) .),, Tran Transp spor orta tati tion on Pla Plann nnin ing: g: Stat State e of the the Art (Applied (Applied Optimiza Optimization tion). ). Springer, Springer, 64, pp. 177–19 177–196. 6. Casc Cascet etta ta,, E., E., Gall Gallo, o, M., Mont Montel ella la,, B., B., 2006 2006.. Model odelss and and algo algori rith thm ms for for the the optimiza optimization tion of signal signal settin settings gs on on urban urban netwo networks rks with stochasti stochastic c assignment. Annals of Operations Research 144 (1), 301–328. 301–328. Ceder, Ceder, A., 2003. 2003. Chapter Chapter 3: designing designing public public transport transport netwo network rk and routes. routes. In: Lam, Lam, W., Bell, M. (Eds.), (Eds.), Advanced Advanced Modeling Modeling for Transit Transit Operatio Operations ns and Service Service Planning Planning.. Elsevier Elsevier Science Science Ltd. Ltd. Pub., Pub., Pergamo Pergamon n Imprint, Imprint, pp. 59–91. 59–91. Ceder, Ceder, A., Wilson, Wilson, N.H.M., N.H.M., 1986. 1986. Bus network network design. design. Transport Transportatio ation n Research Part B 20 (4), (4), 331– 331–34 344. 4. Chakroborty, Chakroborty, P., 2003. Genetic algorithms algorithms for optimal optimal urban transit network network design.  Journal  Journal of Compute Computerr Aided Civil Civil and Infrastruct Infrastructure ure Enginee Engineering ring 18, 18, 184–20 184–200. 0. Chakroborty, Chakroborty, P., Dwivedi, T., 2002. Optimal route network design for for transit systems using genetic algorithms. Engineering Optimization Optimization 34 (1), 83–100. Chen Chen,, M., M., Alfa Alfa,, A.S. A.S.,, 1991 1991.. A netw networ ork k desi design gn alg algo orith rithm m usi using ng a stoc stocha hast stic ic incremen incremental tal traffic assignmen assignmentt approach. approach. Transport Transportatio ation n Science 25 (3), 215– 215– 224. Chiou, S., 2005. Bilevel programming programming for the continuous continuous transport transport network network design problem. problem. Transpor Transportatio tation n Research Research Part B 39 (4), 361–38 361–383. 3. Chiou, Chiou, S., 2008. 2008. A hybrid hybrid approach approach for for optimal optimal design design of signalized signalized road road network. network. Applied Mathematical Mathematical Modelling Modelling 32 (2), 195–207. 195–207. Chow, Chow, J.Y.J., J.Y.J., Regan, Regan, A.C., Arkhipov Arkhipov,, D.I., 2010. 2010. Faster Faster converg converging ing global global heuri heuristic stic for continuous continuous network network design using radial basis functions. functions. Transportation Transportation Research Record 2196, 2196, 102–110. 102–110. Cipr Cipria iani ni,, E., E., Fusc Fusco, o, G., G., Petr Petrel elli li,, M., M., 2006 2006.. A mult multim imod odal al trans transit it netw networ ork k desig design n procedur procedure e for urban urban areas. areas. Journal Journal of Advances Advances in in Transpor Transportatio tation n Studies, Studies, Section Section A 10, 5–20. 5–20. Cipria Cipriani, ni, E., Gori, Gori, S., Petrel Petrelli, li, M., M., 2012. 2012. Transi Transitt network network desig design: n: a proced procedure ure and and an applicati application on to a large urban urban area. Transport Transportation ation Research Research Part Part C 20 (1), 2–14. 2–14. Cleg Clegg, g, J., J., Smit Smith, h, M., M., Xian Xiang, g, Y., Y., Yarr Yarrow ow,, R., R., 2001 2001.. Bile Bileve vell progr program ammi ming ng appl applie ied d to optimising urban transportation. transportation. Transportation Transportation Research Research Part B 35 (1), 41–70. Curti Curtin, n, K.M., K.M., Biba, Biba, S., 2011. 2011. The The transi transitt route route arcarc-no node de servi service ce maxi maximi mizat zation ion problem. European Journal of Operational Research 208 208 (1), (1), 46–56. 46–56. Daga Daganz nzo, o, C.F. C.F.,, Shef Sheffi, fi, Y., Y., 1977 1977.. On sto stochas chasti tic c model odelss of traf traffic fic assi assign gnm ment. ent. Transportation Transportation Science 11 (3), 253–274. 253–274. Dant Dantzi zig, g, G.B. G.B.,, Harv Harvey ey,, R.P. R.P.,, Lans Lansdo dow wne, ne, Z.F. Z.F.,, Robi Robins nson on,, D.W., .W., Maie Maier, r, S.F. S.F.,, 1979 1979.. Formulating Formulating and solving the the network design problem problem by decomposition. decomposition. Transport Transportatio ation n Research Research Part B 13 (1), 5–17. 5–17. Davis, G.A., 1994. Exact local solution of of the continuous continuous network network design problem via stochastic user equilibrium equilibrium assignment. assignment. Transportation Transportation Research Part B 28 (1), 61–75. Desaul Desaulnie niers, rs, G., G., Hickm Hickman an,, M.D., M.D., 2007 2007.. Chapt Chapter er 2: publi public c transi transit. t. In: Barnh Barnhart art,, C., Laporte, G. (Eds.), Handbooks Handbooks in Operations Research and Management Management Science. Science. Elsevier, Elsevier, pp. 69–127 69–127.. Dimitr Dimitriou iou,, L., Tseker Tsekeris, is, T., Stath Stathopo opoulo ulos, s, A., 2008a. 2008a. Geneti Genetic c compu computat tation ion of road road network design design and pricing Stackelberg Stackelberg games with with multi-class users. users. In: Giaco Giacobin bini, i, M. et al. (Eds. (Eds.), ), Applic Applicati ation onss of Evolut Evolution ionary ary Comp Comput uting ing.. Spring Springer, er, Berlin, Berlin, Heidelberg Heidelberg,, pp. 669–67 669–678. 8. Dimitrio Dimitriou, u, L., Stathopo Stathopoulos ulos,, A., Tsekeris, Tsekeris, L., 2008b. 2008b. Reliable Reliable stoch stochastic astic design design of road network systems. systems. International Journal Journal of Industrial and Systems Systems Engineering 3 (5), 549–57 549–574. 4. Dong, Dong, J., Wu, Wu, J., 2003. 2003. Urban Urban traffic traffic networks networks equilibr equilibrium ium status status recogni recognition tion with neura neurall netwo network. rk. In: Procee Proceedin dings gs of 6th IEE IEEE E Intern Internati ation onal al Intell Intellige igent nt Transport Transportatio ation n Systems Conferen Conference, ce, vol. 2, pp. 1049–105 1049–1053. 3. Drezner, Drezner, Z., Salhi, Salhi, S., 2000. 2000. Selecting Selecting a good configura configuration tion of one-way one-way and two-way two-way routes using using tabu tabu search. Control and Cybernetics Cybernetics 29 (3), 725–740. 725–740. Drez Drezne ner, r, Z., Z., Salh Salhi, i, S., S., 2002 2002.. Usin Using g hybr hybrid id met metah aheu euris risti tics cs for for the the oneone-wa way y and two-way two-way network design problem. problem. Naval Research Research Logistics Logistics (NRL) 49 (5), 449–463. Drezne Drezner, r, Z., Wesol Wesolow owsky sky,, G.O., G.O., 1997 1997.. Select Selectin ing g an optim optimum um configu configurat ration ion of oneoneway and two-way two-way routes. Transportation Transportation Science Science 31 (4), 386–394. 386–394. Drezner, Drezner, Z., Wesolow Wesolowsky, sky, G.O., G.O., 2003. 2003. Network Network design design:: selection selection and and design design of of links links and facility facility location. location. Transport Transportatio ation n Research Part A 37 (3), 241–25 241–256. 6. Dubo Dubois is,, D., D., Bel, Bel, G., G., Llib Llibre re,, M., M., 1979 1979.. A set set of meth method odss in tran transp spor orta tati tion on net netwo work rk synthesis and analysis. analysis. The Journal of of the Operational Operational Research Society Society 30 (9), 797–808. Elshafei, Elshafei, E.H., E.H., 2006. 2006. Decision Decision-Mak -Making ing for Roadway Roadway Lane Designati Designation on among among Variable Variable Modes. Modes. Universit University y of Maryland Maryland,, USA. Fan, Fan, W., W., Mach Machem emeh ehl, l, R.B. R.B.,, 2004 2004.. Opti Optima mall Tran Transi sitt Rout Route e Netw Networ ork k Desi Design gn Problem: Problem: Algorithm Algorithms, s, Impleme Implementat ntations ions,, and Numerical Numerical Results. Results. No. SWUTC/ SWUTC/ 04/ 167244-1 167244-1.. Center Center for Transport Transportation ation Research, Research, University University of Texas, Texas, Austin, Austin, Texas. Fan, W., Machemeh Machemehl, l, R.B., R.B., 2006a. 2006a. Optimal Optimal transit transit route route netwo network rk design design problem problem with variable variable transit transit demand: demand: genetic genetic algorith algorithm m approach approach.. Journal Journal of  of  Transportation Transportation Engineering 132 (1), 40–51. Fan, W., Machemeh Machemehl, l, R.B., R.B., 2006b. 2006b. Using Using a simulated simulated annealing annealing algorithm algorithm to solve the transit transit route route network network design design problem. problem. Journal Journal of of Transpor Transportatio tation n Engineering 132 132 (2), 122–132. 122–132. Fan, W., Machemehl, Machemehl, R.B., 2008. Tabu search strategies for the public transportation transportation network optimisations optimisations with variable transit demand. Computer-Aided Computer-Aided Civil and Infrastructure Engineering 23 (7), 502–520. 502–520. Fan, L., Mumford, Mumford, C., 2010. 2010. A metaheu metaheuristic ristic approach approach to the urban urban transit transit routing routing problem. problem. Journal Journal of of Heuristic Heuristicss 16 (3), 353–37 353–372. 2. Frank, Frank, M., Wolfe, Wolfe, P., 1956. 1956. An algorithm algorithm for for quadratic quadratic programm programming. ing. Naval Naval Research Logistics Logistics Quarterly Quarterly 3 (1–2), (1–2), 95–110. 95–110. Friesz, Friesz, T.L., T.L., 1985. 1985. Transpor Transportatio tation n network network equilibrium equilibrium,, design design and aggregation: aggregation: key developments developments and research opportunities. opportunities. Transportation Transportation Research Part A 19 (5–6), 413–427. 413–427. Frie Friesz sz,, T.L. T.L.,, Cho, Cho, H., H., Meht Mehta, a, N.J. N.J.,, Tobi Tobin, n, R.L. R.L.,, Anan Ananda dali ling ngam am,, G., G., 1992 1992.. A simu simula late ted d annealing approach to the network design problem with variational inequality constrain constraints. ts. Transpor Transportatio tation n Science Science 26 (1), 18–26. 18–26. R.Z. Farahani Farahani et al./ European European Journa Journall of Operatio Operational nal Research Research 229 (2013) (2013) 281–302 281–302 Friesz Friesz,, T.L., T.L., Anand Anandali alinga ngam, m, G., Mehta Mehta,, N.J., N.J., Nam, Nam, K., K., Shah, Shah, S.J., S.J., Tobin Tobin,, R.L., R.L., 1993 1993.. The The multiobjective multiobjective equilibrium network design problem revisited: a simulated annealing annealing approach. approach. European European Journal Journal of Operatio Operational nal Research 65 (1), 44–57. 44–57. Fusco, Fusco, G., Gori, Gori, S., Petrelli, Petrelli, M., 2002. 2002. A heuristic heuristic transi transitt network network design design algori algorithm thm for for medium size towns. towns. In: Proceedings of the 13th 13th Mini-EURO Mini-EURO Conference. Gallo, Gallo, M., D’Acierno D’Acierno,, L., Montella Montella,, B., 2010. 2010. A meta-heu meta-heuristic ristic approa approach ch for solving solving the urban network network design problem. problem. European Journal Journal of Operational Research Research 201 (1), 144–15 144–157. 7. Gallo, Gallo, M., Montella Montella,, B., D’Acierno D’Acierno,, L., 2011. 2011. The transit transit network network design design problem problem with elastic elastic deman demand d and and intern internalisat alisation ion of external external costs: costs: an applicati application on to rail freque frequency ncy opti optimi mizat zation ion.. Transp Transport ortati ation on Resea Research rch Part Part C: Emerg Emerging ing Technolo Technologies gies 19 (6), 1276–1 1276–1305 305.. Gao, Gao, Z., Wu, J., Sun, H., 2005. 2005. Solution Solution algorithm algorithm for the bi-level bi-level discrete discrete network network design design problem. problem. Transpor Transportatio tation n Research Part Part B 39 (6), 479–49 479–495. 5. Gao, Gao, Z., Sun, H., Zhang, Zhang, H., 2007. 2007. A globally globally convergen convergentt algorith algorithm m for for transpo transportati rtation on continuous continuous network network design problem. problem. Optimization Optimization and Engineering Engineering 8 (3), 241– 257. Gendreau, Gendreau, M., Potvin, Potvin, J.-Y., J.-Y., 2010. 2010. Handboo Handbook k of Metaheu Metaheuristic ristics, s, second second ed. SpringerSpringerVerlag, Verlag, New York, York, USA. USA. Guan, Guan, J.F., Yang, Yang, H., Wirasingh Wirasinghe, e, S.C., S.C., 2006. 2006. Simultan Simultaneous eous optimiz optimization ation of of transit transit line configuration configuration and passenger line assignment. assignment. Transportation Research Part B 40 (10), (10), 885–90 885–902. 2. Guihaire, Guihaire, V., Hao, J., 2008. 2008. Transit Transit netwo network rk design design and schedulin scheduling: g: a global global review review.. Transport Transportation ation Research Research Part A 42 (10), (10), 1251–1 1251–1273 273.. Hamd Hamdou ouch ch,, Y., Y., Flor Floria ian, n, M., M., Hear Hearn, n, D.W. D.W.,, Lawp Lawpho hong ngpa pani nich ch,, S., S., 2007 2007.. Cong Conges esti tion on pricing for multi-modal transportation transportation systems. Transportation Research Part B 41 (3), (3), 275– 275–29 291. 1. Hasselströ Hasselström, m, D., 1979. 1979. A Method Method for Optim Optimizati ization on of Urban Urban Bus Bus Route Route Networks. Networks. Volvo Bus Corporation, Corporation, Göteborg, Sweden. Hass Hassel elst strö röm, m, D., D., 1981 1981.. Publ Public ic Tran Transp spor orta tati tion on Plan Planni ning ng – A Math Mathem emat atic ical al Programming Programming Approach. Göteborg, Sweden. Hu, Hu, J., Shi, Shi, X., Song, Song, J., Xu, Xu, Y., 2005. 2005. Optim Optimal al design design for for urban urban mass mass transit transit netw network ork base based d on evol evolut utio iona nary ry algo algori rith thm ms. In: In: Wang, ang, L., L., Chen Chen,, K., K., Ong, ng, Y. (Eds (Eds.) .),, Advances Advances in Natural Natural Compu Computatio tation. n. Springer, Springer, Berlin, Berlin, Heidelber Heidelberg, g, pp. 429–42 429–429. 9. Kepaptso Kepaptsoglou glou,, K., Karlaftis, Karlaftis, M., 2009. 2009. Transit Transit route network design design problem: problem: review. review.  Journal  Journal of Transport Transportatio ation n Engineerin Engineering g 135 (8), (8), 491–50 491–505. 5. Koziel, Koziel, S., Yang, Yang, X.S., 2011. 2011. Computa Computation tional al Optimiza Optimization tion,, Methods Methods and and Algorithm Algorithms. s. Springer, Springer, Berlin, Berlin, Heidelberg Heidelberg.. Lampki Lampkin, n, W., W., Saalm Saalman ans, s, P.D., P.D., 1967 1967.. The The design design of routes routes,, servic service e frequen frequencie cies, s, and and schedules for a municipal municipal bus bus undertaking: a case study. Operational Research Quarterly Quarterly 18 (4), 375–39 375–397. 7. Leblan Leblanc, c, L.J., L.J., 1975 1975.. An algori algorithm thm for the the disc discret rete e netwo network rk desig design n prob problem lem.. Transportation Science 9 (3), 183–199. 183–199. LeBlanc, LeBlanc, L.J., Boyce, Boyce, D.E., D.E., 1986. 1986. A bilevel bilevel programm programming ing algorithm algorithm for exact exact solution solution of the network network design design problem problem with user-opt user-optimal imal flows. flows. Transport Transportation ation Research Research Part B 20 (3), 259–26 259–265. 5. Lee, Y., Vuchic, Vuchic, V.R., V.R., 2005. 2005. Transit Transit network network design design with variabl variable e demand. demand. Journal Journal of  Transportation Engineering 131 (1), (1), 1–10. Lee, C., Yang, Yang, K., 1994. 1994. Network Network design of one-way one-way streets streets with simulated simulated annealing. annealing. Papers Papers in Regional Regional Science Science 73 (2), 119–13 119–134. 4. Li, S.G., S.G., Ju, Y.F., Y.F., 2009. 2009. Evalua Evaluatio tion n of bus-e bus-excl xclusi usive ve lanes. lanes. IEEE IEEE Transa Transacti ction onss on Intelligent Transportation Systems 10 (2), 236–245. 236–245. Liu, H.X., H.X., He, X.Z., X.Z., He, B.S., B.S., 2009. 2009. Method Method of successive successive weighted weighted averages averages (MSWA) (MSWA) and self-regulated averaging schemes for solving stochastic user equilibrium problem. Networks and Spatial Economics Economics 9 (4), 485–503. 485–503. Lo, H.K., H.K., Szeto, Szeto, W.Y., W.Y., 2004. 2004. Chapter Chapter 9: Planning Planning transport transport network network improvem improvements ents over over time. time. In: Boyce Boyce,, D., D., Lee, Lee, D.H. D.H. (Eds.) (Eds.),, Urban Urban and and Regi Region onal al Tran Transpo sporta rtatio tion n Model Modeling ing:: Essays Essays in Hono Honorr of David David Boyce Boyce.. E. Elgar, Elgar, Cop.: Cop.: Chelt Cheltenh enham am (G.B. (G.B.), ), Northampton Northampton (Mass.), pp. 157–176. 157–176. Lo, H.K., H.K., Szeto, Szeto, W.Y., W.Y., 2009. 2009. Time-dep Time-depende endent nt transport transport netwo network rk design under under costcostrecovery. recovery. Transport Transportatio ation n Research Research Part B 43 (1), 142–15 142–158. 8. Long, Long, J., Gao, Z., Zhang, Zhang, H., Szeto, Szeto, W.Y., W.Y., 2010. 2010. A turning turning restrictio restriction n design design problem problem in urban road road networks. networks. European Journal of of Operational Research 206 206 (3), 569– 578. Luo, Luo, Z., Z., Pang Pang,, J., Ralp Ralph, h, D.C. D.C.,, 1996 1996.. Math Mathem emat atic ical al Pro Progr gram amss with with Equ Equil ilib ibri rium um Constrain Constraints. ts. Cambridg Cambridge e Univ. Univ. Press, Press, Cambridg Cambridge. e. Magnanti Magnanti,, T.L., Wong, Wong, R.T., R.T., 1984. 1984. Network Network design design and transport transportatio ation n planning planning:: models and algorithms. Transportation Science 18 (1), 1–55. Mandl, Mandl, C.E., C.E., 1980. 1980. Evaluatio Evaluation n and and optimi optimizatio zation n of urban urban public public transport transportation ation networks. networks. European European Journal Journal of Operation Operational al Research 5 (6), 396–40 396–404. 4. Marcotte Marcotte,, P., 1983. 1983. Network Network optimizatio optimization n with continuo continuous us control control parameters. parameters. Transportation Science 17 (2), 181–197. 181–197. Marcotte Marcotte,, P., 1986. 1986. Network Network design design problem problem with congestio congestion n effects: effects: a case of  bilevel programming. programming. Mathematical Mathematical Programming Programming 34 (2), 142–162. 142–162. Marco Marcotte tte,, P., P., Marqu Marquis, is, G., 1992 1992.. Efficie Efficient nt imple impleme ment ntati ation on of heurist heuristics ics for the continuo continuous us network network design design problem. problem. Annals Annals of Operatio Operations ns Research Research 34 (1), 163–176. Math Mathew, ew, T.V., T.V., Sharma Sharma,, S., 2009 2009.. Capaci Capacity ty expa expansi nsion on prob problem lem for large large urba urban n transportation networks. Journal of Transportation Transportation Engineering Engineering 135 (7), 406– 415. Maut Mautton tone, e, A., Urquh Urquhart art,, M.E., M.E., 2009 2009.. A route route set set constr construc uctio tion n algori algorith thm m for for the transit transit network network design design problem problem.. Compute Computers rs & Operatio Operations ns Research Research 36 (8), 2440–2449. Meneguzzer, C., 1995. An equilibrium route choice choice model with explicit treatment of  the effect effect of intersect intersections ions.. Transport Transportatio ation n Research Research Part B 29 (5), 329–35 329–356. 6. 301 Meng, Meng, Q., Yang, Yang, H., 2002. 2002. Benefit Benefit distribut distribution ion and equity equity in road network network design. design. Transport Transportation ation Researc Research h Part B 36 (1), 19–35. 19–35. Meng, Meng, Q., Yang, Yang, H., Bell, Bell, M.G.H. M.G.H.,, 2001 2001.. An equiva equivalen lentt cont continu inuou ously sly differe differenti ntiabl able e model and a locally convergent algorithm for the continuous continuous network network design problem problem.. Transport Transportatio ation n Research Research Part B 35 (1), 83–105 83–105.. Mesba Mesbah, h, M., M., Sarvi, Sarvi, M., M., Currie Currie,, G., 2008 2008.. New New metho methodo dolog logy y for optim optimizi izing ng trans transit it priority at the network network level. Transportation Transportation Research Record 2089, 2089, 93–100. Miandoab Miandoabchi, chi, E., Farahani, Farahani, R.Z., R.Z., 2010. 2010. Optimizi Optimizing ng reserve reserve capacity capacity of urban urban road netwo networks rks in a discre discrete te netwo network rk design design proble problem. m. Advanc Advances es in Engin Engineer eering ing Software Software 42 (12), (12), 1041–1 1041–1050. 050. Miandoab Miandoabchi, chi, E., Farahani, Farahani, R.Z., R.Z., Dull Dullaert, aert, W., Szeto, Szeto, W.Y., W.Y., 2012a. 2012a. Hybrid Hybrid evolutionar evolutionary y metaheuristics for concurrent multi-objective multi-objective design of urban road and public transit networks. networks. Networks and Spatial Spatial Economics Economics 12 (3), 441–480. 441–480. Miandoab Miandoabchi, chi, E., Farahani, Farahani, R.Z., R.Z., Szeto, Szeto, W.Y., W.Y., 2012b. 2012b. Bi-objec Bi-objective tive bimodal bimodal urban road network design design using hybrid hybrid metaheuristics. metaheuristics. Central European European Journal Journal of  Operation Operationss Research Research 20 (4), 583–62 583–621. 1. Migdalas, Migdalas, A., 1995. 1995. Bilevel Bilevel programm programming ing in traffic planning: planning: models, models, method methodss and challenge challenge.. Journal Journal of Global Global Optimizatio Optimization n 7 (4), 381–40 381–405. 5. Ngamchai, Ngamchai, S., Lovell, Lovell, D.J., 2003. 2003. Optimal Optimal time time transfer transfer in bus transit transit route route netwo network rk design using a genetic algorithm. algorithm. Journal of Transportation Engineering 129 129 (5), 510–521. O’Brien, O’Brien, L., Szeto, Szeto, W.Y., W.Y., 2007. 2007. The discrete discrete network network design design problem problem over time. time. HKIE Transacti Transactions ons 14 (4), 47–55. 47–55. Pach Pachec eco, o, J., J., Alva Alvare rez, z, A., A., Casa Casado do,, S., S., Gonz Gonzál ález ez-V -Vel elar arde de,, J.L. J.L.,, 2009 2009.. A tabu tabu sear search ch approach approach to an urban urban transport transport problem problem in northern northern Spain. Spain. Compute Computers rs & Operation Operationss Research Research 36 (3), 967–97 967–979. 9. Pape, Pape, U., U., Reinec Reinecke, ke, E., Reinec Reinecke, ke, Y., 1992 1992.. Entw Entwurf urf und und imple impleme menti ntieru erung ng eines eines linienplanungssystems linienplanungssystems fr den busverkehr im pnv unter einer objektorientierten objektorientierten grafischen entwicklungsumgebu entwicklungsumgebung. ng. Gruppendiplomarbeit. Gruppendiplomarbeit. Pattnaik Pattnaik,, S.B., S.B., Mohan, Mohan, S., Tom, Tom, V.M., V.M., 1998. 1998. Urban Urban bus bus transit transit route route network network design design using genetic algorithm. Journal of Transportation Transportation Engineering Engineering 124 (4), 368– 375. Patz Patz,, A., A., 1925 1925.. Die Die rich richti tige ge aus auswa wahl hl von von ver verke kehr hrsl slin inie ien n bei bei groß großen en Straßenbahnnetzen. Straßenbahnnetzen. 50/51. Poorzahe Poorzahedy, dy, H., Abulghas Abulghasemi, emi, F., 2005. 2005. Applicatio Application n of ant system system to network network design design problem problem.. Transport Transportatio ation n 32 (3), 251–27 251–273. 3. Poorzahe Poorzahedy, dy, H., Rouhani, Rouhani, O.M., O.M., 2007. 2007. Hybrid Hybrid meta-heuris meta-heuristic tic algorithms algorithms for solving solving network design problem. problem. European Journal of of Operational Research 182 182 (2), 578–596. Poorzahe Poorzahedy, dy, H., Turnquis Turnquist, t, M.A., M.A., 1982. 1982. Approxim Approximate ate algorithm algorithmss for the discrete discrete network network design design problem. problem. Transpor Transportatio tation n Research Part Part B 16 (1), 45–55. 45–55. Powel Powell, l, W.B., W.B., Sheffi, Sheffi, Y., 1982 1982.. The The conver convergen gence ce of equili equilibri brium um algo algorit rithm hmss with with predetermined step sizes. Transportation Transportation Science 16 (1), 45–55. Seo, Seo, Y.U., Y.U., Park, Park, J.H., J.H., Jang, Jang, H., Lee, Lee, Y.I., Y.I., 2005. 2005. A study study on settin setting-u g-up p metho methodo dolog logy y and criterion criterion of of exclusive exclusive bus bus lane in urban urban area. Proceedin Proceeding g of the Eastern Eastern Asia Society for Transportation Transportation Studies 5, 325–338. 325–338. Shih, Shih, M., Mahmassa Mahmassani, ni, H.S., H.S., 1994. 1994. A Design Design Methodo Methodology logy for for Bus Transit Transit Netwo Networks rks with with Coor Coordi dina nate ted d Ope Opera rati tion ons. s. No. No. SWUT SWUTC/ C/94 94/6 /600 0016 16-1 -1.. Cent Center er for for Transport Transportation ation Research, Research, Universit University y of Texas, Texas, Austin. Austin. Shih, Shih, M., Mahmassa Mahmassani, ni, H.S., Baaj, M.H., M.H., 1998. 1998. Planning Planning and and design design model model for transit transit route networks with coordinated coordinated operations. operations. Transportation Transportation Research Record 1623, 1623, 16–23. 16–23. Silman, Silman, L.A., Barzily, Barzily, Z., Passy, Passy, U., 1974. 1974. Planning Planning the route route system system for for urban urban buses. buses. Compute Computers rs & Operatio Operations ns Research 1 (2), 201–21 201–211. 1. Sonntag, Sonntag, H., 1977. 1977. Linienpl Linienplanun anung g im öffentlich öffentlichen en personen personennahv nahverkeh erkehr. r. Technisch Technische e Universit Universitt, t, Berlin. Berlin. Spiess, Spiess, H., Florian, Florian, M., 1989. 1989. Optimal Optimal strategie strategies: s: a new assignm assignment ent model model for transit transit networks. networks. Transport Transportatio ation n Research Research Part B 23 (2), 83–102 83–102.. Steenbrin Steenbrink, k, P.A., 1974a. 1974a. Optimiz Optimization ation of of Transport Transport Netwo Network. rk. Wiley, Wiley, New York, York, USA. Steenbrin Steenbrink, k, P.A., P.A., 1974b. 1974b. Transport Transport network network optimiz optimization ation in the Dutch Dutch integra integrall transportation study. Transportation Transportation Research 8 (1), 11–27. 11–27. Suh, Suh, S., Kim, Kim, T., 1992 1992.. Solvin Solving g nonli nonlinea nearr bilev bilevel el progra programm mming ing model modelss of the equili equilibri brium um netw network ork desig design n problem problem:: a compar comparati ative ve review review.. Annal Annalss of  Operation Operationss Research Research 34 (1), 203–21 203–218. 8. Szeto, Szeto, W.Y., W.Y., Lo, H.K., H.K., 2005. 2005. Strategies Strategies for road network network design design over time: robustne robustness ss under under uncertain uncertainty. ty. Transport Transportmet metrica rica 1 (1), 47–63. 47–63. Szeto, Szeto, W.Y., W.Y., Lo, H.K., H.K., 2006 2006.. Transp Transport ortati ation on netw network ork imp improv rovem ement ent and and tolli tolling ng strategies: the issue of of intergeneration equity. Transportation Transportation Research Research Part A 40 (3), (3), 227– 227–24 243. 3. Szeto, Szeto, W.Y., W.Y., Lo, H.K., H.K., 2008. 2008. Time-dep Time-depende endent nt transport transport netwo network rk improvem improvement ent and and tolling tolling strategies. strategies. Transport Transportatio ation n Research Part Part A 42 (2), 376–39 376–391. 1. Szeto, Szeto, W.Y., W.Y., Wu, Wu, Y., 2011. 2011. A simultan simultaneous eous bus rout route e design design and and frequenc frequency y setting setting problem for Tin Shui Shui Wai, Hong Kong. European Journal Journal of Operational Research 209 (2), 141–155. 141–155. Szeto, Szeto, W.Y., W.Y., Jaber, Jaber, X., O’Mahon O’Mahony, y, M., 2010. 2010. Time-dep Time-depende endent nt discrete network network design frameworks considering considering land use. Computer-Aided Computer-Aided Civil and Infrastructure Infrastructure Engineeri Engineering ng 25 (6), 411–42 411–426. 6. Tom, Tom, V.M., V.M., Mohan, Mohan, S., 2003. 2003. Transit Transit route route networ network k design design using using frequenc frequency y coded coded genetic algorithm. algorithm. Journal of Transportation Transportation Engineering Engineering 129 129 (2), (2), 186–195. 186–195. Ukkusur Ukkusuri, i, S.V., S.V., Waller, Waller, S.T., S.T., 2007. 2007. Linear Linear progra programm mming ing models models for the user and system optimal optimal dynamic network network design problem: problem: formulations, formulations, comparisons comparisons and extensions. extensions. Networks Networks and Spatial Economic Economicss 8 (4), 383–406. 383–406. Ukku Ukkusur suri, i, S.V., S.V., Mathew Mathew,, T.V., T.V., Walle Waller, r, S.T., S.T., 2007. 2007. Robu Robust st transp transport ortati ation on netw network ork design under demand demand uncertainty. uncertainty. Computer-Aided Computer-Aided Civil and Infrastructure Engineeri Engineering ng 22 (1), 6–18. 6–18. 302 R.Z. Farahani Farahani et al./ European European Journal Journal of Operation Operational al Research Research 229 (2013) (2013) 281–302 281–302 van Nes, Nes, R., Hamerslag Hamerslag,, R., Immers, Immers, B.H., B.H., 1988. 1988. Design Design of of public public transp transport ort networks. networks. Transportation Transportation Research Record 1202, 74–83. 74–83. Wan, Wan, Q., Lo, H.K., H.K., 2003. 2003. A mixed mixed integ integer er formula formulatio tion n for multi multiple ple-ro -rout ute e transit transit network design. Journal of of Mathematical Mathematical Modelling Modelling and and Algorithms Algorithms 2 (4), 299– 308. Wang, Wang, D.Z.W D.Z.W., ., Lo, H.K., H.K., 2010. 2010. Global Global optim optimum um of the the lineariz linearized ed netwo network rk design design problem problem with with equilibriu equilibrium m flows. flows. Transpor Transportatio tation n Research Research Part B 44 (4), 482– 482– 492. Wardrop, Wardrop, J., 1952. 1952. Some Some theoretic theoretical al aspects aspects of road traffic traffic research. research. Proceedin Proceedings gs of  the Institute Institute of Civil Engine Engineers, ers, Part II, 325–37 325–378. 8. Wei, Wei, C.H. C.H.,, Scho Schonf nfel eld, d, P.M. P.M.,, 1993 1993.. An arti artific ficia iall neur neural al netw networ ork k appr approa oach ch for for evaluating evaluating transport transportatio ation n networ network k improvem improvements ents.. Journal Journal of of Advanced Advanced Transpor Transportatio tation n 27 (2), 129–15 129–151. 1. Wey, W.M., 2000. Model formulation and solution algorithm of traffic signal control control in an urban urban network. network. Compute Computers rs Environme Environment nt and Urban System Systemss 24 (4), 355– 355– 377. Wong, Wong, S.C., Yang, Yang, C., 1999. 1999. An iterative iterative group-ba group-based sed signal optimiz optimizatio ation n scheme scheme for traffic traffic equilibri equilibrium um netwo networks. rks. Journal Journal of Advanced Advanced Transpo Transportati rtation on 33 (2), 201– 201– 217. Wu, Wu, J.J., J.J., Sun, Sun, H.J., H.J., Gao, Gao, Z.Y., Z.Y., Zhang Zhang,, H.Z., H.Z., 2009. 2009. Revers Reversibl ible e lane-b lane-base ased d traffic traffic netwo network rk optimiza optimization tion with an advanced advanced traveller traveller informat information ion system. system. Engineer Engineering ing Optimization Optimization 41, 87–97. 87–97. Wu, D., Yin, Y., Lawphon Lawphongpan gpanich, ich, S., 2011. 2011. Pareto-im Pareto-improv proving ing congestio congestion n pricin pricing g on on multimodal multimodal transportation networks. networks. European Journal Journal of Operational Research 120 (3), 660–669. 660–669. Xion Xiong, g, Y., Y., Schn Schnei eide der, r, J.B. J.B.,, 1992 1992.. Tran Transp spor orta tati tion on netw networ ork k desi design gn usin using g a cumulative algorithm algorithm and neural neural network. Transportation Transportation Research Record 1364, 1364, 37–44. 37–44. Xu, Xu, T., T., Wei, Wei, H., Hu, Hu, G., 2009 2009.. Study Study on contin continuo uous us netw network ork desi design gn proble problem m using using simulated annealing annealing and genetic algorithm. Expert Systems with Applications Applications 36 (2, (2, Part Part 1), 1322 1322–1 –132 328. 8. Yang, Yang, H., 1997. 1997. Sensitivit Sensitivity y analysis for the elastic-de elastic-deman mand d network network equilibrium equilibrium problem problem with applicatio applications. ns. Transpor Transportatio tation n Research Part B 31 (1), 55–70. 55–70. Yang, Yang, X.S., X.S., 2011. 2011. Nature Nature Inspired Metaheu Metaheuristic ristic Algorithm Algorithms. s. Luniver Luniver Press, London, London, UK. Yang, Yang, H., Bell, M.G.H., M.G.H., 1998a. 1998a. Models Models and algorithm algorithmss for for road network network design: design: a review and some new new developments. developments. Transport Reviews Reviews 18 (3), 257–278. 257–278. Yang, Yang, H., Bell, Bell, M.G.H M.G.H., ., 1998 1998b. b. A capaci capacity ty parad paradox ox in netw network ork desi design gn and and how how to avoid avoid it. Transport Transportation ation Researc Research h Part A 32 (7), 539–54 539–545. 5. Yang, Yang, H., Wang, Wang, J.Y.T. J.Y.T.,, 2002 2002.. Travel Travel time time minimi minimizat zation ion versu versuss reserve reserve capacity capacity maximization maximization in the network design design problem. Transportation Research Research Record 1783, 1783, 17–26. 17–26. Yang, Yang, Z., Yu, B., Cheng Cheng,, C., 2007. 2007. A parall parallel el ant ant colon colony y algor algorith ithm m for for bus bus netw network ork optimization. optimization. Computer Computer Aided Civil and Environmental Environmental Engineering Engineering 22 (1), 44– 55. Yu, B., Yang, Yang, Z., Cheng, Cheng, C., Liu, C., 2005. 2005. Optimiz Optimizing ing bus bus transi transitt netwo network rk with with paralle parallell ant colony algorithm. algorithm. Proceedings of the Eastern Asia Society for Transportation Transportation Studies 5, 374–389. 374–389. Zhang, H., Gao, Z., 2007. Two-way Two-way road network design problem problem with variable lanes. lanes.  Journal  Journal of Systems Systems Science Science and System Systemss Engineerin Engineering g 16 (1), 50–61. 50–61. Zhang, H., Gao, Z., 2009. Bilevel programmin programming g model model and solution method for mixed mixed transport transportation ation netwo network rk design proble problem. m. Journal Journal of Systems Systems Science Science and Complexity Complexity 22, 446–459. 446–459. Zhao, Zhao, F., 2006. 2006. Large-scale Large-scale transit transit network network optimiz optimizatio ation n by minimiz minimizing ing user cost and transfers. transfers. Journal Journal of Public Public Transport Transportatio ation n 9 (9), 107–12 107–129. 9. Zhao, Zhao, F., Gan, A., 2003. 2003. Optimiza Optimization tion of Transit Transit Network Network to Minimiz Minimize e Transfe Transfers. rs. No. BD-0 BD-015 15-0 -02. 2. Rese Resear arch ch Cent Center er of Depa Depart rtme ment nt of Tran Transp spor orta tati tion on,, Flor Florid ida a International University, Miami, Florida. Zhao, Zhao, F., Ubaka, Ubaka, I., 2004. 2004. Transit Transit network network optimiz optimization ation – minimiz minimizing ing transfer transferss and optimizi optimizing ng route directness. directness. Journal Journal of Public Public Transportatio Transportation n 7 (1), 67–82. 67–82. Zhao, Zhao, F., Zeng, Zeng, X., 2006. 2006. Simulated Simulated annealing annealing-gene -genetic tic algorithm algorithm for transit netw network ork optimiza optimization tion.. Journal Journal of Computi Computing ng in Civil Civil Engineerin Engineering g 20 (1), 57–68. 57–68. Zhao, Zhao, F., Zeng, Zeng, X., 2007. 2007. Optimiz Optimization ation of of user and operato operatorr cost for large scale transit transit networks. Journal of Transportation Transportation Engineering Engineering 133 (4), 240–251. 240–251. Ziyou, Ziyou, G., Yifan, Yifan, S., 2002. 2002. A reserve reserve capaci capacity ty model model of optimal optimal signal signal control control with user-equilibrium user-equilibrium route route choice. choice. Transportation Transportation Research Research Part Part B 36 (4), 313–323. 313–323.