Social welfare maximizing fleet charging scheduling through voting-based negotiation. (September 2021)

• Record Type: Journal Article
• Authors: Gao, Jie; Wong, Terrence; Wang, Chun
• Is Part Of: Transportation research. Volume 130(2021)
• Publication Date: 2021-09
• Subjects: Smart city -- Transportation network companies (TNCs) -- EV charging scheduling -- Negotiation at a large scale -- SA-inspired automated negotiation mechanism; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2021.103304
• Languages: English
• ISSNs: 0968-090X

Abstract

Highlights: A decentralized electric taxi fleet charging scheduling problem is introduced. A voting-based negotiation mechanism is proposed to maximize the social welfare of E-taxi drivers by complying with their strategic behaviors and conflicting interests. A game theoretic property of the proposed mechanism is proved. The mechanism achieves on average 93% efficiency compared with optimal solutions and scales well to larger problem instances of practical sizes. Abstract: 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.