A time-dependent hierarchical Chinese postman problem

The hierarchical Chinese postman problem (HCPP), a variant of the Chinese postman problem, is an arc routing problem. HCPP is NP-hard and several methods have been developed to solve this problem. Many studies in the literature have taken the minimum distance covered between nodes into consideration. All of these studies ignore time-dependent travel speeds between two locations. Travel speeds (and time) in almost all metropolitan areas change drastically during the day due to a variety of different factors, such as weather condition, peak traffic hours and accidents, along with the distance. Spending minimum time to travel streets is of great importance to ensure traffic flow and road safety, particularly in many practical implementation areas of HCPP, such as snow plowing winter, garbage collection and routing security patrol vehicles. This study introduces a new problem called the time-dependent hierarchical Chinese postman problem that aims to minimize the total travel time, while obeying precedence relationships between edges. This problem differs from most arc routing problems because the duration of traversing a street changes depending on the time of day. The problem was formulated as a mixed integer linear programme. Two metaheuristics were built: a genetic algorithm (GA) and a hybrid simulated annealing (hSA). The proposed model and metaheuristics were tested on modified benchmark instances and randomly generated problem instances with as many as 490 edges. The performance of GA and hSA were compared in terms of solution quality and computational time.