Efficient algorithms for community aware ridesharing group set queries

Abstract

Abstract

Ridesharing services have been becoming aprominent solution to reduce the road trafficcongestionandenvironmentalpollutioninurbanareas.Existingridesharing servicesfallapartinensuringbothfairnessandthesocialcomfortofthegroup members. To address hisissue,weformulatea CommunityawareRidesharing GroupSet(CaRGS)querythatsatisfiesthespatialandsocialconstraintsofthe groupmembers,andfindsanon-conflictingsetofridesharinggroupswithanaim tomaximizethenumberofservedriders.Here,increasednumberofservedriders alsoenhancesthefairnessissueoftheriders.TheCaRGS queryutilizesuserdatain communitylevelsinstead ofdetailsocialnetworkdatatoensureuserprivacy. Inourstudy,weshowthattheproblemoffindinganansweroftheCaRGS queryisNP-Hard.Accordingly,weproposetwoheuristicapproaches:ahierarchical approach andaniterativeapproachtoevaluateCaRGSqueries.Theproposed heuristicapproachesaredesignedin awayto findasetofnon-conflictingridesharing groupsinreal-time.Whilefindingasetofgroups,theheuristicapproachesconsider multipleridesharinggroups’requestssimultaneouslyandtryto resolveriderconflicts amongthegroups inordertoincreasethenumberofservedriders.Weevaluatethe effectiveness,efficiencyandaccuracyofoursolutionthrough extensiveexperiments usingrealdatasetsforbothEuclidean androadnetworkspaces,andpresent a comparativeanalysisamongtheproposedalgorithms.Ingeneral,thehierarchical approachachievesdesirablequeryperformanceintermsofthenumberofserved ridersintheridesharinggroupset.