运筹优化系列4:旅行商问题的深度强化学习算法

科技   2025-01-11 20:02   德国  

旅行商问题(Traveling Salesman Problem,TSP),又称为旅行推销员问题、货郎担问题,是一个著名的组合优化问题。

 旅行商问题虽然是一个抽象的数学问题,但在实际生活中有很多应用,例如:
  • 物流配送:快递员、货车司机等要在多个配送点之间进行配送,需要规划出最短的配送路线,以提高配送效率和降低成本。
  • 电路设计:在印制电路板(PCB)设计中,要将多个电子元件的引脚连接起来,相当于要在这些引脚所对应的 “城市” 之间规划出最短的连接路线,以减少线路长度和信号延迟。
  • 旅游规划:游客要在多个旅游景点之间游玩,希望规划出一条既能参观所有景点又能使总行程最短的路线。
  • 机器人路径规划:机器人要在多个目标点之间移动,需要规划出最短的移动路线,以提高工作效率和减少能源消耗。

01 常见的旅行商问题

  • 经典旅行商问题(Classic Traveling Salesman Problem,TSP):给定一组城市以及每对城市之间的距离,要求找到一条经过所有城市且每个城市仅经过一次的最短巡回路线。例如,有 A、B、C、D 等多个城市,要确定一个从某个起始城市出发,依次遍历所有城市后再回到起始城市的最短路径。

  • 带时间窗的旅行商问题(Traveling Salesman Problem with Time Windows,TSPTW):在经典 TSP 的基础上,为每个城市添加了时间窗限制。也就是说,每个城市都有一个允许服务开始的最早时间和必须完成服务的最晚时间,旅行商必须在相应城市的时间窗内到达该城市进行服务等操作,然后再继续前往其他城市,同样要找到满足这些条件的最短巡回路线。比如,城市 A 可能规定只能在上午 9 点到下午 5 点之间接受服务,旅行商就需要安排行程使其到达城市 A 的时间在此时间窗内。

  • 多目标旅行商问题(Multi-Objective Traveling Salesman Problem,MOTSP在经典 TSP 的基础上,考虑了多个目标的优化需求。也就是说,与经典 TSP 不同的是,这里不是仅仅关注一个目标(如总旅行距离最短),而是要同时考虑多个不同的目标。例如,除了总旅行距离外,还可能要考虑旅行时间最短、旅行成本最低、经过某些特定城市的先后顺序等多个目标。比如,一个旅行商要在多个城市之间进行巡回销售,既要使总行程距离最短以节省交通费用,又要使在每个城市的停留时间总和最短以提高工作效率,同时可能还需要按照特定的客户优先级顺序依次经过某些重点客户所在的城市。


    02 传统旅行商问题的求解方法

传统旅行商问题的求解方法主要分为精确算法和启发式算法两类。
最好的精确解算器Concorde(Applegate et al . 2009)需要136个CPU年才能为85,900个城市的实例找到最优解。这样的计算时间是不可接受的。因此人们提出了许多启发式方法来获得实践中出现的问题的近最优解。例如,领先的启发式算法之一LKH3 (Helsgaun 2017)可以处理数百万个城市的TSP实例。然而,这些算法由特定于TSP的手工规则组成。更重要的是,启发式算法依赖于迭代搜索,并且对于大规模的搜索也很耗时。这限制了它们在时间敏感场景中的应用,例如随叫随到路由(giani等人2003年)和叫车服务(Xu等人2018年)。
为了处理这种对时间敏感的应用,期望使用基于学习的TSP方法,因为它们在推理过程中非常有效。他们可以在训练过程中从大量数据中学习有用的模式,这些模式可以推广到更多的实例。此外,它们不依赖于特定问题的知识,因此可以扩展到处理类似的问题。

03 基于深度强化学习的算法

随着机器学习(ML)和强化学习(RL)的发展,最近越来越多的工作集中在使用ML或RL方法解决组合优化问题。seq2seq模型,即指针网络,在逼近若干组合优化问题(如寻找凸包和TSP)的解方面具有很大的潜力。它使用LSTMs作为编码器,使用注意力机制作为解码器从城市中提取特征坐标。然后,它预测一个描述下一步可能移动的策略,以便对访问城市的排列进行抽样。已经提出了一个指针网络的RL框架,其中指针网络模型通过Actor-Critic算法进行训练,并使用负行程长度作为奖励。RL方法被证明比以前的监督学习方法更有效,并且在多达100个节点的TSP上优于大多数以前的启发式方法。
以往的工作对有约束的问题和多目标问题,如带时间窗的旅行商问题和多目标旅行商问题,没有得到充分的考虑。为了处理约束问题,Bello等提出了一种惩罚方法,在奖励函数上增加了对不可行解的惩罚项。然而,惩罚方法可能导致训练不稳定,并且惩罚项的超参数通常难以调整。一个更好的训练选择是使用分层强化学习方法,它已被广泛应用于解决复杂问题,如具有稀疏奖励的视频游戏和机器人迷宫任务。分层强化学习的主要动机是将复杂的任务分解成几个简单的子问题,这些子问题在层次结构中学习。Haarnoja等为分层强化学习引入了潜在空间策略,其中层次的下层提供了可行的解空间,并约束了上层的行为。然后,较高层根据来自较低层潜在空间的信息做出决策。
对于大规模和带时间窗约束的旅行商问题,Ma等[1]探索了使用分层强化学习方法来解决。他们的目标是近似解决更大规模的TSP问题和解决带约束的TSP问题。贡献有三个方面:首先,提出了一个图形指针网络(GPN)来解决TSP。GPN通过图嵌入层对指针网络进行扩展,收敛速度更快。其次,将向量上下文添加到GPN架构中,并使用早期停止进行训练,以便将模型推广到处理更大规模的TSP实例,例如TSP1000,该模型是在更小的TSP50实例上训练的。第三,采用分层RL框架和GPN架构来有效地求解具有时间窗约束的TSP。
对于超大规模旅行商问题,Pan等[2]提出了一个基于分层强化学习的端到端学习框架,称为H-TSP。提出的H-TSP从头开始构建TSP实例的解决方案,依赖于两个组件:上层策略从要遍历的所有节点中选择节点的一小部分(在实验中最多200个),而下层策略将所选节点作为输入并输出将它们连接到现有部分路由(最初仅包含车厂)的巡回。在联合训练上层和下层策略后,我们的方法可以直接为给定的TSP实例生成解决方案,而不依赖于任何耗时的搜索过程。为了证明所提出方法的有效性,我们对具有不同节点数量的随机生成的TSP实例进行了广泛的实验。他们发现H-TSP可以达到与基于SOTA搜索的方法相当的结果(差距为3.42% vs. 7.32%),更重要的是,我们将时间消耗减少了两个数量级(3.32s vs. 395.85s)。H-TSP是第一个端到端深度强化学习方法,可以扩展到多达10,000个节点的TSP实例。尽管在解决方案质量方面与SOTA的结果仍有差距,但相信H-TSP将对实际应用有用,特别是那些对时间敏感的应用,例如在线呼叫路由和乘车服务。
对于多目标旅行商问题,国内学者黄俊杰[3]提出了基于NBI分解的多目标深度强化学习算法MODRL-NBI。算法采用NBI风格的分解方法将多目标旅行商问题分解为多个单目标旅行商问题,每个子问题都使用一个指针网络进行求解。对于每个 指针网络,设计基于NBI-TCH的损失函数对其进行梯度下降训练,并把训练好的 指针网络通过迁移学习传递给下一个子问题,直至所有的指针网络训练完成。
参考文献:
[1]Ma Q , Ge S , He D ,et al.Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning[J]. arXiv, 2019.DOI:10.48550/arXiv.1911.04936.
[2]Pan X ,et al. H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem. ArXiv preprint, abs/2304.09395.
[3]黄俊杰.基于深度强化学习和进化算法的多目标优化算法设计[D].华南理工大学,2021.DOI:10.27151/d.cnki.ghnlu.2021.003710.

运筹OR帷幄
致力于成为全球最大的运筹学中文线上社区
 最新文章