More Web Proxy on the site http://driver.im/

research-article

SCRAM: A Sharing Considered Route Assignment Mechanism for Fair Taxi Route Recommendations

Authors:

Frédéric Le Mouël,

Minglu LiAuthors Info & Claims

KDD '15: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Pages 955 - 964

https://doi.org/10.1145/2783258.2783261

Published: 10 August 2015 Publication History

Abstract

Recommending routes for a group of competing taxi drivers is almost untouched in most route recommender systems. For this kind of problem, recommendation fairness and driving efficiency are two fundamental aspects. In the paper, we propose SCRAM, a sharing considered route assignment mechanism for fair taxi route recommendations. SCRAM aims to provide recommendation fairness for a group of competing taxi drivers, without sacrificing driving efficiency. By designing a concise route assignment mechanism, SCRAM achieves better recommendation fairness for competing taxis. By considering the sharing of road sections to avoid unnecessary competition, SCRAM is more efficient in terms of driving cost per customer (DCC). We test SCRAM based on a large number of historical taxi trajectories and validate the recommendation fairness and driving efficiency of SCRAM with extensive evaluations. Experimental results show that SCRAM achieves better recommendation fairness and higher driving efficiency than three compared approaches.

Supplementary Material

MP4 File (p955.mp4)

Download
147.25 MB

References

[1]

Suvnet-trace data. http://wirelesslab.sjtu.edu.cn.

[2]

A. Abdulkadiroglu and T. Sonmez. School choice: A mechanism design approach. The American Economic Review, 93(3):729--747, 2003.

[3]

G. Adomavicius and A. Tuzhilin. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. Knowledge and Data Engineering, IEEE Transactions on, 17(6):734--749, 2005.

Digital Library

[4]

Y. Ding, S. Liu, J. Pu, and L. M. Ni. Hunts: A trajectory recommendation system for effective and efficient hunting of taxi passengers. In MDM, pages 107--116. IEEE, 2013.

Digital Library

[5]

A. G. Erdman and G. N. Sandor. Mechanism design: analysis and synthesis (Vol. 1). Prentice-Hall, Inc., 1997.

Digital Library

[6]

Y. Ge, H. Xiong, A. Tuzhilin, K. Xiao, M. Gruteser, and M. Pazzani. An energy-efficient mobile recommender system. In SIGKDD, pages 899--908. ACM, 2010.

Digital Library

[7]

D. E. Goldberg et al. Genetic algorithms in search, optimization, and machine learning, volume 412. Addison-wesley Reading Menlo Park, 1989.

Digital Library

[8]

H. Hu, Z. Wu, B. Mao, Y. Zhuang, J. Cao, and J. Pan. Pick-up tree based route recommendation from taxi trajectories. In Web-Age Information Management, pages 471--483. Springer, 2012.

[9]

J. Lee, I. Shin, and G.-L. Park. Analysis of the passenger pick-up pattern for taxi location recommendation. In NCM, pages 199--204. IEEE, 2008.

Digital Library

[10]

N. Nisan and A. Ronen. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 129--140. ACM, 1999.

Digital Library

[11]

S. Qian, Y. Zhu, and M. Li. Smart recommendation by mining large-scale gps traces. In WCNC, pages 3267--3272. IEEE, 2012.

[12]

P. Resnick and H. R. Varian. Recommender systems. Communications of the ACM, 40(3):56--58, 1997.

Digital Library

[13]

J. Schummer and R. V. Vohra. Mechanism design without money. Algorithmic Game Theory, 10:243--299, 2007.

[14]

L.-Y. Wei, Y. Zheng, and W.-C. Peng. Constructing popular routes from uncertain trajectories. In SIGKDD, pages 195--203. ACM, 2012.

Digital Library

[15]

J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang. T-drive: driving directions based on taxi trajectories. In SIGSPATIAL, pages 99--108. ACM, 2010.

Digital Library

[16]

J. Yuan, Y. Zheng, L. Zhang, X. Xie, and G. Sun. Where to find my next passenger. In UbiComp, pages 109--118. ACM, 2011.

Digital Library

[17]

N. J. Yuan, Y. Zheng, L. Zhang, and X. Xie. T-finder: A recommender system for finding passengers and vacant taxis. Knowledge and Data Engineering, IEEE Transactions on, 25(10):2390--2403, 2013.

Digital Library

[18]

D. Zhang, T. He, Y. Liu, and J. A. Stankovic. Callcab: A unified recommendation system for carpooling and regular taxicab services. In Big Data, International Conference on, pages 439--447. IEEE, 2013.

[19]

M. Zhang, J. Liu, Y. Liu, Z. Hu, and L. Yi. Recommending pick-up points for taxi-drivers based on spatio-temporal clustering. In CGC), pages 67--72. IEEE, 2012.

Digital Library

Cited By

Makhdomi AGillani I(2024)Fair and Efficient Ridesharing: A Dynamic Programming-based Relocation ApproachACM Transactions on Intelligent Systems and Technology10.1145/367540315:5(1-30)Online publication date: 29-Jun-2024
https://dl.acm.org/doi/10.1145/3675403
Wang GHe SJiang LWang SMiao FZhang FDong ZZhang D(2024)FairMove: A Data-Driven Vehicle Displacement System for Jointly Optimizing Profit Efficiency and Fairness of Electric For-Hire VehiclesIEEE Transactions on Mobile Computing10.1109/TMC.2023.332667623:6(6785-6802)Online publication date: Jun-2024
https://doi.org/10.1109/TMC.2023.3326676
Makhdomi AGillani I(2023)Towards a Greener and Fairer Transportation System: A Survey of Route Recommendation TechniquesACM Transactions on Intelligent Systems and Technology10.1145/362782515:1(1-57)Online publication date: 19-Dec-2023
https://dl.acm.org/doi/10.1145/3627825
Show More Cited By

Index Terms

SCRAM: A Sharing Considered Route Assignment Mechanism for Fair Taxi Route Recommendations
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Route Recommendations for Idle Taxi Drivers: Find Me the Shortest Route to a Customer!
KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

We study the problem of route recommendation to idle taxi drivers such that the distance between the taxi and an anticipated customer request is minimized. Minimizing the distance to the next anticipated customer leads to more productivity for the taxi ...
FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms
WWW '20: Proceedings of The Web Conference 2020

We investigate the problem of fair recommendation in the context of two-sided online platforms, comprising customers on one side and producers on the other. Traditionally, recommendation services in these platforms have focused on maximizing customer ...
TFROM: A Two-sided Fairness-Aware Recommendation Model for Both Customers and Providers
SIGIR '21: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval

At present, most research on the fairness of recommender systems is conducted either from the perspective of customers or from the perspective of product (or service) providers. However, such a practice ignores the fact that when fairness is guaranteed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '15: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 2015

2378 pages

ISBN:9781450336642

DOI:10.1145/2783258

General Chairs:
Longbing Cao
University of Technology, Sydney
,
Chengqi Zhang
University of Technology, Sydney
,
Program Chairs:
Thorsten Joachims
Cornell University
,
Geoff Webb
Monash University
,
Dragos D. Margineantu
Boeing Research
,
Graham Williams
Australian Taxation Office

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Research Fund of Future Network of Jiangsu Province
Rhone-Alpes Region, France
CIP program of Morgan Stanley
China National Science Foundation
Research Funds of Science and Technology Commission of Shanghai Municipality

Conference

KDD '15

Sponsor:

KDD '15: The 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 10 - 13, 2015

NSW, Sydney, Australia

Acceptance Rates

KDD '15 Paper Acceptance Rate 160 of 819 submissions, 20%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
847
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)1

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Makhdomi AGillani I(2024)Fair and Efficient Ridesharing: A Dynamic Programming-based Relocation ApproachACM Transactions on Intelligent Systems and Technology10.1145/367540315:5(1-30)Online publication date: 29-Jun-2024
https://dl.acm.org/doi/10.1145/3675403
Wang GHe SJiang LWang SMiao FZhang FDong ZZhang D(2024)FairMove: A Data-Driven Vehicle Displacement System for Jointly Optimizing Profit Efficiency and Fairness of Electric For-Hire VehiclesIEEE Transactions on Mobile Computing10.1109/TMC.2023.332667623:6(6785-6802)Online publication date: Jun-2024
https://doi.org/10.1109/TMC.2023.3326676
Makhdomi AGillani I(2023)Towards a Greener and Fairer Transportation System: A Survey of Route Recommendation TechniquesACM Transactions on Intelligent Systems and Technology10.1145/362782515:1(1-57)Online publication date: 19-Dec-2023
https://dl.acm.org/doi/10.1145/3627825
Wu YCao JXu G(2023)Fairness in Recommender Systems: Evaluation Approaches and Assurance StrategiesACM Transactions on Knowledge Discovery from Data10.1145/360455818:1(1-37)Online publication date: 10-Aug-2023
https://dl.acm.org/doi/10.1145/3604558
Wang TShen ZCao YXu XGong H(2023)Taxi-Cruising Recommendation via Real-Time Information and Historical Trajectory DataIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2021.309320724:8(7898-7910)Online publication date: Aug-2023
https://doi.org/10.1109/TITS.2021.3093207
Zhu H(2022)Group Role Assignment With Constraints (GRA$+$): A New Category of Assignment ProblemsIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2022.3199096(1-14)Online publication date: 2022
https://doi.org/10.1109/TSMC.2022.3199096
Rong HHuo SZhang QZheng HYang C(2022)GREEN: A Global Optimization Scheme for Transportation Efficiency by Mining Taxi MobilityIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2021.308948723:2(1596-1606)Online publication date: Feb-2022
https://doi.org/10.1109/TITS.2021.3089487
Qian SCheng BCao JXue GZhu YYu JLi MZhang T(2022)Detecting Taxi Trajectory Anomaly Based on Spatio-Temporal RelationsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2021.306319923:7(6883-6894)Online publication date: Jul-2022
https://doi.org/10.1109/TITS.2021.3063199
Tran DLeyman PCausmaecker P(2022)Adaptive passenger-finding recommendation system for taxi drivers with load balancing problemComputers & Industrial Engineering10.1016/j.cie.2022.108187(108187)Online publication date: Apr-2022
https://doi.org/10.1016/j.cie.2022.108187
Fabris AMessina SSilvello GSusto G(2022)Algorithmic fairness datasets: the story so farData Mining and Knowledge Discovery10.1007/s10618-022-00854-z36:6(2074-2152)Online publication date: 17-Sep-2022
https://doi.org/10.1007/s10618-022-00854-z
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents