Graph Theoretical Approach for Path Selection in Logistic Problems

In this study, we propose a solution for determining operationally acceptable paths by partitioning a graph structure into cliques. In the proposed approach, the graph representing the road network is partitioned into cliques, with boundary vertices connected by k-partite graphs. A path is considered acceptable if its length lies within a certain neighborhood of the minimal distance between the source node and the end node. The clique and k-partite decomposition increase the efficiency of determining acceptable paths. Formulas and numerical examples show that the number of possible paths between any two vertices in a complete graph is higher than the number of possible paths computed by partitioning the graph into cliques with boundary vertices connected by k-partite graphs. The method was applied to the graph structure that includes certain cities in Turkey, where cliques are based on operational preferences. As a result, it was seen as an effective approach that could be suitable for the realworld road network structure.