Research On Optimization Of Multi-depot Electric Bus Vehicle Scheduling Problem

In the past decade,in order to implement the sustainable development strategy and achieve the national goal of "Carbon Peaking" and "Carbon Neutrality",pure electric buses have been supported and popularized in China.As one of the new energy vehicles,electric buses are favored by public transit corporations and companies in various countries for their lower noise,lower carbon emission,more energy conservation,and more safety performance.According to the data in the Corporate Social Responsibility Report 2020 released by Beijing Public Transportation Group,the percentage of new or clean energy buses in Beijing is 87.34%.The proportion of pure electric buses has increased year by year,accounting for more than 50%.However,compared with traditional fuel buses or gas buses,electric buses have disadvantages such as short travel range,long refueling time and short battery life.Electric buses can hardly complete a full day of transit tasks even when they are fully charged,so they must be constantly recharged.But charging resources are usually more limited.Beijing has built a total of 212 rechargeable depots or charging stations,which is for nearly 1,000 new energy bus lines.This means that without a reasonable scheduling of charging resources,the normal operation of public transportation will be seriously affected.How to use as few vehicles as possible to complete bus route departures while considering charging has become a new challenge that the industry needs to address urgently.Most of the existing studies focus on the problem of single depots or consider charging processes that differ from the reality of the charging process.However,this thesis fully considers the realistic charging situation,investigates the multi-depot electric bus vehicles scheduling problem with flexible charging technology,and examines the uncertain charging time and the waiting for charging due to the limited number of charging piles.Under the condition that the public transportation network and operating parameters are determined,this thesis describes the problem by developing a mixed-integer programming mathematical model that can accurately control the charging time and proves that the model for this problem is NPhard.For algorithm,most of the research has focused on heuristic algorithms in solving this type of problems.Although the solution time is ensured,it does not guarantee that the solution is definitely optimal.The bus dispatching schedule is a long-term plan,and the solution does not have to be completed in real time.Thus,a framework of branch-and-price algorithm is designed for global exact optimal solution according to the special structure and characteristics of the problem model.Based on the ideology of the Dantzig-Wolfe decomposition algorithm,the primary problem model is decomposed into a master problem with chains of trips as the base columns,and a sub-problem for each chain of trips.The sub-problem is solved by improving the Pulse algorithm,which is currently the most effective algorithm for solving this type of subproblem.The use of strategies such as relaxation constraints,advance bounding,multiple column addition and column management effectively resist the deterioration of the master problem and make the whole algorithm more efficient.Finally,this thesis uses a large amount of realistic experimental data and traffic networks to verify the logic and performance of the algorithm and compares it with the existing more efficient mixed-integer programming solver Gurobi.The result shows that Gurobi can only solve the sizes of problem for up to 40 departure tasks.However,the algorithm designed in this thesis can solve the sizes of problem for up to 100 departure tasks.This thesis also provides a sensitivity analysis of the impact on changing parameters which are the number of charging piles,charging rate and the range of battery in the problem.The results can provide additional decision support for decision makers.