Document Open Access Logo

Matching Drivers to Riders: A Two-Stage Robust Approach

Authors Omar El Housni, Vineet Goyal, Oussama Hanguir, Clifford Stein

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.12.pdf
  • Filesize: 0.77 MB
  • 22 pages

Document Identifiers

Author Details

Omar El Housni
  • School of Operations Research and Information Engineering, Cornell Tech, New York, NY, USA
Vineet Goyal
  • Industrial Engineering and Operations Research, Columbia University, New York, NY, USA
Oussama Hanguir
  • Industrial Engineering and Operations Research, Columbia University, New York, NY, USA
Clifford Stein
  • Industrial Engineering and Operations Research, Columbia University, New York, NY, USA

Funding

  • Stein, Clifford: Research partly supported by NSF Grants CCF-1714818 and CCF-1822809.

Cite AsGet BibTex

Omar El Housni, Vineet Goyal, Oussama Hanguir, and Clifford Stein. Matching Drivers to Riders: A Two-Stage Robust Approach. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.12

Abstract

Matching demand (riders) to supply (drivers) efficiently is a fundamental problem for ride-hailing platforms who need to match the riders (almost) as soon as the request arrives with only partial knowledge about future ride requests. A myopic approach that computes an optimal matching for current requests ignoring future uncertainty can be highly sub-optimal. In this paper, we consider a two-stage robust optimization framework for this matching problem where future demand uncertainty is modeled using a set of demand scenarios (specified explicitly or implicitly). The goal is to match the current request to drivers (in the first stage) so that the cost of first stage matching and the worst-case cost over all scenarios for the second stage matching is minimized. We show that this two-stage robust matching is NP-hard under both explicit and implicit models of uncertainty. We present constant approximation algorithms for both models of uncertainty under different settings and show they improve significantly over standard greedy approaches.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • matching
  • robust optimization
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1253-1264. SIAM, 2011. Google Scholar
  2. Nikhil Bansal, Niv Buchbinder, Anupam Gupta, and Joseph Seffi Naor. An o(logk²)-competitive algorithm for metric bipartite matching. In European Symposium on Algorithms, pages 522-533. Springer, 2007. Google Scholar
  3. Piotr Berman, Bhaskar DasGupta, and Eduardo Sontag. Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Discrete Applied Mathematics, 155(6-7):733-749, 2007. Google Scholar
  4. Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms, pages 253-264. Springer, 2007. Google Scholar
  5. Nikhil R Devanur and Thomas P Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce, pages 71-78, 2009. Google Scholar
  6. Nikhil R Devanur, Kamal Jain, and Robert D Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 101-107. SIAM, 2013. Google Scholar
  7. Kedar Dhamdhere, Vineet Goyal, R Ravi, and Mohit Singh. How to pay, come what may: Approximation algorithms for demand-robust covering problems. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 367-376. IEEE, 2005. Google Scholar
  8. Omar El Housni and Vineet Goyal. Beyond worst-case: A probabilistic analysis of affine policies in dynamic optimization. In Advances in neural information processing systems, pages 4756-4764, 2017. Google Scholar
  9. Bruno Escoffier, Laurent Gourvès, Jérôme Monnot, and Olivier Spanjaard. Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation. European Journal of Operational Research, 205(1):19-30, 2010. Google Scholar
  10. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. Google Scholar
  11. Uriel Feige, Kamal Jain, Mohammad Mahdian, and Vahab Mirrokni. Robust combinatorial optimization with exponential scenarios. In International Conference on Integer Programming and Combinatorial Optimization, pages 439-453. Springer, 2007. Google Scholar
  12. Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and Shan Muthukrishnan. Online stochastic matching: Beating 1-1/e. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 117-126. IEEE, 2009. Google Scholar
  13. Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1014-1033. SIAM, 2016. Google Scholar
  14. Yiding Feng and Rad Niazadeh. Batching and optimal multi-stage bipartite allocations. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  15. Yiding Feng, Rad Niazadeh, and Amin Saberi. Two-stage stochastic matching with application to ride hailing. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2862-2877. SIAM, 2021. Google Scholar
  16. Harold N Gabow and Robert E Tarjan. Algorithms for two bottleneck optimization problems. Journal of Algorithms, 9(3):411-417, 1988. Google Scholar
  17. Robert S Garfinkel and KC Gilbert. The bottleneck traveling salesman problem: Algorithms and probabilistic analysis. Journal of the ACM (JACM), 25(3):435-448, 1978. Google Scholar
  18. Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, volume 8, pages 982-991, 2008. Google Scholar
  19. Anupam Gupta, Viswanath Nagarajan, and Ramamoorthi Ravi. Thresholded covering algorithms for robust and max-min optimization. In International Colloquium on Automata, Languages, and Programming, pages 262-274. Springer, 2010. Google Scholar
  20. Bernhard Haeupler, Vahab S Mirrokni, and Morteza Zadimoghaddam. Online stochastic weighted matching: Improved approximation algorithms. In International workshop on internet and network economics, pages 170-181. Springer, 2011. Google Scholar
  21. Dorit S Hochbaum and David B Shmoys. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM (JACM), 33(3):533-550, 1986. Google Scholar
  22. Omar El Housni, Vineet Goyal, and David Shmoys. On the power of static assignment policies for robust facility location problems. arXiv preprint arXiv:2011.04925, 2020. Google Scholar
  23. Patrick Jaillet and Xin Lu. Online stochastic matching: New algorithms with better bounds. Mathematics of Operations Research, 39(3):624-646, 2014. Google Scholar
  24. Bala Kalyanasundaram and Kirk Pruhs. Online weighted matching. Journal of Algorithms, 14(3):478-488, 1993. Google Scholar
  25. Viggo Kann. Maximum bounded 3-dimensional matching is max snp-complete. Information Processing Letters, 37(1):27-35, 1991. Google Scholar
  26. Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 587-596, 2011. Google Scholar
  27. Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352-358, 1990. Google Scholar
  28. Irit Katriel, Claire Kenyon-Mathieu, and Eli Upfal. Commitment under uncertainty: Two-stage stochastic matching problems. Theoretical Computer Science, 408(2-3):213-223, 2008. Google Scholar
  29. Samir Khuller, Stephen G Mitchell, and Vijay V Vazirani. On-line algorithms for weighted bipartite matching and stable marriages. Theoretical Computer Science, 127(2):255-267, 1994. Google Scholar
  30. Nan Kong and Andrew J Schaefer. A factor 12 approximation algorithm for two-stage stochastic matching problems. European Journal of Operational Research, 172(3):740-746, 2006. Google Scholar
  31. Nitish Korula and Martin Pál. Algorithms for secretary problems on graphs and hypergraphs. In International Colloquium on Automata, Languages, and Programming, pages 508-520. Springer, 2009. Google Scholar
  32. Euiwoong Lee and Sahil Singla. Maximum matching in the online batch-arrival model. In International Conference on Integer Programming and Combinatorial Optimization, pages 355-367. Springer, 2017. Google Scholar
  33. Lyft. Matchmaking in lyft line - part 1. https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4, 2016.
  34. Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 597-606, 2011. Google Scholar
  35. Vahideh H Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research, 37(4):559-573, 2012. Google Scholar
  36. Jannik Matuschke, Ulrike Schmidt-Kraepelin, and José Verschae. Maintaining perfect matchings at low cost. arXiv preprint arXiv:1811.10580, 2018. Google Scholar
  37. Aranyak Mehta. Online matching and ad allocation. Theoretical Computer Science, 8(4):265-368, 2012. Google Scholar
  38. Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22-es, 2007. Google Scholar
  39. Aranyak Mehta, Bo Waggoner, and Morteza Zadimoghaddam. Online stochastic matching with unequal probabilities. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1388-1404. SIAM, 2014. Google Scholar
  40. Adam Meyerson, Akash Nanavati, and Laura Poplawski. Randomized online algorithms for minimum metric bipartite matching. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 954-959. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  41. Sharath Raghvendra. A robust and optimal online algorithm for minimum metric bipartite matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  42. Uber. Uber marketplace and matching. https://marketplace.uber.com/matching, 2020.
  43. Vijay V Vazirani. Approximation algorithms. Springer Science & Business Media, 2013. Google Scholar
  44. Lingyu Zhang, Tao Hu, Yue Min, Guobin Wu, Junying Zhang, Pengcheng Feng, Pinghua Gong, and Jieping Ye. A taxi order dispatch model based on combinatorial optimization. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 2151-2159, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact