Introduction
Traffic assignment is the process of finding the flow pattern in a given network with a given travel demand between the origin-destination pairs. Equilibrium assignment finds flow patterns under user equilibrium, when no driver can unilaterally change routes to achieve better travel times. Optimal assignment determines the flow patterns such that the total travel time cost in the network is minimum, usually under external control. Assignment has long been an essential step in the transportation planning process.
Review of Research Stage of TAP
Stage 1: Traditional TAP
Limitation:
- Not applicable for Battery Electric Vehicles (BEV) since there is no relay -
- Only suitable for convex problem -
Reference:
S. C. Dafermos and F. T. Sparrow, The Traffic Assignment Problem for a General Network.Journal of Research of the National Bureau of Standards-B.Vol73B,No.2, pp. 191-117, 1969.
L. J. Leblanc, E. K. Morlok and W. P. Pierskalla, An Efficient Approach to Solving the Road Network Equilibrium Traffic Assignment Problem,Transportation research 9.5, pp. 309-318, 1975.
Stage 2: Range-Bounded TAP
Limitation:
- Not applicable for Battery Electric Vehicles (BEV) since charging stations are also neglected -
- Only suitable for convex problem -
References:
R. Jayakrishnan, Wei T. Tsai, J. N. Prashker, and S. Rajadhyaksha, A faster path-based algorithm for traffic assignment,1994.
L. J. LeBlanc, R. V. Helgasonand D. E. Boyce, ImprovedEfficiency of the Frank-Wolfe Algorittwn for ConvexNetworkProblems. Transportation Science, Vol 19, pp. 445-462,1985
M.Florian, J. Gu61atand H. Spiess, An Efficient Implementation of the PARTAN Variant of the Linear Approximation Method for the Network Equilibrium Problem. Networks, Vol 17, pp. 319-339, 1987.
Stage 3: TAP with relays (flow-independent)
Limitation:
- Neglect the relevance of energy consumption and traffic flow-
- Not applicable to large scale network-
References:
Florian, Michael, Isabelle Constantin, and Dan Florian. “A new look at projected gradient method for equilibrium assignment.” Transportation Research Record: Journal of the Transportation Research Board 2090 (2009): 10-16.
Nikolova, Evdokia, and Nicolás E. Stier-Moses. “A mean-risk model for the traffic assignment problem with stochastic travel times.” Operations Research 62.2 (2014): 366-382.
Stage 4: TAP with relays (flow-dependent)
Objectives:
- Reformulate the flow-dependent TAP-
- Develop efficient solution methods that are adaptive to large scale networks-
References:
He, Fang, Yafeng Yin, and Siriphong Lawphongpanich. “Network equilibrium models with battery electric vehicles.” Transportation Research Part B: Methodological 67 (2014): 306-319.
Problem Statement
\begin{center}
\footnotesize
\tikzstyle{process} = [rectangle, minimum width=4cm, minimum height=1cm, text centered, draw=black, text width=4cm, align=left]
\begin{tikzpicture}[node distance=4cm, >/.tip={Latex}]
\node [process] (primal) {
\textbf{Primal problem}:
A TAP with a given feasible path set
};
\node [process, below of=primal] (master) {
\textbf{Master problem}:
A relay embedded shortest path problem, with given network condition
};
\path[->] (primal.250) edge node [left, text width=1.5cm, align=center] {Updates of network status} (primal.250 |- master.north);
\path[->] (master.70) edge node [right, text width=1.5cm, align=center] {Feasible path set} (master.70 |- primal.south);
\end{tikzpicture}
\end{center}
The above diagram shows the relationship between primal problem and master problem of TAP. The flow-dependent TAP needs a given feasible path set to update network status from time to time dependent on flow. The feasible path set is calculated by the master problem (shortest path with relay), which is the topic discussed here. The reason why this problem needs to take relay into consideration can be explained by the following test case:
\begin{figure} \includegraphics[width=.8\textwidth]{BEV.png} \caption{Shortest path from node 1 to node 20, generated by Dijkstra algorithm} \label{1} \end{figure}
Assume that the energy storage range of BEV is 25 unit energy consumption. From Figure 1, it shows that for the shortest path from node 1 to node 20 needs 38 unit energy consumption, which is larger than the energy storage capacity 25. Problem then arise: Even the path with the lowest energy consumption becomes infeasible under BEV settings. Solution for the problem is that we need to navigate the vehicle to any charging station before it runs out of power on the condition that the path including the charging process should still be the shortest. Therefore the master problem: A relay embedded shortest path problem should be studied. The master problem can be solved by applying Dijkstra algorithm. The Dijkstra algorithm is implemented by separating a path into sub-paths: origin to charging station and charging station to destination. Modified Dijkstra algorithm is able to generate a set of feasible paths for the sub-paths and then select the dominant path from the combination of sub-paths. The challenge this solution faces is that complexity explodes with larger network since it’s a nondeterministic polynomial time (NP) problem. I think of reinforcement learning as an improvement method, which will be discussed in detail in the following sections.
