An Efficient Heuristic Tackling the Service Location Cloud Problem SLCP Exemplified at the Generalized Traveling Salesman Path Problem GTSPP

This paper gives an in-depth analysis of a heuristic tackling the Service Location Cloud Problem SLCP, whose efficient implementation is a necessary prerequisite to solve the Generalized Traveling Salesman Path Problem GTSPP so far based on the recommended well-tried decomposition like Figure 1. For a given weighted directed graph, a partial assignment of clusters to graph nodes, a start s and a target t, the GTSPP reads as follows: Find a shortest s-t-walk that visits each cluster at least once! And for the Asymmetric Steiner Traveling Salesman Path Problem ASTSPP that doesn`t need a cluster assignment but a given cloud Ω: Find a shortest s-t-walk that visits each member of Ω at least once! That means, if there is a SLCP heuristic tackling the objective “Find a cloud of nodes each assigned to a different cluster that enables a shortest s-t-walk through all clusters” then we can heuristically solve the GTSPP: Find a good SLCP cloud and pass it to an ASTSPP heuristic! Fortunately, there is already an efficient ASTSPP heuristic we can rely on to test the performance of the SLCP algorithm ASLCP given below in the interest of good GTSPP solutions. However, the SCLP`s objective to find (a) a cloud Ω of different cluster nodes (b) that enables a shortest s-t-walk corresponds in (b)with the ASTSPP that has to find a shortest s-t-walk through a given cloud Ω. I.e. from the NP-hardness of the ASTSPP follows the NP-hardness of the SLCP. That means that we have to replace the sophisticated SLCP objective by a simplified one that hopefully brings about satisfiable results. This alternative objective reads as follows: Find a least cost “pivot” node x that minimizes the total length s →x → t plus the sum of the minimum lengths s →x → y → t or s →y → x → t considering all nodes y each belonging to a different cluster! This pivot node x refers to a cloud of cluster nodes nearest situated to s, t, and x, that surprisingly well approaches the SLCP objective. Assured by extensive tests on random graphs, the performance analysis reveals a remarkable sample standard deviation SSD= 1,19% ascribed to SLCP-algorithm ASLCP. Accepting higher time consumption, a newly found second optimization feature improves the results further to an astonishing SSD= 0,22%!