Chinese and windy postman problem with variable service costs

摘要

Given a network G=(V,E) of nodes denoted by V, edges between nodes represented by E, and costs associated with the edges, postman problem (PP) is to find the route having the minimum cost that begins and ends with a predefined starting point and spans each edge of the network. PP is a variant of the well-known arc routing problem. In many real-life applications of the PP, costs associated with the edges tend to reduce with each pass on the edges. We propose a new mathematical formulation to represent the postman problem with variable service costs. If the service costs are symmetric, the problem is named as the Chinese postman problem (CPP) with variable service costs (CPPVSC), and it is called as the windy postman problem with variable service costs (WPPVSC), otherwise. CPPVSC turns to be a variant of CPP, and it is an easy problem. We show that no edge can be traversed more than twice in the optimal solution. Moreover, we propose two heuristics for the solution of WPPVSC. Based on the extensive numerical experiments, we can say that both heuristics outperform the state-of-the-art commercial solvers.