Efficient Algorithms for Stochastic Ride-Pooling Assignment with Mixed Fleets

References

• Alonso-Mora J, Samaranayake S, Wallar A, Frazzoli E, Rus D (2017) On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proc. National Acad. Sci. USA 114(3):462–467.Crossref, Google Scholar
• Arkin EM, Hassin R (1998) On local search for weighted k-set packing. Math. Oper. Res. 23(3):640–648.Link, Google Scholar
• Ashlagi I, Burq M, Dutta C, Jaillet P, Saberi A, Sholley C (2018) Maximum weight online matching with deadlines. Preprint, submitted August 9, https://arxiv.org/abs/1808.03526.Google Scholar
• Benjaafar S, Wu S, Liu H, Gunnarsson EB (2021) Dimensioning on-demand vehicle sharing systems. Management Sci. 68(2):1218–1232.Link, Google Scholar
• Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization, volume 6 (Athena Scientific, Belmont, MA).Google Scholar
• Bollobás B, Erdös P (1976) Cliques in random graphs. Math. Proc. Cambridge Philosophical Soc. 80:419–427.Crossref, Google Scholar
• Braverman A, Dai JG, Liu X, Ying L (2019) Empty-car routing in ridesharing systems. Oper. Res. 67(5):1437–1452.Link, Google Scholar
• Buchbinder N, Chen S, Gupta A, Nagarajan V, Naor J (2014) Online packing and covering framework with convex objectives. Preprint, submitted December 29, https://arxiv.org/abs/1412.8347.Google Scholar
• Castro F, Frazier P, Ma H, Nazerzadeh H, Yan C (2020) Matching queues, flexibility and incentives. Preprint, submitted June 16, https://arxiv.org/abs/2006.08863.Google Scholar
• Chan YH, Lau LC (2012) On linear and semidefinite programming relaxations for hypergraph matching. Math. Programming 135(1):123–148.Crossref, Google Scholar
• Chekuri C, Khanna S (2005) A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3):713–728.Crossref, Google Scholar
• Chen D, Ahn S, Chitturi M, Noyce DA (2017a) Toward vehicle automation: Roadway capacity formulation for traffic mixed with regular and automated vehicles. Transportation Res. Part B: Methodological 100:196–221.Crossref, Google Scholar
• Chen Z, He F, Yin Y, Du Y (2017b) Optimal design of autonomous vehicle zones in transportation networks. Transportation Res. Part B: Methodological 99:44–61.Crossref, Google Scholar
• Data NO (2022) Nyc community district data. Accessed November 2, 2021, https://data.cityofnewyork.us/City-Government/Community-Districts/yfnk-k7r4.Google Scholar
• Dong J, Ibrahim R (2020) Managing supply in the on-demand economy: Flexible workers, full-time employees, or both? Oper. Res. 68(4):1238–1264.Link, Google Scholar
• Dong T, Sun X, Luo Q, Wang J, Yin Y (2023) The dual effects of team contest design on on-demand service work schedules. Service Sci., ePub ahead of print March 8, https://doi.org/10.1287/serv.2023.0320.Link, Google Scholar
• Dong T, Xu Z, Luo Q, Yin Y, Wang J, Ye J (2021) Optimal contract design for ride-sourcing services under dual sourcing. Transportation Res. Part B: Methodological 146:289–313.Crossref, Google Scholar
• Feige U, Jain K, Mahdian M, Mirrokni V (2007) Robust combinatorial optimization with exponential scenarios. Fischetti M, Williamson DP, eds. Proc. Internat. Conf. on Integer Programming and Combinatorial Optim. Lecture Notes in Computer Science, vol. 4513 (Springer, Berlin), 439–453.Google Scholar
• Fleischer L, Goemans MX, Mirrokni VS, Sviridenko M (2006) Tight approximation algorithms for maximum general assignment problems. Proc. 17th Annual ACM-SIAM Sympos. on Discrete Algorithm, 611–620.Google Scholar
• Füredi Z, Kahn J, Seymour PD (1993) On the fractional matching polytope of a hypergraph. Combinatorica 13(2):167–180.Crossref, Google Scholar
• Geng X, Li Y, Wang L, Zhang L, Yang Q, Ye J, Liu Y (2019) Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting. Proc. Conf. AAAI Artificial Intelligence 33:3656–3663.Crossref, Google Scholar
• Guda H, Subramanian U (2019) Your uber is arriving: Managing on-demand workers through surge pricing, forecast communication, and worker incentives. Management Sci. 65(5):1995–2014.Abstract, Google Scholar
• Guo X, Caros NS, Zhao J (2021) Robust matching-integrated vehicle rebalancing in ride-hailing system with uncertain demand. Transportation Res. Part B: Methodological 150:161–189.Crossref, Google Scholar
• Gupta A, Nagarajan V (2014) Approximating sparse covering integer programs online. Math. Oper. Res. 39(4):998–1011.Link, Google Scholar
• Gupta A, Nagarajan V, Ravi R (2015) Robust and maxmin optimization under matroid and knapsack uncertainty sets. ACM Trans. Algorithms 12(1):1–21.Crossref, Google Scholar
• Hasan MH, Van Hentenryck P (2021) The benefits of autonomous vehicles for community-based trip sharing. Transportation Res., Part C Emerging Tech. 124:102929.Crossref, Google Scholar
• Hasan MH, Van Hentenryck P, Legrain A (2020) The commute trip-sharing problem. Transportation Sci. 54(6):1640–1675.Link, Google Scholar
• Hazan E, Safra S, Schwartz O (2006) On the complexity of approximating k-set packing. Comput. Complexity 15(1):20–39.Crossref, Google Scholar
• Herminghaus S (2019) Mean field theory of demand responsive ride pooling systems. Transportation Res. Part A Policy Practices 119:15–28.Crossref, Google Scholar
• Hoffman AJ (2003) Inequalities to extremal combinatorial analysis. Selected Papers Alan Hoffman Commentary 10:244.Crossref, Google Scholar
• Karamanis R, Anastasiadis E, Stettler M, Angeloudis P (2021) Vehicle redistribution in ride-sourcing markets using convex minimum cost flows. IEEE Trans. Intelligent Transportation Systems. 23(8):10287–10298.Google Scholar
• Ke J, Zheng Z, Yang H, Ye J (2021) Data-driven analysis on matching probability, routing distance and detour distance in ride-pooling services. Transporation Res., Part C Emerging Tech. 124:102922.Crossref, Google Scholar
• Lavieri PS, Bhat CR (2019) Modeling individuals’ willingness to share trips with strangers in an autonomous vehicle future. Transportation Res. Part A Policy Practice 124:242–261.Crossref, Google Scholar
• Li J, Chen D, Zhang M (2022) Equilibrium modeling of mixed autonomy traffic flow based on game theory. Transportation Res. Part B: Methodological 166:110–127.Crossref, Google Scholar
• Li S, Luo Q, Hampshire RC (2021) Optimizing large on-demand transportation systems through stochastic conic programming. Eur. J. Oper. Res. 295(2):427–442.Crossref, Google Scholar
• Liu Y, Samaranayake S (2020) Proactive rebalancing and speed-up techniques for on-demand high capacity ridesourcing services. IEEE Trans. Intelligent Transportation Systems. 23(2):819–826.Google Scholar
• Lokhandwala M, Cai H (2018) Dynamic ride sharing using traditional taxis and shared autonomous taxis: A case study of NYC. Transportation Res., Part C Emerging Tech. 97:45–60.Crossref, Google Scholar
• Lowalekar M, Varakantham P, Jaillet P (2020) Competitive ratios for online multi-capacity ridesharing. Proc. 19th Internat. Conf. on Autonomous Agents and MultiAgent Systems, 771–779.Google Scholar
• Ma J, Li X, Zhou F, Hao W (2017) Designing optimal autonomous vehicle sharing and reservation systems: A linear programming approach. Transporation Res., Part C Emerging Tech. 84:124–141.Crossref, Google Scholar
• Markov I, Guglielmetti R, Laumanns M, Fernández-Antolín A, de Souza R (2021) Simulation-based design and analysis of on-demand mobility services. Transportation Res. Part A Policy Practice 149:170–205.Crossref, Google Scholar
• Matula DW (1976) The Largest Clique Size in a Random Graph (Department of Computer Science, Southern Methodist University, Dallas, TX).Google Scholar
• Mori JCM, Samaranayake S (2021) On the request-trip-vehicle assignment problem. Proc. SIAM Conf. on Appl. and Comput. Discrete Algorithms, 228–239.Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—i. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Öncan T (2007) A survey of the generalized assignment problem and its applications. INFOR Inform. Systems Oper. Res. 45(3):123–141.Crossref, Google Scholar
• Pagnoncelli BK, Ahmed S, Shapiro A (2009) Sample average approximation method for chance constrained programming: Theory and applications. J. Optim. Theory Appl. 142(2):399–416.Crossref, Google Scholar
• Qin G, Luo Q, Yin Y, Sun J, Ye J (2021) Optimizing matching time intervals for ride-hailing services using reinforcement learning. Transportation Res. Part C Emerging Tech. 129:103239.Crossref, Google Scholar
• Qin ZT, Zhu H, Ye J (2021) Reinforcement learning for ridesharing: A survey. 2021 IEEE International Intelligent Transportation Systems Conference (ITSC) (IEEE, Piscataway, NJ), 2447–2454.Google Scholar
• Santi P, Resta G, Szell M, Sobolevsky S, Strogatz SH, Ratti C (2014) Quantifying the benefits of vehicle pooling with shareability networks. Proc. National Acad. Sci. USA 111(37):13290–13294.Crossref, Google Scholar
• Shah S, Lowalekar M, Varakantham P (2020) Neural approximate dynamic programming for on-demand ride-pooling. Proc. Conf. AAAI Artificial Intelligence 34:507–515.Crossref, Google Scholar
• Shladover SE (2018) Connected and automated vehicle systems: Introduction and overview. J. Intelligent Transportation Systems 22(3):190–200.Crossref, Google Scholar
• Shmoys DB, Tardos É (1993) An approximation algorithm for the generalized assignment problem. Math. Programming 62(1–3):461–474.Crossref, Google Scholar
• Simonetto A, Monteil J, Gambella C (2019) Real-time city-scale ridesharing via linear assignment problems. Transportation Res., Part C Emerging Tech. 101:208–232.Crossref, Google Scholar
• Sundt A, Luo Q, Vincent J, Shahabi M, Yin Y (2021) Heuristics for customer-focused ride-pooling assignment. Preprint, submitted July 23, https://arxiv.org/abs/2107.11318.Google Scholar
• Tang X, Qin Z, Zhang F, Wang Z, Xu Z, Ma Y, Zhu H, et al. (2019) A deep value-network based approach for multi-driver order dispatching. Proc. 25th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining, 1780–1790.Google Scholar
• TLC (2021) Nyc taxi and limousine commission trip record data. Accessed May 2, 2021, https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page.Google Scholar
• Wang H, Yang H (2019) Ridesourcing systems: A framework and review. Transportation Res. Part B: Methodological 129:122–155.Crossref, Google Scholar
• Wei Q, Pedarsani R, Coogan S (2020) Mixed autonomy in ride-sharing networks. IEEE Transportation Control Network Systems 7(4):1940–1950.Crossref, Google Scholar
• Xie J, Liu Y, Chen N (2023) Two-sided deep reinforcement learning for dynamic mobility-on-demand management with mixed autonomy. Transportation Sci., ePub ahead of print January 17, https://doi.org/10.1287/trsc.2022.1188.Link, Google Scholar
• Yang H, Qin X, Ke J, Ye J (2020) Optimizing matching time interval and matching radius in on-demand ride-sourcing markets. Transportation Res. Part B: Methodological 131:84–105.Crossref, Google Scholar
• Yu X, Shen S (2019) An integrated decomposition and approximate dynamic programming approach for on-demand ride pooling. IEEE Trans. Intelligent Transportation Systems 21(9):3811–3820.Crossref, Google Scholar