Transit Route Network Design Problem: Review

Public transportation is largely considered as a viable option for sustainable transportation in urban areas, offering advantages such as mobility enhancement, traffic congestion and air pollution reduction, and energy conservation while still preserving social equity considerations. Nevertheless, in the past decades, factors such as socioeconomic growth, the need for personalized mobility, the increase in private vehicle ownership and urban sprawl have led to a shift towards private vehicles and a decrease in public transportation’s share in daily commuting (Sinha 2003; TRB 2001; EMTA 2004; ECMT 2002; Pucher et al. 2007). Efforts for encouraging public transportation use focuses on improving provided services such as line capacity, service frequency, coverage, reliability, comfort and service quality which are among the most important parameters for an efficient public transportation system (Sinha 2003; Vuchic 2004).

In this context, planning and designing a cost and service efficient public transportation network is necessary for improving its competitiveness and market share. The problem that formally describes the design of such a public transportation network is referred to as the transit route network design problem (TRNDP); it focuses on the optimization of a number of objectives representing the efficiency of public transportation networks under operational and resource constraints such as the number and length of public transportation routes, allowable service frequencies, and number of available buses (Chakroborty 2003; Fan and Machemehl 2006a,b).

The practical importance of designing public transportation networks has attracted considerable interest in the research community which has developed a variety of approaches and models for the TRNDP including different levels of design detail and complexity as well as interesting algorithmic innovations. In this paper we offer a structured review of approaches for the TRNDP; researchers will obtain a basis for evaluating existing research and identifying future research paths for further improving TRNDP models. Moreover, practitioners will acquire a detailed presentation of both the process and potential tools for automating the design of public transportation networks, their characteristics, capabilities, and strengths.

Network design is an important part of the public transportation operational planning process (Ceder 2001). It includes the design of route layouts and the determination of associated operational characteristics such as frequencies, rolling stock types, and so on. As noted by Ceder and Wilson (1986), network design elements are part of the overall operational planning process for public transportation networks; the process includes five steps: (1) design of routes; (2) setting frequencies; (3) developing timetables; (4) scheduling buses; and (5) scheduling drivers. Route layout design is guided by passenger flows: routes are established to provide direct or indirect connection between locations and areas that generate and attract demand for transit travel, such as residential and activity related centers (Levinson 1992). For example, passenger flows between a central business district (CBD) and suburbs dictate the design of radial routes while demand for trips between different neighborhoods may lead to the selection of a circular route connecting them. Anticipated service coverage, transfers, desirable route shapes, and available resources usually determine the structure of the route network. Route shapes are usually constrained by their length and directness (route directness implies that route shapes are as straight as possible between connected points), the usage of given roads, and the overlapping with other transit routes. The desirable outcome is a set of routes connecting locations within a service area, conforming to given design criteria. For each route, frequencies and bus types are the operational characteristics typically determined through design. Calculations are based on expected passenger volumes along routes that are estimated empirically or by applying transit assignment techniques, under frequency requirement constraints (minimum and maximum allowed frequencies guaranteeing safety and tolerable waiting times, respectively), desired load factors, fleet size, and availability. These steps as well as the overall design process have been largely based upon practical guidelines, the expert judgment of transit planners, and operators experience (Baaj and Mahmassani 1991). Two handbooks by Black (1995) and Vuchic (2004) outline frameworks to be followed by planners when designing a public transportation network that include: (1) establishing the objectives for the network; (2) defining the operational environment of the network (road structure, demand patterns, and characteristics); (3) developing; and (4) evaluating alternative public transportation networks.

Despite the extensive use of practical guidelines and experience for designing transit networks, researchers have argued that empirical rules may not be sufficient for designing an efficient transit network and improvements may lead to better quality and more efficient services. For example, Fan and Machemehl (2004) noted that researchers and practitioners have been realizing that systematic and integrated approaches are essential for designing economically and operationally efficient transit networks. A systematic design process implies clear and consistent steps and associated techniques for designing a public transportation network, which is the scope of the TRNDP.

Research has extensively examined the TRNDP since the late 1960s. In 1979, Newell discussed previous research on the optimal design of bus routes and Hasselström (1981) analyzed relevant studies and identified the major features of the TRNDP as demand characteristics, objective functions, constraints, passenger behavior, solution techniques, and computational time for solving the problem. An extensive review of existing work on transit network design was provided by Chua (1984) who reported five types of transit system planning: (1) manual; (2) market analysis; (3) systems analysis; (4) systems analysis with interactive graphics; and (5) mathematical optimization approach. Axhausemm and Smith (1984) analyzed existing heuristic algorithms for formulating the TRNDP in Europe, tested them, and discussed their potential implementation in the United States. Ceder and Wilson (1986) reported prior work on the TRNDP and distinguished studies into those that deal with idealized networks and to those that focus on actual routes, suggesting that the main features of the TRNDP include demand characteristics, objectives and constraints, and solution methods.

At the same period, Van Nes et al. (1988) grouped TRNDP models into six categories: (1) analytical models for relating parameters of the public transportation system; (2) models determining the links to be used for public transportation route construction; (3) models determining routes only; (4) models assigning frequencies to a set of routes; (5) two-stage models for constructing routes and then assigning frequencies; and (6) models for simultaneously determining routes and frequencies. Spacovic et al. (1994) and Spacovic and Schonfeld (1994) proposed a matrix organization and classified each study according to design parameters examined, objectives anticipated, network geometry, and demand characteristics. Ceder and Israeli (1997) suggested broad categorizations for TRNDP models into passenger flow simulation and mathematical programming models. Russo (1998) adopted the same categorization and noted that mathematical programming models guarantee optimal transit network design but sacrifice the level of detail in passenger representation and design parameters, while simulation models address passenger behavior but use heuristic procedures obtaining a TRNDP solution. Ceder (2001) enhanced his earlier categorization by classifying TRNDP models into simulation, ideal network, and mathematical programming models. Finally, in a recent series of studies, Fan and Machemehl (2004, 2006a,b) divided TRNDP approaches into practical approaches, analytical optimization models for idealized conditions, and metaheuristic procedures for practical problems.

The TRNDP is an optimization problem where objectives are defined, its constraints are determined, and a methodology is selected and validated for obtaining an optimal solution. The TRNDP is described by the objectives of the public transportation network service to be achieved, the operational characteristics and environment under which the network will operate, and the methodological approach for obtaining the optimal network design. Based on this description of the TRNDP, we propose a three-layer structure for organizing TRNDP approaches (Objectives, Parameters, and Methodology). Each layer includes one or more items that characterize each study.

The “Objectives” layer incorporates the goals set when designing a public transportation system such as the minimization of the costs of the system or the maximization of the quality of services provided. The “Parameters” layer describes the operating environment and includes both the design variables expected to be derived for the transit network (route layouts, frequencies) as well as environmental and operational parameters affecting and constraining that network (for example, allowable frequencies, desired load factors, fleet availability, demand characteristics and patterns, and so on). Finally, the “Methodology” layer covers the logical–mathematical framework and algorithmic tools necessary to formulate and solve the TRNDP. The proposed structure follows the basic concepts toward setting up a TRNDP: deciding upon the objectives, selecting the transit network items and characteristics to be designed, setting the necessary constraints for the operating environment, and formulating and solving the problem.

Public transportation serves a very important social role while attempting to do this at the lowest possible operating cost. Objectives for designing daily operations of a public transportation system should encompass both angles. The literature suggests that most studies actually focus on both the service and economic efficiency when designing such a system. Practical goals for the TRNDP can be briefly summarized as follows (Fielding 1987; van Oudheudsen et al. 1987; Black 1995): (1) user benefit maximization; (2) operator cost minimization; (3) total welfare maximization; (4) capacity maximization; (5) energy conservation—protection of the environment; and (6) individual parameter optimization.

Mandl (1980) indicated that public transportation systems have different objectives to meet. He commented, “even a single objective problem is difficult to attack” (p. 401). Often, these objectives are controversial since cutbacks in operating costs may require reductions in the quality of services. Van Nes and Bovy (2000) pointed out that selected objectives influence the attractiveness and performance of a public transportation network. According to Ceder and Wilson (1986), minimization of generalized cost or time or maximization of consumer surplus were the most common objectives selected when developing transit network design models. Berechman (1993) agreed that maximization of total welfare is the most suitable objective for designing a public transportation system while Van Nes and Bovy (2000) argued that the minimization of total user and system costs seem the most suitable and less complicated objective (compared to total welfare), while profit maximization leads to nonattractive public transportation networks.

As can be seen in Table 1, most studies seek to optimize total welfare, which incorporates benefits to the user and to the system. User benefits may include travel, access and waiting cost minimization, minimization of transfers, and maximization of coverage, while benefits for the system are maximum utilization and quality of service, minimization of operating costs, maximization of profits, and minimization of the fleet size used. Most commonly, total welfare is represented by the minimization of user and system costs. Some studies address specific objectives from the user, the operator, or the environmental perspective. Passenger convenience, the number of transfers, profit and capacity maximization, travel time minimization, and fuel consumption minimization are such objectives. These studies either attempt to simplify the complex objective functions needed to setup the TRNDP (Newell 1979; Baaj and Mahmassani 1991; Chakroborty and Dwivedi 2002), or investigate specific aspects of the problem, such as objectives (Delle Site and Fillipi 2001), and the solution methodology (Zhao and Zeng 2006; Yu and Yang 2006).

Total welfare is, in a sense, a compromise between objectives. Moreover, as reported by some researchers such as Baaj and Mahmassani (1991), Bielli et al. (2002), Chackroborty and Dwivedi (2002), and Chakroborty (2003), transit network design is inherently a multiobjective problem. Multiobjective models for solving the TRNDP have been based on the calculation of indicators representing different objectives for the problem at hand, both from the user and operator perspectives, such as travel and waiting times (user), and capacity and operating costs (operator). In their multiobjective model for the TRNDP, Baaj and Majmassani (1991) relied on the planner’s judgment and experience for selecting the optimal public transportation network, based on a set of indicators. In contrast, Bielli et al. (2002) and Chakroborty and Dwivedi (2002), combined indicators into an overall, weighted sum value, which served as the criterion for determining the optimal transit network.

There are multiple characteristics and design attributes to consider for a realistic representation of a public transportation network. These form the parameters for the TRNDP. Part of these parameters is the problem set of decision variables that define its layout and operational characteristics (frequencies, vehicle size, etc.). Another set of design parameters represent the operating environment (network structure, demand characters, and patterns), operational strategies and rules, and available resources for the public transportation network. These form the constraints needed to formulate the TRNDP and are, a-priori fixed, decided upon or assumed.

As reported by previous research, the TRNDP is a complex, difficult to solve optimization problem, where traditional mathematical programming formulations and solution techniques cannot be efficiently applied (Baaj and Mahmassani 1991; Chakroborty and Dwivedi 2002). Newell (1979) discerned the complexity of the problem, by noting that “the selection of an optimal route structure for a (transit) network of realistic size is a combinatorial problem of astronomical proportions.” Additionally, he mentioned that, while the selection of optimal frequencies in an existing network is, in general, a convex optimization problem, “. . . the choice of routes is generally a nonconvex (even concave) optimization problem for which no simple procedure exists short of direct comparison of various local minima” (p. 21). Baaj and Mahmassani (1991) indicated sources of complexity for the TRNDP: its combinatorial and multiobjective nature, the difficulties in formulating the problem and formally defining acceptable spatial route layouts, and the nonlinearities and nonconvexities characterizing the problem. Chackroborty (2003) suggested that formulating the TRNDP as a mathematical problem is difficult since the problem is inherently discrete and concepts such as “transfers” and “route continuity” are hard to represent.

Existing research exhibits a diversity of approaches in formulating and solving the TRNDP. In general, such methodologies are classified into two broad categories: analytical and heuristic (Baaj and Mahmassani 1991; Chakroborty and Dwivedi 2002). However, this study classifies methodologies found in the literature, in a disaggregated structure. (Fig. 1). We define two major categories: conventional and heuristic approaches; and relevant subclassifications.

Modeling of transit network design has received considerable attention by researchers for the last four decades; efforts focused on the design of public transportation networks with superior performance to those planned and designed by ad-hoc practices and rules thumb. Different approaches explored the TRNDP demonstrating a variety of methodologies for representing and solving the problem. This study disaggregated the TRNDP into three layers in an effort to reveal key characteristics in modeling the problem: the “objectives” layer, the “parameters” layer, and the “methodology” layer (key-characteristics are summarized in Fig. 3).

The “objectives” and “parameters” layers compose the problem’s design space. Both levels are characterized by a variety of elements, an indication of TRNDP complexity. The design of a public transportation network is driven by different (often contradicting) objectives and affected by a multiattribute design environment. Among objectives, social welfare is reported as the most common: It is typically interpreted as the minimization of the sum of operator and user costs. However, as Baaj and Mahmassani (1991) pointed out, the TRNDP is inherently multiobjective. For this reason, some studies examined multiple objectives, allowing planners to select the best combination of different objectives.

Most common decision variables encountered were routes and frequencies (or equivalently headways). Other decision variables include zone sizes, stop locations, vehicle size, and fare level. Fare setting is, however, frequently a part of the overall transport operator’s strategy and influenced by external socioeconomic factors. Moreover, modern transit systems offer a variety of fare products that are difficult to represent in a single fare “level.”

Decisions between many-to-many and many-to-one patterns is directly related to the urban structure and spatial distribution of human activities: In cases of public transportation networks oriented toward serving commuting trips to and from a city’s CBD, it is expected that a simplified many-to-one pattern may be adequate. Many-to-many patterns are suitable in cases of systems planned to serve cities with multiple activity centers and/or passengers with various trip purposes in urban areas. As for demand characteristics, time and space dependencies have been explicitly examined in some studies. The effects of service characteristics on demand and vice versa have been of particular interest among researchers. Most approaches incorporated mode choice models to capture the share of public transportation for different service configurations. Although as discussed, the overall effects of the public transportation network service on total demand (which may be considerable in networks with many captive passengers) were not incorporated in the models investigated.

Constraints and operational strategies reflect the operator’s policy and resources of the operator. Desired performance and safety aspects are regulated by constraints such as allowable frequencies and load factors along with route shapes and lengths, while the number and size of vehicles and the operating cost are factors indicating resource availability.

Methodologies applied in solving the TRNDP form the problem’s modeling approach; this is the part that has attracted most research efforts. The variety of techniques and tools selected in the different studies is influenced by:

Some conventional models assume idealized situations and require minimal computational effort. However, their results can only serve as indications for planners, particularly for evaluating the performance of existing bus lines. Mathematical programming models could assure optimal solutions under specific constraints; nevertheless, their complexity and difficulty in adequately representing a public transportation network, along with their extensive computational requirements, are major drawbacks.

Early heuristics attempted to improve the level of detail captured under the constraint of the limited, at the time, computational power available. These models were mainly criticized for their inability to handle large networks, the fact that they actually produce approximate, adequate, but not always optimal (or near-optimal) solutions, and for limitations in their technical features, such as the level of representation achieved. Nevertheless, they provided the basis for later methodologies, many of which are based on met heuristic algorithms. Models based solely, or in part, on met heuristics usually retain the philosophy of earlier heuristics. Their structure includes a route generation and a route selection-configuration procedure while metaheuristics are implemented in an effort to obtain network configurations of superior quality. However, in most cases, routes are generated using heuristic techniques.

With or without the use of met heuristics, partitioning the TRNDP in a sequence of procedures is attractive in that these procedures become manageable and the TRNDP easier to process. Two major approaches were identified: (1) route generation and configuration; and (2) route construction and improvement. Route generation in almost all cases is an independent, preprocessing procedure, while route configuration is either sequential (routes are selected and then frequencies are assigned to them), or simultaneous (routes and associated frequencies are determined at the same time). However, researchers in the fields of operations research and optimization argue that sequential methods often provide inferior results compared to methods that simultaneously optimize all aspects of a system [for instance in the case of location—routing optimization problems, as noted by Nagy and Salhi (2007)]. For the TRNDP, this would mean construction of routes and determination of frequencies at the same time. Despite this, the real essence of the problem cannot be neglected. In practice, differences between results obtained through a sequential and a simultaneous approach would probably be of minor importance compared to uncertainties incorporated in the assumptions made with formulating the problem, example are travel speeds, traffic conditions in the route network, and so on. Therefore, from a planning perspective, the existing approaches seem adequate. But to our knowledge, this is a topic yet to be thoroughly investigated. Direct construction and route improvement has been examined to a lesser extent in the literature. However, modern metaheuristics such as ACO seem to be promising in this direction.

Given the above, a general framework can be derived for the TRNDP (Fig. 4). The framework includes two levels. The first level incorporates the design environment (design level), and the second handles the modeling characteristics of the problem. Framework details encompass all aforementioned elements and aspects of the TRNDP, objectives for prevailing conditions and corresponding design parameters should be selected, and an appropriate formulation—solution method consisting of network element generation and configuration supported by an optimization algorithm is implemented.

The objective of this paper was to systematically review and highlight elements of past research dealing with the transit route network design problem (TRNDP). The review revealed over sixty studies published in the last four decades that have addressed the TRNDP, each of them adopting different approaches and assumptions. Elements of these studies were categorized in a three-layer/multi-item structure and a generic framework for developing methodologies for the TRNDP was suggested. As discussed in the review, the complexity of the problem in conjunction with the anticipated level of detail and algorithmic performance has led to different approaches starting from plain analytical models to advanced metaheuristics.

Despite the large number of existing studies, the TRNDP is a field with strong potential for future research. A first direction could be the nature of the problem. Until now all studies have focused on planning daily operations. It would be interesting to systematically investigate models for different environments such as mega-events or emergencies, whose objectives, design characteristics, and solution procedures could vary significantly. Objectives are environment dependent, they are chosen for a public transportation network expected to provide services in day-to-day operations. In the cases of mega-events or emergencies, the above-mentioned objectives may not be suitable. For instance, travel time and capacity were deemed as objectives for planning some public transportation networks of that type, while operator cost was neglected (Bovy 2002; Dimitriou et al. 2006).

Attention should also be given toward improving solutions provided by models. In this sense, models will be expected to lead to more realistic, yet useful, solutions. For instance, detail enhancements can be investigated to represent the design parameters of the TRNDP more realistically, in accordance with continuous improvements in computational capabilities. Reasonable decision variables such as stop locations could be added and operational strategies could be considered either as elements preset or to be decided through the models. These would certainly require more detailed O-D matrices, even at the bus stop level. Also, policies for transfers and items related to passenger behavior (for example, waiting time, walking distances, and so on) could be improved, while for service dependent demand, which has been incorporated in some models in the form of transit demand share, efforts could be toward incorporating influences of service on total demand for travel. However, in conjunction with the above, it would be useful for researchers to investigate the opinion, needs and requirements of practitioners with respect to the outputs of existing models.

Modeling approaches can be improved by using other algorithms, already applied in problems of similar complexity such as efforts could also tackle simultaneous construction and configuration of transit routes. Further modeling with multiple objectives would be another area for further research, for example, the potential of combining existing procedures with algorithms and techniques for multiobjective optimization is of significant interest. Finally, as noted by Fan and Machemehl (2004), other directions for research would include the evaluation of existing models using larger and more complex networks and the development of decision support systems which could interact with the planners and graphically represent results produced by the models.

The paper has benefited from the constructive comments of two anonymous referees. The writers would like to thank them for their time and effort.