The combined line planning modification and vehicle scheduling problem for a fleet of electric buses

• Novel formulation of a two-stage approach for the combined line planning modification and vehicle scheduling problem for a fleet of electric buses. • Reformulation of each stage of the problem as easy to solve mixed-integer quadratic and mixed-integer linear programs. • Application in two real-world case studies in densely populated cities (Athens, Greece and Limassol, Cyprus). • Sensitivity analysis of the trade-off between unserved demand and electric vehicle acquisition costs. Transitioning from conventional public transport fleets to electric ones necessitates comprehensive strategic, tactical, and operational planning. To supplement the research work in this area, the current study focuses on the Combined Line Planning Modification and Electric Vehicle Scheduling Problem, addressing the complexities of integrating electric buses into existing transport networks. We introduce a two-stage approach for the solution of this problem. First, we schedule the fleet for each bus line for different possible layouts (options), that arise from the elimination of bus stops in the existing layout of the examined lines, taking into consideration the charging needs of the buses by solving the Electric Vehicle Scheduling Problem (E-VSP), which is solved as a mixed-integer quadratic program (MIQP). At this stage, the modeling takes into account the real-world timetables of the line, the autonomy of the buses, the number of trips performed per day, the trip distances, and the deadheading distances. All these essential parameters remain the same for all the examined modifications and are based on the data provided by the transport operator for the existing lines. Then, in a second stage, we examine which modification of each bus line is optimal, while considering the passengers’ demand for each stop and the available fleet size, formulated as a mixed-integer linear program (MILP). The goal of the overall two-stage approach is to minimize the unserved passenger demand that arises from the possible modifications of bus lines and the number of required vehicles when transitioning to electromobility.