抢修队的修复工作需要满足两个目标，第一个目标是，在尽可能小的时间开销上使道路网通畅；第二个目标是，对道路网修复后，在保证路网通畅下，使运输效率尽可能高。

我们建立了路网抢修队的修复决策模型，并提出了求解模型的算法，最终生成了合理高效的修复方案。

目前的研究存在一些不足：主要体现在两个方面：首先，已有的工作着眼于路网本身，构建的路网大都过于理想化，仅考虑修复路网中的哪些路段可以实现目标的最优化，而没有考虑这些受损路段是否可达和修复工程队在危险环境中的路线问题，也没有考虑受损路段的修复顺序对应急救援的影响。其次，虽然考虑了抢修队的可达路线，并能够给出道路抢修队的修复策略集，但无法处理像地震、洪水等特大自然灾害所引起的连续路段受损情形。

这篇论文通过强化学习从另一个角度研究了这个问题。首先把这个问题建模为马尔可夫决策过程，然后再利用Q学习方法求解。主要基于这几个考虑：部分可观测状态、延迟回报、探索和利用。

这篇论文主要对比了动态规划方法和Q学习方法用于求解规划方案。在路段受损率较小时, 随着路网规模的增加, Q-learning算法和DP算法均可以使所有应急点可达, 且最终修复的路段数也一样. 在路网修复初期, DP算法可以使更多的应急点可达. 但随着修复过程的推进, Q-learning算法很快就赶上并且超过了DP算法, 这是因为在Q-learning算法中,抢修队牺牲了一部分的短期回报来获取更好的长期回报.

在路段受损率较大时, 随着路网规模的增加, Q-learning算法要明显比DP算法更优. Q-learning算法在路网修复整个阶段都能使更多的应急点可达, 并直至使所有应急点都可达, 且最终修复的路段数也多于DP算法. 因此，在灾情较严重时, 与DP算法相比, Q-learning算法所给的抢修队规划方案能够更快的使更多的应急点可达. 也就是说, Q-learning算法能够更快的使路网交通系统恢复程度最大, 更有利于应急救援的实施和灾民的快速安全疏散.在路网规模和路段受损率都较大时, 无论应急点最大可接受距离变大还是变小,仍然只有Q-learning能够使所有应急点可达, 且修复了更多的路段. 而DP算法随着最大可接受距离的变小, 应急点可达率越来越小.

因此, 当距离约束要求发生变化时, Q-learning更加鲁棒, 能够统筹考虑受损路网的全局, 会随着距离约束要求的变化从全局和长期收益的角度让抢修队重新适应这些约束的变化. 与之明显不同的是, 当距离约束要求变化时, DP算法不能做出相应的调整, 尤其在约束苛刻时, DP算法可能会找不到任何有效规划.

引用格式：苏兆品, 李沫晗, 张国富, 刘扬. 基于Q学习的受灾路网抢修队调度问题建模与求解. 自动化学报, 2020, 46(7): 1467-1478

文章链接：http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180081