Matheuristic Fixed Set Search Applied to Electric Bus Fleet Scheduling

In recent years, there has been an increasing growth in the number of electric vehicles on the road. An important part of this process is the electrification of public transport with the use of electric buses. There are several differences between scheduling an electric or diesel bus fleet to cover a public transport timetable. The main reason for this is that electric buses have a shorter range and need to be charged during operating hours. The related optimization problems are often modeled using mixed-integer programming (MIP). An issue is that standard MIP solvers usually cannot solve problem instances corresponding to real-world applications of the model within a reasonable time limit. In this paper, this is addressed by extending the fixed set search to a matheuristic setting. The conducted computational experiments show that the new approach can be applied to much larger problems than the basic MIP. In addition, the proposed approach significantly outperforms other heuristic and metaheuristic methods on the problem of interest for problem instances up to a specific size.