Research On Multi-type Bus Operation Scheduling Problem Based On Robust Optimization

The road-based bus is an important component of the urban public transportation system,with low-carbon environmental protection,large capacity,and flexible scheduling.However,in recent years,as urban traffic congestion has intensified and passenger demand has become more diverse,passenger satisfaction with road-based bus services has continuously decreased.Therefore,the operation organization mode and operational service efficiency of roadbased bus need to be optimized and improved.Given this,based on robust optimization method,this thesis focuses on the bus timetable design,charging scheduling formulation,customized route planning,emergency bridging organization,to improve the reliability and attractiveness of road-based bus services.The main innovative work is as follows:(1)Based on GPS data,this thesis studies a scenario-based timetable robust optimization model,aims to maximize the expected profits in all scenarios.The K-means clustering approach is utilized to identify the scenarios of spatialtemporal travel time.A set of binary variables is introduced to transform the robust optimization model into an integer linear programming model,and a solution space compression is designed to speed up the solving process.The effectiveness of the proposed model is verified by optimizing the Beijing bus line 628.The results show that the scenario-based robust optimization model could increase the expected profits by 15.80% and 30.74% compared with two deterministic optimization models(maximum probability model and mean model),respectively.In addition,the proposed solution space compression approach could effectively shorten the computing time by 97%.(2)This thesis develops an electric bus opportunity charging scheduling model that considers battery capacity,battery range,battery charging time,and charging facility configuration constraints.The objective is to minimize the total cost during the operation period(including the loss cost of charging facilities,the loss cost of electric vehicle batteries,charging cost,and additional waiting penalty cost for passengers).Considering that the optimal opportunity charging scheduling decision may not meet the bus energy consumption constraint conditions when the vehicle energy consumption is uncertain,a chanceconstrained programming model is developed,and a distributionally robust optimization method is introduced to characterize the probability distribution of uncertain energy consumption through a polyhedral ambiguous set.Strong duality theory and chance-constrained approximation methods were used to transform the chance-constrained programming model into a computable tractable form.The numerical experimental results show that when energy consumption changes in four different scenarios,compared to the deterministic model,the minimum expected total cost of the distributionally robust optimization model is reduced by 26.5%,33.5%,38.7%,and 42.2%,respectively.(3)This thesis studies a customized bus route and timetable optimization model considering holding control strategies,aiming to maximize bus operators’ profits,by optimizing vehicle routes,schedules,and passenger allocation decisions.The uncertain travel time is clustered into several scenarios,and the fluctuation range of each scenario’s probability is characterized by a box uncertainty set and an ellipsoidal uncertainty set.The robust counterpart model is transformed into a computable tractable form through strong duality theory.A hybrid heuristic algorithm combining a genetic algorithm,a large neighborhood search algorithm,and a branch and bound algorithm(GA-LNSBB),and an order-based clustering divide and conquer(OC-D&C)method are designed to address real-world large-scale and ultra-large-scale problems,respectively.The numerical experimental results show that implementing the holding control strategy makes customized bus more flexible in planning routes and allocating orders,which can significantly increase operational profits.The expected profits obtained by the robust optimization model are 44.3% and 23.9%higher than those obtained by the maximum probability model and the mean model,respectively.The GA-LNS-BB hybrid algorithm performs better than CPLEX and GA,LNS,and PSO algorithms regarding solution time and quality.A practical case study in Beijing verified that the OC-D&C method could improve the accuracy and efficiency of the algorithm.(4)This thesis considers the emergency scheduling problem of bridging buses,with the goal of minimizing the maximum travel time of all bridging vehicles,and establishes a distributionally robust credibilistic optimization model that considers the passenger demand uncertainty.The uncertain passenger demand is characterized by parametric interval-valued possibility distributions and their associated uncertainty distribution sets.Based on credibilistic and robust optimization theories,the proposed model is converted into equivalent robust counterpart models.Based on numerical experiments conducted on Shanghai Rail Line 1,the results show that the distributionally robust credibilistic optimization method can provide a better uncertaintyimmunized solution for emergency management problems facing surging passenger flow.This thesis seeks the optimal road-based bus scheduling optimization plan,which can effectively improve the operational efficiency and service level of road-based bus,alleviate traffic congestion,promote sustainable development of urban transit,improve residents’ travel experience,and make important contributions to the economic and social development of the city.