An improved partition merging algorithm to account for maximum waiting time in carpools

Research Article
Open access

An improved partition merging algorithm to account for maximum waiting time in carpools

Andrew Wen 1* , Jinglin Xu 2 , Shunchang Chen 3 , Ryan Wu 4 , Yuntao Lin 5
  • 1 Phillips Academy Andover, Andover, MA, USA    
  • 2 University Hill Secondary School, Vancouver, BC, Canada, V6S 0C6    
  • 3 College of Science and Technology, Wenzhou-Kean University, Wenzhou, Zhejiang, 325000, China    
  • 4 Livingston High School, Livingston, NJ, 07039, USA    
  • 5 Sun Yat-sen University, Guangzhou, Guangdong, 510006, China    
  • *corresponding author andwendrew@gmail.com
Published on 14 June 2023 | https://doi.org/10.54254/2755-2721/6/20230389
ACE Vol.6
ISSN (Print): 2755-273X
ISSN (Online): 2755-2721
ISBN (Print): 978-1-915371-59-1
ISBN (Online): 978-1-915371-60-7

Abstract

Nowadays, traffic problems have become an issue that needs to be solved in every populous country. Especially in large urban areas, people face traffic problems such as road congestion and high exhaust emissions due to the rapid growth of vehicles on the roads. In this context, several researchers have shown that carpooling, i.e., vehicle sharing, is an attractive solution to effectively address the traffic stress that arises when a large number of cars are traveling at the same time. The goal of our carpool scheduling problem is to reduce the number of carpools required by all users while ensuring their waiting time. Previous studies on similar topics have introduced additional static capacity constraints to simplify the problem, which limits the number of carpooling users in a vehicle. However, this does not match most real-world situations. This is because when a passenger gets off the vehicle, their seat should also be vacated for the next user. In this paper, we eliminate the static capacity constraint to enable timely user turnover during the carpooling journey. A greedy algorithm based on iterative matching and summation is proposed. In addition, we introduce the concept of “user waiting time”, i.e., the amount of time a user is willing to wait to be picked up. We apply our algorithm to synthetic and real-world data sets, and our experimental results show that our algorithm has better performance than existing methods.

Keywords:

carpool, vehicle sharing, partition merging, greedy algorithm, user waiting time

Wen,A.;Xu,J.;Chen,S.;Wu,R.;Lin,Y. (2023). An improved partition merging algorithm to account for maximum waiting time in carpools. Applied and Computational Engineering,6,982-991.
Export citation

References

[1]. I. Meyer, S. Kaniovski, and J. Scheffran, “Scenarios for regional passenger car fleets and their co 2 emissions,” Energy Policy, vol. 41, pp. 66–74, 2012.

[2]. R. J. Javid, A. Nejat, and K. Hayhoe, “Quantifying the environmental impacts of increasing high occupancy vehicle lanes in the united states,” Transp. Res. D, vol. 56, pp. 155–174, 2017.

[3]. He, W, Kai, H, Li, D. Intelligent carpool routing for urban ridesharing by mining GPS trajectories. IEEE Trans Intell Transp Syst 2014; 15(5): 2286–2296.

[4]. Zhao T, Yang Y, Wang E. Minimizing the average arriving distance in carpooling. International Journal of Distributed Sensor Networks. January 2020. doi:10.1177/1550147719899369

[5]. Y. Duan, G. Gao, M. Xiao and J. Wu, “A Privacy-Preserving Order Dispatch Scheme for Ride-Hailing Services,” 2019 IEEE 16th International Conference on Mobile Ad Hoc and Sensor Systems (MASS), 2019, pp. 118-126

[6]. T. Oda and C. Joe-Wong, “Movi: A model-free approach to dynamic fleet management,” arXiv preprint arXiv:1804.04758, 2018.

[7]. R. Geisberger, D. Luxen, S. Neubauer, P. Sanders, and L. Volker, “Fast detour computation for ride sharing.” OpenAccess Series in Informatics, vol. 14, pp. 88–99, 01 2010.

[8]. S. Zhang, Q. Ma, Y. Zhang, K. Liu, T. Zhu, and Y. Liu, “Qashare: Towards efficient qos-aware dispatching approach for urban taxi-sharing,” in Proceedings of the IEEE SECON 2015, pp. 533–541.

[9]. F. Buchholz, “The carpool problem,” Citeseer, Tech. Rep., 1997.

[10]. Y. Duan, T. Mosharraf, J. Wu, and H. Zheng, “Optimizing carpool scheduling algorithm through partition merging,” in IEEE ICC, 2018.

[11]. N. Agatz, A. Erera, M. Savelsbergh, and X. Wang, “Optimization for dynamic ridesharing: A review,” European Journal of Operational Research, vol. 223, no. 2, pp. 295–303, 2012.

[12]. A. Shoemaker, S. Vare, “Edmonds’ Blossom Algorithm,” Standford University, CME 323, 2016.

[13]. S. Micali, V. Vazirani, “An O(√V E) algorithm for finding maximum matching in general graphs,” 21st IEEE FOCS, pp. 17–27, 1980.

Cite this article

Wen,A.;Xu,J.;Chen,S.;Wu,R.;Lin,Y. (2023). An improved partition merging algorithm to account for maximum waiting time in carpools. Applied and Computational Engineering,6,982-991.

Data availability

The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.

Disclaimer/Publisher's Note

The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

About volume

Volume title: Proceedings of the 3rd International Conference on Signal Processing and Machine Learning

ISBN：978-1-915371-59-1(Print) / 978-1-915371-60-7(Online)
Editor：Omer Burak Istanbullu
Conference website: http://www.confspml.org
Conference date: 25 February 2023
Series: Applied and Computational Engineering
Volume number: Vol.6
ISSN：2755-2721(Print) / 2755-273X(Online)

© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license. Authors who publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See Open access policy for details).

References

[1]. I. Meyer, S. Kaniovski, and J. Scheffran, “Scenarios for regional passenger car fleets and their co 2 emissions,” Energy Policy, vol. 41, pp. 66–74, 2012.

[2]. R. J. Javid, A. Nejat, and K. Hayhoe, “Quantifying the environmental impacts of increasing high occupancy vehicle lanes in the united states,” Transp. Res. D, vol. 56, pp. 155–174, 2017.

[3]. He, W, Kai, H, Li, D. Intelligent carpool routing for urban ridesharing by mining GPS trajectories. IEEE Trans Intell Transp Syst 2014; 15(5): 2286–2296.

[4]. Zhao T, Yang Y, Wang E. Minimizing the average arriving distance in carpooling. International Journal of Distributed Sensor Networks. January 2020. doi:10.1177/1550147719899369

[5]. Y. Duan, G. Gao, M. Xiao and J. Wu, “A Privacy-Preserving Order Dispatch Scheme for Ride-Hailing Services,” 2019 IEEE 16th International Conference on Mobile Ad Hoc and Sensor Systems (MASS), 2019, pp. 118-126

[6]. T. Oda and C. Joe-Wong, “Movi: A model-free approach to dynamic fleet management,” arXiv preprint arXiv:1804.04758, 2018.

[7]. R. Geisberger, D. Luxen, S. Neubauer, P. Sanders, and L. Volker, “Fast detour computation for ride sharing.” OpenAccess Series in Informatics, vol. 14, pp. 88–99, 01 2010.

[8]. S. Zhang, Q. Ma, Y. Zhang, K. Liu, T. Zhu, and Y. Liu, “Qashare: Towards efficient qos-aware dispatching approach for urban taxi-sharing,” in Proceedings of the IEEE SECON 2015, pp. 533–541.

[9]. F. Buchholz, “The carpool problem,” Citeseer, Tech. Rep., 1997.

[10]. Y. Duan, T. Mosharraf, J. Wu, and H. Zheng, “Optimizing carpool scheduling algorithm through partition merging,” in IEEE ICC, 2018.

[11]. N. Agatz, A. Erera, M. Savelsbergh, and X. Wang, “Optimization for dynamic ridesharing: A review,” European Journal of Operational Research, vol. 223, no. 2, pp. 295–303, 2012.

[12]. A. Shoemaker, S. Vare, “Edmonds’ Blossom Algorithm,” Standford University, CME 323, 2016.

[13]. S. Micali, V. Vazirani, “An O(√V E) algorithm for finding maximum matching in general graphs,” 21st IEEE FOCS, pp. 17–27, 1980.

For authors
Guide for authors Policies for authors Aims and scope Subscription Open access policy
For editors
Policies for editors Editorial board
For reviewers
Policies for reviewers Privacy policy

Cookies are used by this site.
Copyright © 2024 EWA Publishing, its licensors, and contributors. All rights reserved, including text and data mining, AI training, and similar technologies.