Keywords

1 Introduction

In the Network Design Problem (NDP) the main aim is to optimize the network configuration, optimizing a set of criteria related to a set of objectives. Relating to the problem formulation, a mono or multi-objective approach (user, public manager and community) can be followed. Relating to the problem solution, its complexity does not allow using exact algorithms (at least for real problems).

In an urban area, a design problem should consider: (i) the road network design problem (RNDP), related to link directions and signals setting at the junctions for all traffic components (car, bus, …); (ii) the transit network design problem (TNDP), related to the transit routes and frequencies. In most cases, in literature, the two problems are studied separately.

A possible RNDP classification can be made considering the variables involved in the problem. So, three set of problems can be identified: problems with discrete variables [1–7], problems with continuous variables [8–17], problems with mixed variables [18–21]. Discrete variables dealing with the road layout; continuous variables dealing with junction regulation and price (road pricing and park pricing).

The transit design consists of three main aspects: the routes, the frequencies and the scheduling. In [22–24], first indications on the routes and frequencies design are supplied, proposing heuristic approaches to generate the routes. The frequency design is based on flow maximization on the transit lines, considering also the cost management. In [25, 26], first indications on the routes and frequencies design considering the user behaviour are supplied. The scheduling design considers, generally, two topics: the vehicles and the crew scheduling. The two topics can be considered separately or joint in the design model (one of the papers relative to this topic is [27].

In this chapter, a formulation trying to link in a joint method the RNDP and the TNDP is proposed. The problem is formulated considering the route cost for transit system in the objective function of the RNDP. The design variables are, in the RNDP the road layout (topology) and the junctions regulation (link capacity); in the TNDP are the transit routes (topology) and the frequency (route capacity). In term of algorithms, two main stages can be considered: a first stage, in which the road network and the transit routes topology are designed; a second stage, in which the buses frequencies and scheduling are designed (Fig. 1).

Fig. 1
figure 1

Joint road network and transit design problem

Full size image

The highlights of this chapter can be summarized in: joint road and transit network design, a genetic algorithm codified to design reserved lanes for transit vehicles, comparing transit design in optimized and non-optimized network, testing the application of the method in a real network and comparing the result with a real transit line.

The chapter is structured as follows. In Sect. 2 the general model is proposed, in Sect. 3 a solution algorithm is presented. In Sect. 4 some numerical examples relative to the application of the model and algorithm for real system are discusses. Some conclusions and future developments are reported in Sect. 5.

2 Problem Formulation

In the problem (Fig. 1) the inputs are the supply and the demand, distinct into road demand (potential users that move using your vehicle) and the transit demand (potential users that move using the transit system). The design module (RNDP and TNDP) allows configuring the network both for private vehicles (cars, motorcycles, …) and buses. The outputs of this module are an optimized network in terms of topology and junction regulation and the optimized routes for buses. A test is performed to evaluate the results: if it is passed, a module allows designing frequencies and scheduling; else a demand split procedure is applied to evaluate the variation in the demand due the new network configuration. The output is the optimal road and transit plan.

Generally, a network design model is structured considering:

  1. 1.

    the objective function;

  2. 2.

    the design variables;

  3. 3.

    the set of constraints.

The objective function is responsible for explaining the objectives of the problem, both on mono-objective case (only an objective) and in multi-objective case (some objectives to achieve). Example of objectives are the minimum travel time, the maximum safety, the minimum management costs.

The design variables are responsible to formalize the problem, describing the aspects that can be optimized in the problem.

The set of constraints considers can be split in some subset: technical (network connection, signals, number of lanes, number of bus), economic (budget), normative (i.e. maximum CO emission) and the behavioural constraint that simulates the demand–supply interaction.

A general formulation of the design problem, considering the mono-objective case and the minimization approach is reported in Eqs. (1–4):

$$ {\text{Objective}}{:} \quad { \hbox{min} }_{f,y} \,z({\mathbf{f}},{\mathbf{y}}) $$
(1)
$$ {\text{Design variables}}{:} \quad {\mathbf{y}} \in S_{y} $$
(2)
$$ {\text{Constraints}}{:}\quad {\mathbf{f}} = {\mathbf{f}}_{\text{SNL}} ({\mathbf{c}}({\mathbf{f}},{\mathbf{y}})) $$
(3)
$$ f \in S_{f} $$
(4)

where z is the objective function, f is the link flow vector in the multimodal (road and transit) network and y is the configuration vector (design variables).

The vector f has two parts:

  • a link flow vector f (r) for road;

  • a link vector f (t) for transit.

The vector y has three parts:

  • a sub-vector y (1) for junction setting;

  • a sub-vector y (2) for link layout;

  • a sub-vector y (3) for transit routes layout.

The flow vector f is function of the link cost vector functions c with stochastic network loading function f SNL.

The vector y and the vector f belong respectively to:

  • S y the set of admissibility of design variables;

  • S f the set of admissibility of link flow.

A possible specification for the objective function is:

$$ z = z_{1} ({\mathbf{f}}^{{({\text{r}})}} ,{\mathbf{y}}^{(1)} , \, {\mathbf{y}}^{(2)} ) \, + \beta \times z_{2} ({\mathbf{f}}^{{ ( {\text{r)}}}} ,{\mathbf{f}}^{{ ( {\text{t)}}}} ,{\mathbf{y}}^{( 1)} , \, {\mathbf{y}}^{( 2)} ,{\mathbf{y}}^{( 3)} ) $$
(5)

where

  • β is a weight coefficient;

  • z 1 is the cost for the road users;

  • z 2 is the cost for the transit users.

In Eq. (5) the component z 1 is related to network design (RNDP) while the component z 2 is related to the transit routes design (TNDP and RNDP).

3 Algorithms

In this section, two classes of algorithms are considered: an algorithm for TNDP, it allows designing the transit routes; an algorithm for RNDP integrated with TNDP, it allows designing the road network. For simplicity sake, in the follows (Sects. 3.1 and 3.2) the two algorithms are treated separately, but they are correlated considering that the TNDP algorithm work on the designed road network with a feedback. To highlight this correlation, Fig. 2 shows the logical flows of the topological stage reported in Fig. 1. As mentioned in Sect. 1, the input date are the supply and the demand (distinguishing road demand and transit demand). The RNDP procedure allow obtaining an optimized road network configuration; starting from it a feasible transit network is extracted as input for TNDP, that applies a search procedure to finding an optimal topology for transit routes and evaluate the routes cost. A test is performed to evaluate the current solution, if it is passed the solution is accepted, else the demand is split between road and transit and a new iteration is performed.

Fig. 2
figure 2

Proposed algorithms for RNDP and TNDP

Full size image

3.1 Algorithms: RNDP

The output of RNDP are the best road link layout (optimizing the network layout), junctions regulation (optimizing the network in term of signals at junctions) and reserved transit lanes (optimizing the transit routes).

The algorithm implemented to solve the link layout and lane allocation (including the lane reservation) is based on genetic algorithm proposed in [18].

The genetic algorithm allows evolving an initial set of solutions (population) until achieve a goal (in our case, minimize the objective function).

Basic elements of the genetic algorithm are:

  • the selection: is the process of choosing solutions from the population (i.e. an approach is the roulette tournament);

  • the crossover: is the process of taking two solutions and producing from them one or more other solutions;

  • mutation: is the process of create a perturbation in one or more solutions.

The junctions can be solved as in [18], by using a projected gradient algorithm. Known the network layout by the solution of integer variables problem, an assignment is effected in order to calculate the objective function with the current signals setting variables, the procedure is iterated until convergence.

Another simplified way is to optimize the signals at junctions by using an approximate method (such as Webster method).

3.2 Algorithms: TNDP

Designing the transit routes, two phases are considered [28]: design of the potential routes and extraction of the final set of routes.

The design of the potential routes implies: place the last stations; individuate the feasible network (from designed road network); build the transit routes.

The last stations are placed in the neighborhood of other transport modes (like train stations or sea stations) to maximize the inter-modality and the accessibility.

The movements of a transit vehicle (a bus) are more constrained than car movements (i.e. for the vehicle shape or the vehicle length). For this reason, it is necessary to extract in the RNDP level a feasible network starting from the designed road network, eliminating some links with specific criteria (low width, low curve radius, high slope). If in the RNDP are designed reserved links for transit, the feasible network contains the reserved links.

The transit routes design is based on a constructive heuristic, implementing a greedy search. At each iteration three links type (waiting, boarding, alighting) are added, optimizing the component z 2 of Eq. (2). The link addition procedure change if in the current solution there are or there are not partial transit routes. In first case, to add the links, only the forward star of the initial node of the routes or the backward star of the final node is considered. In second case, to add the links, all the links in the feasible network are considered.

The final solution is a set of routes extracted considering the features of designed lines.

4 Application

The test application is performed on the city of Reggio Calabria (Italy).

The aim of this demo application is to highlight how change the transit design joint with an optimized network. Traditional applications in transit design field design the lines considering the demand levels (i.e. drawing the line for the more loads network links) but not considering the variations in road network as optimal lanes allocation and junctions’ regulation.

An existing transit line is considered, crossing the city from south (Airport) to north (University) and vice versa. In this test, the design of the transit line between Airport and University is considered to compare the existing and the designed transit line. For simplicity sake, the comparison is made considering the direction Airport-University; the same analysis could be done in the direction University-Airport. In all the network configurations proposed below, the transit line always passes through some interchange points (i.e. train station, sea station) that do not change in design phase.

  1. (i)

    The first configuration of the examined transit line is the present configuration, designed by the transit manager, with the aim to connect some interchange points in the city. In this context, the line touches, among others, the airport, the train station, the sea station. In Fig. 3, the continuous line shows the actual transit route and some of the main stops. A reserved lane for buses and a lane (in the same direction) for other vehicles characterize the way between the point R1 and the point R2 (Fig. 3, the reserved lanes are indicated with a bold line).

    Fig. 3
    figure 3

    Actual transit line configuration (—I) versus designed transit line in non-optimized network (···II)

    Full size image
  2. (ii)

    A second configuration is due solving the TNDP in a non-optimized road network (as in consolidate literature). The assignment on the feasible network allows identifying, at each iteration, the link with greater flow, generating the transit route between Airport and University. The generated route (dotted line in Fig. 3) differ from the actual route in the links near to the train and the sea station. The reason is that actual route wants to encourage the accessibility stations while the model for transit route design select links belonging on city centre with higher demand.

  3. (iii)

    The third configuration is the solution of the joint problem RNDP and TNDP: in this case, the transit line is designed together with the road network optimization, and the transit line configuration influences the road network design. Two cases are considered: designing reserved lanes (in addition to the existing ones) or not. In first case (III.a), the line designed in optimized network overlap the line designed in non-optimized network. In the second case (III.b), some modifications are introduced in the system, as in Fig. 4. The dotted line is the transit line in non-optimized network, whereas the dashed line is the transit line in optimized network. The main differences is the change in the transit line topology, which after the train station diverges following the reserved lanes (way between R3 and R4 in Fig. 4). Another change is in the way between R1 and R2, now dedicated only at the others vehicles (two lanes in direction north–south). The solution with reserved lanes offers a gain, in term of cost function (2), about of 5 %.

    Fig. 4
    figure 4

    Designed transit line in optimized network (- - - III.a) versus designed transit line in non-optimized network (···III.b)

    Full size image

5 Conclusion and Future Developments

In this chapter, a method for joint road and transit network design in urban area is proposed. The method consists of two main procedures: first, a road network design to optimize the link layout; second the transit routes generation in the optimized network. The consolidated literature gives the transit route generation considering only the demand and addressing the transit route on the more load links with the road network fixed. The proposed procedure want to take into account both the demand and the road network design, with a loop that ties the transit route with the road network design. In fact, the proposed problem formulation, considers jointly the road users and the transit line users and the whole objective function evaluates the road users and the transit users costs and the general management costs. In this formulation, the infrastructures in the supply is assumed rigid whereas the demand is elastic (to consider the variations in the users choice). The proposed procedure to solve the whole problem, considers two algorithms: a genetic algorithm to solve the road network design problem, a greedy algorithm to solve the transit route design.

A preliminary test in a real road network is performed, considering two different cases for network design: reserving some lanes to transit lines or not. Is emerged that reserving some lanes to the transit lanes, in this experiments, a gain for all users in the objective function is possible considering that also the road system is optimized.

The results have to be considered preliminary and future developments concern the problem extension, considering more than one transit line and updating the search algorithm.