Optimization of Chinese Postman Problem Using Fuzzy-Based Priority Weighted Graph

Abstract

: In the early 1960s, Chinese mathematician Mei-Ko Kwan (M. Guan) introduced a method aimed at minimizing mail carriers’ route lengths. This method led to the exploration of various formulations of the Chinese Postman Problem (CPP), resulting in at least eight distinct formulations. In response to a practical concern, a new problem formulation called the Priority Constrained Chinese Postman Problem (PCCPP) emerged. In PCCPP, a linear order is provided for a set of significant nodes, and the objective is to traverse all edges at least once while prioritizing the prompt visitation of higher-priority nodes. This paper presents a modified approach to Chinese Postman Problems (CPP) using priorities in a fuzzy environment ranking function applied to priority nodes in CPP to get the optimal result. Finally, this paper also illustrates and justifies the implementation of the modified approach with a numerical problem. The consideration of multi-factors in a multi-graph with priorities gives another scope of research. JEL Codes: C44 Received: 18/07/2024. Accepted: 29/09/2024. Published: 13/10/2024.

Keywords

• Priority
• Eulerian tour
• fleury algorithm
• Dijkstra’s algorithms
• Undirected Graph
• Triangular Fuzzy Number