Mostafa Ameli

Jean-Patrick Lebacque

Ludovic Leclercq
email: ludovic.leclercq@ifsttar.fr

Cross-comparison of convergence algorithms to solve trip-based dynamic traffic assignment problems

Keywords: Trip-based traffic assignment, User equilibrium, Large-scale network applications, Step size, Convergence

Solving a dynamic traffic assignment problem in a transportation network is a computational challenge. This study first reviews the different algorithms in the literature used to numerically calculate the User Equilibrium (UE) related to dynamic network loading. Most of them are based on iterative methods to solve a fixed-point problem.

Two elements must be computed: the path set and the optimal path flow distribution between all origin-destination pairs. In a generic framework these two steps are referred to as the outer and the inner loops, respectively. The goal of this study is to assess the computational performance of the inner loop methods that calculate the path flow distribution for different network settings (mainly network size and demand levels). Several improvements are also proposed to speed up convergence: four new swapping algorithms and two new methods for the step size initialization used in each descent iteration. All these extensions significantly reduce the number of iterations to obtain a good convergence rate and drastically speed up the overall simulations. The results show that the performance of different components of the solution algorithm is sensitive to the network size and saturation. Finally, the best algorithms and settings are identified for all network sizes with particular attention being given to the largest scale.

INTRODUCTION

Dynamic Traffic Assignment (DTA) refers to the process of: (i) identifying the relevant paths between all Origin-Destination (OD) pairs in a transportation network, and (ii) determining the path flow distribution, considering the total OD flow demand and the time evolution of traffic states inside the network. For the first step, many researches have proposed multiple path selection models by considering the time and dynamics of the network, e.g., (Jayakrishnan, Tsai, Prashker, & Rajadhyaksha, 0 Abbreviations: UE, user equilibrium; DTA, dynamic traffic assignment; OD, origin-destination 1994; [START_REF] Mahmassani | Dynamic network traffic assignment and simulation methodology for advanced system management applications[END_REF][START_REF] Xie | A greedy path-based algorithm for traffic assignment[END_REF]. The second step depends on the user behavior rule we want to adopt, which leads to different definitions of the network equilibrium. The best known is User Equilibrium (UE) when all users try to minimize their own travel time selfishly. It corresponds to Wardrop's first principle [START_REF] Wardrop | Road paper. some theoretical aspects of road traffic research[END_REF], where users are assumed to be perfectly rational and have perfect information on the network's status [START_REF] Miaou | Laboratory evaluation of real-time dynamic traffic assignment systems[END_REF], i.e., the predicted travel time on all the relevant alternatives is known at the beginning of all the users trips [START_REF] Ng | A dynamic route choice model considering uncertain capacities[END_REF]. Implementing this simple behavioral rule for Dynamic Network Loading (DNL) is far from trivial [START_REF] Lin | A dantzigwolfe decomposition-based heuristic for off-line capacity calibration of dynamic traffic assignment[END_REF]. DNL is the combination of DTA with a traffic simulator that calculates network states and travel times [START_REF] Yu | A polymorphic dynamic network loading model[END_REF]. The critical issue is that the simulator needs to know the path flow distribution in order to predict the travel time accurately while the DTA process requires this information to estimate the path flow distribution [START_REF] Bekhor | A pathbased algorithm for the cross-nested logit stochastic user equilibrium traffic assignment[END_REF]. Mathematically, this problem corresponds to a fixed-point search, which requires an iterative solution method to converge. Transforming the DTA problem into a fixed-point problem allow using a large number of algorithms. The main idea stems from the theory of fixed-point re-statement [START_REF] Xu | Iterative algorithms for nonlinear operators[END_REF]. Since one run of the traffic simulator is computationally expensive, in particular for a large-scale network, in the field of transportation, it is essential to use an efficient algorithm to solve the fixed-point problem.

The general principle of the algorithms to solve the fixedpoint problem is to reassign a fraction of the users at each step [START_REF] Friesz | The mathematical foundations of dynamic user equilibrium[END_REF]. The algorithm usually reassigns the part of the users who have chosen a non-optimal path because the travel time estimation was misleading [START_REF] Sancho | Applying projection-based methods to the asymmetric traffic assignment problem[END_REF]. The critical issue is to reach a given level of convergence while minimizing the number of iterations. This study aims to investigate the performance of convergence algorithms to solve the DTA problem.

Multiple convergence algorithms have been proposed in the literature to solve this problem. There are two main approaches to determine how many users at each step should be reassigned: analytical and simulation-based. The analytical approach, e.g., [START_REF] Jiang | Computing and analyzing mixed equilibrium network flows with gasoline and electric vehicles[END_REF][START_REF] Mounce | Route swapping in dynamic traffic networks[END_REF][START_REF] Wang | Dynamic traffic assignment: A review of the methodological advances for environmentally sustainable road transportation applications[END_REF], is very accurate but can only be applied in practice to small networks with few ODs. Several studies proposed exact decomposition techniques to reduce the computational complexity of the traffic assignment problems in static [START_REF] Jafari | A decomposition approach to the static traffic assignment problem[END_REF] and dynamic cases [START_REF] Mehrabipour | A decomposition scheme for parallelization of system optimal dynamic traffic assignment on urban networks with multiple origins and destinations[END_REF]. However, congestion patterns are almost intractable analytically due to multiple non-linear interactions inside the network [START_REF] Taale | Better convergence for dynamic traffic assignment methods[END_REF]. Simulation-based approaches can match any given network, but obviously the simulation time increases with the number of nodes/links and vehicles inside the network.

Traffic simulators can be divided into two classes: Flowbased models, which consider the flow on each path and Trip-based models, which define how many travelers take each path. Macroscopic traffic flow models fall into the first category while microscopic models belong to the second. In other words, the flow-based models have a continuous solution space while trip-based ones have a discrete solution space [START_REF] Ramadurai | B-dynamic: An efficient algorithm for dynamic user equilibrium assignment in activity-travel networks 1[END_REF]. Both kinds of simulators can be coupled with convergence algorithms. The macroscopic approach and flow-based models usually converge faster as the path flow discipline is more flexible (flows are not necessarily equivalent to vehicle units), but without adding integrality constraints, they are less realistic for OD pairs with low demand as vehicles are split into parts in practice. In this study, we decide to focus on the trip-based approach because it is more realistic as each vehicle is reproduced individually. Microscopic traffic simulators are now widely used for operational studies, and we have chosen to focus on DTA performance for this kind of model. In summary, trip-based DNL attempts to assign particle-discretized time-dependent origin/destination (OD) flows in a dynamic network equilibrium framework [START_REF] Jayakrishnan | Distributed computing and simulation in a traffic research test bed[END_REF].

Regarding the real-world application, there are several computer packages in the literature. [START_REF] Jeihani | A review of dynamic traffic assignment computer packages[END_REF] reviewed the DTA models used in the most well-known. Indeed, a lot of effort has been paid in providing a new mathematical representation to solve the DTA problem; however, it is also essential to have an idea about the overall efficiency of different computational methods. Here, we consider the simulator as a black box to make this study compatible with any existing traffic simulation software. We then focus on solution methods. This study reviews existing algorithms to solve the fixed-point problem and proposes multiple improvements to speed-up the convergence for a given level of accuracy. Particularly, for large-scale networks as computation times usually count in hours or even days; therefore, slight improvements may be valuable. This study aims to address the following questions:

• Which solution algorithm is efficient to find the DTA solution by considering the size and loading of the network?

• Is there a way to improve the existing methods to find a good quality solution in terms of optimality and feasible computation time for large-scale?

This study considers common convergence algorithms in the literature and attempts to overcome the drawbacks of existing methods to improve the performance of the solution algorithm for simulation-based DTA problems. We aim to provide guidance to practitioners about the best settings to solve simulationbased DTA problems. The next section, Problem statement, provides a discussion on the mathematical conditions for the UE solution. It also presents the two indicators that will be used to assess the algorithm's performance. The benchmark of the solution algorithm for finding the UE is presented in the Methodology section. The improvements made to the solution algorithm with the new swapping algorithms are presented in the section Investigating the solution algorithm. The experimental design is presented in the section Numerical experiment. The results obtained are discussed in the section Numerical results. Finally, we provide concluding remarks and introduce the future directions of work in the Conclusion section.

PROBLEM STATEMENT

Mathematical formula for UE

Let us consider a network ( , ) with a finite set of nodes and a finite set of directed links . The demand is given and time-dependent. The period of interest (planning horizon) of duration is discretized into a set of small time intervals indexed by ( ∈ = { 0 , 0 + , 0 + 2 , ..., 0 + } and 0 + = ). is the duration of the time intervals. In an interval , travel times and traffic conditions are estimated on average and are assumed constant for the DTA. Note that the departure time of users are fixed in this study. In the sequel, the minimum cost path is considered as the shortest path. The important notations which must be introduced for the dynamic equilibrium model are as follows:

: OD pairs, subset of origin × destination nodes, ⊂ × . : index of origin-destination (OD) pair, ∈ .

, : set of paths for in departure time interval . ( ): cardinality of a set .

According to the definition, we have:

̂ , = ∑ ∈ , , , ( , ) ; ∀ ∈ , , ∈ (1)
̂ * , = ∑ * ∈ * , ∑ ∈ * , , * , ( * , ) ; ∀ ∈ , ∈ (2)
Equation ( 1) presents the calculation of mean travel cost of path and equation ( 2) is the same presentation for the shortest path * . For each OD pair ∈ and for all paths ∈ , the dynamic traffic network equilibrium conditions with given travel demand and the users' departure time for the aforementioned traffic network equilibrium problem are:

̂ , -̂ * , ≥ 0 ; ∀ ∈ , ∈ , , ∈ (3)
( , )( ̂ , -̂ * , ) = 0 ; ∀ ∈ , ∈ , , ∈ (4) ( , ) ≥ 0 ; ∀ ∈ , , ∈ (5)
According to constraint (3), the shortest path * has the minimum travel cost for the related OD pair. Equation ( 4) indicates that all users travel on shortest path with minimum travel cost at UE state and the flow of paths cannot be negative, according to constraint (5). [START_REF] Lu | Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem[END_REF], extended the work of Smith, 1993, and reformulated the problem as a non-linear problem in order to minimize the gap function. The gap function is defined as the gap between average path travel time and average shortest path travel time. Consequently, the solution to this fixed-point problem is equivalent to finding the solution to the following variational inequality:

∑ ∈ ∑ =1 ∑ ∈ , , , * ( , , ) -( , , * ) ≥ 0 (6)
where ( , , * ) is the optimal number of trips from OD pair that are assigned to path at departure time and ( , , ), ( , , * ) ∈  satisfy the equilibrium.  denotes the flow constraints based on . In equation ( 6), both ( , , ) and ( * , , ) are decision variables and hence the gap function is a function of both variables.

Then a vector of ( * , , ) solves equation ( 6) if and only if it is a fixed-point of the following mapping [START_REF] Marcotte | A new algorithm for solving variational inequalities with application to the traffic assignment problem[END_REF]:

Γ ≜ arg min ( , )∈ [ ( , )] [ ̂ , ] (7)
where [ ( , )] denotes the vector of ( , ); ∀ ∈ , , ∈ and [ ̂ , ] denotes the vector of ̂ , ; ∀ ∈ , , ∈ . For the proof and details, see [START_REF] Kaufman | User-equilibrium properties of fixed points in dynamic traffic assignment[END_REF]. Before presenting the solution algorithm, we need to present the convergence indicators used in this study to evaluate the quality of the solution for the trip-based dynamic network user equilibrium.

Convergence quality

In the trip-based DTA problem, the goal is to minimize the left side of the Equation ( 8) for all paths and OD pairs. In other words, finding the UE situation is equivalent to minimizing the delay of each user compared to the optimal option of the associated OD pair (shortest path) in the network. By this definition we can define a quality indicator for solutions which is calculated as the average delay of each user [START_REF] Janson | Dynamic traffic assignment for urban road networks[END_REF]

: = ∑ ∈ ∑ =1 ∑ ∈ ( , ) ∑ ∈ , ( , , - * , , ) ∑ ∈ ∑ =1 ( , ) (8)
Note that this formula uses the experienced travel time to calculate the gap rather than the path travel time. The is zero for the perfect UE path flow distribution, so the best optimization algorithm obtains minimum . Equation ( 8) has physical meaning for measuring the distance between solution and UE. The second indicator is a characterized assignment violation, i. e. users that are assigned on (a) non-optimal path(s). The violation indicator is calculated by the following steps:

1. Calculate the user violation: it is defined by considering the gap of each user ( ):

= 1; if , - * * ≥ 0; o.w. (9)
where , denotes the experienced travel time of the user who travels for OD pair and * denotes the shortest path of OD pair . If the gap between the user perceived travel time and the shortest path travel time is bigger than of the shortest path travel time, the user is in violation. = 0 means perfect UE, but in practice with trip-based simulation, it is more appropriate to set up a margin to count users that are miss-assigned.

2. Compute the OD violation: the OD pair is in violation when more than ′ of the users on are in violation.

The function defines the OD violation:

= ⎧ ⎪ ⎨ ⎪ ⎩ 1; if ∑ ∈ ( ) ≥ ′ 0; o.w. ( 10
)
where denotes the set of users, who travel for OD pair .

The violation indicator of network

is the share of ODs in violation. The second indicator for the quality of solution (Violation) is defined as follows:

( ) = ∑ ∈ ( ) (11)
The value of and ′ are fixed at 10% in this study to evaluate the quality of the solution from a different angle as . The violation index provides a more threat assessment of how the equilibrium is achieved on the OD-basis. Note that, similar to , the perfect UE means ( ) = 0 with = ′ = 0. While gives an idea about the average level of the convergence for the solution in a continuous way, the violation index defines how many out-liners we can accept. The two criteria represent the level of confidence we want to achieve at the OD level ( ) and then at the network level ( ′ ). Please note that we do not use ( ) in the convergence loop and simply calculate it afterwards to assess how the process is doing.

METHODOLOGY

In large-scale DTA problems, there are three costly steps in terms of computation in simulation-based DTA models: traffic simulation, shortest path discovery, and optimization. Here, we focus on the optimization step. According to the state of the art, it appears that the most advanced framework for solving the simulation-based DTA problem as a black-box optimization problem is that proposed by [START_REF] Lu | Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem[END_REF] with a clear decomposition between outer and inner loops. The outer loop is responsible for path discovery and does not include any traffic simulation. The inner loop determines path flow distribution for all OD pairs in the network and includes multiple DNL. The classic approach executes both steps in one top loop. In large-scale network problems, it is extremely costly to keep the data of all possible paths between each OD pair. With [START_REF] Lu | Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem[END_REF]'s framework, the simulator simply keeps the feasible paths discovered by the outer loops.

The outer loop is only about path discovery. Therefore, improving the computation time there means finding a more efficient shortest path algorithm, which is not in the scope of this study. This study focuses on path flow distribution, which is the role of the inner loop and plays a pivotal role in the overall UE calculation by reducing the number of simulation run we have to launch to get the equilibrium. The solution algorithm is presented in Figure 1 and is detailed in the following:

Step 1. Initialization: Load the network and the OD matrix, with real data or simple assignment models (e.g., Allor-nothing algorithm).

Step 2. Time-dependent shortest path Calculation: Calculate the time dependent shortest path(s) for each OD pair .

Step 3. Update the cost functions: Read the information from the simulator output and update the cost of paths (links) on the network graph and update the quality indicators.

Step 4. Outer loop convergence test: Check the stop conditions: }). is a small and fixed value. Otherwise go to the next step.

If it has converged, the process is stopped (END). Note that the path set is a set of paths that contains used path(s) ( ( , ) > 0) and shortest path(s) which have been used or not ( ( * , ) ≥ 0) for all ODs which come from step 2.

Step 5. Inner loop Initialization: Load the path flow distribution of Step 1 by [START_REF] Lu | Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem[END_REF] or other initialization methods (this study) in order to generate the initial assignment to start the inner loop.

Step 6. Update the path assignment: Swapping trips from a path to another(s) based on an optimization method in order to load the flow to the different path candidates.

Step 7. Simulation: Command the simulator to simulate the new assignment pattern provided by Step 6.

Step 8. Identify the shortest path(s): The simulator returns the experienced travel time of all the users on different ODs. The shortest path travel time can be changed, and it is possible that we have another shortest path from the path set based on the simulation results. Note that we have a fixed path set in this step and we do not need to use the shortest path algorithm.

Step 9. Update the cost function: Update the network data from the simulator run in Step 3.

Step 10. Inner loop convergence test: Check the stop conditions:

a. Maximum number of inner loop iterations ( ) is reached OR b. small enough variation in solution quality:

| - -1 | -1 ≤ Λ ; ∀ ∈ {1, ..., } (12)
where is the quality of the solution of inner loop iteration and Λ is a fixed threshold (Λ = 1%) for comparing the relative .

At the end of each Inner Loop, if there is insufficient variation in solution quality, we converge and go to step 12. Otherwise, we continue to Step 11.

Step 11. Keep the best solution: Compare the solution quality ( ) of the current inner loop iteration ( ) with the best solution of the current outer loop (

). Note that if we are in the first inner loop iteration ( = 1), we consider the of Step 4 as the initial best and compare it with the current solution. If the solution has better quality, we replace the best solution by the current solution. Otherwise, the best solution is kept. The solution contains the path assignment pattern and solution's

. Afterward, we continue iterating in the inner loop by going back to Step 6.

Step 12. Best solution check: The goal of this step is to ensure that our last solution is the best solution of the current outer loop. We compare the last solution with the current best solution from Step 11. If the last solution is the best ( ≤ ), go to the outer loop to explore the network and find (a) new shortest path(s) (Step 2). Otherwise, a final simulation is executed in the next step for the best assignment pattern which is not the last one we obtain.

Step 13. Simulation of the best solution: simulate the traffic state (like Step 7) with the best assignment pattern of the inner loop provided by Step 11 to move to the next time period or the next outer loop iteration (Step 2).

Note that in the inner loop convergence test (Step 10), the stop conditions are the maximum number of iterations and variations of the gap, so the last iteration solution is not necessarily the best solution of the inner loop. Therefore, Steps 11-13 are keeping the best solution of the inner loop when the algorithm goes back to the outer loop. This will be even better when using trip-based approaches because their discrete nature makes them less stable and we will, therefore, have more cases where the solution of the last iteration is not the best over the current inner loop.

INVESTIGATING THE SOLUTION ALGORITHM

In this section, we focus on improving the inner loop (in Figure 1). They correspond to steps 5 and 6.

Swapping algorithms

Swapping algorithms corresponds to Step 6 in Figure 1, where the solution algorithm updates the path assignment. Here, we benchmark different algorithms that exist in the literature and also propose new ones. Table 1 gives a complete summary of all the algorithms with their references.

Method of Successive Average (MSA)

The method of successive average (MSA) is the best known algorithm for solving the fixed-point problem. Most of the studies in the literature used MSA as a reference algorithm. The MSA was presented for the first time by [START_REF] Robbins | A stochastic approximation method[END_REF]. The MSA is still widely used in simulation-based DTA (e.g., [START_REF] Zhang | A network traffic assignment model for autonomous vehicles with parking choices[END_REF]), because it is simple to implement and does not require the derivative information of the flow cost function [START_REF] Nagel | Agent-based traffic assignment: Going from trips to behavioural travelers[END_REF]. The MSA updates the path flow by using a descent direction and a predetermined step size. [START_REF] Mounce | On the convergence of the method of successive averages for calculating equilibrium in traffic networks[END_REF] investigates different descent direction methods for the MSA algorithm and concludes that MSA works well on large networks when combined with a swap towards the least costly route(s). Therefore, the classic descent direction ( ) of the iteration ( ) for path is extracted from the auxiliary path assignments obtained by All-or-nothing discipline, i.e., everyone is put on the active shortest path. Consequently, in iteration , the MSA algorithm swaps a fraction of users to the shortest path(s) from each non-shortest path (Equation ( 1)). Mathematically, a fraction of the total number of users on non-shortest paths is added to the shortest path(s).

+1 , = , + ( , -, ) (13)
where , is the number of trips for OD pair which travel on path in iteration at each time step.

denotes the step size of the MSA algorithm. The MSA step size satisfies the following [START_REF] Sheffi | Urban transportation networks[END_REF]:

∞ ∑ =1 2 < ∞ (14) ∞ ∑ =1 = ∞ (15)
The classic MSA uses one over the iteration index plus one as a step size (Equation ( 4)) to ensure the algorithm converges.

The step size can be defined with respect to Equations ( 2) and

(3). = 1 + 1 (16)
The first drawback of the MSA is that it swaps a fixed number of users from all non-shortest paths to the shortest one without considering the actual travel time on these paths; it does not consider the gap between the shortest and other paths. First, [START_REF] Sbayti | Efficient implementation of method of successive averages in simulation-based dynamic traffic assignment models for large-scale network applications[END_REF] implemented the classic MSA method in trip-based DTA, using the random selection technique in view to reducing memory requirements. Second, they attempted to overcome the first drawback by proposing a criterion-based selection that ranks the users based on experienced travel time. They showed that on a real network, both methodologies were observed to converge, and that the criterion-based technique also produced a better solution than MSA in terms of closeness to optimal. However, by increasing the number of users in a large-scale network, ranking them based on travel cost is a computationally costly approach. Moreover, [START_REF] Sbayti | Efficient implementation of method of successive averages in simulation-based dynamic traffic assignment models for large-scale network applications[END_REF] uses the same predetermined step size as the MSA method.

The second drawback is about predetermining the step size. The step size rule pushes the process to stabilize. There may be a risk of stabilizing before reaching the optimal solution. The step size has a direct impact on the number of iterations (computation time) and convergence speed. There is no exact method for determining the step size in the literature [START_REF] Huang | Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues[END_REF][START_REF] Szeto | Non-equilibrium dynamic assignment[END_REF]. The step size does not guarantee the quality of the solution at the end, which may not be the actual UE [START_REF] Levin | Improving the convergence of simulation-based dynamic traffic assignment methodologies[END_REF]. One of the goals of this study is to improve the performance of the optimization process by proposing new methods for step size determination in the simulation-based optimization framework. There are several extensions for MSA algorithm in the literature, which attempt to overcome the drawbacks of existing methods to improve the performance of the solution algorithm for simulation-based DTA problems.

MSA Ranking

As mentioned in the previous section, the first drawback of the MSA algorithm for DTA application is that the MSA does not consider the travel time of the non-shortest path and simply swaps a fixed fraction of users to the shortest path. In other words, the MSA does not take into account the quality of the path in terms of travel time. To overcome this drawback of the MSA algorithm, there is an extension of the MSA in the literature called MSA ranking [START_REF] Sbayti | Efficient implementation of method of successive averages in simulation-based dynamic traffic assignment models for large-scale network applications[END_REF]. The idea of MSA ranking is that the users are first ranked by experienced travel time then a maximum number of users with long experienced travel time are swapped to the shortest(s) path, based on the MSA algorithm's step size. The maximum number of swaps is observed when no users have been previously assigned to the shortest path.

= . ( 17
)
The advantage of this algorithm is that it swaps users from the most expensive paths to the shortest path so the direction of solution searching can be improved to obtain a good solution in terms of quality for the trip-based UE problem. On the other hand, with a large number of users traveling between many ODs by many possible paths, ranking the users is a costly process in a large-scale problem. However, it is a good reference when taking all the MSA-based algorithms into account because it usually provides the best solutions (low and Violation values).

Projection-based algorithms

Here, we adapt two swapping algorithms with an extension of the MSA-based formula. 1-The within-day fixed-point algorithm is a projectionbased algorithm designed for non-linear fixed-points of nonexpanding maps. [START_REF] Friesz | The mathematical foundations of dynamic user equilibrium[END_REF] applies this algorithm to flow-based (continuous) dynamic user equilibrium problem by differential variational inequalities. We adapt this algorithm as a Projection method (PM) to the trip-based DTA problem. The validation of the algorithm for the fixed-point problem is well defined in [START_REF] Halpern | Fixed points of nonexpanding maps[END_REF]. The swapping algorithm of the Projection method is based on the transformation of the cost to the flow by a constant ( ), which is the time step size of the algorithm. From the standpoint of application, the unit of is and measures users' sensitivity to travel costs. The swapping algorithm for trip-based DTA is as follows:

= ( ), .( ̂ , -̂ , ) (18)
where ̂ , denotes the mean travel time of all paths of OD pair in time interval . At every iteration, the algorithm attempts to swap users from the path with longer travel time compared to mean travel time to the shortest path and other low-cost paths. Note that is determined in the light of the recent study of (K. [START_REF] Han | Computing dynamic user equilibria on large-scale networks: From theory to software implementation[END_REF] in which this algorithm is applied to a flow-based DTA problem. Note that in equation ( 18), we can have a negative number for swapping, meaning that users should be added to this path. It also gives an indication of how many should be added. This only concerns paths whose path travel time is below the mean travel time ( ̂ , ). 2-Friesz, Kim, Kwon, & Rigdon (2011) extended the Projection algorithm by using a common method for speeding up the convergence in Hilbert space when solving the fixed-point problem. The idea is to retrieve the initial solution at each iteration by using a weighted coefficient based on a second step size for calculating the Projection algorithm solution. Let us consider as the assignment pattern in iteration of the Projection algorithm. The solution of this algorithm, labelled as Projection Initialization (PI) algorithm, will be:

= 0 + (1 - ) ( 19
)
where 0 is the initial flow pattern at the beginning of the process and is the step size determined by the following formula:

= ( 1 1 + ) (20)
where is a parameter to be designated and which must satisfy 0 < < 1.

3-The third algorithm in this category is developed based on the Projection Initialization algorithm. The same procedure is applied for the MSA algorithm to evaluate the impact of sticking to the initial solution on the optimization process. Therefore, the flow formula of the Initialization MSA (IMSA) algorithm is as follows:

= 0 + (1 - ) (21)
where in equation ( 19) is replaced by , which is the solution of the MSA algorithm in iteration . As with the Projection initialization algorithm, is determined by equation (20). [START_REF] Lu | Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem[END_REF] proposed the gap-based step size and proved that it satisfies the step size conditions. The volume of swapping is proportional to the gap (the difference between the non-shortest path and shortest path cost) over the path cost multiplied by MSA step size:

Gap-based algorithm and Gap-based normalized algorithm

= ̂ , -̂ * , ̂ , . ( 22
) = ; if = 0 1; o.w. ( 23
)
We recall that is the outer loop iteration index. This algorithm solves the problem of sorting and also circumvents the first drawback of the MSA formula (Section 4.1.1). However, it also uses the step-size which can induce the convergence of the algorithm to a non-optimal solution. Moreover, the multiplication of the gap indicator and the MSA step size can provide a small step size for this algorithm. Here we normalize the gap indicator to provide a relative fraction for the step size which gives the algorithm more flexibility in swapping at each iteration. The algorithm can swap more or fewer users from path with respect to the gap of other paths of OD pair :

= ̂ , -̂ * , ∑ ∈ ( , ) ( ̂ , -̂ * , ) . ( 24
)
This swapping algorithm is applied for each OD pair. This algorithm attempts to normalize the gap indicator of the Gap-Based algorithm (GB), which is called the Gap-based normalization (GBN) algorithm in this study.

Probabilistic algorithm

We first introduced the Probabilistic algorithm in Ameli, Lebacque, & Leclercq (2017) for solving the multi-class multimodal equilibrium, but we never investigated it in detail. This algorithm calculates for each user the probability of swapping ( ) by equation 25. Then the Bernoulli trial is implemented in simulation for a user in order to decide to swap or not according to the result of the trial.

= ( = 1) = , - * , , (25)
where denotes the binary swap decision variable. This algorithm is the only one which does not use step size. Moreover, it avoids the ranking process and saves computation time. The Probabilistic algorithm can be considered as an implementation of the Gap-based algorithm to a trip-based approach if we adjust the probability of reducing the impact of the descent step. However, here we basically relax the step size. The Probabilistic algorithm is totally flexible when searching the solution space based on the probabilistic process.

Hybrid algorithms

Hybrid algorithms are different combinations of Gap-based, Probabilistic and MSA algorithms for each individual step of the calculation. 1-Halat, Zockaie, [START_REF] Halat | Dynamic network equilibrium for daily activitytrip chains of heterogeneous travelers: application to largescale networks[END_REF] applied a hybrid algorithm for a dynamic activity-based model. The algorithm is a similar to the Probabilistic method as it adds a step size to equation ( 25). This algorithm is called Step size Probabilistic (SSP), and calculates the swap probability by the following formula:

= , - * , , . (26)
The first hybrid algorithm uses a random number and compares it with to make the swap decision for each user. 2-Verbas, [START_REF] Verbas | Dynamic assignment-simulation methodology for multimodal urban transit networks[END_REF] applied the Gapbased algorithm for transit network assignment problems and used the probabilistic algorithm for each user on each path to swap more users with high travel cost without ranking. The algorithm is called Gap-based Probabilistic (GBP). For path , the number of swapping users is determined by equation ( 22) and the users are selected by Equation ( 25) for swapping. [START_REF] Verbas | Gapbased transit assignment algorithm with vehicle capacity constraints: Simulation-based implementation and largescale application[END_REF] showed that this hybrid algorithm obtains better solutions than the MSA algorithm in large-scale transit assignment problems. 3-The third hybrid algorithm is the Boost-up Gap-based (BGB) algorithm and is proposed by this study. The idea is to boost step size of the Gap-based algorithm. For path , we multiply the number of swaps by a fraction of the swap number of the Gap-based and MSA algorithms:

= ( ), [ . ( )]. (27)
This section presents different alternatives for Step 6 of the solution algorithm.

Inner loop initialization

The solving process in the inner loop should start with an initial path flow distribution to first estimate travel times by simulation (Step 5 in Figure 1). The usual approach is to assign the total demand to the shortest path(s), using free-flow travel times (All-or-nothing initial assignment). In Step 5, at the beginning of each outer loop before entering the inner loop, the assignment pattern is initialized and reset to the assignment pattern in Step 1 [START_REF] Lu | Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem[END_REF]. We investigate an alternative approach for the assignment pattern initialization. Keeping the assignment pattern approach removes Step 5 from the solution algorithm. Consequently, the algorithm starts the outer loop with the optimal solution from the previous outer loop ( -1). Obviously, this will be very efficient for solving static situations, but we want to investigate its performance with dynamic loading.

Initial step size selection

The third investigation is the definition of the descent step size. The initial step size ( 1 ) defines how many users can be swapped during the first iteration. It is the largest step size during the inner loop and determines the exploration domain of the solution space. In two-level simulation-based methodology [START_REF] Lu | Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem[END_REF], the initial step size of the first inner loop of the outer loop ( 1, ) is calculated by the iteration counter of the outer loop ( ):

1, = 1 + 1 (28)
This setting improves the speed of convergence because increasing decreases 1, , so the largest number of swaps for the current inner loops in outer loop + 1 begins with a smaller value in comparison with outer loop . On the other hand, increasing reduces the exploration domain of the inner loop. In order to overcome this drawback, this study proposes two new approaches to set up the step size.

Re-initializing the step size

The idea of re-initializing the step size (Reset) method is to reset the step size by the inner loop iteration index:

, = 1 + 1 (29)
This approach at the beginning of each outer loop starts the optimization with 1, = 1 2 to have more flexibility for searching the solution space. In other words, this approach can increase the maximum number of swaps at each iteration in comparison to the initial approach ( 1, ≥ 1, ).

Smart step size

Here we design an approach that uses adaptive step size for each OD pair . First, all the inner loops are initiated with the same step size whatever the OD pair. At the end of the first iteration ( = 1), the OD gap for OD pair is calculated as follows:

= ∑ ∈ ( , ) [ ( , ).( ̂ -̂ * )] (30)
Then, we keep the step size and run the second loop ( = 2). At the end of the second loop, we update the OD gap and compare it with the previous OD gap. If the OD gap is improved, we keep the step size to swap the same fraction of users for a possibly better solution, otherwise we decrease the OD step size to decrease the number of swaps. The step size for OD pair at inner loop iteration is:

= ⎧ ⎪ ⎨ ⎪ ⎩ -1 -1 +1 ; if ≥ -1 -1 ; o.w. ; ∀ ∈ {2, ..., }, 1 = 1 2 (31)
Equation ( 31) adapts the step size for each OD pair depending on how the quality of the solution is improved. This method mimics the Newton-Raphson method in numerical analysis [START_REF] Ypma | Historical development of the newtonraphson method[END_REF]. It has been proven to be very efficient for continuous problems, but this is the first time it is used in the context of DTA and for the discrete formulation (trip-based model).

To conclude this section, we present all the methods considered in this study in Table 1. Before comparing the methods, we need to present the dynamic trip-based simulator and test cases.

NUMERICAL EXPERIMENTS

In this work, we use Symuvia1 as a trip-based simulator for calculating travel time in traffic networks. Symuvia is a microscopic simulator based on the Lagrangian resolution of the LWR model [START_REF] Leclercq | The lagrangian coordinates and what it means for first order traffic flow models[END_REF]. This carfollowing law has been further extended to account for all the features of urban traffic: bounded acceleration (Leclercq, 2007a), lane-changing with relaxation [START_REF] Laval | Microscopic modeling of the relaxation phenomenon using a macroscopic lane-changing model[END_REF], multi-class [START_REF] Leclercq | A multiclass car-following rule based on the lwr model[END_REF], signalized and unsignalized intersections (Chevallier & Leclercq, 2009a), roundabouts [START_REF] Chevallier | Microscopic dualregime model for single-lane roundabouts[END_REF]. The simulation time-step is equal to 1 second, and we retrieve the travel time information at the link and node level every 1 minute. This study considers three networks with different topologies to investigate if the network size influences the algorithm settings. Note that all the networks in this study are mono-modal, i.e., with car-traffic only. A 5 × 5 grid network (5by5) is used for the smallest scale network, see Figure 2(a). All the intersections are signalized, and the green and red light duration is set to 30 seconds. The simulation period is 2 hours for 19 origins and 16 destinations. The medium-scale network exemplifies a Manhattan type city with a ring road (Ring city), see Figure 2(b). This network corresponds to 14×14 two-way regular roads with a speed limit of 50km/h. These roads delimit blocks that are grouped 3 by 3 to form 5×5 zones. A two-way ring road with a speed limit of 90km/h has 12 interchanges with peripheral zones. All the intersections are signalized except the interchanges with the ring road, and the green and red light duration is set to 30 seconds. Ring city is simulated for 50 minutes with 26 origins and 24 destinations. The large-scale network of this study is the network of two French cities: Lyon 6e + Villeurbanne (Lyon6V). This network has 1,883 Nodes, 3,383 Links, 94 Origins, 227 Destinations. All the signalized intersections in the real field have been implemented in the simulator with their actual signal timing. It is illustrated in Figures 2(c) and 2(d). The network is loaded with travelers of all ODs with given departure times in order to represent 2.5 hours of the network with the demand of three levels of saturation based on the study of [START_REF] Krug | Reconstituting demand patterns of the city of lyon by using multiple gis data sources[END_REF].

The Macroscopic Fundamental Diagram (MFD) shows the rapid evolution and gives a synthetic overview of network states. It usually distinguishes three situations. First, the curve increases from (0, 0) and traffic states remain under-saturated when demand is light. This is referred to as the Under Saturation (US) scenario. Travel production, which is equivalent to the total travel distance for a given period of time, stabilizes while the accumulation (or total travel time) still increases, i.e., the network progresses to maximal capacity and then it quickly becomes unloaded. This corresponds to the Saturation (S) scenario when we reach to the maximal capacity of the network, and then unload it. Finally, production decreases when the total travel time continues increasing. This is the Over Saturation (OS) scenario where the network is heavily congested and remains at the maximum capacity of the network for a long time. We tune the demand to observe all three levels of saturation in numerical experiments to assess the impact of network loading on the performance of the fixed-point algorithm. Table 2 presents the total demand for all the test cases of this study. The MFDs of each demand scenario for all the networks are presented in Figure 3. The points in the figures represent the state of the network at each successive 5-min time period. The MFD of the US scenarios shows the evolution of the state of the networks with almost free-flow travel time during the simulation for each network (Figures 3(a), 3(d) and 3(g)). The saturated MFD diagrams for each network (Figures 3(b), 3(e) and 3(h)) show that the S demand scenarios put the states of the networks in saturation level during the simulation. Finally, the OS scenario moves the network states to a heavily congested situation in which the saturation level is very high (Figures 3(c), 3(f) and 3(i)).

Demand is constant, but the network state evolves dynamically due to spreading congestion in all three scenarios.

RESULTS

All the experiments are first initiated with the All-or-nothing assignment algorithm (see Step 1 in Figure 1). In this study, we impose a limit on the maximum number of iterations and compare the final solutions obtained by the different algorithms. This is to contain the computational cost and to bring the experiments closer to usual practice in which traffic engineers try to control maximum computation times. Each scenario is executed for five outer loops ( = 5). This means that users have to finally choose between a minimum of six paths (the first path comes from Step 1) for each OD pair. Note that the maximum number of the outer loop iterations is not the limitation. At one point, increasing the number of discovered paths will simply add close alternatives that do not improve the solution.

To confirm this intuition, we rerun the large-scale scenario with the saturated level of demand with an increasing number of the outer loop. It appears that the final gap values, even when the number of outer loop iterations reaches 20, remain very close to the original one with five outer loop iterations only. So, we keep = 5 for all scenarios. The inner loops run for a maximum of ten iterations ( = 10) for a small network, twenty for Ring city ( = 20), and thirty for a large-scale network ( = 30). We restrict the number of inner loop iterations for each network to obtain a complete comparison of the performances of the algorithms in the same settings. The different values of are determined as a function of the size of the network, based on the studies of [START_REF] Halat | Dynamic network equilibrium for daily activitytrip chains of heterogeneous travelers: application to largescale networks[END_REF]; [START_REF] Verbas | Gapbased transit assignment algorithm with vehicle capacity constraints: Simulation-based implementation and largescale application[END_REF]. All the experiments are conducted on a 64-bit personal computer with a 12-core central processing unit of 2.10 GHz speed, and a memory of 128 GB. The experiments are conducted in three stages. First, we compare all the swapping algorithms. Then the best swapping algorithms are chosen for the second stage. The initialization methods are tested in the second stage. Finally, the best combinations of swapping algorithms and initialization methods are considered for the third stage. The step size methods are examined in the third stage.

Comparison of swapping algorithms

The first stage of the numerical experiments entails finding the best swapping algorithm. We track and Violation indicators to assess the performance of each swapping algorithm.

The final values are presented in Table 3 for the nine scenarios. Metal colors highlight the top three algorithms (Gold = first, Silver = second, Bronze = third) for each scenario. Moreover, Figure 4 presents a bar chart of the computation times.

Regarding the uniqueness of the UE, this is the case for the DNL problem when users have the same characteristic (homogeneous demand) and travel time functions are increasing [START_REF] Ameli | Dayto-day multimodal dynamic traffic assignment: Impacts of the learning process in case of non-unique solutions[END_REF][START_REF] Iryo | On the uniqueness of equilibrated dynamic traffic flow patterns in unidirectional networks[END_REF]. Monotonicity exists at the link level for the traffic simulator of this study [START_REF] Leclercq | Hybrid approaches to the solutions of the âĂIJlighthill-whitham-richardsâĂİ model[END_REF] but not at the node because most of the intersections are signalized. Therefore, we cannot claim, on the basis of the literature, that we have unicity; however, we have a similar solution in terms of path flow distribution whatever the algorithm used in each case. In particular, in the small-scale network (5by5), MSA ranking, Probabilistic, and Projection initialization algorithms lead to optimal values for the US scenario (Table 3). Furthermore, the path flow distributions are equal, possibly providing the optimal UE for this scenario.

According to Figure 4(a), the Projection initialization algorithm converges fastest to the best solution. In the saturation scenario, the best solution is obtained by Probabilistic algorithm, but Gap-based normalization algorithm is the fastest algorithm to converge (Figure 4(b)) while the by this algorithm is ranked second among all the algorithms. In the saturation scenario, the results provided by the Gap-based, Boost-up Gap-based, Projection initialization, and Initialization MSA algorithms are poor in comparison with the best solution. In the over-saturation scenario, the Gap-based normalization and Boost-up Gap-based algorithms perform well in terms of solution quality and CT.

Table 3 shows that the Probabilistic algorithm provides the best solutions in all the scenarios of the medium-scale network (Ring city). For the US scenario, the Gap-based Probabilistic algorithm converges fast (Figure 4(d)) and also to a good solution, with a only 0.28 second longer than the best solution. In the S scenario, the Probabilistic algorithm is significantly better than the others in terms of solution quality. Initialization MSA algorithm converges fast (Figure 4(e)) but to a bad solution, which is more than 25 times bigger than the best solution.

In the large-scale network (Lyon6V), The results show that many algorithms with low CTs converge to solutions far from the best solution. This happens because the solution space for the large-scale is more complicated than the solution space of smaller networks, and most of the solution algorithm with step size can be stick to the local optimum and cannot explore very different path flow distribution. For instance, in the OS scenario, the MSA ranking, Gap-based and Step size Probabilistic algorithms converge faster than the others (Figure 4(i)), but the and Violation are very poor in comparison with the Moreover, the results in Table 3 show that the performance of the swapping algorithms depends not only on the scale of the traffic network but also on the saturation level. Because the solution space of the fixed-point problem becomes more complex when the level of saturation is increased. As a result, the intermediate solutions of the inner loop are not stable. In other words, when the level of congestion increases, the correlation of ODs, which share links, is increased. Therefore, any change in the reassignment process can change significantly the quality indicators. The performance analysis of the algorithms is analyzed as follows:

• The MSA method works well in small-scale, but by increasing the size of the traffic network, it obtains poor results for and Violation in comparison with the other algorithms. It is noteworthy that the MSA algorithm is one of the worst algorithms on the largescale, particularly for the US scenario. The reasons for this performance of the drawbacks of MSA algorithms (Section 4.1.1), but its CT is comparable with other algorithms in the US and S scenario.

• The MSA ranking algorithm is not among the top three algorithms in the large-scale. However, because of the ranking process, it provides good enough solution compared to the best algorithm except in the OS scenario, where the MSA ranking algorithm converges faster than the others but to a bad solution. This algorithm is still suffering the drawback of predefined step size, which force this algorithm to converge.

• The Gap-based algorithm does not appear in the top three algorithms for all the scenarios, but it obtains solutions with small for all the US demand scenarios. In these test cases, when increasing the level of network saturation, the Gap-based algorithm cannot converge to a high-quality solution. Using the gap indicator in the step size formula helps to converge to the local optimum while preventing the algorithm from exploring a wide range of solutions for the global optimum.

• The Gap-based Normalized algorithm performs better than the Gap-based algorithm in most of cases. The normalization techniques improve the performance of the Gap-based method, especially in the saturation and OS scenarios.

• Generally, the Probabilistic algorithm is the best algorithm in the US and S scenarios of all the networks and also it also provides good performance for the OS scenario in the small and the medium test cases. It should be recalled that the Probabilistic algorithm is the only step size free algorithm of this study. It can explore the solution space without limitation, which makes it more robust than other algorithms. However, in the largescale and OS scenario, the CT of Probabilistic algorithm is very high, and it could not provide a good solution compared to the best algorithm. It means that this algorithm does not fully cover the solution space under the determined computation budget.

• The hybrid algorithms (Section 4.1.6) work better than MSA and Gap-based algorithms in the large-scale and US scenario, but they are dominated by Probabilistic algorithm because the step size still limits them. The Step size Probabilistic algorithm, which is a combination of MSA and Gap-based algorithms, provides better results than both methods in the medium-and the large-scale networks with US and saturation levels of demand. When the saturation level of the network increase, the Gap-based Probabilistic algorithm cannot provide a good solution. The Step size Probabilistic and Gap-based Probabilistic algorithms are dominated by the Probabilistic algorithm in all test cases. The Boostup Gap-based algorithm, which used the boost-up step size performs better in OS scenarios where there is a large number of trips to optimize.

• The projection-based algorithms (Section 4.1.3) are good for small scale. Their CT is increased significantly by the saturation level of the network. In addition, they have a high CT in the large-scale network compared to other algorithms. Using the initialization technique in the swapping formula increases the algorithm CT significantly, particularly in saturated level and does not help that much the algorithm to provide a better solution.

Figure 5 presents the convergence pattern of swapping algorithms. Top five algorithms in terms of the indicator for each saturation level of small-and medium-scale networks are presented in Figures 5(a)-5(f). For the large-scale network, we present more swapping algorithm convergence pattern (Figure 5(g)-5(i)) to analyze more algorithms.

According to Figure 5, the saturation level has an impact on the scale of at each level of the outer loop during the optimization process. In the US scenario, the value decreases suddenly for the first outer loop but for more saturated scenarios adding the new shortest path changes scale of users, particularly in the large-scale network. As shown in figure 5(i), the gap value slumps for the outer loop five, where users have six alternatives per OD to choose.

In addition to the quality of the final solution, converging with the less number of outer loops ( < 5 in this study) to a solution with good quality is important in practice. In other words, the algorithm with a minimum number of outer loops and good solution in terms of can be more efficient. Note that the solution with good quality means the of the solution is below a predetermined satisfaction threshold. Here, we consider a given satisfaction threshold ( ) for the quality of the solution at outer loop iteration ( ) in order to investigate which algorithms can reach faster this threshold ( ≤ ). The values of for US and S scenarios are approximately equal to ⌈2 × * ⌉ + 1 where * denotes the best quality of the final solution obtained by swapping algorithm in second. For the OS scenarios in large-scale, we set the to 9 minutes based on the initial (≈ 15 min) which is obtained by the All-or-nothing algorithm. Figure 5 presents the values for each scenario. We can see in this figure, the first time that each algorithm is positioned below threshold before the last iteration and then determine the minimal number of the outer loop to guaranty a given level of performance. The Probabilistic algorithm can converge faster in the small and medium networks according to the value. For instance, about the Ring city network saturated scenario, if we want to reach the level of = 1 minute ( = 60), we need to do only one outer loop iteration with the Probabilistic algorithm. In the large-scale considering the threshold helps to save CT. In the large-scale network, the MSA algorithm for the saturated scenario, and the MSA ranking algorithm for OS scenario are much faster than others and need only two outer loops to reach the threshold.

MSA ✓ ✓ MSAR ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ GB GBN ✓ ✓ ✓ ✓ Prob. ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ SSP ✓ ✓ GBP ✓ ✓ ✓ BGB ✓ ✓ PM ✓ ✓ ✓ PI ✓ ✓ IMSA ✓
All our analyses give good hints about which are the best swapping algorithms. As we discussed in Section 4, there are different components in the optimization process, which can help the swapping algorithm to find a better solution. Consequently, the swapping algorithms with good quality indicators ( and Violation) for the final solution and CT in each scenario (all the golden cells in Table 3) are chosen for the next stage of the numerical experiment. We also consider all algorithms which obtain a solution with a similar value for and Violation to the best algorithms solution for the next stage. For more investigation in the large-scale, we choose at the swapping algorithms including all colored cells in Table 3 and algorithms with ≤ ; ∀ < in Figure 5 for each saturation level. In other words, we also consider the swapping algorithms which converge to the before the last outer loop.

Table 4 presents which algorithms are selected in each scenario for further investigation. MSA ranking and Probabilistic algorithms are suitable for all scenarios. MSA algorithm is efficient for small network, and Projection method and Step size Probabilistic algorithm are efficient for the large-scale network. Gap-based Normalized and Boost-up Gap-based algorithms provide good results in more saturated scenarios, while Gapbased Probabilistic algorithm is good for US scenarios and larger networks.

Initialization methods

The second stage of the numerical experiments corresponds to Step 5 in the solution algorithm (Figure 1). The methodology improvements to this step are discussed in Section 4.2. Now, an alternative initialization method (Keep solution; Table 1) for the inner loop is applied for all numerical experiments. The results for combinations of swapping algorithms and initialization methods are presented in Tables 5 and6. Table 5 presents the quality indicators of final solutions for initialization methods in all networks. About 5by5 network, in the US scenario, it is shown that Keep solution initialization obtains the optimal solution for all best three algorithms. Also, in S and OS scenarios, this method improves the performance of all swapping algorithms in comparison with the same swapping algorithm and All-or-nothing initialization. The results on the small network show that the Probabilistic and Keep solution combination provides the best solution in all saturation levels.

In Ring city network, same as 5by5, the Keep solution method improves the performance of swapping algorithms in particular for the Probabilistic method. The differences between All-or-nothing and Keep solution violation value of two closed solution in Table 5, box of MSA ranking and S scenario, shows the different direction of searching by swapping algorithm and the impact of the starting point at the beginning of each outer loop on the final result of optimization methods.

In the large-scale test case, the impact of the initialization is significant. It means that the quality of the solution by keep solution method is always better than All-or-nothing with a considerable difference of , e.g., the Keep solution method obtains a better solution (more than 50% lower ) for Step size Probabilistic and Probabilistic algorithms in US and saturation levels.

Table 6 presents the CT of all experiments in this stage. First, the results prove that the initialization method has an impact on CT. Second, the Keep solution method which is indicated by "Keep" in the Table 6 improves the speed of convergence for all swapping algorithms in comparison with the All-or-nothing method which is the default method in the literature. Third, the combination of Probabilistic and Keep Probabilistic method is excluded simply because it does not have a step size (Section 4.1.5). For methods with step size, the one or two best combinations in all test cases are chosen. The new methods for step size initialization are compared with the initial method (Section 4.3). Note that we fix the seed for probability functions in the Step size Probabilistic and Gap-based Probabilistic in order to compare the impact of step sizes. The results of applying the three methods on the three networks are presented in Tables 7 and8. Medal colors highlight the top three combinations for each scenario.

AGap V(G) AGap V(G) AGap V(G) AGap V(G) AGap V(G) AGap V(G) AGap V(G) AGap V(G) AGap V(G
Table 7 presents the quality indicators for the final solution of all experiments for all networks. Smart step size improves the performance of the MSA and Gap-based Normalized algorithms. The Reset method improves the MSA for the small network. For the medium-scale network (Ring city), the results show that the Reset method improves the MSA ranking algorithm, and the Smart method works well with Gap-based Probabilistic algorithm (Table 7). In the Boost-up Gap-based algorithm, the step size of this method is already modified at each inner loop by boost-up techniques. The result shows that applying the alternative step size methods cannot improve the performance of this algorithm.

The results in Table 7 for the large-scale show that the Smart method improves the solution of Gap-based Probabilistic and Initialization MSA algorithms compared to the Initial method which is the default setting for step size initialization and Reset method. Same as Ring city network, the Reset method improves the performance of Step size Probabilistic algorithm. The CT for all experiments of this stage is presented in Table 8. The Smart and Reset methods converge slowly in the small network, but they converge faster than the Initial method in the large-scale network particularly the Smart method for Initialization MSA and oversaturated scenario compared to other methods with which we can save a minimum of one day of computation.

CONCLUSIONS

This paper focuses on improving the solution algorithms for finding the user equilibrium considering trip-based dynamic network loading. We highlight the current drawbacks of existing swapping algorithms and propose several solutions to overcome them, and speed up the convergence. A significant contribution of this paper is the full benchmark of all algorithms for different network size and level of saturation. We compare the performance of the solution algorithms (see Table 1 as a synthesis of main algorithms and methods in this study) based on the quality of solutions and computation times. According to Table 9 and the results, this study shows that:

• The network size and saturation level has an impact on the performance of solution algorithms to solve the DTA problem.

• The combination of Probabilistic approach (without step size) and Keep solution initialization appears in most of the cases in Table 9 as the best algorithm.

• The initial assignment and step size at the beginning of the outer loop have a significant impact on the final solution and convergence speed of the algorithm.

• An alternative method, proposed by this study, to initialize the assignment pattern at the beginning of the outer loop (Section 4.2) improves the performance of all swapping algorithms compared to the recent methodology in the literature (Table 9).

• Two new methods, proposed by this study, for the initialization of the step size (Section 4.3) ensures that the algorithm converges and it has a direct impact on the speed of convergence. However, the step size cannot guarantee the quality of the final solution.

The analysis for the impact of The network size and saturation level on the convergence process shows that the classic algorithms (e.g., MSA) exhibit good performance in the smallscale network, but they do not provide a good solution in the large-scale network. The computational cost of the classic algorithms are also prohibitive for the large-scale network. One of the hybrid algorithms, Step size Probabilistic (see section 4.1.6), works faster in the large-scale network (Table 9). The MSA ranking is efficient for small-and medium-scale networks, but it cannot provide good results for the large-scale network. Moreover, the results show that some algorithm such as Gap-based algorithm, and Projection method are dominated by other algorithms for all scenarios.

The combination of Probabilistic approach (without step size) and Keep solution initialization is not necessarily always the best in terms of quality and speed, but it is the one that is most likely to obtain the best solution in all scenarios and can be considered as the most robust alternative. If the focus is only on the quality of the solution, more than one configuration can be used in most of the cases (Table 9). However, the computation time is very important, particularly for the large-scale network. For instance, in the large-scale and oversaturated scenario, Probabilistic algorithm cannot provide a better solution than Initialization MSA algorithm, but it is more than two days faster than Initialization MSA algorithm in computation time (Table 6).

About the two new methods for step size, they provide a better solution with a combination of different swap formulas than the classic method in the literature. The algorithms based on MSA are improved by the Reset step size method. Besides, the Smart method improves the algorithm based on the gap function and projection method. The new step size methods

FIGURE 1

 1 FIGURE 1 Solution algorithm for trip-based dynamic network equilibrium

FIGURE 2

 2 FIGURE 2 The three traffic networks of this study. (a): Smallscale network. (b): medium-scale network. (c) and (d): Largescale network.

FIGURE 3

 3 FIGURE 3The macroscopic fundamental diagram of 9 demand scenarios of the three traffic networks. There are 3 different saturation levels per network: Under Saturation (US), Saturation (S) and Over Saturation (OS).

FIGURE 4

 4 FIGURE 4The computation time bar chart of 9 demand scenarios of the three traffic networks. There are 3 different saturation levels per network: Under Saturation (US), Saturation (S) and Over Saturation (OS)

FIGURE 5

 5 FIGURE 5Convergence patterns for the swapping algorithms of all scenarios. There are 3 different saturation levels per each network: Under Saturation (US), Saturation (S) and Over Saturation (OS). denotes the satisfaction threshold.

  0

  compromise between quality and computation time for all network size and saturation levels.

TABLE 1

 1 All the methods in the inner loop considered in this study

	Method	Abbreviation	Reference
		Swapping algorithms (Step 6)
	MSA	MSA	Robbins & Monro (1951)
	MSA ranking	MSAR	Sbayti et al. (2007)
	Projection method	PM	Adapted Halpern (1967)
	Projection Initialization	PI	Adapted Friesz et al. (2011)
	Initialization MSA	IMSA	New
	Gap-based	GB	Lu et al. (2009)
	Gap-based Normalized	GBN	New
	Probabilistic	Prob.	Ameli et al. (2017)
	Step size Probabilistic	SSP	Halat et al. (2016)
	Gap-based Probabilistic	GBP	Verbas et al. (2015)
	Boost up Gap-based	BGB	New
	Inner loop initialization (Step 5)
	Default method	All-or-nothing Lu et al. (2009)
	Keep the assignment	Keep solution New
	Initial step size selection (Step 6)
	Default method	Initial	Lu et al. (2009)
	Re-initializing the step size	Reset	New
	Smart step size	Smart	New

TABLE 2

 2 Total demand for all test cases

	Level of saturation	5by5 Ring city Lyon6V
	Under Saturation (US) 3,520	12,000	20,000
	Saturation (S)	5,197	19,000	54,190
	Over Saturation (OS) 8,100	22,500	100,000

TABLE 3

 3

	Results of numerical experiments for eleven swapping algorithms [ (second)]	MSA MSAR GB GBN Prob. SSP GBP BGB PM PI IMSA	0.91 0.17 1.10 0.91 0.17 0.88 0.73 0.91 0.48 0.17 1.47	0.05 0.05 0.08 0.05 0.05 0.08 0.07 0.06 0.06 0.05 0.05	11.22 13.34 82.65 11.22 3.50 39.18 22.36 64.05 37.79 112.09 80.19	0.13 0.13 0.16 0.13 0.13 0.18 0.16 0.18 0.18 0.16 0.17	0.70 0.85 1.18 0.70 0.93 1.44 2.37 0.71 1.05 1.56 1.19	0.04 0.09 0.08 0.04 0.05 0.07 0.09 0.08 0.08 0.08 0.08	5.79 2.99 8.66 4.30 2.74 5.47 3.02 5.13 4.41 3.27 38.13	0.13 0.06 0.13 0.11 0.06 0.12 0.08 0.10 0.10 0.10 0.24	30.96 12.81 18.31 16.35 8.33 40.13 12.33 24.72 200.71 206.70 205.24	0.17 0.16 0.21 0.15 0.16 0.19 0.16 0.22 0.36 0.38 0.36	50.06 20.81 47.73 49.35 16.16 36.16 48.38 26.00 230.71 189.04 225.24	0.26 0.16 0.17 0.26 0.14 0.21 0.20 0.18 0.36 0.32 0.33	109.47 18.78 37.01 41.09 12.30 16.15 13.59 35.47 20.01 41.09 39.75	0.32 0.15 0.20 0.24 0.12 0.14 0.13 0.21 0.19 0.24 0.24	79.89 39.54 237.35 29.14 24.72 47.73 121.45 62.98 1157.21 27.83 798.47	0.25 0.24 0.35 0.16 0.13 0.25 0.26 0.25 0.35 0.15 0.43	180.38 233.44 183.83 80.79 106.83 339.87 153.00 240.95 108.45 73.43 47.18	0.22 0.28 0.23 0.17 0.19 0.30 0.34 0.35 0.27 0.15 0.14
		Network / algorithm	US AGap Violation	5by5 S AGap Violation	OS AGap Violation	US AGap Violation	Ring S city AGap Violation	OS AGap Violation	US AGap Violation	Lyon S 6V AGap Violation	OS AGap Violation

TABLE 4

 4 Best swapping algorithms

	Network	5by5	Ring city	Lyon 6V
	Scenario US S OS US S OS US S OS

TABLE 5

 5

			OS
		Lyon 6V	S
			US
	(second)]		OS
	Results of initialization methods [	Ring city	US S
			OS
		5by5	S
			US
		Network	Scenario	Algorithm / Indicator

  Table 9 presents the best configuration of the solution algorithm that

TABLE 7

 7 Results of initial step size methods [

	(second)]

Note that Symuvia is an open-source simulator which will be made freely available during summer

(http://www.licit.ifsttar.fr).(a) 5by5 (b) Ring city (c) c Google (d) Lyon6V

ACKNOWLEDGMENTS

The authors would like to thank the anonymous referees for their thoughtful comments, which helped improve both the exposition and technical quality of the paper.

This project is supported by the European Research Council (ERC) under the European Union's Horizon 2020 and innovation program (Grant agreement No 646592 -MAGnUM project).

solution method is faster than other methods in most of the cases as we can observe that this method always in the top two fastest methods in all scenarios (gold and silver cells in Table 6).

In order to have a better comparison between the performance of different initialization methods, the inner loop convergence patterns of MSA ranking and Probabilistic algorithms with both initialization methods are presented in Figure 6. The results correspond to the saturation scenario for the large-scale network. The default setting, which is the "Allor-nothing" method, starts at each outer loop with the same assignment pattern. It works like as handbrake at the beginning of each outer loop and forces the algorithm to start from the assignment with a high . Therefore, the swapping algorithm should attempt to come back to the optimal region by several iterations.

It is obvious that "All-or-nothing" method needs more iteration (CT) compared to the Keep solution method to find the new optimal solution for each outer loop. The Keep solution method converges faster than the other one and also provides a better solution (Table 5). For instance, in Figure 6, The Keep solution method prevents the MSA ranking method from spending several iterations in order to come back to the lower range of and also helps this swapping algorithm to converge faster than the initial version. Note that the first outer loop is the same for both methods and then from the second one "MSA ranking + Keep solution" continue with previous path flow distribution, but the initial version of the MSA ranking starts the second outer loop with the All-or-nothing assignment.

Moreover, Figure 6 shows the flexibility of probabilistic algorithm to search the solution space. The probabilistic algorithm moves in a larger range of during each outer loop, and it does not improve the solution sequentially except when the probability of swapping (equation ( 25)) is very low for all users, i.e., the algorithm is close to the optimal solution.

Step size methods

In the previous stage, we presented and discussed the results of the initialization method, i.e., Step 5 in Figure 1. Here, we will present and discuss the results for the step size methods (Step 6). For the final stage, we select the best methods (colored in Tables 5 and6) except the Probabilistic algorithm. The

speed up the convergence of all algorithms, especially in the large-scale (Table 8).

For future work, the authors are looking for meta-heuristic algorithms for DTA problem in order to speed up the optimization process with parallel computation. In addition, designing the framework to predetermine the computation budget based on network size, topology, and saturation level is an interesting topic.