An Approximate Dynamic Programming Approach to Dynamic Stochastic Matching
针对网约车、在线游戏、肾脏交换等场景中的动态随机匹配问题，提出基于线性规划的近似动态规划方法，通过新的近似线性规划重构高效求解并给出紧的界，证明策略接近最优。
Dynamic stochastic matching problems arise in a variety of recent applications, ranging from ridesharing and online video games to kidney exchange. Such problems are naturally formulated as Markov decision processes (MDPs) that are, however, intractable in general. To improve tractability, we investigate the linear programming-based approach to approximate dynamic programming. This approach can provide both feasible control policies and bounds on the MDPs’ optimal policy value, which can be used to establish optimality gaps. However, the approximate linear programs (ALPs) resulting from this approach can often be difficult to solve. To address this computational challenge, we derive novel ALP reformulations that can be used for a broad class of dynamic stochastic matching problems that incorporate, among others, possible match failures and certain restrictions on feasible matchings. We show that these ALP reformulations can be solved efficiently and applied to a broad class of dynamic matching problems. In addition, our numerical results indicate that our ALP reformulations can produce tight bounds that allow us to establish near-optimal policy performance for a broad set of problem instances. Thus, ALP reformulations can present an attractive alternative for applications that involve dynamic stochastic matching. History: Accepted by Nicola Secomandi, Area Editor for Stochastic Models & Reinforcement Learning. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0203 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0203 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .