Full text

Turn on search term navigation

1. Introduction

The equilibrium traffic assignment problem has been widely studied since the early 1950s [1], both with respect to theoretical properties and proposing solution methods and algorithms. The Method of Successive Averages (MSA) is one of the most commonly used algorithms for solving the problem; it was proposed by References [2,3], and its convergence was stated by Reference [4]. The MSA proposed by References [2,3] operates on link flows (MSA-FA). On the other hand, Reference [5] proposed the MSA-CA which operates on link costs; while, Reference [6] devised the MSA-ACO based on Ant Colony Optimisation. Solution algorithms in the case of elastic demand were proposed and analysed by References [5,7,8].

The MSA algorithm at each iteration, k, averages the traffic flows calculated by stochastic uncongested network loading, with weight 1/k, with the results of the previous iteration, with weight (k–1)/k. Alternative step sequences (or weighting methods) were proposed, among others, by References [9,10,11]. More recently, Reference [12] proposed three revised versions of the traditional MSA method, namely: (i) Restarting MSA (RMSA), where the iteration counter is re-initialised after a specific number of iterations; (ii) Double RMSA (R2MSA), where the iteration counter is re-initialised to a variable value; (iii) Weighted MSA (WMSA), based on the self-regulated averaging method proposed by Reference [13] for solving the stochastic user equilibrium problem. The above-mentioned MSA schemes have been adopted by Reference [14] for solving a stochastic frequency-based assignment considering pre-trip/en-route path choice behaviour. Similarly, Reference [15], which extended the approach proposed in Reference [16], compared different MSA-based resolution techniques in the case of a stochastic assignment with multi-vehicle types (i.e., connected, automated, and autonomous vehicles, as well as traditional ones).

A generalisation of the averaging procedure, not limited to the traffic assignment problem, was provided by Reference [17]; while, Reference [18] proposed a refresh memory method for solving the combined assignment-control problem.

With the computing capabilities of modern PCs, the solution time of the traffic assignment problem is fairly short, also for large-size networks, if the problem has to be solved only once or a few times. Network Design Problems (NDPs) are usually solved by adopting procedures that use assignment algorithms as subroutines (bi-level approach); some reviews on NDPs can be found in References [19,20,21,22]. Indeed, for evaluating the objective function corresponding to a solution to the NDP, it is necessary to estimate traffic flows on the network. In this case, in most approaches, the assignment problem has to be solved a number of times equal to the solutions examined by the NDP algorithm; hence, several thousands of times in real-scale applications. Therefore, reducing the computing time of assignment algorithms is an important target since it may lead to a significant reduction in computing times for solving NDPs. In this context, Reference [23] proposed an MSA-based algorithm acting on the traffic flows adopted in the initialisation phases for reducing calculation times of NDPs when the topology of the network configuration remains unchanged.

With respect to the previous literature, in this paper we propose a new method that adopts a variant to the MSA algorithm: It is based on a parameter that can be set for each network to minimise the computing time. Moreover, in order to show its promising performance, it has been compared to other methods proposed in the literature. Finally, after the setting phase, the algorithm can be included within the NDP algorithm, minimising the whole computing time for solving the problem.

The remaining part of the paper is organised as follows: Section 2 introduces the model formulation; the proposed algorithm is analysed in Section 3, and Section 4 summarises the numerical results; Section 5 concludes the paper and outlines the research prospects. In Appendix A the convergence of the proposed algorithm is stated, and Appendix B presents a comparison with some MSA-based algorithms is provide. In Appendix C and Appendix D, the Network Design Problem and the algorithm used for its solution in the numerical test are illustrated.

2. Model Formulation

The traffic assignment problem consists of estimating traffic flows on a transportation network. In order to solve this problem, we need three elements: the travel demand (summarised in an Origin-Destination matrix), the transportation supply (modelled with a supply model) and the user path choice behaviour (modelled with a path choice model). Several models can be used for solving the problem depending on the transportation system (road network, mass-transit network, multimodal transportation network, etc.), the assumptions on the travel demand (fixed or variable), the approach to studying the interactions between demand and supply (user equilibrium or dynamic approach), the dependence or otherwise of link costs on flows (uncongested or congested), the assumption on the route choice model (deterministic or stochastic), and so forth. An in-depth analysis of traffic assignment models can be found elsewhere (see, for instance, Reference [24]). Even if the proposed algorithm can also be used to solve other assignment problems, in this paper, we consider the congested road network, fixed demand, user equilibrium approach and stochastic route choice model.

On a road network, the link flow vector, f, once the transport demand has been fixed, depends on link costs, and hence, on the link cost vector, c:

f = φ(c)

with:

φ(c) = AP(ATc) d

where A is the link-path incidence matrix, whose components, alp, are equal to 1 if link l belongs to path p and 0 otherwise; P is the path choice probability matrix, with a column for each od pair and a row for each path p; the generic element, Pp,od, of this matrix represents the probability that a user will use path p from origin o to destination d (if path p does not connect the od pair, Pp,od is equal to 0); d is the demand vector, whose components are the demand values dod for each od pair.

The generic cost, cl, of link l can be assumed dependent only on the flow on the same link, fl.

Formally, we can write:

c = χ(f)

Substituting (2) in (1), we obtain the following:

f = φ(χ(f))

which relates flows, f, and costs, c. Equation (3) is a fixed-point problem; the solution is represented by the equilibrium traffic flows, f*, which is congruent with the corresponding link costs, c = χ(f*).

Formally, we can write:

f* = φ(χ(f*))    or   f* = A P(ATχ(f*)) d

In this case, it may be stated, under some assumptions, that the solution to the fixed-point problem (4) exists and is unique [5] and that the MSA algorithm converges to it [4].

3. Solution Algorithm

In order to solve the fixed-point problems (4) we propose an algorithm based on the MSA general framework. The first formulation of MSA [2] generates a succession of feasible link flow vectors, f k, starting from an initial solution (usually f 0 = 0). At each iteration k, the solution fk is generated by combining traffic flows obtained by a Stochastic Uncongested Network (SUN) assignment, fSUNk = φSUN(ck), with the previous solution, f k−1

At each iteration k, in order to generate the solution fk, the results of the SUN assignment, fSUNk, are averaged, with weight 1/k, with the results of the previous iteration, f k−1, with weight (k − 1)/k:

fk = ((k − 1)/k) · f k−1 + (1/k) · fSUNk

that is:

fk = f k−1 + 1/k (fSUNk− f k−1)

Since the algorithm works directly on flows, it is also known as MSA-FA (Flow Averaging). Algorithm 1 reports the code of the traditional MSA-FA algorithm, where ε represents the stop threshold.

Algorithm 1 Traditional MSA-FA algorithm

1: k = 0

2: f0 = 0

3: do while |fSUNk − f k−1|/f k−1 ≥ ε

4: k = k + 1

5: ck = χ(f k−1)

6: fSUNk = φSUN(ck)

7: fk = f k−1 + 1/k · (fSUNk − f k−1)

8: loop

9: f * = fk

10: end

It is worth noting that the averages applied to the flows belonging to successive iterations have to be considered an algorithmic trick and should not be confused with the weights that simulate the learning process in the dynamic assignment models. Indeed, the MSA algorithms apply to stationary models, while the simulation of learning processes (comparison between expected and experienced performances) are typical of day-to-day dynamics models [24,25].

Since, as shown in Appendix B, most of the MSA-based algorithms proposed in the literature for solving the traffic assignment problem are based on a modification of the weight formulation (i.e., term 1/k in the traditional MSA algorithm), our proposal consists in providing a further variant of the MSA-FA algorithm substituting the term k in Equation (5) or (6) with the following function:

ξ(k) = 1 + (k–1) · η

where η is a parameter between 0 and 1; for η = 1 we obtain the classic MSA algorithm, and for η = 0 we obtain that fk = fSUNk (in this case the algorithm does not consider at each iteration the results of the previous ones). This method tends to muffle the weight given to f k−1 (with η < 1) with respect to the corresponding weight given with the classic MSA algorithm. The weights of f k−1, w−1, and fSUNk, wSUN, at each iteration k become:

w−1 = ((k–1) · η)/(1 + (k–1) · η)

wSUN = 1/(1 + (k–1) · η)

In Algorithm 2 the code of the generalised MSA-FA algorithm (i.e., GMSA-FA) is reported. Figure 1 reports the values at each iteration k of wSUN (equal to 1 − w−1) for values of η between 1 (classic MSA) and 0 and for the first 100 iterations.

Algorithm 2 Generalised MSA-FA algorithm

1: k = 0

2: f0 = 0

3: do while |fSUNk − f k−1|/f k−1 ≥ ε

4: k = k + 1

5: ck = χ(f k−1)

6: fSUNk = φSUN(ck)

7: fk = f k−1 + 1/ξ(k) · (fSUNk − f k−1)

8: loop

9: f * = fk

10: end

It can be noted that the weight of fSUNk decreases less rapidly for lower values of parameter η. Convergence of the proposed algorithm is stated in Appendix A, where the algorithm is shown to converge for each value of η > 0.

4. Numerical Results Numerical tests were conducted on a small test network and on two real-scale networks (an urban and a rural network). Each network, by means of the graph theory, was represented as a set of links and nodes. The links represent the phases of the trips (as for instance, the roads) and the nodes represent the transitions between two consecutive links. Among the nodes, it is possible to identify the centroid nodes that represent the origin and destination of each trip. 4.1. Small Network

The small network consisted of 16 oriented links (see Figure 2), whose link performances (i.e., the link travel times) were expressed by means of a BPR function [26], that is:

tl = (Ll/v0,l) · (1 + α · (fl/Capl)β)

where tl is the travel time associated to link l; Ll is the length of link l; vo,l is the free-flow speed associated to link l; fl is the link flow associated to link l; Capl is the capacity of link l; α and β are function parameters. The main features of the considered network are summarised in Table 1.

Bold links have higher capacity and free-flow speed with respect to the others. We assume that nodes 1, 2, 3 and 4 are also the origins and destinations of the trips, according to the OD vector, d, reported in Table 2. In the tests, we adopted Multinomial Logit as the stochastic path choice model and assumed that the cost of each link was equal to the running time expressed in minutes with parameter θ equal to 0.5 (coefficient of variation about 0.2). We implemented the proposed algorithm in Visual Basic. We tested the proposed algorithm with the following values of parameter η: 1 (classic MSA), 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 0.05, 0.01, 0. For each value, we tested the OD vector reported in Table 2 multiplied by the following coefficients: 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8, and 2.0. The use of different OD vectors, as well as different multipliers, is to analyse the algorithm’s performance for different congestion levels. Indeed, the vectors thus obtained produce average saturation degrees (flow/capacity ratio) on the network between 0.249 and 0.838, as reported in Table 3. The convergence threshold was assumed to be equal to 1% for all tests.

In all cases, the proposed algorithm was able to reduce the iterations for the convergence with some values of η lower than 1 (MSA). It can be noted that, upon reducing the value of η, the number of iterations starts to decrease until a minimum value is reached. The number of iterations then begins to increase until the case of η = 0 when, according to also to the theoretical properties examined in Appendix A, the algorithm may not converge.

In Table 4, the number of iterations required for convergence for all cases is reported (the algorithm was stopped in any event when the iterations reached 999); minimum values are written in bold. In the same table, the percentage variations in terms of iteration number are reported. However, it is worth noting that all variants of the algorithm provide the same results. The difference among them is only the number of iterations necessary to achieve the convergence condition. In Figure 3, the results of Table 4 are summarised.

Note that the reduction in the number of iterations, and hence, in computing time, provided by the proposed algorithm can be very significant for medium-high congested networks, i.e., up to −61% compared with the traditional version of the MSA algorithm. 4.2. Real-Scale Urban Network

The real-scale urban test network is the network of Benevento, a town in the south of Italy with about 61,000 inhabitants. The network, as represented in Figure 4, has 1577 oriented links, comprising about 216 km of roads, 678 nodes and 80 centroids (66 internal and 14 external). The peak-hour OD matrix was made available by studies carried out while drawing up the Urban Traffic Plan. The route choice model is Multinomial Logit with an implicit enumeration of paths according to the algorithm proposed in Reference [27].

In order to test the proposed algorithms under several network congestion levels, over the available OD matrix, seven other matrices were generated, multiplying all cells of the OD matrix by the following factors: 0.6, 0.8, 1.2, 1.4, 1.6, 1.8, and 2.0. The corresponding average saturation degrees are summarised in Table 5.

On this network, we tested the proposed algorithm with the same values of parameter η as those adopted for the small test network; we tested the algorithm with two different values of the coefficient of variation (standard deviation to mean ratio), Cv, equal to 0.10 and 0.05. Moreover, in these cases, the proposed algorithm was able to reduce the iterations for convergence with some values of η lower than 1 (MSA). In this case, the best performances were obtained with values between 0.4 and 0.6 (see Table 6) for Cv = 0.10 and between 0.3 and 0.6 (see Table 7) for Cv = 0.05; the reductions in the number of iterations reached −76% (Cv = 0.10) and −79% (Cv = 0.05) with respect to the traditional version of the MSA algorithm. In Figure 5 and Figure 6, the results of Table 6 and Table 7 are illustrated. Moreover, in this case, the utility of the proposed algorithm is more significant for medium-high demand levels.

4.3. Real-Scale Rural Network

The real-scale rural test network is the regional road network of Campania, an Italian Region with more than 5.8 million inhabitants. The network, as represented in Figure 7, has 764 road links, representing about 8700 km of roads, 262 road nodes and 91 centroids.

We tested the proposed approach considering the OD matrix in the morning peak-hour, where the total trips are 165,328 veh/h; we also tested values of demand between 0.6 and 2.0 times the actual value, producing an average saturation degree between 0.4 and 1.25 (see Table 8). Moreover, in this case, we use the Multinomial Logit route choice model with the implicit enumeration of paths [27].

On this network, we tested the proposed algorithm with the same values of parameter η previously adopted, assuming a coefficient of variation equal to 0.3. Moreover, in these cases, the proposed algorithm was able to reduce the iterations for convergence with some values of η lower than 1 (MSA). The best performances were obtained with values between 0.3 and 0.6 (see Table 9); the reductions in the number of iterations reached −69% with respect to the traditional version of the MSA algorithm. In Figure 8, the results of Table 9 are illustrated.

4.4. Application to a Network Design Problem

The proposed algorithm was tested inside a procedure for solving Network Design Problem (NDP) on the rural real-scale network described in Section 4.3. In particular, we considered a network capacity expansion problem [28] where there were limited resources for improving the performances of a rural road network. In this problem, the current configuration of the road network is known, and no other roads can be added to it; instead, each existing road can be improved, increasing its capacity and free-flow speed. The decision variables of this problem are binary, yi = 0/1, where yi = 1 indicates that road i is improved in the solution, while yi = 0 indicates that road i remains in the starting configuration. The details of NDP and of its model formulation are reported in Appendix C.

In order to compare the results obtained with the proposed muffled algorithm and the classic MSA, we tested the Neighbourhood Search Algorithm (NSA) with steepest descent method; it was used, for instance, in References [28,29]. A brief description of the algorithm is reported in Appendix D.

The tests were conducted under the actual demand (1.0 d), and therefore, assuming the parameter η = 0.5 in the muffled proposed algorithm, since it is the best value for this demand level (see Table 9). The results of the comparison between MSA and muffled algorithm are summarised in Table 10; note that the computing time saved is about 44% (over 2.5 h). The different numbers of examined neighbourhoods and objective function values are only due to the convergence test; indeed, even if the convergence test is the same, the flows generated at each iteration of the algorithms can be slightly different and may influence the final solution. In Figure 9, the comparison among MSA and muffled algorithm is reported in terms of computing times and objective function values. These results underline the utility of the proposed algorithm inside Network Design Problem solution procedures; indeed, we have to consider also that several meta-heuristic algorithms use NSAs as subroutines (Scatter Search, Tabu Search, etc.), and then, the computing time saved should be multiplied by the number of NSAs performed for reaching the final solution.

5. Conclusions and Research Prospects The results obtained on the small and on the real-scale networks show that the proposed algorithm is able to reduce the number of iterations for convergence, and hence, computing times compared with the classic MSA approach; in particular, the reductions arrive in percentage up to –79% with respect to the classic MSA for the best value of the parameter. On all networks the results are similar, showing that the benefits of the proposed algorithm are significant for medium-high congested demand levels (average saturation degrees over about 0.4); less significant, but not negligible, are the benefits for lower demand levels.

In all tests, the best values of parameter η lie between 0.3 and 0.6. An important characteristic of the proposed algorithm is that there is a parameter that can be opportunely chosen, so to optimise the performances before starting with network design procedure; moreover, examining Figure 3, Figure 5, Figure 6 and Figure 8 it is evident that, especially for medium-high levels of demand, a minimum can be found. In our test, we adopt a 0.1 step, but the parameter η can assume any value between 1 (MSA) and 0 (0 excluded), and therefore, other values can be tested in order to find the one that minimises the computing times.

The reduction in computing times can be not important if the assignment procedure is performed only once or a few times: with current computing capabilities, the savings are lower than a minute on the real-scale network. By contrast, if the assignment is a subroutine of the Network Design Problem, that requires the calculation of the equilibrium traffic flows many thousands of times, the reduction in computing time of an assignment is transferred to the computing time of the network design algorithm, allowing as much as several days to be saved in the calculation. In our test on the rural road network, the proposed algorithm is able to save about 44% of computing time, equivalent to about 2.5 h for a single NSA procedure. Future research will focus on testing other real-scale networks, testing the algorithm on multimodal networks and under the assumption of elastic demand and proposing a similar algorithm for solving the combined assignment-control problem. Moreover, testing the proposed algorithm within other real-scale network design procedures will be the subject of future studies.

Figure 1. Values of weights wSUN.

Figure 2. Small network.

Figure 3. Results on the small network.

Figure 4. Urban real-scale network.

Figure 5. Results on the urban real-scale network (Cv = 0.10).

Figure 6. Results on the urban real-scale network (Cv = 0.05).

Figure 7. Rural real-scale network.

Figure 8. Results on the rural real-scale network.

Figure 9. Comparison between algorithms in terms of computing times vs. objective function values.

Link Length (km) Capacity (veh/h) Free-Flow Speed (km/h) BPR Param. α BPR Param. β
1–521800602.04.0
5–121800602.04.0
1–321800502.04.0
3–121800502.04.0
3–633600900.24.0
6–333600900.24.0
5–623600800.24.0
6–523600800.24.0
5–241800502.04.0
2–541800502.04.0
6–251800702.04.0
2–651800702.04.0
6–453600900.24.0
4–653600900.24.0
4–231800602.04.0
2–431800602.04.0

Origin Destination OD Flow (veh/h)
121700
21600
13500
31700
14650
41100
23800
32450
24750
42450
341250
43200

Matrix 0.6 d 0.8 d 1.0 d 1.2 d 1.4 d 1.6 d 1.8 d 2.0 d
Av. Sat. Degree0.2490.3320.4150.4990.5830.6680.7530.838

Iterations Needed for Convergence
Matrix 0.6 d 0.8 d 1.0 d 1.2 d 1.4 d 1.6 d 1.8 d 2.0 d
η = 1(MSA)784596168287422582
η = 0.9674080147239350478
η = 0.8683471126201291397
η = 0.75113063107170247329
η = 0.6514295492143209279
η = 0.5415274881125183243
η= 0.4413234373112163237
η = 0.3511244681133208310
η = 0.26153466117194305457
η = 0.182661123222374591892
η = 0.051245112233429727>999>999
η = 0.0131182504>999>999>999>999>999
Percentage Variations with Respect to MSA
Matrix0.6 d0.8 d1.0 d1.2 d1.4 d1.6 d1.8 d2.0 d
η = 1(MSA)--------
η = 0.9−14%−13%−11%−17%−13%−17%−17%−18%
η = 0.8−14%0%−24%−26%−25%−30%−31%−32%
η = 0.7−29%38%−33%−34%−36%−41%−41%−43%
η = 0.6−29%75%−36%−44%−45%−50%−50%−52%
η = 0.5−43%88%−40%−50%−52%−56%−57%−58%
η = 0.4−43%63%−49%−55%−57%−61%−61%−59%
η = 0.3−29%38%−47%−52%−52%−54%−51%−47%
η = 0.2−14%88%−24%−31%−30%−32%−28%−21%
η = 0.114%225%36%28%32%30%40%53%
η = 0.0571%463%149%143%155%153%--
η = 0.01343%2175%1020%-----

In bold are reported the best results.

Matrix 0.6 d 0.8 d 1.0 d 1.2 d 1.4 d 1.6 d 1.8 d 2.0 d
Av. Sat. Degree0.2460.3240.4000.4720.5450.6180.6910.764

Iterations Needed for Convergence
Matrix 0.6 d 0.8 d 1.0 d 1.2 d 1.4 d 1.6 d 1.8 d 2.0 d
η = 1(MSA)58173250525561
η = 0.958142536383943
η = 0.858121927282832
η = 0.758101520202129
η = 0.65791215152026
η = 0.54791112152125
η = 0.447101112182427
η = 0.348111315213033
η = 0.2410141720284145
η = 0.1414222833497479
η = 0.0542237485888136146
η = 0.01477147196244385619664
Percentage Variations with Respect to MSA
Matrix0.6 d0.8 d1.0 d1.2 d1.4 d1.6 d1.8 d2.0 d
η = 1(MSA)--------
η = 0.90%0%−18%−22%−28%−27%−29%−30%
η = 0.80%0%−29%−41%−46%−46%−49%−48%
η = 0.70%0%−41%−53%−60%−62%−62%−52%
η = 0.60%−13%−47%−63%−70%−71%−64%−57%
η = 0.5−20%−13%−47%−66%−76%−71%−62%−59%
η = 0.4−20%−13%−41%−66%−76%−65%−56%−56%
η = 0.3−20%0%−35%−59%−70%−60%−45%−46%
η = 0.2−20%25%−18%−47%−60%−46%−25%−26%
η = 0.1−20%75%29%−13%−34%−6%35%30%
η = 0.05−20%175%118%50%16%69%147%139%
η = 0.010%0%−18%−22%−28%−27%−29%−30%

In bold are reported the best results.

Iterations Needed for Convergence
Matrix 0.6 d 0.8 d 1.0 d 1.2 d 1.4 d 1.6 d 1.8 d 2.0 d
η = 1(MSA)58204749495359
η = 0.957163436363842
η = 0.847132526263438
η = 0.746101819213539
η = 0.64691414203134
η = 0.53681014243436
η = 0.43591016274043
η = 0.336111020345054
η = 0.238141227467176
η = 0.131123264984132141
η = 0.05417394590158251269
η = 0.01454160186402724>999>999
Percentage Variations with Respect to MSA
Matrix0.6 d0.8 d1.0 d1.2 d1.4 d1.6 d1.8 d2.0 d
η = 1(MSA)--------
η = 0.90%−13%−20%−28%−27%−27%−28%−29%
η = 0.8−20%−13%−35%−47%−47%−47%−36%−36%
η = 0.7−20%−25%−50%−62%−61%−57%−34%−34%
η = 0.6−20%−25%−55%−70%−71%−59%−42%−42%
η = 0.5−40%−25%−60%−79%−71%−51%−36%−39%
η = 0.4−40%−38%−55%−79%−67%−45%−25%−27%
η = 0.3−40%−25%−45%−79%−59%−31%−6%−8%
η = 0.2−40%0%−30%−74%−45%−6%34%29%
η = 0.1−40%38%15%−45%0%71%149%139%
η = 0.05−20%113%95%−4%84%222%374%356%
η = 0.01−20%575%700%296%720%1378%--

In bold are reported the best results.

Matrix 0.6 d 0.8 d 1.0 d 1.2 d 1.4 d 1.6 d 1.8 d 2.0 d
Av. Sat. Degree0.400.530.650.770.901.011.131.25

Iterations Needed for Convergence
Matrix 0.6 d 0.8 d 1.0 d 1.2 d 1.4 d 1.6 d 1.8 d 2.0 d
η = 1(MSA)1926262936546370
η = 0.91632202227384651
η = 0.81424181721283339
η = 0.71219131417232630
η = 0.61015111114182126
η = 0.5912101114172226
η = 0.4811111316212735
η = 0.3710121519263444
η = 0.2912162127364862
η = 0.113192635476387115
η = 0.051931456184117163218
η = 0.0160114>999258366525747>999
Percentage Variations with Respect to MSA
Matrix0.6 d0.8 d1.0 d1.2 d1.4 d1.6 d1.8 d2.0 d
η = 1(MSA)--------
η = 0.9−16%23%−23%−24%−25%−30%−27%−27%
η = 0.8−26%−8%−31%−41%−42%−48%−48%−44%
η = 0.7−37%−27%−50%−52%−53%−57%−59%−57%
η = 0.6−47%−42%−58%−62%−61%−67%−67%−63%
η = 0.5−53%−54%−62%−62%−61%−69%−65%−63%
η = 0.4−58%−58%−58%−55%−56%−61%−57%−50%
η = 0.3−63%−62%−54%−48%−47%−52%−46%−37%
η = 0.2−53%−54%−38%−28%−25%−33%−24%−11%
η = 0.1−32%−27%0%21%31%17%38%64%
η = 0.050%19%73%110%133%117%159%211%
η = 0.01216%338%-790%917%872%1086%-

In bold are reported the best results.

MSA (η = 1.0) Muffled (η = 0.5) % Difference
Examined solutions601962233.39%
Examined neighbourhoods59613.39%
SNLs72,89339,103−46.36%
Computing time [h]5.833.25−44.18%
Starting objective function value [€]38,010,674,17437,971,126,906
Final objective function value [€]29,363,169,24829,305,075,507
% variation of objective function value−22.75%−22.82%

Author Contributions

Conceptualisation, M.G. and L.D.; Data curation, M.B., M.G., M.M., L.D.; Formal analysis, M.G. and L.D.; Investigation, M.G. and L.D.; Methodology, M.G. and L.D.; Validation, M.B. and M.M.; Writing-original draft, M.B., M.G., M.M., L.D.; Writing-review and editing, M.B., M.G., M.M., L.D. All authors have read and agreed to the published version of the manuscript.

Funding

This research was partially funded by Federico II University of Naples (Italy), grant number 000009-ALTRO-R-2020-LD "Department research DICEA" and by University of Sannio, University Research Fund FRA_2018.

Conflicts of Interest

The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results.

Appendix A. Theoretical Properties

There are three theoretical properties of a mathematical problem and its solution algorithm: existence, uniqueness and convergence. The first two properties are related to the mathematical problem and consist in proving that there is at least one solution (existence), and there is at most one solution (uniqueness). The combination of these two properties implies that the solution to the problem exists and is unique.

Once the existence and uniqueness of the problem are stated, it is necessary to adopt or develop suitable solution algorithms that are able to provide the numerical solution to the problem. Hence, it is necessary to state theoretically the convergence (i.e., the ability to provide the solution in a finite number of iterations) of the proposed algorithms.

The conditions ensuring the existence and the uniqueness of traffic assignment problem can be found in Reference [5]. As for convergence, the same paper proposed an extension of Blum's theorem [30] where it was shown that a convergent solution algorithm for solving the fixed-point problem of a functiony=λ(x)which satisfies some suitable conditions could be formulated by the following recursive equation:

xk+1=xk+μk (λ(xk)-xk)withxk∈Sx

If the sequence{μk}k>0satisfies the following conditions:

∑k>0μk=+∞

∑k>0(μk)2=M<+∞

In particular, the above-mentioned suitable conditions are:

1. x∈Sxandy∈SxwhereSxis a non-empty, compact and convex set;

2. a unique solution to the fixed-point problemx*=λ(x*);

3. a functionφ(x)≥0∀x∈Sxwhereφ(x)is continuous with first∇φ(x)and second∇2φ(x)derivative continuous;

4. ∇2φ(x)T[λ(x)-x]<0∀x∈Sx,x∉Sx˜and∇2φ(x˜)T[λ(x˜)-x˜]=0∀x˜∈Sx˜whereSx˜⊆Sxandx*∈Sx˜;

5. |φ(x)-φ(x*)|>0∀x∈Sx,x∉Sx˜and|φ(x˜)-φ(x*)|=0∀x˜∈Sx˜;

6. xT ∇2φ(x')x=M<+∞∀x,x'∈Sx.

In Reference [5], it is showed that if the sequence{μk}k>0satisfies the condition:

μk∈[0,1]

then the elements of the sequence described by Equation (A1) belong to set Sx, which is convex. Moreover, by fixing∇φ(x)=c(x)-c*, withx=fandc*=c(f*), all Conditions (1)-(6) are satisfied. Hence, the convergence proof is only related to checking Conditions (A2)-(A4).

Finally, Reference [5] showed that the traditional approach of MSA, i.e.,ξ(k)=k, satisfies (A2)-(A4) conditions, since:

∑k>01ξ(k)=∑k>01k=+∞

∑k>0(1ξ(k))2=∑k>01k2=π6<+∞

In the case of the proposed generalised function, i.e., ξ(k) = 1 + ((k - 1) ⋅ η), condition (A4) is satisfied, and since fork→+∞we obtainξ(k)~η⋅k, it is possible to show that:

∑k>01ξ(k)~∑k>01η⋅k=1η⋅∑k>01k=+∞

∑k>0(1ξ(k))2~∑k>01(η⋅k)2=1η2⋅∑k>01k2=1η2⋅π6<+∞

i.e., all convergence conditions are satisfied for the proposed algorithm for each value of η > 0.

Appendix B. Algorithm Performance Comparison

Most of the MSA-based algorithms proposed in the literature for solving the traffic assignment problem are based on a modification of the weight formulation (i.e., term 1/k in the traditional MSA algorithm) by adopting a 1/ξ(k) function, that is:

fk = fk-1 + 1/ξ(k) (fSUNk - fk-1)

The differences in formulation among these algorithms are related to the adopted ξ(k) function. Indeed, the traditional MSA algorithm [2,3] assumes:

ξ(k) = k

Likewise, our proposal described in Section 3 adopts:

ξ(k) = 1 + (k-1) ⋅ η

Obviously, in the case of η = 1, our proposal provides the traditional MSA formulation, that is (A11) degenerates into (A10).

In order to provide some comparisons in terms of convergence speed of the proposed algorithm with some other MSA-based algorithms, we have considered:

1. the Refresh Memory method (RM), also indicated as Restarting MSA method (RMSA), proposed by Reference [18] and applied by Reference [12], whose ξ(k) function may be formulated as follows:

ξ(k) = 1, 2, ..., ζ, 2, 3, ..., 2 ζ, 4, 5, ..., 4 ζ, ..., x, x+1, ..., x ζ, ...

with:

x integer x = 1, 2, 4, 8, ...

where we have assumed ζ = 10 (method acronym 'RM 10') as proposed by Reference [18];

2. the Polyak method (POL) [9], whose ξ(k) function is formulated as follows:

ξ(k) = k2/3

3. the Nagurney and Zhang method (NAZ) [10], whose ξ(k) function is formulated as follows:

ξ(k) = 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ..., x, x, ..., x (x times), ...

4. the Bar-Gera and Boyce method (BGB) [11], whose ξ(k) function is formulated as follows:

ξ(k) = ζ

where we have assumed ζ equal to 5 (method acronym 'BGB 5') and equal to 10 (method acronym 'BGB 10')

Our proposal has been classified as muffled method by adopting the acronym 'M η', so that 'M 1' represents the traditional MSA formulation.

The comparison among algorithm formulations has been implemented in the case of the urban network of Benevento (described in Section 4.2) by adopting a Cv value equal to 0.05. Numerical results are shown in Table A1 and Figure A1.

Table

Table A1.Comparison among MSA-based algorithms.

Table A1.Comparison among MSA-based algorithms.

Iterations Needed for Convergence
Matrix 0.6 d 0.8 d 1.0 d 1.2 d 1.4 d 1.6 d 1.8 d 2.0 d
M 1 (MSA)58204749495359
M 0.957163436363842
M 0.847132526263438
M 0.746101819213539
M 0.64691414203134
M 0.53681014243436
M 0.43591016274043
M 0.336111020345054
M 0.238141227467176
M 0.131123264984132141
M 0.05417394590158251269
M 0.01454160186402724>999>999
RM 1058121515254546
POL4681115325762
NAZ45912194596108
BGB 5911152020>999>999>999
BGB 10152130393939>999>999
Percentage Variations with Respect to MSA
Matrix0.6 d0.8 d1.0 d1.2 d1.4 d1.6 d1.8 d2.0 d
M 1 (MSA)--------
M 0.90%-13%-20%-28%-27%-27%-28%-29%
M 0.8-20%-13%-35%-47%-47%-47%-36%-36%
M 0.7-20%-25%-50%-62%-61%-57%-34%-34%
M 0.6-20%-25%-55%-70%-71%-59%-42%-42%
M 0.5-40%-25%-60%-79%-71%-51%-36%-39%
M 0.4-40%-38%-55%-79%-67%-45%-25%-27%
M 0.3-40%-25%-45%-79%-59%-31%-6%-8%
M 0.2-40%0%-30%-74%-45%-6%34%29%
M 0.1-40%38%15%-45%0%71%149%139%
M 0.05-20%113%95%-4%84%222%374%356%
M 0.01-20%575%700%296%720%1378%--
RM 100%0%-40%-68%-69%-49%-15%-22%
POL-20%-25%-60%-77%-69%-35%8%5%
NAZ-20%-38%-55%-74%-61%-8%81%83%
BGB 580%38%-25%-57%-59%---
BGB 10200%163%50%-17%-20%-20%--

In bold are reported the best results.

Numerical results have shown that the proposed approach (i.e., the muffled method), at least in the case under consideration (the urban network of Benevento with a Cv coefficient equal to 0.05) almost always provides the best results, i.e., it requires the minimum number of iterations to reach convergence.

It is worth noting that, although the convergence can be demonstrated theoretically (as already shown in Appendix A), a theoretical proof cannot be performed in the case of the convergence speed property which represents an empirical element to be verified by means of numerous and appropriate tests.

Applsci 10 05698 g0a1 550

Figure A1.Comparison among MSA-based algorithms.

Figure A1.Comparison among MSA-based algorithms.

However, although it is not possible to generalise the optimal performance of the proposed methodology in an absolute way, the results obtained give hope that at least the proposed method can be included among the ones providing optimal performances. Obviously, the confirmation of this statement can only be obtained through a large number of tests in the case of different networks both in terms of context (urban vs. rural), network dimension (urban, provincial or regional network), demand and/or congestion levels.

Appendix C. Network Design Problem (NDP)

The NDP tackled in the test reported in Section 4.4 is a network capacity expansion problem where there are limited resources for improving the performances of a rural road network. The problem is the same tackled in Reference [28], slightly simplified, considering only the demand in the morning peak-hour. The problem is formulated as follows:

yopt = Arg y min (β1 ⋅ (Σl cl(y, fl*(y)) ⋅ fl*(y)) + β2 ⋅ (Σi yi cri) + β3 ⋅ (Σl (Reckm ⋅ Σl fl*(y) ⋅ Ll)))

subject to:

yi = 0/1 ∀ i ∈ I

Σi yi cri ≤ B

f*(y) = AP(ATχ(f*, y)) d

where yi is the decision variable related to road i; y is the decision variable vector; β1, β2 and β3 are the weights of the objective function terms; cl(.) is the cost function on road link l; fl* is the equilibrium flow on road link l; f* is the equilibrium flow vector; cri represents the cost of the improving intervention on road i (on an hourly basis, assuming a useful life of the intervention of 20 years); Reckm is the average environmental cost produced by a car travelling 1 km (€/km); Ll is the length of road link l; B is the total available budget (on an hourly basis); A is the link-path incidence matrix; P is the path choice probability matrix; χ( ) is the cost function vector; d is the demand vector.

The objective function to be minimised, shown in (A17), is given by the sum of user costs, improvement costs and environmental costs in terms of air pollution produced by cars. Other objective function formulation could also have been used (for instance, which would have considered the impact of the design solutions on road accident phenomena or on the severity of accidents) which would obviously have produced different optimal solutions. But the purpose of this application is to show the benefits of adopting the proposed assignment algorithm in providing the same solution as traditional algorithms, but in significantly shorter calculation times, rather than providing an analysis of the best objective function to be used in network design problems.

However, the decision variable yi is equal to 1 if the road i is improved, 0 otherwise. Equation (A18) identifies the constraint on the binary nature of decision variables, Equation (A19) is the budget constraint and Equation (A20) represents the equilibrium assignment constraint.

In order to apply the proposed model to test network described in Section 4.3, we have to identify the roads, i, that can be improved, and for each of them, the corresponding improvement costs. Each road, i, is composed by several road links, l. In this test network, we identify 102 roads, and therefore, 102 decision variables, yi. In Figure A2, the 102 roads are reported. In Table A2 the possible interventions are summarised, in terms of performance improvements and costs.

Applsci 10 05698 g0a2 550

Figure A2.Identification of decision variables.

Figure A2.Identification of decision variables.

Table

Table A2.Intervention table.

Table A2.Intervention table.

Road Current Configuration Improved Configuration Road Current Configuration Improved Configuration
v0 Cap v0 Cap cri (€/h) v0 Cap v0 Cap cri (€/h)
1704000110450027.12525020007040007.10
2704000110450030.14535020007040004.66
3704000110450036.40545020007040003.62
4704000110450012.29555020007040009.51
5704000110450031.54565020007040004.53
6704000110450030.63575020007040003.35
7704000110450068.125850200070400011.13
8704000110450051.39595020007040006.52
9704000110450028.216050200070400011.95
10704000110450037.67615020007040008.32
11704000110450035.93625020007040003.58
12704000110450021.26635020007040004.94
13704000110450019.99645020007040000.28
14704000110450013.14655020007040002.85
15704000110450020.73665020007040004.59
16704000110450016.526750200070400011.33
1770400011045004.73685020007040007.47
18704000110450012.07695020007040003.09
19704000110450027.58705020007040001.40
20704000110450014.78715020007040005.40
2150200070400010.48725020007040005.67
225020007040005.75735020007040002.65
2350200070400011.24745020007040000.42
2450200070400015.75755020007040002.50
2550200070400014.69765020007040000.73
265020007040001.14775020007040006.04
274015005020005.79785020007040000.80
284015005020006.23795020007040002.82
2950200070400010.15805020007040003.12
305020007040004.53815020007040002.60
3150200070400016.17825020007040005.69
325020007040004.038350200070400011.31
334015005020004.168450200070400011.98
344015005020003.39855020007040002.03
354015005020008.49865020007040003.24
364015005020002.22875020007040001.33
374015005020004.15885020007040006.07
385020007040007.59895020007040002.72
395020007040007.86905020007040004.18
405020007040009.18915020007040004.51
415020007040003.91925020007040002.33
4250200070400010.89935020007040008.02
435020007040003.93945020007040007.16
445020007040006.18955020007040007.07
455020007040009.17965020007040001.29
465020007040001.23975020007040001.25
475020007040007.699850200070400010.69
485020007040008.38995020007040001.66
495020007040006.1210050200070400010.51
505020007040005.331015020007040009.63
515020007040008.131025020007040002.63

Appendix D. Network Design Solution Algorithms

In order to solve the NDP described in Appendix C, we have used a steepest descent Neighbourhood Search Algorithm (NSA); this algorithm was previously used for solving NDPs as a subroutine of meta-heuristic algorithms, among others, by References [28,29].

Given a solution, y, the set of solutions that can be obtained from solution y changing only one value of a variable yi, from 0 to 1 or vice versa, is called neighbourhood of y, N(y); note that other kinds of neighbourhoods can be defined, depending on the kind of problem and on the dimension of neighbourhood (for instance, changing more than one variable per time). The NSA, starting from a solution, yk, generates the following solution, yk+1, so that:

yk+1 ∈ N(yk)

and, with the steepest descent approach,

z(yk+1) = Min {z(y); ∀ y ∈ N(yk)}

where z(y) formally represents the objective function. The procedure then generates, at each iteration, a solution better than the previous one, choosing, among all solutions belonging to the neighbourhood, the one with the best objective function value. The procedure ends when solution yk is a local optimum, that is when:

z(yk) ≤ z(y) ∀ y∈ N(yk)

This algorithm is able to find a local optimum, and therefore, is often used inside meta-heuristic algorithms that need local search subroutines. In the test reported in this paper, we use the NSA only one time, starting from the current solution: y0 = 0.

1. Wardrop, J.G. Some theoretical aspects of road traffic research. Proc. Inst. Civ. Eng. Part II 1952, 1, 325-378.

2. Sheffi, Y.; Powell, W.B. A comparison of stochastic and deterministic traffic assignment over congested networks. Transp. Res. Part B Methodol. 1981, 15, 53-64.

3. Sheffi, Y.; Powell, W.B. An algorithm for the equilibrium assignment problem with random link times. Networks 1982, 12, 191-207.

4. Powell, W.B.; Sheffi, Y. The convergence of equilibrium algorithms with predetermined step sizes. Transp. Sci. 1982, 6, 45-55.

5. Cantarella, G.E. A general fixed-point approach to multimodal multi-user equilibrium assignment with elastic demand. Transp. Sci. 1997, 31, 107-128.

6. D'Acierno, L.; Montella, B.; De Lucia, F. A stochastic traffic assignment algorithm based on Ant Colony Optimisation. Lect. Notes Comput. Sci. 2006, 4150, 25-36.

7. Cantarella, G.E.; de Luca, S.; Di Gangi, M.; Di Pace, R. Stochastic equilibrium assignment with variable demand: Literature review, comparisons and research needs. WIT Trans. Built Environ. 2013, 130, 349-364.

8. Cantarella, G.E.; Cartenì, A.; de Luca, S. Stochastic equilibrium assignment with variable demand: Theoretical and implementation issues. Eur. J. Oper. Res. 2015, 241, 330-347.

9. Polyak, B.T. New method of stochastic approximation type. Automat. Rem. Contr. 1990, 51, 937-946.

10. Nagurney, A.; Zhang, D. Projected Dynamical Systems and Variational Inequalities with Applications; Kluwer: Boston, MA, USA, 1996.

11. Bar-Gera, H.; Boyce, D. Solving a non-convex combined travel forecasting model by the method of successive averages with constant step sizes. Transp. Res. Part B Methodol. 2006, 40, 351-367.

12. Cantarella, G.E.; De Luca, S.; Di Gangi, M.; Di Pace, R. Approaches for solving the stochastic equilibrium assignment with variable demand: Internal vs. external solution algorithms. Optim. Methods Softw. 2015, 30, 338-364.

13. Liu, H.X.; He, X.; He, B. Method of Successive Weighted Averages (MSWA) and self-regulated averaging schemes for solving stochastic user equilibrium problem. Netw. Spat. Econ. 2009, 9, 485-503.

14. Di Gangi, M.; Cantarella, G.E.; Vitetta, A. Solving stochastic frequency-based assignment to transit networks with pre-trip/en-route path choice. EURO J. Transp. Logist. 2019, 8, 661-681.

15. Cantarella, G.E.; Di Febbraro, A.; Di Gangi, M.; Giannattasio, O. Solving stochastic assignment to transportation networks with TVs and AVs. Transp. Res. Procedia 2020, 42, 7-18.

16. Cantarella, G.E.; Di Febbraro, A. Transportation Systems with Autonomous Vehicles: Models and algorithms for equilibrium assignment. Transp. Res. Procedia 2017, 27, 349-356.

17. Mokkadem, A.; Pelletier, M. A generalization of the averaging procedure: The use of two-time-scale algorithms. SIAM J. Control. Optim. 2011, 49, 1523-1543.

18. Cascetta, E.; Gallo, M.; Montella, B. Models and algorithms for the optimization of signal settings on urban networks with stochastic assignment. Ann. Oper. Res. 2006, 144, 301-328.

19. Magnanti, T.; Wong, R. Network design and transportation planning: Models and algorithms. Transp. Sci. 1984, 18, 181-197.

20. Yang, H.; Bell, M.G.H. Models and algorithms for Road Network Design: A review and some new developments. Transp. Rev. 1998, 18, 257-278.

21. Feremans, C.; Labbé, M.; Laporte, G. Generalized network design problems. Eur. J. Oper. Res. 2003, 148, 1-13.

22. Farahani, R.Z.; Miandoabchi, E.; Szeto, W.Y.; Rashidi, H. A review of urban transportation network design problems. Eur. J. Oper. Res. 2013, 229, 281-302.

23. Zilioniene, D.; D'Acierno, L.; Botte, M.; Gallo, M. A general methodology for reducing computing times of road network design algorithms. Int. J. Supply Oper. Manag. 2019, 6, 126-141.

24. Cascetta, E. Transportation Systems Analysis: Models and Applications; Springer: New York, NY, USA, 2009.

25. Cantarella, G.E.; Watling, D.; de Luca, S.; Di Pace, R. Dynamics and Stochasticity in Transportation Systems: Tools for Transportation Network Modeling; Elsevier: Amsterdam, The Netherlands, 2019.

26. Bureau of Public Roads. Traffic Assignment Manual; U.S. Department of Commerce, Urban Planning Division: Washington, DC, USA, 1964.

27. Dial, R.B. A probabilistic multi-path traffic assignment model which obviates path enumeration. Transp. Res. 1971, 5, 83-111.

28. Gallo, M.; D'Acierno, L.; Montella, B. A meta-heuristic algorithm for solving the road network design problem in regional contexts. Procedia Soc. Behav. Sci. 2012, 54, 84-95.

29. Gallo, M.; D'Acierno, L.; Montella, B. A meta-heuristic approach for solving the Urban Network Design Problem. Eur. J. Oper. Res. 2010, 201, 144-157.

30. Blum, J.R. Multidimensional stochastic approximation methods. Ann. Math. Stat. 1954, 25, 737-744.

Marilisa Botte1,*, Mariano Gallo2, Mario Marinelli2 and Luca D’Acierno1

1Department of Civil, Architectural and Environmental Engineering, Federico II University of Naples, Via Claudio 21, 80125 Naples, Italy

2Department of Engineering, University of Sannio, Piazza Roma 21, 82100 Benevento, Italy

*Author to whom correspondence should be addressed.

Word count: 6934

Show less

© 2020. This work is licensed under http://creativecommons.org/licenses/by/3.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

Abstract

In this paper, we propose a generalisation of the Method of Successive Averages (MSA) for solving traffic assignment problems. The generalisation consists in proposing a different step sequence within the general MSA framework to reduce computing times. The proposed step sequence is based on the modification of the classic 1/k sequence for improving the convergence speed of the algorithm. The reduction in computing times is useful if the assignment problems are subroutines of algorithms for solving Network Design Problems—such algorithms require estimation of the equilibrium traffic flows at each iteration, hence, many thousands of times for real-scale cases. The proposed algorithm is tested with different parameter values and compared with the classic MSA algorithm on a small and on two real-scale networks. A test inside a Network Design Problem is also reported. Numerical results show that the proposed algorithm outperforms the classic MSA with reductions in computing times, reaching up to 79%. Finally, the theoretical properties are studied for stating the convergence of the proposed algorithm.

Details

Title
A Methodology for Increasing Convergence Speed of Traffic Assignment Algorithms Based on the Use of a Generalised Averaging Function
Author
Botte, Marilisa  VIAFID ORCID Logo  ; Gallo, Mariano  VIAFID ORCID Logo  ; Marinelli, Mario  VIAFID ORCID Logo  ; Luca D’Acierno  VIAFID ORCID Logo 
First page
5698
Publication year
2020
Publication date
2020
Publisher
MDPI AG
e-ISSN
20763417
Source type
Scholarly Journal
Language of publication
English
DOI
https://doi.org/10.3390/app10165698
ProQuest document ID
2436217940
Copyright
© 2020. This work is licensed under http://creativecommons.org/licenses/by/3.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.