禁忌搜索算法提升农村有奖邮递员问题求解效率

农村有奖邮递员问题（Rural Prize-Collecting Postman Problem, RPP）是一种扩展自经典的中国邮递员问题（Chinese Postman Problem, CPP）和弧路由问题（Arc Routing Problem, ARP）的离散优化问题。RPP旨在寻找在给定无向图中，从一个特定的“存款”节点d出发并返回该节点的路径，使得总收益最大化，同时满足一定的约束条件。在这个问题中，每次沿着图的边进行服务都会产生成本，但只有第一次经过某个边时才会获得利润奖励。 本文提出了一种基于禁忌搜索（Tabu Search）的启发式算法来解决RPP。禁忌搜索是一种超启发式算法，它结合了多种搜索策略以提高求解复杂问题的能力。与之前的研究相比，新算法在处理不同类型实例时展现出良好的性能。它考虑了利润函数只在首次遍历边时起作用的特点，并且在寻找最大利润周期的过程中，需要考虑到边的重复遍历会导致成本累积。 禁忌搜索的核心在于维护一个“禁忌表”，以避免近期访问过的状态，从而防止陷入局部最优解，促进搜索跳出当前解决方案的局限。在解决RPP时，这个特性对于处理复杂的奖励结构至关重要，因为奖励的获得依赖于路径的唯一性。 本文的研究工作对农村有奖邮递员问题的求解策略有所贡献，特别是在使用禁忌搜索这一高效搜索方法方面。研究结果发表在《理论计算机科学电子笔记》（Electronic Notes in Theoretical Computer Science）上，读者可以通过Elsevier网站获取原文（www.elsevier.com/locate/entcs），并且该论文遵循了CCBY-NC-ND许可协议，允许开放访问。作者Guillermo Palma来自委内瑞拉加拉加斯的Simon Bolivar大学计算机和技术信息学院，他的邮箱地址为gpalma@ldc.usb.ve。