《Frontiers in Public Health》:Online bipartite matching methodology for anti-epidemic resources allocation: an adaptive time window based on reinforcement learning
编辑推荐:
背景:本研究旨在调查重大疫情期间医疗健康物联网系统(Internet of Healthcare System, HIS)中多个供应商与接收者之间的抗疫资源在线匹配问题,并考虑了供需异质性。方法:开发了一种基于时间窗口的多阶段在线动态二分匹配模型,该模型可重构
背景:本研究旨在调查重大疫情期间医疗健康物联网系统(Internet of Healthcare System, HIS)中多个供应商与接收者之间的抗疫资源在线匹配问题,并考虑了供需异质性。方法:开发了一种基于时间窗口的多阶段在线动态二分匹配模型,该模型可重构为马尔可夫决策过程(Markov decision process, MDP)。提出了一种基于强化学习(reinforcement learning, RL)的自适应时间窗口批处理二分匹配算法,该算法利用最近邻优先(nearest neighbor first, NNF)启发式策略来分配抗疫资源。结果:固定时间窗口批处理匹配策略(FTWBM)中的最优窗口大小优于自适应时间窗口批处理匹配策略(ATWBM)的结果。然而,ATWBM策略在适应疫情防控动态变化方面表现出更高的有效性,尤其是在部分乐观情景下。结论:结果表明,尽管平均匹配率持续增加,但平均等待时间随着匹配时间窗口的扩大先下降后上升。这一发现意味着医疗运营管理者应根据疫情动态和资源可用性调整匹配时间窗口。
重大疫情对公共卫生系统构成严峻挑战,中国正积极推动医疗健康物联网系统(HIS)建设,通过共享平台实现抗疫资源的高效分配。然而,疫情期间供需异质性、信息不对称以及实时动态变化,使得资源匹配面临困境。现有研究多采用离线优化方法,难以在个体层面实现快速响应。为此,研究人员针对HIS环境下多供应商与接收者之间的在线匹配问题,提出了一种基于强化学习(RL)的自适应时间窗口批处理匹配方法。该研究发表于《Frontiers in Public Health》。
研究人员构建了多阶段在线动态二分匹配模型(MSODBM),将其转化为马尔可夫决策过程(MDP),并设计了基于强化学习的自适应时间窗口批处理二分匹配算法(ATWBM),采用最近邻优先(NNF)启发式策略。通过合成数据集(3000组接收者请求和1800组供应商资源)进行实验,比较固定时间窗口批处理策略(FTWBM)与ATWBM的性能。
关键技术方法主要包括:1) MSODBM——考虑供需异质性和优先级约束,将问题建模为时空动态决策;2) MDP建模——将批处理匹配过程形式化为状态-动作-奖励序列;3) 基于ε-贪婪算法的自适应时间窗口选择——平衡探索与利用,以最小化平均等待时间为学习奖励;4) 基于服务等级的多阶段二分图匹配算法(G-HMBMC)——按接收者防疫等级(dr)和供应商供给等级(sr)分层优先匹配;5) 容量受限的匈牙利算法扩展——通过引入容量属性和增强路径搜索,解决多对多匹配问题;6) NNF策略——以曼哈顿距离最小化为目标,优先匹配距离最近的供需对。
研究结果分为两部分:
**Impact of fixed batch size on the matching time window**:固定批次大小实验显示,批次大小(bs)从1增至8时,平均匹配率从约0.5升至0.89,而平均等待时间先降后升,bs=4时达到最优平衡(平均匹配率77.0%,95%置信区间[0.706, 0.834];平均等待时间11.64分钟,95%置信区间[10.501, 12.777])。结果表明即时匹配(bs=1)效果劣于延迟批处理匹配,且存在一个最优窗口大小。
**Impact of adaptive batch sizes on the matching time window**:自适应批次大小实验通过控制初始探索概率(ε
0)、策略改进间隔(K
θ)和衰减系数(λ)进行分析。结果显示,在部分乐观情景(K
θ=2)下匹配结果通常优于完全乐观情景(K
θ=0)。小衰减系数(λ=0.2)维持较大探索空间,能发现更优匹配策略;完全乐观策略配合小衰减系数同样取得良好结果。强调了保持适当探索的重要性。
此外,比较了ε-贪婪、上置信界(UCB)和汤普森采样(TS)三种强化学习算法。UCB在平均匹配率上表现最优(均值0.845,95%置信区间[0.780, 0.910]),且稳定性高;ε-贪婪在平均等待时间上最短(均值11.25分钟)但变异性大;TS介于两者之间。统计检验表明UCB的匹配率显著优于其他两种算法。
讨论部分总结了FTWBM与ATWBM的对比:FTWBM中固定最优窗口(如bs=4)的匹配结果优于ATWBM,但ATWBM在适应疫情动态变化方面更具优势,尤其通过优化控制参数可不断提升匹配性能。在动态环境下,ATWBM比FTWBM更有价值。不同强化学习算法中,UCB在匹配率上领先,而ε-贪婪在等待时间上更短,管理者可根据目标选择。
研究结论部分翻译如下:本研究的主要贡献和管理启示如下。第一,在抗疫资源在线匹配中,延迟批处理匹配通常优于即时匹配。随着匹配时间窗口扩大,平均等待时间先下降后上升,而平均匹配率持续增加至一定程度。因此,医疗运营管理者应寻求平均等待时间与平均匹配率之间的平衡,优先选择低等待时间与高匹配率的窗口。第二,在疫情发展和供需动态变化不可预测的背景下,不存在普遍最优或静态的匹配时间窗口。管理者应根据疫情进展和资源可用性定期调整匹配时间窗口。当疫情快速蔓延导致需求激增和供应短缺时,较大窗口可提高匹配率但可能增加等待时间;较小窗口也可有效利用。第三,自适应时间窗口策略实验表明,较高的探索概率显著提升资源匹配效率。疫情期间供需不确定,保持对匹配时间窗口的高度探索对于有效资源配置至关重要。此外,实际应用中医疗运营管理者还需结合导航地图确定准确的行程时间。尽管本研究模型有效解决了抗疫资源在线匹配问题,但仍存在局限:仅关注时间因素对资源分配的影响,而资源供应能力、跨区域短缺分布、人口集中度与空间分布等因素也需研究;同时,资源分配中的效率与公平平衡问题同样值得关注。