A chance-constrained programming approach to optimal management of car-rental fleets of electric vehicles

In the current context of growing electrification of the transport sector, offering rental and sharing programs for electric vehicles is considered one of the strategies to achieve decarbonization targets. Such programs should be supported by suitable optimization tools to manage the vehicle fleet, and make rental provision profitable for its operator. In this paper, we consider a rental system having a single station for electric vehicle pickup and delivery. For this system, we address the operational problem of simultaneously assigning rental requests to vehicles and determining the charging policies during inactivity intervals. The objective is to maximize the profit for the operator by minimizing the costs for electricity. The considered problem is complicated by uncertainty regarding the battery energy level when a vehicle returns to the station. This leads to a chance-constrained programming formulation, where the request-to-vehicle assignment and charging policies are determined by minimizing electricity costs while ensuring that the energy demand of the served requests is met with a prescribed high probability. Since the formulated mixed-integer problem with probabilistic constraints is hard to solve, a suboptimal approach is proposed, consisting of two sequential steps. In the first step, request-to-vehicle assignment is accomplished via a suitably designed heuristic procedure. Then, for a given assignment, the charging policy of each vehicle is determined by solving a relaxed chance-constrained problem. Numerical results are presented to assess the performance of both the assignment procedure and the optimization problem which determines the electric vehicle charging policies.