Intuitionistic Fuzzy Orienteering Problem and Its Work-Depth Analysis

Abstract

Orienteering is an NP-hard problem that originated from a water sport where a player is required to visit a set of control points connecting the source and the destination, collect the maximum possible rewards or scores associated with the control points and arrive at the destination within the time bound. It finds its application in the tourism industry, telecommunication networks and other computational problems where things like human behaviour and hesitancy of the decision maker must be considered. To tackle the uncertainty involved in the parameters we represent them using trapezoidal intuitionistic fuzzy numbers (TIFN) resulting in intuitionistic fuzzy orienteering problem (IFOP). A technique based on max-min formulation is presented to deal with IFOP using a new method for ranking TIFNs. Also, a work-depth analysis for the parallel version of IFOP is presented to show that IFOP is work-preserving and can be implemented on a multiprocessor model like PRAM to obtain the solution for large instances efficiently.