The effects of including social factors in ride-matching algorithms on the performance and the quality of matches

Abstract

Advancement in communication technologies has fostered alternative transport modes, such as ride-sharing. Ride-sharing aims to increase vehicle occupancy rates by matching riders with the drivers, who have empty seats on their vehicles and have similar routes and time schedules. Regarding to the success of a ride-sharing system, many researchers have been interested in efficient ride-matching algorithms. Ride-matching optimization problem is considered as NP-Hard Problem. In most of the ride-matching algorithms in the literature, to be able find matches at short notice some parameters were omitted. Hence, social characteristics and choices of participants, such as gender, age, employment status and willingness to socialize, were not included in many ride-matching algorithms. In this paper, the effects of including such factors in a ride-matching algorithm on the performance and the quality of the matches are investigated. Several ride-matching algorithms in the literature are simulated with randomly generated data. The simulation results show that when social factors are included the computation times and the quality of the matches increase significantly.

Keywords

• Dynamic Ride-Sharing
• Ride-matching
• Social parameters
• Transportation

References

1. Agatz N, Erera A L, Savelsbergh M W P & Wang X (2011). Dynamic ride-sharing: A simulation study in metro Atlanta. Procedia Social and Behavioral Sciences, 17, 532-550. DOI: 10.1016/j.sbspro.2011.04.530
2. Agatz N, Erera A, Savelsbergh M & Wang X (2012). Optimization for dynamic ride-sharing: A review, European Journal of Operational Research, 223(2), 295-303. DOI: 10.1016/j.ejor.2012.05.028
3. Aydin Ö F (2019). A Biosequence Based Ride-Matching Algorithm that Takes into Account Social Factors. PhD Thesis, Boğaziçi University, Department of Civil Engineering, Istanbul, Turkey.
4. Chan N D & Shaheen S A (2012). Ridesharing in North America: Past, Present, and Future. Transport Reviews, 32(1), 93-112. DOI: 10.1080/01441647.2011.621557
5. European Environment Agency (2005). Household consumption and the environment, 11, European Environment Agency.
6. European Environment Agency. (2015). Occupancy rates of passenger vehicles, European Environment Agency.
7. Ghoseiri K, Haghani A & Hamedi M (2011). Real-Time Rideshare Matching Problem. Final report, University of Maryland, Department of Civil and Environmental Engineering, MD, USA.
8. Gu Q-P, Liang J L & Zhang G. (2018). Algorithmic analysis for ridesharing of personal vehicles. Theoretical Computer Science, 749, 36-46. DOI: 10.1016/j.tcs.2017.08.019

9. Herbawi W M & Weber M (2012). A genetic and insertion heuristic algorithm for solving the dynamic ridematching problem with time windows. Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference, pp. 385-392. DOI: 10.1145/2330163.2330219
10. Nielsen J R, Hovmoller H, Blyth P-L & Sovacool B K. (2015). Of “white crows" and “cash savers:" A qualitative study of travel behavior and perceptions of ridesharing in Denmark. Transportation Research Part A: Policy and Practice, 78, 113-123. DOI: 10.1016/j.tra.2015.04.033
11. Qian X, Zhang W, Ukkusuri S V & Yang C (2017). Optimal assignment and incentive design in the taxi group ride problem. Transportation Research Part B: Methodological, 103, 208-226. DOI: 10.1016/j.trb.2017.03.001
12. Shaheen S & Cohen A (2018). Shared ride services in North America: definitions, impacts, and the future of pooling. Transport Reviews, 39(4), 1-16. DOI: 10.1080/01441647.2018.1497728
13. Shaheen S, Cohen A & Bayen A (2018). The Benefits of Carpooling. UC Berkeley: Transportation Sustainability Research Center. http://dx.doi.org/10.7922/G2DZ06GF.