Preferential Optimization of Multi-Hop Dynamic Ridesharing Based on R-Trees and Multi-Agent Systems

Abstract

For several years, we have been witnessing an increase in pollution and traffic jams in large cities. Research has therefore focused on the development of new, greener, and more flexible means of transport to complement the existing static transport offer. These means of transport are intended to be shared and dynamic to attract more people. One of these promising means of transportation is dynamic multi-hop ridesharing which makes it possible to route a rider through several drivers for a more flexible ridesharing offer. While the majority of papers on this topic deal with the global optimality of the system, we are interested in a preferential optimization for each individual in the system. In this context, this paper addresses an innovative solution to the on-demand multi-hop dynamic ridesharing problem where each actor (driver or rider) is represented by an autonomous and interactive entity called an “agent.” This ridesharing system is, therefore, a multi-agent system (MAS) in which each agent has a limited rationality. This MAS permits us to define the communications, perceptions, and preferences of drivers and riders. We detail a preference-weighted objective function for riders that allows the simulation of a wide range of behaviors. We propose the use of R-trees to optimize the computational cost of identifying candidate drivers and the best associated transfer nodes. We present various simulation scenarios by varying user preferences and instance parameters. Our experiments show that our model can efficiently simulate real-world behaviors and is able to optimize ridesharing on a case-by-case basis.

Keywords

artificial intelligence and advanced computing applications innovative public transportation services and technologies intelligent agents intelligent transportation systems modeling ridesharing traveler behavior and values

Get full access to this article

View all access options for this article.

References

Agatz

Erera

A. L.

Savelsbergh

M. W.

Wang

Dynamic Ride-Sharing: A Simulation Study in Metro Atlanta. Procedia -Social and Behavioral Sciences, Vol. 17, 2011, pp. 532–550. https://doi.org/10.1016/j.sbspro.2011.04.530.

Kleiner

Nebel

Ziparo

V. A.

A Mechanism for Dynamic Ride Sharing Based on Parallel Auctions. Proc., Twenty-Second International Joint Conference on Artificial Intelligence, Barcelona, Spain, AAAI Press, 2011, pp. 777–780.

Di Febbraro

Gattorna

Sacco

Optimization of Dynamic Ridesharing Systems. Transportation Research Record: Journal of the Transportation Research Board, 2013. 2359: 44–50.

Herbawi

Weber

The Ridematching Problem with Time Windows in Dynamic Ridesharing: A Model and a Genetic Algorithm. Proc., IEEE Congress on Evolutionary Computation, Brisbane, Australia, IEEE, New York, 2012, pp. 1–8. https://doi.org/10.1109/CEC.2012.6253001.

Cortès

C. E.

Matamala

Contardo

The Pickup and Delivery Problem with Transfers: Formulation and a Branch-and-Cut Solution Method. European Journal of Operational Research, Vol. 200, No. 3, 2010, pp. 711–724. https://doi.org/10.1016/j.ejor.2009.01.022.

Borovica-Gajic

Kulik

GeoPrune: Efficiently Matching Trips in Ride-Sharing Through Geometric Properties. Proc., 32nd International Conference on Scientific and Statistical Database Management, SSDBM 2020, Association for Computing Machinery, New York, 2020, pp. 1–12. https://doi.org/10.1145/3400903.3400912.

Tafreshian

Masoud

Trip-Based Graph Partitioning in Dynamic Ridesharing. Transportation Research Part C: Emerging Technologies, Vol. 114, 2020, pp. 532–553. https://doi.org/10.1016/j.trc.2020.02.008.

Pelzer

Xiao

Zehe

Lees

M. H.

Knoll

A. C.

Aydt

A Partition-Based Match Making Algorithm for Dynamic Ridesharing. IEEE Transactions on Intelligent Transportation Systems, Vol. 16, No. 5, 2015, pp. 2587–2598. https://doi.org/10.1109/TITS.2015.2413453.

Zheng

Wolfson

T-Share: A Large-Scale Dynamic Taxi Ridesharing Service. Proc., IEEE 29th International Conference on Data Engineering (ICDE), IEEE, New York, 2013, pp. 410–421. https://doi.org/10.1109/ICDE.2013.6544843.

10.

Masoud

Nam

Jayakrishnan

Promoting Peer-to-Peer Ridesharing Services as Transit System Feeders. Transportation Research Record: Journal of the Transportation Research Board, 2017. 2650: 74–83.

11.

Guttman

R Trees: A Dynamic Index Structure for Spatial Searching. Proc., ACM SIGMOD International Conference on Management of Data, ACM SIGMOD Record, Vol. 14, ACM, New York, 1984. https://doi.org/10.1145/971697.602266.

12.

Manolopoulos

Nanopoulos

Papadopoulos

A. N.

Theodoridis

R-Trees: Theory and Applications, Springer, London, 2010.

13.

Manolopoulos

Theodoridis

Tsotras

V. J.

Spatial Indexing Techniques. In Encyclopedia of Database Systems ( Liu

Tamer Özsu

, eds.), Springer, Boston, MA, 2009.

14.

Kulik

Borovica-Gajic

Aldwyish

Highly Efficient and Scalable Multi-hop Ride-Sharing. Proc., 28th International Conference on Advances in Geographic Information Systems, ACM, New York, 2020, pp. 215–226. https://doi.org/10.1145/3397536.3422235.

15.

Tong

Zeng

Zhou

Chen

A Unified Approach to Route Planning for Shared Mobility. Proceedings of the VLDB Endowment, Vol. 11, No. 11, 2018, pp. 1633–1646. https://doi.org/10.14778/3236187.3236211.

16.

Lin

Sasidharan

Wolfson

A Model of Multimodal Ridesharing and Its Analysis. Proc., 17th IEEE International Conference on Mobile Data Management (MDM), IEEE, New York, 2016, pp. 164–173. https://doi.org/10.1109/MDM.2016.34.

17.

Sycara

K. P.

Multiagent Systems. AI Magazine, Vol. 19, No. 22, 1998, p. 79. https://doi.org/10.1609/aimag.v19i2.1370.

18.

Bandara

H. A. N. C.

Dias

A Multi-Agent System for Dynamic Ride Sharing. Proc., International Conference on Industrial and Information Systems (ICIIS), IEEE, New York, 2009, pp. 199–203. https://doi.org/10.1109/ICIINFS.2009.5429866.

19.

Kamar

Horvitz

Collaboration and Shared Plans in the Open World: Studies of Ridesharing. Proc., Twenty-First International Joint Conference on Artificial Intelligence, Citeseer, San Francisco, CA, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2009, pp. 187–194.

20.

Jeribi

Mejri

Zgaya

Hammadi

Vehicle Sharing Services Optimization Based on Multi-Agent Approach. IFAC Proceedings Volumes, Vol. 44, No. 1, 2011, pp. 13040–13045. https://doi.org/10.3182/20110828-6-IT-1002.00615.

21.

Mathieu

Nongaillard

Effective Evaluation of Autonomous Taxi Fleets. Proc., ICAART, Vol. 1, SCITEPRESS – Science and Technology Publications, Lda, Portugal, 2018, pp. 297–304.

22.

Herbawi

Weber

Modeling the Multihop Ridematching Problem with Time Windows and Solving It Using Genetic Algorithms. Proceedings -International Conference on Tools with Artificial Intelligence, ICTAI, Athens, Greece, Vol. 1, IEEE, New York, 2012, p. 96. https://doi.org/10.1109/ICTAI.2012.21.

23.

A Multi-Modal Route Planning Approach with an Improved Genetic Algorithm. The International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. 38, 2012, pp. 343–348.

24.

Papadias

Shen

Tao

Mouratidis

Group Nearest Neighbor Queries. Proc., 20th International Conference on Data Engineering, IEEE, New York, 2004, pp. 301–312.

25.

Yiu

Mamoulis

Papadias

Aggregate Nearest Neighbor Queries in Road Networks. IEEE Transactions on Knowledge and Data Engineering, Vol. 17, 2005, pp. 820–833. https://doi.org/10.1109/TKDE.2005.87.

26.

Fevre

Zgaya-Biau

Mathieu

Hammadi

Multi-Agent Systems and R-Trees for Dynamic and Optimised Ridesharing. Proc., IEEE International Conference on Systems, Man, and Cybernetics (SMC), Melbourne, Australia, IEEE, New York, 2021, pp. 1352–1358. https://doi.org/10.1109/SMC52423.2021.9658823.

27.

Chen

Yao

Wang

Z.-J.

Gao

Shang

Guo

Flexible Aggregate Nearest Neighbor Queries and its Keyword-Aware Variant on Road Networks. IEEE Transactions on Knowledge and Data Engineering, Vol. 33, No. 12, 2020, pp. 3701–3715. https://doi.org/10.1109/TKDE.2020.2975998.

28.

Ferber

Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence, Addison-Wesley, Boston, MA, 1999.

29.

Adler

Heeringa

Search Space Reductions for Nearest-Neighbor Queries. Proc., Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Proceedings 5, Xi’an, China, April 25–29, 2008, Springer, Berlin, Heidelberg, pp. 554–567.

30.

Pareto

Cours d’’economie politique, Vol. 1. Librairie Droz, Switzerland, 1964.

31.

Boeing

OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks. Computers, Environment and Urban Systems, Vol. 65, 2017, pp. 126–139. https://doi.org/10.1016/j.compenvurbsys.2017.05.004.

32.

Gerte

Konduri

K. C.

Eluru

Is There a Limit to Adoption of Dynamic Ridesharing Systems? Evidence from Analysis of Uber Demand Data from New York City. Transportation Research Record: Journal of the Transportation Research Board, 2018. 2672: 127–136.

33.

Cheikh

S. B.

Hammadi

Multi-Criterion Tabu Search to Solve the Dynamic Carpooling Based on the Choquet Integral Aggregation. Journal of Traffic and Logistics Engineering, Vol. 2, No. 2, 2014, pp. 126–132. https://doi.org/10.12720/jtle.2.2.126-132.

34.

Cheikh-Graiet

S. B.

Dotoli

Hammadi

A Tabu Search Based Metaheuristic for Dynamic Carpooling Optimization. Computers & Industrial Engineering, Vol. 140, 2020, pp. 106–217. https://doi.org/10.1016/j.cie.2019.106217.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.15 MB