Hierarchical Chinese postman problem with fuzzy travel times

Document Type : Research Paper

Authors

1 Continuing Education Application and Research Center, Erzurum Technical University, Erzurum, Turkey

2 Department of Industrial Engineering, Faculty of Engineering, Ataturk University, Erzurum, Turkey

Abstract

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 24.2.3 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-2019b programming language. Using the developed algorithms, the results of different ranking methods and solution times were compared.

Keywords

Iranian Journal of Fuzzy Systems
Volume 18, Issue 5
September and October 2021
Pages 87-105

Files

Share

How to cite

Statistics