Fairness-aware Real-time Algorithm For Ridesharing

In the ridesharing scenario,multiple passengers with similar routes and times travel together,which can reduce travel costs and ease traffic congestion.Meanwhile,reducing the number of vehicles required in the road network can reduce the energy consumption for transportation.However,most of the existing ridesharing works have ignored the impact of inconsistent charging standards of vehicles providing ridesharing services on the quality of passenger travel services.This dissertation studies the matching problem between drivers and passengers in ridesharing,where ridesharing platform will receive ridesharing requests in real time.Since both drivers and passengers should make decisions in the matching,this dissertation models the matching process between drivers and passengers as a Stackelberg game.Specifically,the drivers who provide the ridesharing service are the leaders,and their game strategies are setting the charge standard,while the passengers who send ridesharing requests are the followers,who need to choose the vehicle that send them to their destination.Meanwhile,there are requirements such as travel costs and waiting time for matching between drivers and passengers.According to the service quality obtained by passengers,a quantifiable and comparable service quality fairness index can be defined.In order to ensure that passengers have a more similar travel service quality,this thesis transforms the passenger-driver matching problem in ridesharing scenario into a constrained fairness index maximization problem.A two stage Stackelberg Game based ridesharing matching algorithm,named TSGM,is designed to solve the above problem.Specifically,this algorithm consists of requests partition algorithm,filtering algorithm and Stackelberg game algorithm.The proposed requests partition algorithm divides the larger scattered request set received by the ridesharing platform into multiple smaller relatively concentrated sets,which can reduce the scale of a single problem in the subsequent solving process.According to the result obtained by the requests partition algorithm,the filtering algorithm filters out the set of vehicles that meet the constraints near each request set and can provide ridesharing service,and use it as the input of the subsequent algorithm to implement the matching between drivers and passengers.The Stackelberg game algorithm is a pricing and matching algorithm.This algorithm describes the driver-passenger matching process as a multi-round iterative process in which drivers adjust charge and passengers reselect vehicles.Through the adjustments of both drivers and passengers,a higher fairness index is finally achieved in ridesharing.This thesis constructs a simulation dataset suitable for this experiment based on the New York taxi dataset.The experiment in this thesis consists of two parts.The first part is the verification of the convergence of the proposed algorithm.In the second part,the thesis compares the proposed algorithm with two existing works in different parameter settings.The experimental results show that the algorithm proposed in this dissertation has a higher fairness index in different parameter settings.The fairness index of algorithm TSGM is24.40% and 33.22% higher than those two existing works on average,respectively.Meanwhile,drivers who provide ridesharing services have a relatively high rate of return.The proposed algorithm is 11.20% and 1.61% higher than the drivers of two comparison algorithms on average,respectively.