Optimizing Algorithm for Allocating Passengers in Shared Taxis

Document Type : Research Paper


1 Professor, School of Civil Engineering, Iran University of Science and Technology, Tehran, Iran

2 School of Civil Engineering, Iran University of Science and Technology

3 Department of Civil -Transportation Planning and Engineering, Imam Khomeini International University


The issue of sharing vehicles has been riding since the '70s, but the advent of smartphones has made it a competitive choice to other transportation modes in recent years. The lack of restrictions on the movement of Internet-based passenger sharing systems leads to patrolling numerous personal vehicles in the network; this exacerbates congestion in high-traffic areas. On the other hand, the significant presence of circulating taxis and their non-optimal performance have disrupted the normal flow of traffic during peak hours and have led to an increase in travel time. This paper outlines a novel optimization algorithm for sharing repetitive and pre-planned trips. This algorithm is implemented on the midtown area network of Manhattan, New York, USA. Three scenarios were defined to simulate common services' status with the base scenario (do-nothing), which makes comparing possible with indicators such as distance travelled, and taxi occupancy ratio determined by passenger coefficient. Results of the first scenario - sending the nearest car - shows a decrease of 10.51%, the second scenario - allocating passengers to the nearest taxi - shows an increase of 10.16%, and finally the third scenario - the proposed algorithm - shows an increase of 25.56% in total mileage compared to the base scenario. Moreover, by defining Sharing Importance Factor (SIF) and using the proposed algorithm, it is possible to organize round-trip taxis, service repetitive and pre-planned trips, and significantly reduce the distance travelled throughout the network, and finally increase the passenger coefficient.


- Aarhaug, Jørgen, & Skollerud, Kåre. (2014). Taxi: different solutions in different segments. Transportation Research Procedia, 1(1), 276-283.
- Afandizadeh Zargari, Shahriar, Mirzahossein, Hamid, & Chiu, Yi-Chang. (2016). Quick Link Selection Method by Using Pricing Strategy Based on User Equilibrium for Implementing an Effective Urban Travel Demand Management. Promet-Traffic&Transportation, 28(6), 605-614.
- Al-Maolegi, Mohammed, & Arkok, Bassam. (2014). An improved apriori algorithm for association rules. arXiv preprint arXiv:1403.3948.
- Babicheva, Tatiana, & Burghout, Wilco. (2019). Empty vehicle redistribution in autonomous taxi services. EURO Journal on Transportation and Logistics, 8(5), 745-767. doi:https://doi.org/10.1007/s13676-019-00146-5
- Barann, Benjamin, Beverungen, Daniel, & Müller, Oliver. (2017). An open-data approach for quantifying the potential of taxi ridesharing. Decision Support Systems, 99, 86-95.
- Brownell, Christopher K. (2013). Shared autonomous taxi networks: An analysis of transportation demand in nj and a 21st century solution for congestion. Princeton University, April.
- Cao, Yi, Wang, Shan, & Li, Jinyang. (2021). The Optimization Model of Ride-Sharing Route for Ride Hailing Considering Both System Optimization and User Fairness. Sustainability, 13(2), 902. Retrieved from https://www.mdpi.com/2071-1050/13/2/902
- Chakraborty, Jayita, Pandit, Debapratim, Chan, Felix, & Xia, Jianhong. (2020). A review of Ride-Matching strategies for Ridesourcing and other similar services. Transport Reviews, 1-22.
- Chan, Nelson D, & Shaheen, Susan A. (2012). Ridesharing in North America: Past, present, and future. Transport Reviews, 32(1), 93-112.
Cormen, Thomas H, Leiserson, Charles E, Rivest, Ronald L, & Stein, Clifford. (2009). Introduction to algorithms: MIT press.
- Cramer, Judd, & Krueger, Alan B. (2016). Disruptive change in the taxi business: The case of Uber. American Economic Review, 106(5), 177-182.
- El Hosni, Hadi, Farhat, Nourhan, Nimer, Rakan, Alawieh, Nour, El Masri, Chadi, Saroufim, Mark, Artail, Hassan, & Naoum-Sawaya, Joe. (2012). An optimization-based approach for passenger to shared taxi allocation. Paper presented at the SoftCOM 2012, 20th International Conference on Software, Telecommunications and Computer Networks.
- Herbawi, Wesam, & Weber, Michael. (2012). Modeling the multihop ridematching problem with time windows and solving it using genetic algorithms. Paper presented at the 2012 IEEE 24th International Conference on Tools with Artificial Intelligence.
- Jin, Scarlett T., Kong, Hui, & Sui, Daniel Z. (2019). Uber, Public Transit, and Urban Transportation Equity: A Case Study in New York City. The Professional Geographer, 71(2), 315-330. doi:10.1080/00330124.2018.1531038
- Jung, Jaeyoung, Jayakrishnan, R, & Park, Ji Young. (2016). Dynamic shared‐taxi dispatch algorithm with hybrid‐simulated annealing. Computer‐Aided Civil and Infrastructure Engineering, 31(4), 275-291.
- Kümmel, Michal, Busch, Fritz, & Wang, David ZW. (2016). Taxi dispatching and stable marriage. Procedia Computer Science, 83, 163-170.
- Lee, Ker-Tsung, Lin, Da-Jie, & Wu, Pei-Ju. (2005). Planning and design of a taxipooling dispatching system. Transportation research record, 1903(1), 86-95.
- Manjunath, A., Raychoudhury, V., Saha, S., Kar, S., & Kamath, A. (2021). CARE-Share: A Cooperative and Adaptive Strategy for Distributed Taxi Ride Sharing. IEEE Transactions on Intelligent Transportation Systems, 1-17. doi:10.1109/TITS.2021.3066439
- Mirzahossein, Hamid, & Zargari, Shahriar Afandizadeh. (2018). A Combined Model of Congestion Toll Pricing Based on System Optimization with Minimum Toll. Tehnički vjesnik, 25(4), 1162-1168.
- Rayle, Lisa, Dai, Danielle, Chan, Nelson, Cervero, Robert, & Shaheen, Susan. (2016). Just a better taxi? A survey-based comparison of taxis, transit, and ridesourcing services in San Francisco. Transport Policy, 45, 168-178.
- Regue, Robert, Masoud, Neda, & Recker, Will. (2016). Car2work: Shared mobility concept to connect commuters with workplaces. Transportation research record, 2542(1), 102-110.
- Salanova, Josep Maria, Estrada, Miquel, Aifadopoulou, Georgia, & Mitsakis, Evangelos. (2011). A review of the modeling of taxi services. Procedia-Social and Behavioral Sciences, 20, 150-161.
- Salanova, Josep Maria, Romeu, Miquel Estrada, & Amat, Carles. (2014). Aggregated modeling of urban taxi services. Procedia-Social and Behavioral Sciences, 160, 352-361.
Team, Regulatory Reform. (2014). Case Study: New York City Taxis Regulatory Reform for the 21st Century City.
- Thaithatkul, Phathinan, Seo, Toru, Kusakabe, Takahiko, & Asakura, Yasuo. (2015). A passengers matching problem in ridesharing systems by considering user preference. Journal of the Eastern Asia Society for Transportation Studies, 11, 1416-1432.
- Wang, Hao, Zhang, Kai, Chen, Junhua, Wang, Zhifeng, Li, Guijun, & Yang, Yuqi. (2018). System dynamics model of taxi management in metropolises: Economic and environmental implications for Beijing. Journal of environmental management, 213, 555-565.
- Wang, Yazhe, Zheng, Baihua, & Lim, Ee-Peng. (2018). Understanding the effects of taxi ride-sharing—A case study of Singapore. Computers, Environment and Urban Systems, 69, 124-132.
- Zhang, C., Dong, M., Ota, K., & Guo, M. (2016). A Social-Network-Optimized Taxi-Sharing Service. IT Professional, 18(4), 34-40. doi:10.1109/MITP.2016.71