| As the public transit system has the advantages of green,highly efficiency,and energy-saving,it plays an important role in improving traffic conditions in metropolis.The schedule of buses is one of the core components of bus company’s daily operation,it not only determines the efficiency of fleets’ resource allocation,but also provides the basis for real-time dispatching.Normally,the schedule generated by traditional approaches is based on timetable and trip set,taking the couple constraints between any pair of trips into consideration.When using the electric transit buses instead the conventional ones,one needs to take care of the constraints incurred by the characteristics of electric buses.At the same time,transit bus scheduling problem(TBSP)is a complex combinatorial optimization problem,it probably leads to infeasible solutions when adding new constraints directly to the existing models and methods,making the electric TBSP difficult to solve.In this condition,one needs new models and algorithms to solve the problem to promote developments and applications of electric transit buses.How to schedule the electric buses precisely and efficiently has become an important issue in front of the bus company managers and researchers.In this dissertation,the operating process and driving characteristics of electric transit buses are analyzed,models and algorithms for scheduling electric transit buses are proposed,to help bus companies efficiently arranging their electric buses.It provides theoretical support to electric transit bus arrangement systems and sets up template to other public industries that using electric vehicles in their resource allocation and operation optimization management.The main work and innovation of this dissertation are as follows:(1)According to the impact of different charging modes to the operation of electric transit buses,the scheduling modes are divided into two categories: the “slow-charging mode” and “fast-charging/battery-exchanging mode”.Based on the actual operating data,the operational characteristics of electric buses are analyzed.According to the features of public transport operation,the schedule is represented as a topological network consisting of depots,trips,charging stations,trip operating sequence and charging opportunities.Then,the electric TBSP is transformed into a network flow optimization problem.(2)The electric transit bus scheduling based on “slow charging” is converted into a mileage-constrained vehicle scheduling problem.Two types of optimization models are formulated.One is the compact model,taking the minimization of fixed cost,operational cost and deadhead driving/waiting cost as objective functions,adopting limited maximum bus driving mileage and couple condition between successive trips as constraints,employing the connections between any pair of trips as variables.The other one is a 0-1 integral programming model based on set partitioning theory,taking the total cost of the schedule as the objective function,employing the feasible bus plans as variables,and all of the complicated constraints are implicitly defined in the set of feasible bus plans.An optimization algorithm based on branch-and-price technique is designed to solve the latter one.The lower bound can be achieved by iterations of column generation,and the integral solution is obtained by branch-and-bound.The computational results on simulated examples and practical instances show the efficiency of the models and algorithm.(3)The electric TBSP based on fast-charging/battery-exchanging is converted into a vehicle scheduling problem with energy replenishment,and an optimization model is formulated.Two algorithms are designed to solve the fastcharging/battery-exchanging electric TBSP.One is a hybrid meta-heuristic approach based on variable neighborhood search and tabu search,which is used to approximatively solve large scale instances;the other one is a mathematical programming method based on branch-and-price technique,which is used to accurately solve small or medium scale instances.The computational experience shows the feasibility and efficiency of the hybrid meta-heuristic algorithm and the exact algorithm.(4)In the context of promoting green transportation,the impact of fixed cost with multiple bus types and emission cost of conventional buses to the bus fleet operation is analyzed.Considering a hybrid operation of electric and conventional buses,a Heterogeneous Transit Bus Scheduling(HTBS)problem is proposed.Based on different emission limitation,four types of optimization models are formulated,these are: HTBS model with emission cost,HTBS model with limited vehicles;HTBS model with hard emission constraint and HTBS model with soft emission constraint.The computational complexity of the models is analyzed,and a mathematical programming-based algorithm is designed to solve instances with some dozens of trips. |
