Utility-aware Matching Algorithms For Carpooling

As an environmental-friendly transportation method,carpooling is effective to alleviate the traffic congestion,and to reduce the fuel consumptions and the emission of air pollutions.In order to stimulate both drivers and passengers to participate in carpooling,the quality of experience(Qo E)and utilities of them must be guaranteed.However,most of existing works fail to take the Qo E and utilities of both drivers and passengers into account at the same time,which may result that one side of them suffers poor Qo E and negative utilities.This dissertation focuses on the matching and pricing problem in dynamic carpooling,where drivers can dynamically receive the request assignments of new passengers from the software platform.Specifically,the matching process of both drivers and passengers is modeled as a double auction game,due to the resource transactions between them.In this game,each passenger can submit a bid,to indicate his/her maximum payment for requesting the shared journey.And each driver can submit a bid,to indicate the minimum payoff for him/her with the passengers in the vehicle to accept a new passenger.Meanwhile,both drivers and passengers have Qo E requirements,such as seat capacity,waiting time and detour distance.Therefore,the matching and pricing problem is formulated as an optimization problem of maximizing the average utility,which aims to guarantee Qo E and utilities of both drivers and passengers.A double auction based utility aware matching algorithm,named DAM,is proposed to solve the formulated problem.Specifically,the proposed algorithm DAM consists of pruning module,auction module and compensation partition module.The proposed pruning module based on the Qo E requirements is used to find the matching candidates for drivers or passengers,so as to accelerate the matching process.The proposed auction module is comprised of calculating strategy,matching strategy and pricing strategy.In calculating strategy,the difference on bids between drivers and passengers is calculated.In matching strategy,the final matching between drivers and passengers is generated.In pricing strategy,the clearing prices for drivers and passengers are determined.The proposed compensation partition module is used to compensate for drivers and passengers in their vehicles for detouring,by partitioning the payoffs of drivers.Meanwhile,algorithm DAM satisfies individual rational,truthfulness and budget balance,and it is computationally efficient.Simulation is conducted on a simulated dataset,which is built by minding the taxi trajectory dataset of Beijing city.Meanwhile,two baseline algorithms are also proposed in this dissertation,to evaluate the performance of the proposed algorithm.Simulation results show that,the proposed algorithm DAM improves the average utility by 25.62% and 17.83%,respectively,for different maximum tolerable waiting time,compared with two baseline algorithms.Moreover,DAM also improves the average utility by 25.49% and 16.85%,respectively,for different maximum tolerable detour ratio,compared with two baseline algorithms.