A branch-and-cut algorithm for the maximum benefit Chinese postman problem
A branch-and-cut algorithm for the maximum benefit Chinese postman problem
复制标题
求解最大收益中国邮递员问题的分支割法
DOI：
10.1007/s10107-011-0507-6
复制
发表时间：
2011
影响因子：
2.7
通讯作者：
J. Sanchis
中科院分区：
文献类型：
--
作者：
Á. Corberán;Isaac Plana;A. M. Rodríguez‐Chía;J. Sanchis
最大效益中国邮差问题（MBCPP）是一个np困难问题，它考虑了与每个边缘相关的几个效益，每次通过服务穿越边缘时都有一个效益。我们的目标是找到一个封闭的步行方式，以获得最大的收益。我们提出了一种无向MBCPP的IP公式，并基于其相关多面体的描述，提出了一种分支切割算法，并给出了在多达1000个顶点和3000条边的实例上的计算结果。
The Maximum Benefit Chinese Postman Problem (MBCPP) is an NP-hard problem that considers several benefits associated with each edge, one for each time the edge is traversed with a service. The objective is to find a closed walk with maximum benefit. We propose an IP formulation for the undirected MBCPP and, based on the description of its associated polyhedron, we propose a branch-and-cut algorithm and present computational results on instances with up to 1,000 vertices and 3,000 edges.