Dynamic planning for simultaneous recharging and relocation of shared electric taxies: A sequential MILP approach

Short driving range, limited chargers, and long charging times challenge the profitability of electric taxi operations. In this paper, a charging algorithm is developed to accompany a taxi service with online trip requests, which uses a private charging infrastructure for both slow and fast charging. The vehicle charging curves are assumed to be piece-wise linear functions. The proposed algorithm uses historical operation data to generate a pro-active planning that avoids queuing of vehicles. The algorithm is built upon three sequential, iterative, finite-horizon Mixed Integer Linear Programs. This iterative process, in which the three MILPs are solved sequentially, allows the current time-step to be optimized, while taking future time-steps into account. This is achieved by optimizing over multiple time-steps, but only implementing the current time-step in each iteration. The sequential aspect of the algorithm allows the vast amount of information over time and space to be exploited for charging trip decisions in real time, while maintaining a tractable computation time. The first level with the longest horizon is an aggregated, daily problem, that plans the charging duration required for the fleet. The second level has a horizon of up-to three hours and is an aggregated, zone-based problem for determining charger selection and empty vehicle relocations. The third level translates the outputs of the first two problems to executable decisions for individual vehicles based on their real-time location, state of charge, and assigned passengers. The first level is the most computationally expensive and is solved using Column Generation. The performance of the first two levels is then independent of the fleet size, which makes the algorithm highly scalable. A case study with travel data for the city of Barcelona is used to test the model. Results show that the proposed method can utilize the full capacity of the charging infrastructure, and improve the number of accepted requests by 14% compared to employing a naive charging rule.