Abstract: Urban road networks are generally shared by cars, buses and freight vehicles whose travel times are reciprocally affected (the crossed congestion phenomenon). Hence, simulating performances of urban road networks requires the development of a multimodal assignment model that takes into account the effects of reciprocal influences among vehicles on user travel choices. The proposed model is tested on a real dimension network, adopting three algorithmic approaches (external, internal and hyper-network) for its solution and comparing their performances in terms of computing times and result reliability. Finally, we discuss the effects of crossed congestion on freight path choices and the influences of freight vehicle presence on (road and transit) user choices.
INTRODUCTION
Generally, a multimodal assignment problem has to be adopted when it is necessary to estimate user flows on different transportation systems under two assumptions: network costs affect not only path choice but also modal split and at least two transportation modes are congested (i.e., their performance depends on network flows). In particular, this problem can be considered an equilibrium problem with elastic demand and can therefore be formulated as a fixed-point problem.
Elastic assignment problems can usually be classified into deterministic or stochastic equilibrium models according to the assumption on the random residual of the path choice model. In both cases, Cantarella (1997) and Cascetta (2001) proved that, with suitable assumptions on cost functions, demand functions and path choice models, it is possible to state the existence and uniqueness of the equilibrium solution. Moreover, Cantarella (1997) proposed an extension of Blum’s theorem (Blum, 1954) where he showed that under suitable assumptions on cost functions, demand functions and path choice models, it is possible to state the convergence of solution algorithms for solving the fixed-point problem.
The aim of this study is to propose an assignment model where the elasticity of demand is associated to a mode choice model, considering the phases of trip generation and distribution as rigid. Moreover, in order to apply assumptions suitable in urban contexts, we hypothesise that travel times of transit systems depend on flows of private cars and freight vehicles in the case of shared lanes and are constant (with respect to the flows) in the case of exclusive lanes.
The proposed model introduces some theoretical complications because it does not satisfy some assumptions proposed by Sheffi (1985), Oppenheim (1995) and Cantarella (1997) for stating the uniqueness of the equilibrium solution in the case of elastic demand. This problem was analysed and solved by D'Acierno et al. (2002), extending cost function assumptions in the case of a bimodal (road and transit) context. Hence, in this paper, we extend the previous model to the case in which there is a third congested system, that is the freight distribution system.
The proposed model is solved by adopting the three different approaches (external, internal and hyper-network) used to solve elastic demand assignment problems and analysing effects of freight distribution on (road and transit) user choices.
The study is structured as follows: the proposed fixed-point problem is analysed in the next section; then extensions of solution algorithms proposed by Cascetta (2001) and D'Acierno et al. (2002) for managing elastic demand problems are described. Study describes the application of the algorithms in the case of a real dimension network and compares them in terms of calculation times and reliability of solutions. Finally, appendix A proposes in detail the proof of theoretical properties of the proposed model.
PROPOSED MODEL FORMULATION
The assignment problem proposed in this paper for simulating user flows on an urban network where three transportation systems are considered (i.e., road, transit and freight systems) is based on the following assumptions:
| • | Demand is elastic at mode choice level for the road and transit systems (that is users can choose whether to travel by road or on the transit system) |
| • | Demand is rigid for the freight system (that is network performances affect only path choice and not travel demand or freight quantities) |
| • | The path choice behaviour of the transit user is pre-trip/en route (hyper-path approach proposed by Nguyen et al. (1998). Indeed, users of the transit systems are unable to determine exactly which is the first (transit) vehicle belonging to their choice set that will arrive at a certain stop/station. Therefore, under this hypothesis it is assumed that the users do not choose a predetermined path but rather a travel strategy called hyper-path |
| • | Road, transit and freight systems are affected reciprocally in terms of travel times in the case of shared lanes |
| • | Transit travel times are constant (with respect to road and freight vehicle flows) in the case of exclusive lanes. Indeed, in this case, travel times depend only on transit vehicle flows and dwelling times at stops/stations |
| • | The assignment model is multi-class with undifferentiated congestion (that is the cost function of each user category can be expressed as a linear transformation of a cost function common to all the classes and dependent on total link flows) |
| • | The average occupancy index for the road system is constant for all user categories |
| • | Capacity constraints are neglected in all transportation systems |
With the above hypotheses, the user flows on the network can be obtained by means of the interaction between three kinds of models: a supply model, that simulates transport performances depending on user flows, a demand model, that imitates user choice influenced by performances of the three considered transportation systems and a flow propagation model, that describes how path flows load links generating link flows.
The supply model can be formulated as:
| (1) |
where: Cim is the vector of path generalised costs for mode m associated to user category i; m is the generic transportation system, where m = r for the road system, m = t for the transit system and m = f for the freight system; βim is a non-negative coefficient for mode m associated to user category i, which allows the multi-class approach to be considered; Aim is the link-path incidence matrix for mode m associated to user category i; cm is the vector of link generalised costs for mode m. fr is the link flow vector of the road system (m = r); φt is the frequency vector of the transit system, which is equal to the vehicle flow vector associated to the transit system (m = t); ff is the link flow vector of the freight system (m = f); Cmi,NA is the vector of non-additive (NA) path costs for mode m associated to user category i, which expresses costs that depend only on paths of mode m (such as road tolls at motorway entrance/exit points).
Likewise, the demand model, based on the assumption that users are rational decision-makers maximising the utility associated to their choices, can be formulated as:
| (2) |
where: Fim is the path flow vector for mode m associated to user category i; Pik,m is the path choice matrix for mode m associated to user category i; dim is the travel demand vector for mode m associated to user category i.
Moreover, the flow propagation model is based on the assumption of intra-period (within day) and inter-period (day to day) stationarity (i.e., it is assumed that demand and supply remain constant over a period of time long enough to allow the system to reach a stationary or steady-state condition). This hypothesis on temporal dimensions allows the flow propagation model to be formulated as an instantaneous propagation model (i.e., path flows are instantaneously propagated on links), that is:
| (3) |
where: fim is the link flow vector for mode m associated to user category i; Bim is the link-path incidence matrix for mode m associated to user category i, which is equal to matrix Aim only in the case of road and freight system.
Indeed, the assumption of the hyper-path approach requires the use of different link-path matrices in Eq. 1 and 3 for the transit system.
Finally, it is worth noting that the link flow vector for mode m, indicated as fm, can be expressed as:
| (4) |
where: wim is the homogenisation coefficient for mode m associated to user category i, which takes into account the influence of user categories on link performances.
Combining Eq. 1, 2 and 3 with Eq. 4, the demand-supply interaction model, known as the assignment model, is obtained as a fixed-point model (Cantarella, 1997) and formulated generically as:
| (5) |
In particular, taking into account the assumptions of the proposed model, the fixed model can be characterised for each mode by means of the following relations:
| (6) |
| (7) |
| (8) |
In particular, the proposed assignment problem can be formulated via three sub-problems: a fixed-point problem with elastic demand for the road system, whose solution is vector fr*; a stochastic network loading for the transit system (due to the fact that transit user flows do not affect network performances), whose solution is vector ft^ and a fixed-point problem with rigid demand for the freight system (due to the fact that freight demand is not affected by network performances), whose solution is vector ff*.
However, the multimodal aspects are expressed by:
| • | The dependency of link cost vectors (cm) on equilibrium vehicle flow vectors of all transportation systems (fr*, φt and ff*) |
| • | The dependency of each demand vector of congested systems (road and transit systems), indicated respectively as dir and dit, on all path cost vectors of these systems (Cir and Cit) and therefore on equilibrium vehicle flow vectors of all transportation systems (fr*, φt and ff*) |
These considerations imply that, in order to solve Eq. 6-8, it is necessary to solve Eq. 6 and 8 jointly and then to implement (Eq. 4).
Extending the analysis developed by D'Acierno et al. (2002), as shown in appendix A, we may state that the fixed-point problem described by Eq. 6-8 has at least one solution if:
| • | Path choice functions of the road and freight systems (i.e., matrices Pik, r and Pik, f) are continuous |
| • | Travel demand functions of the road and the transit systems (i.e., vector dir and dit) are continuous and upper bounded |
| • | Cost functions of all transportation systems (i.e., vectors cr, ct and cf) are continuous |
| • | Each OD pair is connected |
The first three assumptions are generally satisfied by almost all functions proposed in the literature, whereas the last hypothesis is related to the network framework analysed and is generally respected.
Likewise, it is possible to extend the considerations of D'Acierno et al. (2002) in order to state the uniqueness of the equilibrium solution. In particular, as shown in appendix A, we can show that the fixed-point problem described by Eq. 6-8 has at most one solution if:
| • | Path choice functions of all transportation systems (i.e., matrices Pik, r, Pik, t and Pik, f) are additive, non-increasing with respect to generalised path costs (i.e., vectors Cir, Cir and Cif), continuous with continuous first partial derivatives |
| • | Demand functions of the road system (i.e., vector dir) are non-negative, upper bounded and non-increasing with respect to generalised path costs (i.e., vectors Cir, Cit and Cif) |
| • | Cost functions of the road and freight systems (i.e., vectors cr and cf) are increasing with respect to link flows (i.e., fr and ff) |
The first and second assumptions are satisfied by almost all functions proposed in the literature, whereas the second hypothesis is generally not satisfied. However, D'Acierno et al. (2002) showed that if one condition on a cost function is verified, also the third condition is verified. In particular, the extension of the cost function condition in the case of the proposed model can be formulated as:
| (9) |
where: clr is the l-th component of vector cr,; clt is the l-th component of vector ct; clf is the l-th component of vector cf; flr and fhrare respectively the l-th and h-th component of vector fr, with l ≠ h; φlt and φht are respectively the l-th and h-th component of vector φt, with l ≠ h; flf and fhf are respectively the l-th and h-th component of vector ff, with l ≠ h; Sfr is the feasibility set of vector fr; Sφt is the feasibility set of vector φt; Sff is the feasibility set of vector ff.
The cost function condition described in Eq. 9 can be expressed by means of the following Fig. 1 and 2.
In particular, in Fig. 1 when road flows (or equivalently bus or freight vehicle flows) are low, bus speeds are lower than freight vehicle speeds (bus travel times are higher than those of freight vehicles) and freight vehicle speeds are lower than car speeds (freight travel times are higher than those of cars). Moreover, when road flows (or equivalently bus or freight vehicle flows) increase, the speeds of the three systems tend to converge.
Likewise, Fig. 2 represents the case when the bus travel time on a link is equal to the freight travel time or road travel time plus a constant term that expresses the dwelling time at bus stops.
| Fig. 1: | First case of cost functions |
| Fig. 2: | Second case of cost functions |
However, in urban contexts it is possible to have the first diagram, the second or a linear combination of both. Since derivative operators are linear operators, that is:
| (10) |
the proposed condition, described by Eq. 9, could be always satisfied.
SOLUTION ALGORITHMS
The effectiveness of a model is related to the possibility of developing algorithms that provide solutions in reasonable computing times. Therefore we developed four solution algorithms for solving the proposed multimodal assignment problem. In particular, we provided an extension of algorithms proposed by D'Acierno et al. (2002) and based on the three algorithmic approaches (external, internal and hyper-network) for the solution of elastic demand assignment problems (as shown by Cascetta, 2001).
Based on the extension of Blum (1954) theorem, convergence of internal approach algorithms was stated under some quite general assumptions (Cantarella, 1997; Cascetta, 2001). Likewise, Sheffi (1985) and Cascetta (2001) showed that hyper-network approaches are theoretically equivalent to internal ones and hence the general assumptions of Cantarella (1997) and Cascetta (2001) allow their convergence to be stated. By contrast, the convergence of external approach algorithms was not proved in the literature. In any event, if it is possible to state that the solution exists and is unique and the external approach algorithm converges, it converges just to the equilibrium solution.Solution algorithms for all proposed approaches are based on an MSA-FA framework (Cantarella, 1997); inside this framework the stochastic network loading algorithm adopted is that proposed by Dial (1971) for road and freight systems and the modified version by Nguyen et al. (1998) for the transit system. These algorithms generate implicitly paths (a necessary requirement on real dimension networks) and the immediate calculation of the EMPU (Expected Maximum Perceived Utility) variables, which allow us to calculate the demand component in the case of elastic demand (i.e., in the case of the road and transit systems).
The algorithm proposed by Dial (1971), as well as its modified version proposed by Nguyen et al. (1998), consists of three phases:
| • | Phase 1: Dial-efficient path generation |
| • | Phase 2: Weight calculation (by which also the EMPU variables and hence travel demand vectors may be calculated) |
| • | Phase 3: Network loading |
In all three algorithmic approaches adopted, phase 1 is performed only once, since the assumption of additive path (hyper-path) choice models means that the choice set is independent of the values of generalised costs. Moreover, we applied the property of independence of network costs with regard to transit user flows. Therefore, the loading of the transit network can be performed only once, after the equilibrium flows on road and freight systems have been calculated.
Once a starting modal split has been fixed, the external approach algorithm calculates the EMPU variables of the road system by an MSA-FA algorithm (phase 2 and 3 cycles) applied on road and freight systems and the EMPU variables of the transit system by means of only one implementation of phase 2 applied on the transit system. These EMPU variables are used to calculate a new modal split, thereby recalculating the costs on the networks and the new values of the EMPU variables. When a stopping criterion on modal split is satisfied, the algorithm terminates and the corresponding flows of the road and the freight systems are the multimodal equilibrium ones, that is the solution of Eq. 6 and 8, while a last transit network loading (phase 3) has to be performed to obtain the transit flows, that is the solution of Eq. 7.
The first version of the external-approach algorithm differs from the second in the starting flow values adopted in the MSA-FA algorithms to calculate the rigid demand flows on road and freight networks. In the first case the starting flows are equal to zero; in the second, instead, they are equal to the flows obtained in the previous assignments.
Once a null starting flow vector has been fixed, the internal approach algorithm calculates the EMPU variables of both road and transit systems, applying phase 2 to all three (road, transit and freight) systems. The algorithm calculates the stochastic network loading flows on the road and the freight networks (phase 3) after the calculation of the modal split. With the obtained flows, it recalculates the EMPU variables until convergence on road and freight flows is reached, that is the solution of Eq. 6 and 8 are obtained. Also in this approach, it is necessary to perform a last transit network stochastic loading (phase 3) in order to obtain the (equilibrium) transit flows, that is the solution of Eq. 7.
The hyper-network approach algorithm executes a rigid demand assignment model on a multimodal supply network model (hyper-network) that allows the simulation of the mode choice on the network by using specific dummy links (modal diversion links). Therefore this algorithm consists in the use of a rigid demand MSA-FA algorithm (phase 2 and phase 3 cycles). This particular network framework is an extension of the hyper-network model proposed by D'Acierno et al. (2006). A scheme of the adopted hyper-network supply model is reported in Fig. 3.SOME APPLICATIONS ON A REAL DIMENSION NETWORK
The proposed algorithms were tested on a real dimension network, whose features are reported in Table 1. Comparing the transit system and the road networks, it may be noted that the link ratio is about 7:1. This explains the huge difference (about 36 times) between the computing times (reported in Table 2) of network loading for the road and freight system (phases 2 and 3 in the case of these transportation systems) and demand model performance, which also incorporates the weight calculation of the transit system (phase 2).
| Fig. 3: | The hyper-network supply model |
| Table 1: | Test network features |
A comparison among the algorithms is reported in Table 3. An important result is that the three algorithms converge to the same solution. Indeed, the maximum percentage error never exceeds 5.00% which represents the threshold used in the stopping criterion of the algorithms. However, though it was not possible to demonstrate the convergence of all solution algorithms, we numerically proved the convergence of the proposed algorithms.
Comparison between the two versions of the external algorithm shows that the second version obviously requires less stochastic loading on road and freight systems. In terms of computing times, the internal approach algorithm requires much lower times than the external ones (about 3 times as long), which can be explained by the different number of iterations required to converge (i.e., the number of required network loadings indicated in Table 3 is lower in the case of the internal approach).
Moreover, the internal and hyper-network approaches coincide both in terms of iterations and results, but in the hyper-network approach the computation times are slightly higher (about 1.20 times), since the dummy links (i.e., modal links shown in Fig. 3 increase the number of total links in the network to be examined.
| Table 2: | Computing times (Intel Core 2 Quad Q6600 - 2.40 GHz) |
| Table 3: | Comparison among algorithm approaches |
These dummy links, as described in the previous section, allow the implicit simulation of the mode choice model and therefore the demand model application is not performed in the hyper-network approach (as shown in Table 2 and 3). Indeed, as described in the previous section, the hyper-network approach simulates implicitly the mode choice model (i.e., the demand model) by means of dummy links.
Finally, in order to verify the usefulness of a multimodal approach in urban freight distribution two experiments were performed. The first aimed to analyse the presence of freight vehicles on trip choices of conventional (i.e. road and transit) users. In particular, the simulation obtained considering the proposed three-system assignment model was compared with those obtained by neglecting freight vehicles. Our results showed that the maximum difference in user flows is 60.00% in the case of the road system and 4.44% in the case of the transit system; likewise, the average difference in user flows is 6.42% in the case of the road system and 0.28% in the case of the transit system. These results show the usefulness of simulating freight and road systems jointly to obtain a better estimation of road flows; the effects on transit user flows are, instead, less important.
The second trial was based on the analysis of the influence of road and transit system vehicles on freight vehicle route choices. The simulation obtained by considering the proposed three-system assignment model was compared with a monomodal assignment model with rigid demand applied only on the freight system. In this case, results showed that the difference in freight vehicle flows is 169.39% in the maximum case and 4.94% in the average case.
Thus the two experiments showed that neglecting freight vehicle presence can substantially modify link flows. Likewise, neglecting the multimodal aspects in the urban context, that is the presence of a road and transit system, can considerably change the minimum cost path used by freight vehicles.
CONCLUSIONS AND RESEARCH PROSPECTS
The proposed multimodal assignment problem allows transportation systems in the urban context to be simulated by considering the effects of private cars and freight vehicles on congestion. Although, it is not possible to state the convergence theoretically, the developed algorithms converge to the same solution in reasonable computation times. Moreover, the comparison among the different approaches showed that, at least in the case of the analysed network, the internal-cycle algorithms are more efficient in terms of computing times.
An important result is that neglecting freight vehicles generates average differences in road and transit user flows lower than 5.00%, which is the threshold used in the stopping criterion of the algorithms, although in terms of maximum difference these values can be considerable only in the case of the road system (which may exceed 50.00%). By contrast, simulating the freight system without taking account of congestion generated by road and transit systems (i.e. considering only the freight system and neglecting any other transportation system) can generate maximum differences in freight vehicle flows higher than 169%, even if in terms of averages these values are lower than the stopping criterion threshold (set at 5.00%).
Future research should address the use of the proposed model as a simulation tool in network design problems in order to account for all transportation components in urban contexts.
APPENDIX A
In this appendix, we propose an extension of the proofs proposed by D'Acierno et al. (2002) for stating the existence and the uniqueness of the fixed-point solution described by Eq. 6-8.
The existence of the fixed-point solution: The fixed-point problem (described by Eq. 6-8) has at least one solution if:
| • | Path choice functions of the road and freight systems (i.e., matrices Pik,r and Pik,f) are continuous |
| • | Travel demand functions of the road and the transit systems (i.e., vector dir and dit) are continuous and upper bounded |
| • | Cost functions of all transportation systems (i.e., vectors cr, ct and cf) are continuous |
| • | Each OD pair is connected |
Proof: In fact, vectors fr*, ft^ and ff* are the fixed points of the compound function described by the above-mentioned equations, which under the above assumptions are continuous functions defined over a non-empty, compact and convex set (if each OD pair is connected). Moreover, these equations assume values only in the definition set; thus, all assumptions of Brouwer’s theorem on the existence of fixed points are satisfied (Cantarella, 1997; Cascetta, 2001).
The uniqueness of the fixed-point solution: The fixed point problem (described by Eq. 6-8) has at most one solution if:
| • | Path choice functions of all transportation systems (i.e. matrices Pik,r, Pik,t and Pik,f) are additive, non-increasing with respect to generalised path costs (i.e. vectors Cir, Cit and Cif), continuous with continuous first partial derivatives |
| • | Demand functions of the road system (i.e. vector dir) are non-negative, upper bounded and non-increasing with respect to generalised path costs (i.e., vectors Cir, Cit and Cif) |
| • | Cost functions of the road and freight systems (i.e., vectors cr and cf) are increasing with respect to link flows (i.e. fr and ff) |
Proof: If path choice models are defined by non-increasing functions with respect to generalised path costs and demand functions are non-negative, upper bounded and non-increasing with respect to generalised path costs, the elastic demand stochastic uncongested network assignment function (obtained by combining Eq. 2-4) is non-increasing monotone with respect to link costs, that is:
with:
where Sc is the feasibility set of vector c.
The proof is then completed by reductio ad absurdum. If two different equilibrium link flow vectors existed, f1* ≠f2*εSf (with Sf = [Sfr, Sφt, Sff]), assuming c1* = c(f1*) and c2* = c(f1*), the equilibrium definition f1* = f(c1*) and f2* = f(c2*) and the monotonicity of the stochastic uncongested network assignment function with c' = c1* and c" = c2* yields:
Since, vector φt is fixed, from the monotonicity of the road and freight cost functions (i.e., vectors cr and cf), with f' = f1*≠f" = f2*, it follows that:
Thus, there is a contradiction between the monotonicity of the cost functions and that of the stochastic uncongested network assignment function.