Label Correcting Algorithms for the Multiobjective Temporal Shortest Path Problem

The shortest path problem is one of the most fundamental and well-studied optimization problems in graphs and networks. In the most prominent case where the length of a path is given as the sum of the lengths of its arcs, the problem can be solved efficiently in polynomial time by label setting approaches if all arc lengths are assumed to be nonnegative or by label correcting approaches if negative lengths are allowed.

Many graphs and networks, however, are inherently dynamic in the sense that the available connections between nodes – or even the nodes themselves – change over time. Prominent examples include airline or railway networks, where each train or flight connection has a specific departure time [10, 16]. Such situations are naturally modeled by (discrete-time) temporal graphs [10, 11], where the nodes (corresponding to airports or railway stations in the example) are static, but the arc set changes in discrete time steps. In this case, paths of interest are so-called temporal paths that respect the temporal nature of the graph, meaning that the next arc of a path must always start at a node after the previous one has arrived there. Given the temporal aspect, several natural interpretations of a “shortest” temporal path arise depending on the specific objective of interest. The most prominent objectives include minimizing the arrival time at the destination, the duration (difference between arrival time and start time), or the traversal time (sum of arc lengths) of a path, or maximizing its start time (for a given latest possible arrival time).

In many situations, for instance when choosing a path in an airline or railway network, one might actually not only be interested in optimizing one of these objectives, but several at the same time, meaning that the considered shortest path problem in a temporal graph becomes multiobjective. The solutions one is typically interested in when considering optimization problems with several potentially conflicting objectives are called efficient solutions or Pareto optimal solutions [7]. An efficient solution is characterized by the property that it cannot be improved in any objective without simultaneously worsening at least one other objective. The vector of objective values (the image of an efficient solution in the objective space) is called a nondominated image or a nondominated point [7]. Each nondominated image corresponds to a different trade-off among the objectives, and the goal in a multiobjective optimization problem typically consists of computing all nondominated images together with one corresponding efficient solution for each of them.

These observations motivate a systematic study of the (single-source) multiobjective temporal shortest path problem. Given a temporal graph, a source node $s$, and $p$ objectives, this problem consists of computing, for each destination node $v$, all nondominated images of temporal $s$-$v$-paths together with one corresponding efficient path for each image. For a very general class of objectives, including arrival time, duration, traversal time, start time, and many others, this problem has recently been studied in [1] under two assumptions on the objectives. The first assumption states that the value of a path in an objective cannot improve when the path is extended by another arc (referred to as monotonicity in the following). Monotonicity generalizes the nonnegativity assumption on arc lengths required for label setting algorithms in the classical additive shortest path problem. The second assumption, referred to as isotonicity in the following, states that if one path has an objective value at least as good as that of another path, then this relation is preserved when both paths are extended by the same arc. Using both assumptions, Bazgan et al. [1] present a general label setting algorithm for the multiobjective temporal shortest path problem with an arbitrary number of objectives. However, similarly to the classical static shortest path problem, where arc lengths are not necessarily nonnegative, the monotonicity and isotonicity assumptions imposed in [1] are not satisfied by all relevant objectives in temporal shortest path problems. For example, in airline networks it can often be observed that booking a flight from airport A via airport B to airport C is strictly cheaper than booking only the first leg from A to B. Thus, when minimizing travel cost, the objective violates monotonicity. This phenomenon can be systematically exploited via dedicated websites such as Skiplagged (https://skiplagged.com) using a technique known as hidden-city ticketing [15], or skiplagging, in which a passenger books a longer itinerary but intentionally skips one or more final flight legs.

In this paper, we therefore study the single-source multiobjective temporal shortest path problem with general objectives that are not required to satisfy monotonicity and/or isotonicity. As we demonstrate through explicit examples in Section 2, a key difficulty in the case of general objectives, even for static graphs, is that cycles may need to be traversed an arbitrary finite number of times in order to generate all nondominated images. We therefore consider a restricted problem variant in which a maximum admissible path length $K$ is given as part of the input, and only paths containing at most $K$ arcs are considered. For this setting, we develop general label correcting algorithms and prove their correctness both for isotonic objectives without monotonicity (Section 3) and for fully general objectives where neither property is assumed (Section 4). The key difference between these two settings is that isotonicity permits the removal of dominated labels during each iteration, whereas in the absence of isotonicity dominated labels can only be safely removed after the final iteration. In Section 5, we further establish several sufficient conditions under which no bound on the admissible path length is required. Under these conditions, our algorithms compute all nondominated images when executed for a suitably bounded number of iterations. These conditions include, in particular, rational-valued additive objectives, thereby generalizing the classical setting of additive cost objectives on static graphs.

This section contains the definitions and terminology used throughout the paper.

Let $n≔|V|,m≔|R|$, and let ${\delta }^{+}(v)$ and ${\delta }^{-}(v)$ denote the set of outgoing and ingoing arcs of $v\in V$, respectively. Moreover, let $[k]≔\{1,\mathrm{\dots },k\}$ for $k\in {\mathbb{N}}_{\ge 1}$ and $[0]≔\mathrm{\varnothing }$. The arrival time of an arc $r\in R$ at its end node $\omega (r)$ is $\tau (r)+\lambda (r)$. Therefore, a temporal path $P=(v_0,r_1,v_1,\mathrm{\dots },r_k,v_k)$ is a nonempty, finite sequence of nodes and temporal arcs such that, for each $i\in [k]$, it holds that $\alpha (r_i)=v_{i-1}$ and $\omega (r_i)=v_i$, and for each $i\in [k-1]$, it holds that $\tau (r_i)+\lambda (r_i)\le \tau (r_{i+1})$. We call a path $P=(v_0)$ with no arcs a zero-arcs path. The length of a path $P=(v_0,r_1,v_1,\mathrm{\dots },r_k,v_k)$ is the number of arcs it is composed of, i.e. $|P|=k$. A temporal $s$-$v$-path is a temporal path $P=(v_0,r_1,v_1,\mathrm{\dots },r_k,v_k)$ with $v_0=s$ and $v_k=v$, and we call the nodes $\alpha (P)≔v_0$ and $\omega (P)≔v_k$ the start node and the end node of $P$, respectively. A path $P=(v_0,r_1,v_1,\mathrm{\dots },r_k,v_k)$ is called simple if the nodes $v_0,\mathrm{\dots },v_{k-1}$ are pairwise distinct, and it is called a (temporal) cycle if $k\ge 1$ and $v_0=v_k$. The concatenation of two paths $P=(v_0,r_1,v_1,\mathrm{\dots },r_k,v_k)$ and $P^{\prime }=(v_0^{\prime },r_1^{\prime },v_1^{\prime },\mathrm{\dots },r_{k^{\prime }}^{\prime },v_{k^{\prime }}^{\prime })$ with $v_k=v_0^{\prime }$ and $\tau (r_k)+\lambda (r_k)\le \tau (r_1^{\prime })$ is defined as the path $(P,P^{\prime })≔(v_0,r_1,v_1,\mathrm{\dots },r_k,v_k,r_1^{\prime },v_1^{\prime },\mathrm{\dots },r_k^{\prime },v_{k^{\prime }}^{\prime })$. Given a path $P=(v_0,r_1,v_1,\mathrm{\dots },r_k,v_k)$, any path $(v_i,r_{i+1},v_{i+1},\mathrm{\dots }{r}_j,v_j)$ with $0\le i\le j\le k$ is called a subpath of $P$.

We evaluate the quality of paths using several criteria or objectives. The following definition generalizes the definition from [1], where nonnegative, rational-valued objectives are considered, to values in any totally ordered set. Since our analysis depends only on the structural properties of the objectives and not on a particular encoding, we do not fix a concrete representation.

For instance, maximizing the start time would be expressed by the latest start time objective $({\mathbb{Q}}_{\ge 0}\cup \{+\mathrm{\infty }\},\le ,\tau ,\min ,+\mathrm{\infty },\max )$, and minimizing the arrival time by the earliest arrival time objective $({\mathbb{Q}}_{\ge 0},\le ,\lambda +\tau ,\max ,0,\min )$. Note that, as in [1], the binary operator $\oplus$ is required to be associative, i.e., $(a\oplus b)\oplus c=a\oplus (b\oplus c)$ for all $a,b,c\in M$, but not commutative, i.e., we can have $a\oplus b\ne b\oplus a$. Next, we define two properties of objectives, which were jointly referred to as monotonicity in [1]. Here, we define them separately for ease of discussion.

Note that the isotonicity condition can be formulated equivalently by asking that $a\ge a^{\prime }$ with $a,a^{\prime }\in M$ implies that $a\oplus b\ge a^{\prime }\oplus b$ for all $b\in M$. We use both formulations in the following. The next definition defines objective values of paths in a temporal graph.

Intuitively, monotonicity of an objective $(M,\le ,f,\oplus ,\overline{0},\mathrm{dir})$ means that extending a path $P$ by an additional arc $r$ cannot improve its objective value $f(P)$. Isotonicity means that, if two temporal paths $P_1$ and $P_2$ with objective value $f(P_1)$ at least as good as $f(P_2)$ are extended by the same arc $r$, then the objective value $f(P_1)\oplus f(r)$ of the extension of $P_1$ will also be at least as good as the objective value $f(P_2)\oplus f(r)$ of the extension of $P_2$.

The following definitions introduce required terminology from multiobjective optimization.

In static shortest path problems, cycles that can be repeatedly traversed to improve an objective value are referred to as negative (cost) or improving cycles. In the temporal case, such cycles must necessarily be zero-duration cycles (i.e., all arcs in the cycle have traversal time zero and the same start time), and in our setting with general objectives, whether traversing a zero-duration cycle improves an objective might depend on the subpath traversed previously. This is made formal in the following definitions.

Thus, an improving cycle $C$ in objective $j$ is a zero-duration cycle reachable from $s$ that can be traversed indefinitely, such that each traversal can eventually be followed by further traversals yielding strictly better values in objective $j$. In contrast to additive cost objectives on static graphs, an improving cycle in a temporal graph need not improve the objective at every repetition. Nevertheless, it may cause the set of nondominated images of $s$-$v$-paths to be infinite or empty for some nodes $v$.

In this section, we study the SSMTSPP-MPL with isotonic objectives that are not required to satisfy monotonicity in the sense of Definition 3; we refer to this variant as the isotonic SSMTSPP-MPL. This setting generalizes the classical additive case in which arc costs may be negative. In that case, isotonicity holds trivially, whereas monotonicity fails whenever negative arc values are permitted.

Our label correcting algorithm for isotonic objectives is given in Algorithm 1. Due to isotonicity, nondominated images can arise only from extensions of nondominated labels. Hence, dominated labels can be discarded in each iteration.

Observe that the earliest arrival time objective $({\mathbb{Q}}_{\ge 0},\le ,\tau +\lambda ,\max ,0,\min )$ is isotonic. Hence, using it as the first objective is consistent with the assumptions of Algorithm 1.

We begin by establishing two propositions concerning the label sets $L(v,k)$ generated by Algorithm 1. Their proofs adapt the main arguments used in the correctness proof of the label correcting algorithm for the static multiobjective shortest path problem (see, e.g., [6]) to the temporal setting with isotonic objectives.

In this section, we present a label correcting algorithm (Algorithm 2) for the SSMTSPP-MPL in the general case where the objectives are neither required to be monotone nor isotonic. In the absence of isotonicity, labels corresponding to nondominated images may arise exclusively from extending dominated labels. Therefore, dominated labels cannot be discarded in earlier iterations, in contrast to Algorithm 1.

The proof of correctness of Algorithm 2 is similar to the proofs of Proposition 16 and Theorem 18. The key difference is that dominated labels are removed only at the end of the final iteration $k^{\prime }\le K$, immediately before termination. Consequently, in all iterations , each set $L(v,k)$ generally contains not only labels corresponding to images of $k$-efficient paths, but one corresponding label for each possible image of an $s$-$v$-path of length at most $k$. As a result, the size of $L(v,k)$ can no longer be bounded by the number of $k$-nondominated images of $s$-$v$-paths as in Corollary 20; in fact, it may be exponential in this number. Nevertheless, by arguments analogous to those for Algorithm 1, the following statement holds for Algorithm 2:

Note that, for monotone but non-isotonic objectives, the same general algorithm is required since monotonicity alone does not justify discarding dominated labels in earlier iterations. Hence, all possible images must be retained until immediately before termination.

Example 11 in Section 2.1 shows that temporal paths of arbitrarily large finite length may need to be considered in the SSMTSPP, even when all objectives are isotonic. Consequently, Algorithms 1 and 2 can, in general, solve the problem only when a maximum admissible path length $K$ is imposed. In Section 5.1, we establish several sufficient conditions under which no such bound is required. Under these conditions, Algorithm 1 correctly solves the SSMTSPP for isotonic objectives and Algorithm 2 does so for arbitrary objectives when executed for a sufficient, precomputable number of iterations. Section 5.2 then considers the specific isotonic setting of rational additive objectives, which generalizes the classical additive cost setting, and shows that executing Algorithm 1 for $m=|R|$ iterations suffices to solve the SSMTSPP.