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

research-article

Investigating Optimal Carpool Scheme by a Semi-Centralized Ride-Matching Approach

Authors:

Lili DuAuthors Info & Claims

IEEE Transactions on Intelligent Transportation Systems, Volume 23, Issue 9

Pages 14990 - 15004

https://doi.org/10.1109/TITS.2021.3135648

Published: 01 September 2022 Publication History

Abstract

Carpooling service obtains a significant interest in both industry and academic fields for its potential to improve mobility and save travel costs. However, the existing approaches for exploring online carpooling routes for riders struggle with the trade-off between system optimality and computation efficiency. This study is motivated to develop a semi-centralized ride-matching strategy (SCM) to address this difficulty. Specifically, we model the carpooling service problem (CSP) by a mixed-integer programming (CSP-MIP), which explores an optimal carpooling solution for a large-scale of riders to minimize system service time by using a small CAV fleet to serve all the riders. To address the computation difficulty, we first analyze and quantify the carpooling chances (C2) among riders according to their trip features. According to the C2, we decompose a large-scale CSP-MIP involving all riders in a network into small sub-MIPs, each including a small number of riders in a carpooling community, without over sacrificing the system optimality. For each sub-MIP, we develop a network flow algorithm combined with a greedy ride-matching model to explore a local optimal solution. The experiments built upon the Hardee network demonstrated that the SCM could solve the CSP efficiently. It significantly improves the computation efficiency while maintaining the system performance as it’s compared to the existing approaches.

References

[1]

N. Agatz, “Optimization for dynamic ridesharing: A review,” Eur. J. Oper. Res., vol. 223, no. 2, pp. 295–303, 2012.

[2]

A. Amey, “A proposed methodology for estimating rideshare viability within an organization, applied to the mit community,” in Proc. TRB Annu. Meeting, 2011, pp. 1–6.

[3]

M. Nourinejad and M. J. Roorda, “Agent based model for dynamic ridesharing,” Transp. Res. C, Emerg. Technol., vol. 64, pp. 117–132, Mar. 2016.

[4]

M. Li, N. Zheng, X. Wu, and X. Huo, “An efficient matching method for dispatching autonomous vehicles,” in Proc. IEEE Intell. Transp. Syst. Conf. (ITSC), Oct. 2019, pp. 3013–3018.

[5]

A. Clauset, M. E. Newman, and C. Moore, “Finding community structure in very large networks,” Phys. Rev. E, Stat. Phys. Plasmas Fluids Relat. Interdiscip. Top., vol. 70, no. 6, 2004, Art. no.

[6]

M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Phys. Rev. E, Stat. Phys. Plasmas Fluids Relat. Interdiscip. Top., vol. 69, Feb. 2004, Art. no.

[7]

N. Agatz, A. L. Erera, M. W. P. Savelsbergh, and X. Wang, “Dynamic ride-sharing: A simulation study in metro Atlanta,” Proc.-Social Behav. Sci., vol. 17, pp. 532–550, Dec. 2011.

[8]

K. Ghoseiri, A. Haghani, and M. Hamed, “Real-time rideshare matching problem,” Mid-Atlantic Univ. Transp. Center, Chennai, India, Tech. Rep. UMD-2009-04, 2010.

[9]

X. Xing, “SMIZE: A spontaneous ride-sharing system for individual urban transit,” in Proc. German Conf. Multiagent Syst. Technol. Berlin, Germany: Springer, 2009, pp. 165–176.

[10]

K. Bimbraw, “Autonomous cars: Past, present and future a review of the developments in the last century, the present scenario and the expected future of autonomous vehicle technology,” in Proc. 12th Int. Conf. Informat. Control, Autom. Robot., Jul. 2015, pp. 191–198.

[11]

S. Winter and S. Nittel, “Ad hoc shared-ride trip planning by mobile geosensor networks,” Int. J. Geograph. Inf. Sci., vol. 20, no. 8, pp. 899–916, 2006.

[12]

H. Tsao and D. Lin, Spatial and Temporal Factors in Estimating the Potential of 500 Ridesharing for Demand Reduction. Berkeley, CA, USA: Institute of Transportation Studies, 1999.

[13]

L. Häme and H. Hakula, “A maximum cluster algorithm for checking the feasibility of dial-a-ride instances,” Transp. Sci., vol. 49, no. 2, pp. 295–310, May 2015.

Digital Library

[14]

T. Zhang, R. Ramakrishnan, and M. Livny, “BIRCH: An efficient data clustering method for very large databases,” ACM SIGMOD Rec., vol. 25, pp. 103–114, Jun. 1996.

Digital Library

[15]

P. Kranen, I. Assent, C. Baldauf, and T. Seidl, “The ClusTree: Indexing micro-clusters for anytime stream mining,” Knowl. Inf. Syst., vol. 29, no. 2, pp. 249–272, 2011.

Digital Library

[16]

P. Kalczynski and M. Miklas-Kalczynska, “A decentralized solution to the car pooling problem,” Int. J. Sustain. Transp., vol. 13, no. 2, pp. 81–92, Feb. 2019.

[17]

R. Baldacci, V. Maniezzo, and A. Mingozzi, “An exact method for the car pooling problem based on Lagrangean column generation,” Oper. Res., vol. 52, no. 3, pp. 422–439, Jun. 2004.

Digital Library

[18]

W. M. Herbawi and M. Weber, “A genetic and insertion heuristic algorithm for solving the dynamic ridematching problem with time Windows,” in Proc. 14th Int. Conf. Genetic Evol. Comput. Conf., 2012, pp. 385–392.

[19]

M.-K. Jiau and S.-C. Huang, “Services-oriented computing using the compact genetic algorithm for solving the carpool services problem,” IEEE Trans. Intell. Transp. Syst., vol. 16, no. 5, pp. 2711–2722, Oct. 2015.

Digital Library

[20]

P. Minett and J. Pearce, “Estimating the energy consumption impact of casual carpooling,” Energies, vol. 4, no. 1, pp. 126–139, Jan. 2011.

[21]

S. Seyedabrishami, A. Mamdoohi, A. Barzegar, and S. Hasanpour, “Impact of carpooling on fuel saving in urban transportation: Case study of Tehran,” Proc.-Social Behav. Sci., vol. 54, pp. 323–331, Oct. 2012.

[22]

J. Lo and S. Morseman, “The perfect uberPOOL: A case study on trade-offs,” in Proc. Ethnograph. Praxis Ind. Conf., Jan. 2018, pp. 195–223.

[23]

Y. Li and S. H. Chung, “Ride-sharing under travel time uncertainty: Robust optimization and clustering approaches,” Comput. Ind. Eng., vol. 149, Nov. 2020, Art. no.

[24]

S. Chen, H. Wang, and Q. Meng, “Solving the first-mile ridesharing problem using autonomous vehicles,” Comput.-Aided Civil Infrastruct. Eng., vol. 35, no. 1, pp. 45–60, Jan. 2020.

[25]

A. Tafreshian and N. Masoud, “Trip-based graph partitioning in dynamic ridesharing,” Transp. Res. C, Emerg. Technol., vol. 114, pp. 532–553, May 2020.

[26]

H. Xu, J. Pang, F. Ordánez, and M. Dessouky, “Complementarity models for traffic equilibrium with ridesharing,” Transp. Res. B, Methodol., 81, pp. 161–182, Apr. 2015.

[27]

S. Feigon and C. Murphy, “Shared mobility and the transformation of public transit,” TRB Conf. Project J-11, Task 2, 2016.

[28]

Y. Dumas, J. Desrosiers, and F. Soumis, “The pickup and delivery problem with time Windows,” Eur. J. Oper. Res., vol. 54, no. 1, pp. 7–22, 1991.

[29]

W. P. Nanry and J. W. Barnes, “Solving the pickup and delivery problem with time Windows using reactive tabu search,” Transp. Res. B, Methodol., vol. 34, no. 2, pp. 107–121, 2000.

[30]

H.-F. Wang and Y.-Y. Chen, “A genetic algorithm for the simultaneous delivery and pickup problems with time window,” Comput. Ind. Eng., vol. 62, no. 1, pp. 84–95, Feb. 2012.

Digital Library

[31]

R. Baldacci, E. Bartolini, and A. Mingozzi, “An exact algoritFhm for the pickup and delivery problem with time Windows,” Oper. Res., vol. 59, no. 2, pp. 414–426, 2011.

Digital Library

[32]

L. Grandinetti, F. Guerriero, F. Pezzella, and O. Pisacane, “The multi-objective multi-vehicle pickup and delivery problem with time Windows,” Proc.-Social Behav. Sci., vol. 111, pp. 203–212, Feb. 2014.

[33]

G. Guo and T. Xu, “Vehicle rebalancing with charging scheduling in one-way car-sharing systems,” IEEE Trans. Intell. Transp. Syst., early access, Dec. 20, 2020. 10.1109/TITS.2020.3043594.

Digital Library

[34]

G. Guo and Y. Xu, “A deep reinforcement learning approach to ride-sharing vehicles dispatching in autonomous mobility-on-demand systems,” IEEE Intell. Transp. Syst. Mag., early access, Apr. 1, 2020. 10.1109/MITS.2019.2962159.

Cited By

Wen DLi YLau F(2024)A Survey of Machine Learning-Based Ride-Hailing PlanningIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.334517425:6(4734-4753)Online publication date: 10-May-2024
https://dl.acm.org/doi/10.1109/TITS.2023.3345174
Peng WDu L(2023)A Novel Real-Time Coordinated Ridesharing Route Choice MechanismIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.332794125:5(3548-3560)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3327941

Index Terms

Investigating Optimal Carpool Scheme by a Semi-Centralized Ride-Matching Approach

Index terms have been assigned to the content through auto-classification.

Recommendations

Incentivizing Commuters to Carpool: A Large Field Experiment with Waze
Problem definition: Traffic congestion is a serious global issue. A potential solution, which requires zero investment in infrastructure, is to convince solo car users to carpool. Academic/practical relevance: In this paper, we leverage the Waze Carpool ...
Time-optimal and privacy preserving route planning for carpool policy
Abstract
To alleviate the traffic congestion caused by the sharp increase in the number of private cars and save commuting costs, taxi carpooling service has become the choice of many people. Current research on taxi carpooling services has focused on ...
"Baby, You can Ride my Bike": Exploring Maneuver Indications of Self-Driving Bicycles using a Tandem Simulator
MHCI

We envision a future where self-driving bicycles can take us to our destinations. This allows cyclists to use their time on the bike efficiently for work or relaxation without having to focus their attention on traffic. In the related field of self-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Intelligent Transportation Systems

IEEE Transactions on Intelligent Transportation Systems Volume 23, Issue 9

Sept. 2022

2944 pages

ISSN:1524-9050

Issue’s Table of Contents

1558-0016 © 2022 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Publisher

IEEE Press

Publication History

Published: 01 September 2022

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wen DLi YLau F(2024)A Survey of Machine Learning-Based Ride-Hailing PlanningIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.334517425:6(4734-4753)Online publication date: 10-May-2024
https://dl.acm.org/doi/10.1109/TITS.2023.3345174
Peng WDu L(2023)A Novel Real-Time Coordinated Ridesharing Route Choice MechanismIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.332794125:5(3548-3560)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3327941

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents