Models And Algorithms For The Large-scale Frequency-based Transit Equilibrium Assignment Problem

With the continuous development of urban economy and society,the travel demand is also increasing.Public transit(including rail,bus,BRT,etc.),as an important part of the metropolitan transportation system,is growing to undertaken large amounts of ridership.As a key application for transit network planning and policy evaluation,travel demand forecasting is a fundamental computational tool for transit system operation and management to improve the service level of high-capacity transit.This research focuses on the frequency-based transit equilibrium assignment problem(TEAP),which aims to establish a spatial equilibrium between the demand for moving between pairs of locations in a network and the supply capacity available to serve such demand.However,the complexity within a transit itinerary(including waiting,boarding,alighting,transferring,etc.)makes it difficult to properly represent the choice behaviors of transit passengers,which needs to simultaneously account for congestion effects(e.g.,queuing,comfort,and capacity constraints)along different parts.Besides,travel choice on transit networks is broadly defined as a hyperpath rather than a simple path.The complex structure of it makes existing algorithms struggling to solve today’s large-scale problems.To this end,this paper firstly proposes a point-to-point service evaluation method for transit systems to objectively measure its competitiveness based on the optimal hyperpath(Chapter2);then extends the TEAP model and proposes two efficient solution algorithms with two variants of topological decomposition schemes(Chapters 3 and 4);and finally proposes a TEAP model that considers capacity constraints and presents the solution algorithm based on two novel algorithmic frameworks(Chapter 5).The main contents and contributions are summarized as follows.(1)Chapter 2 proposes a point-to-point evaluation methodology that quantifies the competitiveness of transit relates to taxi and evaluates it through a case study based multifaceted empirical data collected in Shenzhen,such as taxi GPS trajectories,bus and rail service schedules.For each taxi trip given the O-D’s location,we first search for the best transit hyperpath in a multi-modal network(bus and railway).Then,we measure the competitiveness of the transit service relative to taxi according to the preference of a rational traveler and conduct sensitivity analysis.Compared with traditional methods(manual survey),our proposed methodology is less costly and more reliable,while providing the details of an individual transit trip.Without considering the on-board congestion effects,the method can be regarded as a special case to the all-or-nothing assignment.(2)Chapter 3 proposes two hyperpath-based TEAP algorithms: a greedy algorithm and a gradient projection(GP)algorithm.With the help of the O-D based decomposition scheme,we design a uniform hyperpath-based algorithmic framework.Moreover,a hyperpath management scheme called Adaptive Inner Looping(AIL)is devised to determine which O-D pairs need more or less work to accelerate convergence.Compared with existing ”quasi-link-based”algorithms,numerical results show that the hyperpath-based algorithm is much more efficient in handling large-scale problems.(3)Chapter 4 presents an destination-based TEAP reformulation and proves the equivalence with the hyperpath-based TEAP model.Built on the concept of hypergraph,the proposed hyperbush algorithm(HBA)predicates on the idea of decomposing a hypergraph into hyperbushes,each rooted at a destination(or an origin).A hyperbush is an acyclic hypergraph that stores,in a highly compact manner,all hyperpaths destined for a destination.By maintaining hyperbushes(including hyperbush expansion,equilibration and trimming operations)and limiting traffic assignment to them,HBA promises to obtain more precise solutions at a lower computational cost,both in terms of CPU time and memory consumption.Our numerical experiments confirm that HBA runs up to 5-7 times faster than the hyperpath-based algorithms in obtaining high quality solutions for large-scale problems,at a considerably 4-5 times lower memory consumption.(4)Chapter 5 further presents a TEAP model that explicitly considering capacity constraints because of transit vehicles’ limited space.By introducing the Lagrangian multipliers,we define the generalized hyperpath cost and prove the equivalence between the model and the equilibrium condition.The method of multiplier is then applied to solve the model by transforming it into an uncapacitated TEAP subproblem,which greatly reducing the computational complexity.The experimental results show that the model can describe the changes of passengers’ route choice due to the inability to get boarded,making the results of the flow distribution more reasonable.In a nutshell,on the one hand,this research enables to help transit agencies to cope with the competition from other modes using multifaceted empirical data;on the other hand,it designs and develops several efficient algorithms for the large-scale TEAP,thereby providing theoretical and application support for the upper-level transit network planning.