View article

The Hierarchical Windy Postman Problem (HWPP) is an arc routing problem in which an order relation is imposed on the arcs/edges of the graph, and one has to pass through each edge at least once while adhering to the hierarchical priority relations. The tour starts from and ends at a specific node and the aim is to minimize the length of the tour. We consider a variant of the HWPP in which (i) the precedence order of the edge hierarchies is linear and edges within each hierarchy are connected and (ii) the cost of serving each edge decreases with the number of times it is traversed, and we refer to it as HWPP with variable service costs. An integer non-heuristic linear mathematical formulation is proposed, and a solution approach is designed. Our solution heuristic adapts the layer algorithm of Dror et al. (Networks 17:283–294, 1987) but employs an integer mathematical formulation as a sub-procedure instead of the …