Approximate solutions for the maximum benefit chinese postman problem
Approximate solutions for the maximum benefit chinese postman problem
复制标题
中国邮递员利益最大化问题的近似解
DOI：
10.1080/00207720500282292
复制
发表时间：
2005
影响因子：
4.3
通讯作者：
W. Chiu
中科院分区：
文献类型：
--
作者：
W. Pearn;W. Chiu
最大效益中国邮递员问题（MBCPP）是经典中国邮递员问题的一个有趣而实用的推广，有许多实际应用。MBCPP网络上的每个弧与有服务的遍历的服务成本、无服务的遍历的空驶成本以及一组益处相关联。每经过一条弧线，就会产生一个收益。MBCPP的目标是找到一个邮递员行程穿越一组选定的弧线，总净效益最大化。这样的概括更能反映现实世界的情况。MBCPP已被证明是更复杂的农村邮递员问题，这是一个NP难问题。因此，很难找到多项式时间有界算法来精确求解该问题。在本文中，我们首先回顾了现有的精确求解过程，并介绍了几种启发式算法，包括分支扫描算法，连接算法与各种连接策略，和有向树算法，以解决MBCPP近似。我们还应用了一个选择，两个选择，组件交换和组件下降的过程，以改善解决方案。所提出的算法进行了测试和比较。大量的计算结果提供和分析。
The Maximum Benefit Chinese Postman Problem (MBCPP) is an interesting and practical generalization of the classical Chinese Postman Problem, which has many real-world applications. Each arc on the MBCPP network is associated with a service cost for the traversal with service, a deadhead cost for the traversal with no service, and a set of benefits. Each time an arc is traversed, a benefit is generated. The objective of the MBCPP is to find a postman tour traversing a selected set of arcs with the total net benefit maximized. Such a generalization reflects real-world situations more closely. The MBCPP has been shown to be more complicated than the Rural Postman Problem, which is an NP-hard problem. Therefore, it is difficult to find polynomial-time bounded algorithms to solve the problem exactly. In this paper, we first review an existing exact solution procedure, and introduce several heuristic algorithms including the Branch-Scan algorithm, the Connection algorithm with various connection strategies, and the Directed Tree algorithm, to solve the MBCPP approximately. We also apply one-opt, two-opt, component exchange, and component-drop procedures to improve the solutions. The proposed algorithms are tested and compared. Extensive computational results are provided and analysed.