Efficiently finding earliest and latest paths via binary weighting in multi-objective network routing

This paper studies two path-selection procedures, called the earliest path and the latest path algorithms, which are based on assigning binary weights to the arcs of a network. For this purpose, the i-th arc is given a weight equal to either 2^(i-1) or 2^(m-i). With this choice, paths that preserve connectivity between a source and a destination can be retrieved directly according to their lexicographical order, yielding minimal or maximal representations. Instead of a mere focus on physical distance, the approach follows the ordering generated by the binary addition tree, which makes it possible to reflect several competing criteria within a single binary structure. This way, we divide the space of paths implicitly into three parts. (1) the path vectors under which the network is certainly disconnected, (2) the ones under which connectivity may occur, and (3) the path vectors for which no simple path is possible. Although the resulting approaches keep the same O((|V|+|E|)log|V|) time complexity as Dijkstra's algorithm, our representation is richer than that of standard shortest-path formulations. Numerical results show that the proposed strategy significantly reduces computation time when compared with classical multi-objective routing methods. The proposed method can also be used in various real-world networks, e.g., communications, transportation, and logistics networks, in which finding the system reliability as well as identifying a quick relevant path are both significantly important.