Social welfare maximizing fleet charging scheduling through voting-based negotiation

As an alternative to traditional taxi services, Transportation Network Companies (TNCs) such as Uber and Lyft are playing an increasingly important role in the paradigm shifting from car ownership to mobility as a service. We consider an electric vehicle fleet charging scheduling problem in the TNC setting where taxi drivers, as freelancers, have their individual preferences regarding when and where to charge their vehicles. In this setting, obtaining social welfare maximizing schedules is particularly difficult as drivers may behave strategically in competing over shared charging resources to advance their own benefits rather than the system wide social welfare. We propose a negotiation mechanism which allows drivers to collectively evolve an incumbent schedule into a socially beneficial one through an iterative voting process. The proposed mechanism provides a platform which enables multilateral negotiation among a large number of drivers. We prove that, given the design of the proposed mechanism, drivers’ best response strategy is to truthfully vote their best valued candidate schedules according to the acceptance quota prescribed by the scheduler at each voting round. In addition, experiment results show that the mechanism achieves on average 93% efficiency compared with optimal solutions and scales well to larger problem instances.