Computational Methods for Scheduling the Charging and Assignment of an On-Site Shared Electric Vehicle Fleet

Abstract

We investigate a fleet scheduling problem arising when a company has to manage its own fleet of electric vehicles. Aim is to assign given usage reservations to these vehicles and to devise a suitable charging plan for all vehicles while minimizing a cost function. We formulate the problem as a compact mixed integer linear program, which we strengthen in several ways. As this model is hard to solve in practice, we perform a Benders decomposition, which separates the problem into a master problem and a subproblem and solves them iteratively in an alternating manner. We perform the decomposition in two different ways. First we follow a more classical way, then we enrich the master problem making it stronger but also more complex and the subproblem smaller and simpler to solve. To improve the overall performance, we propose a problem-specific General Variable Neighborhood Search metaheuristic for solving the master problem in earlier iterations. Experimental results show that directly solving the complete mixed integer linear program usually performs well for small to some medium sized problem instances. For larger instances, however, it is not able to find any reasonable primal solutions anymore, while the Benders decomposition scales much better. Especially the variant with the heuristic delivers high quality solutions in reasonable time. The Benders decomposition with the more complex master problem also yields reasonable dual bounds and thus practically relevant quality guarantees for the larger instances.

Keywords

• Electric vehicles
• fleet scheduling
• mathematical programming
• Benders decomposition
• heuristic algorithms