# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 1 Introduction  
Shortest-path algorithms are widely applied in many areas, such as transportation, telecommunication, optimization, and computer science [1, 2, 3]. Numerous efficient algorithms have been developed to address this problem and its variants, such as the \(k\) shortest path (KSP) problem [4], the \(k\) simple shortest path (KSSP) problem [5], and the time-dependent shortest path problem [6]. To provide the necessary context, we briefly introduce the concepts of KSP and KSSP. Informally, KSP refers to the top \(k\) shortest paths between two points in a network. If we impose the additional constraint that these paths must not contain any repeated nodes, we are dealing with KSSP. Rigorous definitions are provided in Section 3. While the multiple origin and destination versions of the shortest path problem have received specialized attention, the KSSP problem remains under-researched for the multiple destinations case. This problem class encompasses different variants that arise in several practical applications described below. However, current algorithmic approaches predominantly revolve around the use of naive and repetitive application of the single destination algorithm, thereby ignoring the distinct characteristics of the class as well as opportunities for computational efficiency. Therefore, this paper focuses on the multi-destination KSSP problem by developing specialized solution procedures based on the label-setting framework. There are applications where finding KSSP to multiple destinations is necessary. One such example is the multi-path routing of vehicles to multiple destinations at the end of mass gathering events, such as sporting events and concerts. Another practical problem relates to routing last-mile connectivity fleets from a transit station to multiple passenger destinations [7]. Other applications where such a solution may be useful include routing autonomous vehicles under dynamic traffic scenarios to multiple activity locations [8], navigation to multiple destinations in complex indoor environments [9], and evacuating people through multiple paths from a building under hazard to multiple safe shelters. The last decade has witnessed an increasing number of efficient algorithms and heuristics for the KSSP problem to improve upon the popular [PERSON]'s algorithm [10; 11; 12; 13]. These algorithms, however, have been designed and implemented for the single destination case, whereas KSSP algorithms from a single origin to multiple destinations remain relatively scarce in the literature. The KSSP problem from a single source to all destinations (one-to-all) requires finding the top \(k\) simple shortest paths to each node in the network. The multi-destination KSSP encompasses a class of problems with several variants. Two variants are presented in this paper, listed below. Besides the one-to-all KSSP, these variants include finding (i) the top \(k\) simple shortest paths to each node from a subset of destinations if they exist and (ii) all the simple shortest paths from the origin to any destination within a time or cost budget. The KSSP, even for the single destination case, is more complex than the KSP due to the constraint of cycle-free paths, though it provides realistic paths. While existing single-destination KSSP algorithms can be extended in a straightforward manner to accommodate multiple destinations, this approach is computationally inefficient due to redundant shortest-path computations to the same intermediate node for different destinations in the existing deviation-based approaches. Therefore, motivated by the above shortcomings in the literature, the aim of this paper is to propose a novel label-setting algorithm as an efficient solution for the multiple destinations case, diverging from the prevalent deviation-based, path replacement, or label-correcting approaches available in the literature.