Research On Boundedly Rational Dynamic Traffic Network Equilibrium Problems Based On Column Generation Algorithm

With the development of economy and society,the number of private cars is increasing significantly,and the congestion problem is becoming prominent.How to improve the travel efficiency and alleviate traffic congestion has become important scientific issues of traffic science.At present,the research on traffic network equilibrium model and algorithm has been widely used in traffic network planning,traffic policy evaluation and other fields to optimize urban traffic management.Based on the existing theories and methods of urban dynamic traffic network equilibrium,this thesis considers the boundedly rational choice behavior of travelers,extends the mathematical model,designs the column generation-based algorithms,and models the service and incentive mechanisms of shared car.The details are as follows:First,analysis and solution to the bounded rational dynamic user equilibrium(BRDUE)problem.The traditional column generation algorithm is slow in solving the dynamic user equilibrium problem,and the existing strategy only involves improving the frequency of conducting path searching.To expand the application of BR-DUE model,four different strategies are proposed combined with time and space dimensions,and then embedded in a tolerance-based column generation algorithm.A tolerance-based minimum cost path search strategy allows travelers seeking non-optimal paths and accelerates the CG algorithm by decreasing the size of the path sets.Self-adjusted convergence threshold strategy defines and adjusts the relative convergence threshold dynamically and can decrease the number of dynamic network loading during the intermediate iterations.From the temporal dimension,a varied temporal resolution strategy tries to assign flows to potential time-dependent paths by temporal exploration and exploitation.Path search skipping strategy performs path search only at potential time intervals and accelerates the CG algorithm by decreasing the number of the path searches.With these four strategies,the tolerance-based CG(TBCG)algorithm is proposed.The numerical results show that the TBCG algorithm leads to significant computation time reductions compared with CG algorithm.Second,analysis and solution to the activity-based bounded rational dynamic user equilibrium problem.Multi-dimensional choice facets,long target time horizon and time window constraints bring great challenges to the application of the activity-based BRDUE models in large network.Based on the TBCG algorithm,the multi-state supernetwork is introduced to design an efficient algorithm for solving the activity-based BR-DUE problems.First,with the formulation of the link cost in multi-state supernetwork,the activity-based BR-DUE problem is proposed.Second,the spatial and temporal exploration and exploitation strategies are proposed.Exploration strategies:spatial exploration strategy modifies the tolerance-based minimum cost path search strategy and can search for the activity-travel patterns.Temporal exploration strategy uses a more flexible criterion to extend the current time regions.Exploitation strategies:spatial exploitation strategy adjusts the original lower bound of the relative convergence threshold to ensure the accuracy of the solution.Temporal exploitation considers the attributes of activities and takes one day as the time horizon.Based on the above four strategies,an improved TBCG algorithm is proposed.The numerical results demonstrate that the improved TBCG algorithm can solve the activity-based BR-DUE problem effectively without losing solution quality.Third,modeling and solving the complex relationship between supply and demand of shared cars under different first-come-first-served(FCFS)mechanisms.To reduce the waiting time of travelers and improve the efficiency of car sharing service,the complex relationship between the supply and demand of shared cars is studied.First,the supply and demand relations are formulated under four FCFS mechanisms,which include no waiting FCFS,aggregate FCFS,disaggregate FCFS and the VIP membership disaggregate FCFS.Although four mechanisms have the same supply-demand dynamics under some condition of oversupply,the two disaggregate mechanisms lead to more efficient shared car utilization rates compared with other two mechanisms.Second,a path expansion strategy is proposed to calculate the travel cost under disaggregate mechanisms,and the corresponding BR-DUE model is proposed.Last,within the multi-state supernetwork,the improved TBCG algorithm is adjusted to solve the proposed BR-DUE problem.Numerical examples demonstrate that different FCFS mechanisms tend to have different supply-demand dynamics and that the disaggregate mechanisms are more efficient in satisfying the demand of shared cars.Four,modeling and solving the incentive mechanisms of the user-based shared car relocation problem.To solve the problem of uneven space-time distribution of shared cars and minimize the cost of operators,the shared car relocation problems are proposed.First,the supply-demand relationship under four different relocation schemes are formulated to reflect the supply-demand relationship between shared cars and users.The trigger conditions under the alternate pick-up and drop-off location incentives are presented.Second,the path expansion strategy is improved to calculate the path cost under ride-sharing incentive.Incorporating the bounded rationality,this thesis defines the incentive-based boundedly rational dynamic user equilibrium and proposes the corresponding equilibrium conditions.In addition,the transfer processes of path flows under different incentive mechanisms are analyzed.With the consideration of the problem attributes,the improved TBCG algorithm is adjusted to solve the proposed equilibrium model.Numerical example shows that with the increase of incentive degree,more users are served with the alternate pick-up,drop-off location or ride-sharing incentives.