The New Approaches for Solving Hierarchical Chinese Postman Problem with Stochastic Travel Times

Abstract

The hierarchical Chinese postman problem (HCPP) aims to find the shortest tour or tours by passing through the arcs classified according to precedence relationship. HCPP, which has a wide application area in real-life problems such as shovel snow and routing patrol vehicles where precedence relations are important, belongs to the NP-hard problem class. In real-life problems, travel time between the two locations in city traffic varies due to reasons such as traffic jam, weather conditions, etc. Therefore, travel times are uncertain. In this study, HCPP was handled with the chance-constrained stochastic programming approach, and a new type of problem, the hierarchical Chinese postman problem with stochastic travel times, was introduced. Due to the NP-hard nature of the problem, the developed mathematical model with stochastic parameter values cannot find proper solutions in large-size problems within the appropriate time interval. Therefore, two new solution approaches, a heuristic method based on the Greedy Search algorithm and a meta-heuristic method based on ant colony optimization were proposed in this study. These new algorithms were tested on modified benchmark instances and randomly generated problem instances with 817 edges. The performance of algorithms was compared in terms of solution quality and computational time.