Research On Some Optimization Problems In Urban Public Transit Operation Planning

As the core of the public transit company's planning business,the quality of the public transit operation planning scheme is directly related to the efficient operations of the public transit company.Bus scheduling and driver scheduling are the most important parts of the public transit operation planning.It is proved that a scientific and reasonable optimization scheme of bus scheduling and driver scheduling can not only achieve the effective allocation of public resources,but also can reduce operating costs.On the other hand,a good scheme can also be more fair,satisfied and effective for drivers,result in ensuring the efficient operations of transit companies.Therefore,the research focuses on some optimization problems about urban public transit operation planning,including bus scheduling problem,driver scheduling problem and driver rostering problem,and attentions are mainly paid on model development and algorithm design.Firstly,from a systematic optimal point of view,this thesis uses integrated research methods to study the integrated optimization problem of bus scheduling and driver scheduling in cross line mode.The integrated model considers some constraints,such as depots capacities,depot parking and so on,and minimizes the number of buses and operating cost for all buses for the bus scheduling problem.Besides,for driver scheduling,the model minimizes the number of drivers and operating cost for all drivers and maximizes driver's meal time satisfaction by considering some constraints.For example,slack labor intensity,the maximum time of changing bus and meal time etc.Finally,according to the features of this integrated model,a nested ant colony algorithm for solving the above mentioned problem is designed.Moreover,a realistic example is given to verify the effectiveness of the integrated model and its algorithm.Secondly,by considering some uncertainty existed in real traffic,this thesis studies bus scheduling and driver scheduling integrated optimization problem with uncertain information,which considers some conditions,such as vehicle breakdown and delayed trips by congestion.The integrated model considers some constraints,such as the confidence level of two trips connecting feasibility,the impact of vehicle breakdown and so on,and minimizes the number of buses and operating cost for all buses for bus scheduling problem.For the driver scheduling problem,the model minimizes the number of drivers and operating cost for all drivers and maximize driver's meal time satisfaction by considering some constraints,such as slack labor intensity,the maximum time of changing bus and meal time,etc.Finally,according to the features of this integrated model with uncertain information,two nested ant colony algorithms,which are based on the model transformation and random simulation for solving the above mentioned problem is designed.Moreover,a realistic example is given to compare the relationship between the reliability and the cost of the model based on the given information and uncertain information.Then,this thesis studies crew rostering problem based on balanced work time and personal preference,including single cycle crew rostering problem and fixed cycle rostering problem.For single cycle crew rostering problem,the target is to balance the work time of each duty group by considering the requirement of rest.For fixed cycle rostering problem,the model considers some hard constraints,such as the lower limit of the number of drivers,leave request of the drivers and considers some soft constraints,such as the continuous working days,rest frequency,the rest time between two adjacent duty and personal preference etc,to balance work time of each driver.In order to solve the above two models,a special heuristic algorithm is designed.Moreover,a realistic example is given to verify effectiveness of the above algorithms.Finally,on the basis of the theory and algorithm which are mentioned above,an urban public transit planning and operation module is designed and developed by using Microsoft Visual Studio 2008 development platform,SQL Server 2008 r2 and C#.Functions of the module include basic data management,creating bus timetables,bus scheduling,driver scheduling,driver rostering and so on.