Hierarchical Chinese postman problem with fuzzy travel times

The hierarchical Chinese postman problem (HCPP), one of the kinds of Chinese postman problem (CPP), aims to visit at least once the arcs are classified according to their precedence relations and to find the shortest tour or tours. In HCPP, if the travel time values between two nodes constituting the cost are not crisp, this problem type can be said to be the hierarchical Chinese postman problem with fuzzy travel times (HCPP-FTT). In real-life problems, as the travel time between the nodes is not fixed due to various factors, in this study triangular fuzzy numbers are used at objective function coefficients of a small-size sample problem. Different ranking methods are used to defuzzify the fuzzy numbers and the acquired results are compared. The mathematical model formed is resolved using CPLEX solver GAMS ۲۴.۲.۳ software. Besides, in this study, a large-size real-life problem was discussed. The objective function coefficients representing the travel time between the two nodes in the case study discussed were considered as trapezoidal fuzzy numbers. Due to the NP-hard nature of the problem, the mathematical model cannot find solutions in large size problems in the appropriate time interval. For this reason, in this study, the heuristic method based on the Greedy Search (GS) algorithm and the meta-heuristic method based on ant colony optimization (ACO) is proposed for the solution of the real-life problem. The proposed algorithms are coded using the Matlab-۲۰۱۹b programming language. Using the developed algorithms, the results of different ranking methods and solution times were compared.

کلیدواژه ها:

Hierarchical Chinese postman problem ، arc routing problem ، Fuzzy number ، Fuzzy ranking methods