Matheuristics for a multi-day electric bus assignment and overnight recharge scheduling problem

To limit greenhouse gas emissions in the public transportation sector, transit authorities are constantly increasing the proportion of electric buses (EBs) in their fleets. Due to space and budget constraints, more often than not, the number of chargers that can be installed at the depots is less than the number of EBs in the fleet. Moreover, even if there is one charger for each EB, it is virtually impossible to use all the chargers at the same time due to maximum power grid constraints. Thus, there is a need to devise optimization techniques that help to recharge the buses in an efficient and acute way, taking into account these charging infrastructure capacity constraints. In this study, we consider a multi-day electric bus assignment and overnight recharge scheduling problem that can be briefly stated as follows. Given a set of vehicle blocks (sequences of timetabled bus trips performed by the same bus on a given day) to be operated over several days, a set of identical EBs, and a set of chargers available at the depot whose charging function is a piecewise linear function, the problem consists in assigning an EB to each block and to schedule the overnight recharging operations at the depot such that the EBs never run out of energy when performing their blocks and the depot charging capacity is never exceeded. The objective is twofold: minimizing the total charging costs and minimizing the impact of the charging decisions in the long-term health of the batteries. We first model this problem as a mixed integer linear program (MILP) that can be solved with a commercial solver. Then, to yield faster computational times, we develop two multi-phase matheuristics based on the MILP. To show the interest of considering a multiple-day horizon, we introduce two other matheuristics that mimic current industrial practices and solve the problem sequentially, one day at a time. To evaluate all these algorithms, we use a set of 264 instances generated from data of an EB operator.