{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T15:45:30Z","timestamp":1781279130113,"version":"3.54.1"},"reference-count":110,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"EPFL Lausanne"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Artif Intell Rev"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the optimization of large-scale, real-time ridesharing systems and propose a modular design methodology, <jats:italic>Component Algorithms for Ridesharing<\/jats:italic> (CAR). We evaluate a diverse set of CARs (14 in total), focusing on the <jats:italic>key algorithmic components<\/jats:italic> of ridesharing. We take a multi-objective approach, evaluating 10 metrics related to <jats:italic>global efficiency<\/jats:italic>, <jats:italic>complexity<\/jats:italic>, <jats:italic>passenger<\/jats:italic>, and <jats:italic>platform<\/jats:italic> incentives, in settings designed to <jats:italic>closely resemble reality<\/jats:italic> in every aspect, focusing on vehicles of capacity two. To the best of our knowledge, this is the <jats:italic>largest<\/jats:italic> and most <jats:italic>comprehensive<\/jats:italic> evaluation to date. We (i) identify CARs that perform well on global, passenger, or platform metrics, (ii) demonstrate that lightweight <jats:italic>relocation schemes<\/jats:italic> can significantly improve the Quality of Service by up to <jats:inline-formula><jats:alternatives><jats:tex-math>$$50\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>50<\/mml:mn>\n                    <mml:mo>%<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and (iii) highlight a <jats:italic>practical<\/jats:italic>, <jats:italic>scalable<\/jats:italic>, <jats:italic>on-device<\/jats:italic> CAR that works well across all metrics.<\/jats:p>","DOI":"10.1007\/s10462-022-10145-0","type":"journal-article","created":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T19:48:05Z","timestamp":1644954485000},"page":"5781-5844","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Putting ridesharing to the test: efficient and scalable solutions and the power of dynamic vehicle relocation"],"prefix":"10.1007","volume":"55","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-6516-2495","authenticated-orcid":false,"given":"Panayiotis","family":"Danassis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marija","family":"Sakota","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aris","family":"Filos-Ratsikas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Boi","family":"Faltings","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,2,15]]},"reference":[{"key":"10145_CR1","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1016\/j.sbspro.2011.04.530","volume":"17","author":"N Agatz","year":"2011","unstructured":"Agatz N, Erera AL, Savelsbergh MW, Wang X (2011) Dynamic ride-sharing: a simulation study in metro atlanta. Procedia Soc Behav Sci 17:532\u2013550","journal-title":"Procedia Soc Behav Sci"},{"issue":"2","key":"10145_CR2","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.ejor.2012.05.028","volume":"223","author":"N Agatz","year":"2012","unstructured":"Agatz N, Erera A, Savelsbergh M, Wang X (2012) Optimization for dynamic ride-sharing: a review. Eur J Oper Res 223(2):295\u2013303","journal-title":"Eur J Oper Res"},{"key":"10145_CR3","doi-asserted-by":"crossref","unstructured":"Alonso-Gonz\u00e1lez MJ, van Oort N, Cats O, Hoogendoorn-Lanser S, Hoogendoorn S (2020) Value of time and reliability for urban pooled on-demand services. Transp Res Part C: Emerg Technol 115:102621","DOI":"10.1016\/j.trc.2020.102621"},{"key":"10145_CR4","doi-asserted-by":"crossref","unstructured":"Alonso-Mora J, Samaranayake S, Wallar A, Frazzoli E, Rus D (2017a) On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the National Academy of Sciences","DOI":"10.1073\/pnas.1611675114"},{"key":"10145_CR5","doi-asserted-by":"crossref","unstructured":"Alonso-Mora J, Wallar A, Rus D (2017b) Predictive routing for autonomous mobility-on-demand systems with ride-sharing. In: 2017 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), pp 3583\u20133590, 10.1109\/IROS.2017.8206203","DOI":"10.1109\/IROS.2017.8206203"},{"key":"10145_CR6","doi-asserted-by":"crossref","unstructured":"Asadpour A, Lobel I, van Ryzin G (2020) Minimum earnings regulation and the stability of marketplaces. In: Proceedings of the 21st ACM Conference on Economics and Computation, ACM, EC \u201920","DOI":"10.1145\/3391403.3399462"},{"key":"10145_CR7","unstructured":"Ashlagi I, Azar Y, Charikar M, Chiplunkar A, Geri O, Kaplan H, Makhijani R, Wang Y, Wattenhofer R (2017) Min-cost bipartite perfect matching with delays. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"key":"10145_CR8","doi-asserted-by":"crossref","unstructured":"Ashlagi I, Burq M, Dutta C, Jaillet P, Saberi A, Sholley C (2019) Edge weighted online windowed matching. In: Proceedings of the 2019 ACM Conference on Economics and Computation, ACM, EC \u201919","DOI":"10.1145\/3328526.3329573"},{"key":"10145_CR9","doi-asserted-by":"crossref","unstructured":"Banerjee S, Freund D, Lykouris T (2017) Pricing and optimization in shared vehicle systems: An approximation framework. In: Proceedings of the 2017 ACM Conference on Economics and Computation, ACM","DOI":"10.1145\/3033274.3085099"},{"issue":"5","key":"10145_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2783434","volume":"62","author":"N Bansal","year":"2015","unstructured":"Bansal N, Buchbinder N, Madry A, Naor J (2015) A polylogarithmic-competitive algorithm for the k-server problem. J ACM 62(5):1\u201349","journal-title":"J ACM"},{"key":"10145_CR11","unstructured":"Bartal Y (1996) Probabilistic approximation of metric spaces and its algorithmic applications. In: Proc. of 37th Conference on Foundations of Computer Science, IEEE"},{"key":"10145_CR12","unstructured":"Bartal Y, Grove E (2000) The harmonic k-server algorithm is competitive. Journal of the ACM (JACM)"},{"key":"10145_CR13","doi-asserted-by":"crossref","unstructured":"Bathla K, Raychoudhury V, Saxena D, Kshemkalyani AD (2018) Real-time distributed taxi ride sharing. In: 2018 21st International Conference on Intelligent Transportation Systems (ITSC), IEEE, pp 2044\u20132051","DOI":"10.1109\/ITSC.2018.8569315"},{"key":"10145_CR14","doi-asserted-by":"crossref","unstructured":"Bei X, Zhang S (2018) Algorithms for trip-vehicle assignment in ride-sharing. In: Thirty-Second AAAI","DOI":"10.1609\/aaai.v32i1.11298"},{"key":"10145_CR15","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.cie.2016.01.023","volume":"94","author":"V B\u00e9langer","year":"2016","unstructured":"B\u00e9langer V, Kergosien Y, Ruiz A, Soriano P (2016) An empirical comparison of relocation strategies in real-time ambulance fleet management. Comput Ind Eng 94:216\u2013229","journal-title":"Comput Ind Eng"},{"issue":"1","key":"10145_CR16","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman R (1958) On a routing problem. Q Appl Math 16(1):87\u201390","journal-title":"Q Appl Math"},{"key":"10145_CR17","unstructured":"Bertsekas DP (1998) Network optimization continuous and discrete models. Athena Scientific Belmont"},{"key":"10145_CR18","doi-asserted-by":"crossref","unstructured":"Bienkowski M, Kraska A, Liu HH, Schmidt P (2018) A primal-dual online deterministic algorithm for matching with delays. In: International Workshop on Approximation and Online Algorithms, Springer","DOI":"10.1007\/978-3-030-04693-4_4"},{"key":"10145_CR19","unstructured":"Bliek C, Bonami P, Lodi A (2014) Solving mixed-integer quadratic programming problems with ibm-cplex: a progress report. In: Proceedings of the twenty-sixth RAMP symposium, pp 16\u201317"},{"key":"10145_CR20","volume-title":"Online computation and competitive analysis","author":"A Borodin","year":"2005","unstructured":"Borodin A, El-Yaniv R (2005) Online computation and competitive analysis. Cambridge University Press, Cambridge"},{"key":"10145_CR21","unstructured":"Brown T (2016) Matchmaking in lyft line \u2014 part 1. eng.lyft.com\/matchmaking-in-lyft-line-9c2635fe62c4"},{"key":"10145_CR22","unstructured":"Brown T (2016) Matchmaking in lyft line \u2014 part 2. eng.lyft.com\/matchmaking-in-lyft-line-691a1a32a008"},{"key":"10145_CR23","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Coester C, Joseph, Naor (2020) Online $$k$$-taxi via double coverage and time-reverse primal-dual. arXiv:2012.02226","DOI":"10.1007\/978-3-030-73879-2_2"},{"key":"10145_CR24","unstructured":"Buchholz N (2018) Spatial equilibrium, search frictions and dynamic efficiency in the taxi industry. Tech. rep., mimeo, Princeton University"},{"key":"10145_CR25","doi-asserted-by":"crossref","unstructured":"B\u00fcrger M, Notarstefano G, Bullo F, Allg\u00f6wer F (2012) A distributed simplex algorithm for degenerate linear programs and multi-agent assignments. Automatica","DOI":"10.1016\/j.automatica.2012.06.040"},{"key":"10145_CR26","doi-asserted-by":"crossref","unstructured":"Chen M, Shen W, Tang P, Zuo S (2019) Dispatching through pricing: modeling ride-sharing and designing dynamic prices. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence","DOI":"10.24963\/ijcai.2019\/24"},{"key":"10145_CR27","doi-asserted-by":"crossref","unstructured":"Chen R, Cassandras CG (2019) Optimization of ride sharing systems using event-driven receding horizon control. arXiv:190101919","DOI":"10.1016\/j.ifacol.2021.04.039"},{"key":"10145_CR28","doi-asserted-by":"crossref","unstructured":"Chrobak M, Larmore LL (1991a) An optimal on-line algorithm for k servers on trees. SIAM Journal on Computing","DOI":"10.1137\/0220008"},{"key":"10145_CR29","first-page":"1","volume":"7","author":"M Chrobak","year":"1991","unstructured":"Chrobak M, Larmore LL (1991) The server problem and on-line games. On-line Algorithm 7:1","journal-title":"On-line Algorithm"},{"key":"10145_CR30","unstructured":"Chrobak M, Karloff H, Payne T, Vishwanathan S (1990) New results on server problems. SIAM Journal on Discrete Mathematics pp 291\u2013300"},{"key":"10145_CR31","doi-asserted-by":"crossref","unstructured":"Coester C, Koutsoupias E (2019) The online $$k$$-taxi problem. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, ACM","DOI":"10.1145\/3313276.3316370"},{"issue":"1","key":"10145_CR32","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10479-007-0170-8","volume":"153","author":"JF Cordeau","year":"2007","unstructured":"Cordeau JF, Laporte G (2007) The dial-a-ride problem: models and algorithms. Ann Oper Res 153(1):29\u201346","journal-title":"Ann Oper Res"},{"key":"10145_CR33","unstructured":"Danassis P (2022) Scalable multi-agent coordination and resource sharing. Ph.D thesis, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL), Lausanne"},{"key":"10145_CR34","doi-asserted-by":"publisher","unstructured":"Danassis P, Faltings B (2020) Efficient allocations in constant time: Towards scalable solutions in the era of large scale intelligent systems. In: Giacomo GD, Catal\u00e1 A, Dilkina B, Milano M, Barro S, Bugar\u00edn A, Lang J (eds) ECAI 2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020), IOS Press, Frontiers in Artificial Intelligence and Applications, vol 325, pp 2895\u20132896, https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.3233\/FAIA200441","DOI":"10.3233\/FAIA200441"},{"key":"10145_CR35","doi-asserted-by":"publisher","unstructured":"Danassis P, Filos-Ratsikas A, Faltings B (2019) Anytime heuristic for weighted matching through altruism-inspired behavior. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, International Joint Conferences on Artificial Intelligence Organization, pp 215\u2013222, https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.24963\/ijcai.2019\/31","DOI":"10.24963\/ijcai.2019\/31"},{"key":"10145_CR36","doi-asserted-by":"publisher","unstructured":"Danassis P, Wiedemair F, Faltings B (2021) Improving multi-agent coordination by learning to estimate contention. In: Zhou ZH (ed) Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, International Joint Conferences on Artificial Intelligence Organization, pp 125\u2013131, https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.24963\/ijcai.2021\/18, main Track","DOI":"10.24963\/ijcai.2021\/18"},{"key":"10145_CR37","unstructured":"Danassis P, Triastcyn A, Faltings B (2022) A distributed differentially private algorithm for resource allocation in unboundedly large settings. In: Proceedings of the 21th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS-22, International Foundation for Autonomous Agents and Multiagent Systems"},{"key":"10145_CR38","unstructured":"Dehghani S, Ehsani S, Hajiaghayi M, Liaghat V, Seddighin S (2017) Stochastic k-server: How should uber work? In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017"},{"key":"10145_CR39","doi-asserted-by":"crossref","unstructured":"Dickerson JP, Sankararaman KA, Srinivasan A, Xu P (2018) Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. In: Thirty-Second AAAI Conference on Artificial Intelligence","DOI":"10.1609\/aaai.v32i1.11477"},{"key":"10145_CR40","unstructured":"Dutta C, Sholley C (2018) Online matching in a ride-sharing platform. arXiv preprint arXiv:1806.10327"},{"key":"10145_CR41","first-page":"55","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Maximum matching and a polyhedron with 0 1-vertices. J Res Natl Bureau Stand B 69:55\u201356","journal-title":"J Res Natl Bureau Stand B"},{"issue":"1","key":"10145_CR42","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s11116-016-9729-z","volume":"45","author":"DJ Fagnant","year":"2018","unstructured":"Fagnant DJ, Kockelman KM (2018) Dynamic ride-sharing and fleet sizing for a system of shared autonomous vehicles in austin, texas. Transportation 45(1):143\u2013158","journal-title":"Transportation"},{"key":"10145_CR43","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol J, Rao S, Rao S, Talwar K (2003) A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC \u201903","DOI":"10.1145\/780542.780608"},{"issue":"3","key":"10145_CR44","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol J, Rao S, Talwar K (2004) A tight bound on approximating arbitrary metrics by tree metrics. J Comput Syst Sci 69(3):485\u2013497","journal-title":"J Comput Syst Sci"},{"key":"10145_CR45","doi-asserted-by":"crossref","unstructured":"Feder T, Greene D (1988) Optimal algorithms for approximate clustering. In: Proceedings of the twentieth annual ACM symposium on Theory of computing, ACM, pp 434\u2013444","DOI":"10.1145\/62212.62255"},{"issue":"3","key":"10145_CR46","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1016\/S0022-0000(05)80060-1","volume":"48","author":"A Fiat","year":"1994","unstructured":"Fiat A, Rabani Y, Ravid Y (1994) Competitive k-server algorithms. J Comput Syst Sci 48(3):410\u2013428","journal-title":"J Comput Syst Sci"},{"key":"10145_CR47","doi-asserted-by":"publisher","unstructured":"Fielbaum A, Alonso-Mora J (2020) Unreliability in ridesharing systems: Measuring changes in users\u2019 times due to new requests. Transportation Research Part C: Emerging Technologies 121:102831. https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.trc.2020.102831, https:\/\/2.zoppoz.workers.dev:443\/https\/www.sciencedirect.com\/science\/article\/pii\/S0968090X2030735X","DOI":"10.1016\/j.trc.2020.102831"},{"key":"10145_CR48","doi-asserted-by":"publisher","unstructured":"Fielbaum A, Bai X, Alonso-Mora J (2021) On-demand ridesharing with optimized pick-up and drop-off walking locations. Transportation Research Part C: Emerging Technologies 126:103061. https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.trc.2021.103061, https:\/\/2.zoppoz.workers.dev:443\/https\/www.sciencedirect.com\/science\/article\/pii\/S0968090X21000887","DOI":"10.1016\/j.trc.2021.103061"},{"key":"10145_CR49","doi-asserted-by":"crossref","unstructured":"Fielbaum A, Kronmueller M, Alonso-Mora J (2021b) Anticipatory routing methods for an on-demand ridepooling mobility system. Transportation pp 1\u201342","DOI":"10.1007\/s11116-021-10232-1"},{"key":"10145_CR50","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.trb.2013.08.012","volume":"57","author":"M Furuhata","year":"2013","unstructured":"Furuhata M, Dessouky M, Ord\u00f3\u00f1ez F, Brunet ME, Wang X, Koenig S (2013) Ridesharing: The state-of-the-art and future directions. Transp Res Part B: Methodol 57:28\u201346","journal-title":"Transp Res Part B: Methodol"},{"key":"10145_CR51","doi-asserted-by":"publisher","unstructured":"Gao J, Wang Y, Tang H, Yin Z, Ni L, Shen Y (2017) An efficient dynamic ridesharing algorithm. In: 2017 IEEE International Conference on Computer and Information Technology (CIT), pp 320\u2013325, https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1109\/CIT.2017.33","DOI":"10.1109\/CIT.2017.33"},{"key":"10145_CR52","doi-asserted-by":"crossref","unstructured":"Garg N, Nazerzadeh H (2020) Driver surge pricing. In: Proceedings of the 21st ACM Conference on Economics and Computation, ACM, EC \u201920","DOI":"10.1145\/3391403.3399476"},{"key":"10145_CR53","doi-asserted-by":"crossref","unstructured":"Ghili S, Kumar V (2020) Spatial distribution of supply and the role of market thickness: Theory and evidence from ridesharing. In: Proceedings of the 21st ACM Conference on Economics and Computation, ACM, EC \u201920","DOI":"10.1145\/3391403.3399534"},{"key":"10145_CR54","doi-asserted-by":"crossref","unstructured":"Giordani S, Lujak M, Martinelli F (2010) A distributed algorithm for the multi-robot task allocation problem. In: Int. Conf. on Industrial, Engineering and Other Applications of Applied Intelligent Systems","DOI":"10.1007\/978-3-642-13022-9_72"},{"key":"10145_CR55","unstructured":"Goemans MX, Williamson DP (1997) The primal-dual method for approximation algorithms and its application to network design problems. Approximation algorithms for NP-hard problems pp 144\u2013191"},{"key":"10145_CR56","doi-asserted-by":"crossref","unstructured":"Gu\u00e9riau M, Dusparic I (2018) Samod: Shared autonomous mobility-on-demand using decentralized reinforcement learning. In: 2018 21st International Conference on Intelligent Transportation Systems (ITSC), IEEE","DOI":"10.1109\/ITSC.2018.8569608"},{"issue":"1","key":"10145_CR57","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha S, Khuller S (1999) Greedy strikes back improved facility location algorithms. J Algorithms 31(1):228\u2013248","journal-title":"J Algorithms"},{"key":"10145_CR58","doi-asserted-by":"crossref","unstructured":"He S, Shin KG (2019) Spatio-temporal capsule-based reinforcement learning for mobility-on-demand network coordination. In: The World Wide Web Conference, WWW 2019, ACM, pp 2806\u20132813","DOI":"10.1145\/3308558.3313401"},{"key":"10145_CR59","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.trb.2018.02.001","volume":"111","author":"SC Ho","year":"2018","unstructured":"Ho SC, Szeto W, Kuo YH, Leung JM, Petering M, Tou TW (2018) A survey of dial-a-ride problems: Literature review and recent developments. Transp Res Part B: Methodol 111:395\u2013421","journal-title":"Transp Res Part B: Methodol"},{"issue":"3","key":"10145_CR60","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"WL Hsu","year":"1979","unstructured":"Hsu WL, Nemhauser GL (1979) Easy and hard bottleneck location problems. Discret Appl Math 1(3):209\u2013215","journal-title":"Discret Appl Math"},{"key":"10145_CR61","unstructured":"Huang T, Fang B, Bei X, Fang F (2019) Dynamic trip-vehicle dispatch with scheduled and on-demand requests. In: The Conference on Uncertainty in Artificial Intelligence (UAI)"},{"key":"10145_CR62","doi-asserted-by":"crossref","unstructured":"Ismail S, Sun L (2017) Decentralized hungarian-based approach for fast and scalable task allocation. In: 2017 Int. Conf. on Unmanned Aircraft Systems (ICUAS)","DOI":"10.1109\/ICUAS.2017.7991447"},{"key":"10145_CR63","doi-asserted-by":"crossref","unstructured":"Jiang S, Chen L, Mislove A, Wilson C (2018) On ridesharing competition and accessibility: Evidence from uber, lyft, and taxi. In: Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, ACM","DOI":"10.1145\/3178876.3186134"},{"key":"10145_CR64","doi-asserted-by":"crossref","unstructured":"Kooti F, Grbovic M, Aiello LM, Djuric N, Radosavljevic V, Lerman K (2017) Analyzing uber\u2019s ride-sharing economy. In: Proceedings of the 26th International Conference on World Wide Web Companion, 2017, ACM","DOI":"10.1145\/3041021.3054194"},{"key":"10145_CR65","unstructured":"Kosoresow AP (1996) Design and analysis of online algorithms for mobile server applications. PhD thesis, Stanford University, Stanford, CA, USA, aAI9702926"},{"issue":"2","key":"10145_CR66","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.cosrev.2009.04.002","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias E (2009) The k-server problem. Comput Sci Rev 3(2):105\u2013118","journal-title":"Comput Sci Rev"},{"issue":"5","key":"10145_CR67","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E Koutsoupias","year":"1995","unstructured":"Koutsoupias E, Papadimitriou CH (1995) On the k-server conjecture. J ACM (JACM) 42(5):971\u2013983","journal-title":"J ACM (JACM)"},{"key":"10145_CR68","doi-asserted-by":"crossref","unstructured":"Lee JR (2018) Fusible hsts and the randomized k-server conjecture. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), IEEE","DOI":"10.1109\/FOCS.2018.00049"},{"key":"10145_CR69","unstructured":"Lesmana N, Zhang X, Bei X (2019) Balancing efficiency and fairness in on-demand ridesourcing. In: Proceedings of the 33rd Conference on Neural Information Processing Systems (NEURIPS)"},{"key":"10145_CR70","doi-asserted-by":"crossref","unstructured":"Li M, Qin Z, Jiao Y, Yang Y, Wang J, Wang C, Wu G, Ye J (2019) Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning. In: The World Wide Web Conference, WWW 2019, ACM","DOI":"10.1145\/3308558.3313433"},{"key":"10145_CR71","unstructured":"Lioris J, Cohen G, Seidowsky R, Salem HH (2016) Dynamic evolution and optimisation of an urban collective taxis systems by discrete-event simulation. In: ITS World Congress 2016, p 10"},{"key":"10145_CR72","doi-asserted-by":"publisher","unstructured":"Lokhandwala M, Cai H (2018) Dynamic ride sharing using traditional taxis and shared autonomous taxis: A case study of nyc. Transportation Research Part C: Emerging Technologies 97:45\u201360. https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.trc.2018.10.007, https:\/\/2.zoppoz.workers.dev:443\/https\/www.sciencedirect.com\/science\/article\/pii\/S0968090X18307551","DOI":"10.1016\/j.trc.2018.10.007"},{"key":"10145_CR73","unstructured":"Lowalekar M, Varakantham P, Jaillet P (2019) Zac: A zone path construction approach for effective real-time ridesharing. In: ICAPS"},{"key":"10145_CR74","doi-asserted-by":"crossref","unstructured":"Ma H, Fang F, Parkes DC (2019) Spatio-temporal pricing for ridesharing platforms. In: Proceedings of the 2019 ACM Conference on Economics and Computation, ACM, pp 583\u2013583","DOI":"10.1145\/3328526.3329556"},{"key":"10145_CR75","doi-asserted-by":"crossref","unstructured":"Manasse M, McGeoch L, Sleator D (1988) Competitive algorithms for on-line problems. In: Proceedings of the twentieth annual ACM symposium on Theory of computing, ACM, pp 322\u2013333","DOI":"10.1145\/62212.62243"},{"issue":"2","key":"10145_CR76","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"MS Manasse","year":"1990","unstructured":"Manasse MS, McGeoch LA, Sleator DD (1990) Competitive algorithms for server problems. J Algorithms 11(2):208\u2013230","journal-title":"J Algorithms"},{"issue":"2","key":"10145_CR77","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1080\/15568318.2016.1226997","volume":"11","author":"LM Mart\u00ednez","year":"2017","unstructured":"Mart\u00ednez LM, Correia GHA, Moura F, Mendes Lopes M (2017) Insights into carsharing demand dynamics: Outputs of an agent-based model application to lisbon, portugal. Int J Sustain Transp 11(2):148\u2013159","journal-title":"Int J Sustain Transp"},{"key":"10145_CR78","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/j.trb.2019.02.003","volume":"123","author":"A Mourad","year":"2019","unstructured":"Mourad A, Puchinger J, Chu C (2019) A survey of models and algorithms for optimizing shared mobility. Transp Res Part B: Methodol 123:323\u201334","journal-title":"Transp Res Part B: Methodol"},{"key":"10145_CR79","doi-asserted-by":"crossref","unstructured":"Nanda V, Xu P, Sankararaman KA, Dickerson JP, Srinivasan A (2020) Balancing the tradeoff between profit and fairness in rideshare platforms during high-demand hours. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, AAAI Press","DOI":"10.1145\/3375627.3375818"},{"issue":"5","key":"10145_CR80","doi-asserted-by":"publisher","first-page":"2587","DOI":"10.1109\/TITS.2015.2413453","volume":"16","author":"D Pelzer","year":"2015","unstructured":"Pelzer D, Xiao J, Zehe D, Lees MH, Knoll AC, Aydt H (2015) A partition-based match making algorithm for dynamic ridesharing. IEEE Trans Intell Transp Syst 16(5):2587\u20132598. https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1109\/TITS.2015.2413453","journal-title":"IEEE Trans Intell Transp Syst"},{"key":"10145_CR81","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.trb.2017.03.001","volume":"103","author":"X Qian","year":"2017","unstructured":"Qian X, Zhang W, Ukkusuri SV, Yang C (2017) Optimal assignment and incentive design in the taxi group ride problem. Transp Res Part B: Methodol 103:208\u2013226","journal-title":"Transp Res Part B: Methodol"},{"key":"10145_CR82","doi-asserted-by":"crossref","unstructured":"Raghavan P, Snir M (1989) Memory versus randomization in on-line algorithms. In: International Colloquium on Automata, Languages, and Programming, Springer, pp 687\u2013703","DOI":"10.1007\/BFb0035792"},{"key":"10145_CR83","doi-asserted-by":"crossref","unstructured":"Riley C, van Hentenryck P, Yuan E (2020) Real-time dispatching of large-scale ride-sharing systems: Integrating optimization, machine learning, and model predictive control. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20","DOI":"10.24963\/ijcai.2020\/609"},{"key":"10145_CR84","doi-asserted-by":"crossref","unstructured":"Ruch C, H\u00f6rl S, Frazzoli E (2018) Amodeus, a simulation-based testbed for autonomous mobility-on-demand systems. In: 2018 21st International Conference on Intelligent Transportation Systems (ITSC), IEEE","DOI":"10.1109\/ITSC.2018.8569961"},{"issue":"1","key":"10145_CR85","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s10100-011-0222-7","volume":"21","author":"T Rudec","year":"2013","unstructured":"Rudec T, Baumgartner A, Manger R (2013) A fast work function algorithm for solving the k-server problem. CEJOR 21(1):187\u2013205","journal-title":"CEJOR"},{"key":"10145_CR86","doi-asserted-by":"crossref","unstructured":"Santi P, Resta G, Szell M, Sobolevsky S, Strogatz SH, Ratti C (2014) Quantifying the benefits of vehicle pooling with shareability networks. Proceedings of the National Academy of Sciences","DOI":"10.1073\/pnas.1403657111"},{"key":"10145_CR87","unstructured":"Santos DO, Xavier EC (2013) Dynamic taxi and ridesharing: A framework and heuristics for the optimization problem. In: Twenty-Third International Joint Conference on Artificial Intelligence"},{"issue":"19","key":"10145_CR88","doi-asserted-by":"publisher","first-page":"6728","DOI":"10.1016\/j.eswa.2015.04.060","volume":"42","author":"DO Santos","year":"2015","unstructured":"Santos DO, Xavier EC (2015) Taxi and ride sharing: A dynamic dial-a-ride problem with money as an incentive. Expert Syst Appl 42(19):6728\u20136737","journal-title":"Expert Syst Appl"},{"key":"10145_CR89","doi-asserted-by":"publisher","unstructured":"Shah S, Lowalekar M, Varakantham P (2020) Neural approximate dynamic programming for on-demand ride-pooling. Proceedings of the AAAI Conference on Artificial Intelligence 34(01):507\u2013515. https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1609\/aaai.v34i01.5388, https:\/\/2.zoppoz.workers.dev:443\/https\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/5388","DOI":"10.1609\/aaai.v34i01.5388"},{"issue":"4","key":"10145_CR90","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1080\/01441647.2018.1497728","volume":"39","author":"S Shaheen","year":"2019","unstructured":"Shaheen S, Cohen A (2019) Shared ride services in north america: definitions, impacts, and the future of pooling. Transp Rev 39(4):427\u2013442. https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1080\/01441647.2018.1497728","journal-title":"Transp Rev"},{"key":"10145_CR91","doi-asserted-by":"crossref","unstructured":"Silwal S, Gani MO, Raychoudhury V (2019) A survey of taxi ride sharing system architectures. In: 2019 IEEE International Conference on Smart Computing (SMARTCOMP), IEEE, pp 144\u2013149","DOI":"10.1109\/SMARTCOMP.2019.00044"},{"key":"10145_CR92","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.trc.2019.01.019","volume":"101","author":"A Simonetto","year":"2019","unstructured":"Simonetto A, Monteil J, Gambella C (2019) Real-time city-scale ridesharing via linear assignment problems. Transp Res Part C: Emerg Technol 101:208\u2013232","journal-title":"Transp Res Part C: Emerg Technol"},{"key":"10145_CR93","doi-asserted-by":"publisher","unstructured":"Spieser K, Treleaven K, Zhang R, Frazzoli E, Morton D, Pavone M (2014) Toward a Systematic Approach to the Design and Evaluation of Automated Mobility-on-Demand Systems: A Case Study in Singapore, Springer International Publishing, Cham, pp 229\u2013245. https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/978-3-319-05990-7_20","DOI":"10.1007\/978-3-319-05990-7_20"},{"key":"10145_CR94","unstructured":"Spieser K, Samaranayake S, Gruel W, Frazzoli E (2016) Shared-vehicle mobility-on-demand systems: a fleet operator\u2019s guide to rebalancing empty vehicles. In: Transp. Research Board 95th Annual Meeting"},{"key":"10145_CR95","doi-asserted-by":"publisher","unstructured":"Stiglic M, Agatz N, Savelsbergh M, Gradisar M (2015) The benefits of meeting points in ride-sharing systems. Transportation Research Part B: Methodological 82:36\u201353. https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.trb.2015.07.025, https:\/\/2.zoppoz.workers.dev:443\/https\/www.sciencedirect.com\/science\/article\/pii\/S0191261515002088","DOI":"10.1016\/j.trb.2015.07.025"},{"key":"10145_CR96","doi-asserted-by":"crossref","unstructured":"S\u00fchr T, Biega AJ, Zehlike M, Gummadi KP, Chakraborty A (2019) Two-sided fairness for repeated matchings in two-sided markets: A case study of a ride-hailing platform. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, ACM","DOI":"10.1145\/3292500.3330793"},{"key":"10145_CR97","doi-asserted-by":"crossref","unstructured":"Tang M, Ow S, Chen W, Cao Y, Lye K, Pan Y (2017) The data and science behind grabshare carpooling. In: 2017 IEEE International Conference on Data Science and Advanced Analytics (DSAA)","DOI":"10.1109\/DSAA.2017.68"},{"key":"10145_CR98","doi-asserted-by":"publisher","unstructured":"Tsao M, Milojevic D, Ruch C, Salazar M, Frazzoli E, Pavone M (2019) Model predictive control of ride-sharing autonomous mobility-on-demand systems. In: 2019 International Conference on Robotics and Automation (ICRA), pp 6665\u20136671, https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1109\/ICRA.2019.8794194","DOI":"10.1109\/ICRA.2019.8794194"},{"key":"10145_CR99","doi-asserted-by":"publisher","unstructured":"van Engelen M, Cats O, Post H, Aardal K (2018) Enhancing flexible transport services with demand-anticipatory insertion heuristics. Transportation Research Part E: Logistics and Transportation Review 110:110\u2013121. https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.tre.2017.12.015, https:\/\/2.zoppoz.workers.dev:443\/https\/www.sciencedirect.com\/science\/article\/pii\/S1366554517307810","DOI":"10.1016\/j.tre.2017.12.015"},{"key":"10145_CR100","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.trc.2019.08.006","volume":"107","author":"R Vosooghi","year":"2019","unstructured":"Vosooghi R, Puchinger J, Jankovic M, Vouillon A (2019) Shared autonomous vehicle simulation and service design. Transp Res Part C: Emerg Technol 107:15\u201333","journal-title":"Transp Res Part C: Emerg Technol"},{"key":"10145_CR101","doi-asserted-by":"publisher","unstructured":"Wallar A, Van Der\u00a0Zee M, Alonso-Mora J, Rus D (2018) Vehicle rebalancing for mobility-on-demand systems with ride-sharing. In: 2018 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), pp 4539\u20134546, https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1109\/IROS.2018.8593743","DOI":"10.1109\/IROS.2018.8593743"},{"key":"10145_CR102","doi-asserted-by":"publisher","unstructured":"Wen J, Zhao J, Jaillet P (2017) Rebalancing shared mobility-on-demand systems: A reinforcement learning approach. In: 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC), pp 220\u2013225, https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1109\/ITSC.2017.8317908","DOI":"10.1109\/ITSC.2017.8317908"},{"key":"10145_CR103","doi-asserted-by":"crossref","unstructured":"Widdows D, Lucas J, Tang M, Wu W (2017) Grabshare: The construction of a realtime ridesharing service. In: 2017 2nd IEEE International Conference on Intelligent Transportation Engineering (ICITE)","DOI":"10.1109\/ICITE.2017.8056896"},{"key":"10145_CR104","doi-asserted-by":"crossref","unstructured":"Xu D, Tian Y (2015) A comprehensive survey of clustering algorithms. Annals of Data Science","DOI":"10.1007\/s40745-015-0040-1"},{"key":"10145_CR105","doi-asserted-by":"crossref","unstructured":"Xu Y, Xu P (2020) Trade the system efficiency for the income equality of drivers in rideshare. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020","DOI":"10.24963\/ijcai.2020\/580"},{"key":"10145_CR106","doi-asserted-by":"publisher","unstructured":"Xue R, Sun DJ, Chen S (2015) Short-term bus passenger demand prediction based on time series model and interactive multiple model approach. Discrete Dynamics in Nature and Society 2015. https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1155\/2015\/682390","DOI":"10.1155\/2015\/682390"},{"key":"10145_CR107","doi-asserted-by":"crossref","unstructured":"Yuen CF, Singh AP, Goyal S, Ranu S, Bagchi A (2019) Beyond shortest paths: Route recommendations for ride-sharing. In: The World Wide Web Conference, ACM, pp 2258\u20132269","DOI":"10.1145\/3308558.3313465"},{"key":"10145_CR108","doi-asserted-by":"crossref","unstructured":"Zavlanos MM, Spesivtsev L, Pappas GJ (2008) A distributed auction algorithm for the assignment problem. In: Decision and Control, 2008., IEEE","DOI":"10.1109\/CDC.2008.4739098"},{"key":"10145_CR109","first-page":"2245","volume":"33","author":"B Zhao","year":"2019","unstructured":"Zhao B, Xu P, Shi Y, Tong Y, Zhou Z, Zeng Y (2019) Preference-aware task assignment in on-demand taxi dispatching: An online stable matching approach. Proceed AAAI Conf Artif Intell 33:2245\u20132252","journal-title":"Proceed AAAI Conf Artif Intell"},{"key":"10145_CR110","doi-asserted-by":"publisher","unstructured":"Zhou C, Dai P, Li R (2013) The passenger demand prediction model on bus networks. In: 2013 IEEE 13th International Conference on Data Mining Workshops, pp 1069\u20131076, https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1109\/ICDMW.2013.20","DOI":"10.1109\/ICDMW.2013.20"}],"container-title":["Artificial Intelligence Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/content\/pdf\/10.1007\/s10462-022-10145-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/article\/10.1007\/s10462-022-10145-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/content\/pdf\/10.1007\/s10462-022-10145-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T07:34:38Z","timestamp":1661931278000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/10.1007\/s10462-022-10145-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,15]]},"references-count":110,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["10145"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/s10462-022-10145-0","relation":{},"ISSN":["0269-2821","1573-7462"],"issn-type":[{"value":"0269-2821","type":"print"},{"value":"1573-7462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,15]]},"assertion":[{"value":"15 February 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}