Abstract: A generalization of the Chinese Postman Problem is studied in which the delays at a subset of priority nodes are penalized in the cost function. As it is shown that the problem is NP-hard, two tour constructing heuristics are proposed, and their properties are studied. It is proved that one of the heuristics gives optimal solutions on a subset of instances with bounded cost of delays. The implementations of the heuristics are compared on several types of randomly generated instances.Keywords: Chinese postman problem, ARP, heuristics, Eulerian graphPublished in DKUM: 05.06.2012; Views: 13757; Downloads: 45 Link to full text
