 # Nonlinear Complementarity Problem (NCP) Formulation

For fixed demands, the DTA problem with the tolerance-based DUO route choice principle is to find a route flow vector f* such that: (8.13) (8.14) (8.15) (8.16) (8.17)

where is the demand of OD pair rs at time t; is a unique mapping yield ing route travel times for a given route flow vector f.

Eqs. (8.13)-(8.14) express the tolerance-based DUO principle. Eqs. (8.15)-(8.17) are the flow conservation and non-negativity conditions. Eq. (8.16) considers the traffic flow component as a unique functional mapping yielding route travel times for given route flows.

The tolerance-based DUO route choice problem (8.13)-(8.17) can be reformulated as an NCP by introducing three more conditions. By attaching to the flow conservation condition (8.15), we obtain (8.18)

As , the shortest OD travel time, must be greater than zero, - must hold at optimality. Adding this to the problem (8.13)-(8.17) will not alter the optimality condition. For mathematical completeness, we also introduce two more conditions to the original problem: (8.19) (8.20)

They include and as special cases and therefore do not change the optimality condition of the original problem ((8.13)-(8.17)). The DUO route choice problem with fixed demands can then be considered as the problem of finding a route flow vector to satisfy Eqs. (8.13)-(8.20).

By putting Eq. (8.16) into Eqs. (8.13) and (8.14), the DUO route choice problem with fixed demands (8.13)-(8.20) can be written as an NCP: to find such that (8.21) (8.22)

and (8.23)

where (8.24) (8.25)

and is a vector of is a vector of lowest OD travel times, and; , and follow earlier definitions.

# Solution Existence and Uniqueness

For ease of explanation, we first define a non-negative gap function H(f): (8.26)

where the indicator variable equals 1 if the flow on route p between OD pair rs at time t is nonzero, and equals zero otherwise. This gap is the largest difference between the travel time of all used routes and the corresponding shortest OD travel times under the route flow pattern f, and measures how far the current solution is from the traditional DUO solution.

To analyse the existence and uniqueness of solutions, we define the theoretical gap (TG), which is the minimum of the largest difference between the travel time of all used routes and the corresponding shortest OD travel times of all feasible flow patterns. In other words, TG is the smallest gap of all the feasible solutions. Mathematically, the theoretical gap (TG) is expressed as follows: (8.27)

The value of the theoretical gap depends on the network and the demand pattern. In DTA formulations with the more realistic physical-queue representation, the route travel time functions may not be always continuous with respect to the route flows, rendering the existence of solutions not always possible (Szeto, 2003), or equivalently their theoretical gap never reaches zero. For the tolerance-based DUO route choice problem with physical queues, in a similar manner, solution existence is not guaranteed. A solution exists to the problem if and only if the theoretical gap is less than or equal to εmax: (8.28)

According to Eq. (8.28), the existence of solutions to the physical-queue tolerance-based DUO problem depends on the theoretical gap (which is related to the network topology and demand pattern) and the parameter εmax (which is related to the behaviour of the network users). In general, as εmax and hence constraint (8.28) are gradually relaxed, solution existence gradually becomes easier. However, we emphasise the importance of specifying the tolerance level from a behaviour perspective rather than as a numerical means for obtaining equilibrium solutions. If the tolerance level is specified at a level higher than the actual behaviour, then the solution will stop at a premature 'equilibrium', even though in reality, travelers are still swapping routes in the search of better ones. For point queue DTA models, the route travel time is always continuous with respect to route flows. The solution set is convex. Once a continuous transformation function (Han et ah, 2014) is used to reformulate the problem, a solution always exists to the problem regardless of the value of εmax. In summary, solution existence is both a function of the network topology and travel demand, the behavioural tolerance of the users on route swapping, and choice of travel flow models.

On the issue of uniqueness of solution, as one can see, when εmax approaches infinity, all feasible gap values satisfy (8.28) and hence the corresponding flows are solutions, implying that multiple solutions are possible in this problem. In fact, even if the tolerance is zero, multiple solutions can still be possible, similar to the case of the traditional DUO problem (Lo & Szeto, 2002a; Szeto, 2003).