Research On Flexible Feeder Transit Route Planning Based On Improved Tabu Search Algorithm

With the rapid development of urbanization in China,urban areas expanding and urban population filling in,the issues of increasing travel demand,huge car ownership,heavy environmental pollution,massive energy consumption become more and more severe.Public transportation system,which helps with traffic demand,environmental pollution and energy consumption,serves well for high-traffic locations and routes,but it could barely cover areas with low traffic,which means the regular public transportation system has poor accessibility and could not provide convenient door-todoor service in such areas.The flexible transit system,as a new transit system between the regular public transit and the taxi service,provides quasi-personal service based on customers' reservations,which could solve the problems that regular public transit couldn't solve in low-traffic areas as a feeder system or a microcirculation system.This research reviews current theories and methods in the transit route network design,the flexible transit route design and etc.,and studies features of the flexible transit system and compatibilities of this system serving as a feeder system.Based on analysis of operating mechanism and formularization of critical aspects,this research builds a model describing routes of flexible feeder transit system.This model aims at minimizing customer trip costs and system operation costs as well as maximizing potential traffic attraction with constraints of operating time,vehicle load threshold and etc.This model deals with not only single-hub system but multi-hub system which is more practical.Flexible feeder transit system accepts reservations ahead of time as well as in time,which means vehicles could modify its route in operation and provide more flexible and personal service.This research uses a two-phase model to describe static route planning and dynamic route modification and develops two different methods to accomplish dynamic modification.The first method,Segment Expanding Method,which focus on local segment expansion and optimizes only a local segment of the whole route,is simpler in calculation but may not get the best result for whole system.The second method,Off-Route Method,which optimizes system costs and traffic attraction of the whole route,could always get the best result for the entire route but need much more calculation.Given the strength and shortcomings of the two methods,this research provides a more practical heuristic method: Neighbor Inserting Method.The model built in this research is np-hard,which means there are no analytic solutions for this model.This research chooses Tabu Search algorithm to get the best algebraic solution.But some improvements and modifications must be made for both the model and the algorithm before model calculation because of conflicts of this model and the search algorithm.This paper creates five methods of modification: route shrink,route virtualization,node mirror,node removing and constraints punishment.With the route model and the improved algorithm mentioned,this research applies flexible feeder transit system in Huilongguan district in Beijing,which demonstrates the effect and reliability of the model and the algorithm created by this research.