Multi-Criteria Route Planning with Little Regret

A multitude of algorithms and heuristics has been proposed for all three main query types for multi-criteria route planning mentioned above. A* variants tailored to bi-objective search (BOA*) or multi-objective search (MOA*) have been demonstrated to greatly reduce the search space compared to Pareto-Dijkstra for FPS and CSP queries [24, 2, 20]. Methods to approximate the Pareto frontier were described in [15, 30]. In [29], an anytime approach was introduced that discovers a subset of Pareto-optimal paths quickly and then adds new solutions over time. A recent overview of the development of multi-objective route planning is provided in [27].

Even more pronounced speed-ups can be achieved if preprocessing is applied to the input graph. In [28], query answering for bi-criteria FPS using a contraction hierarchy (CH) data structure was reported to be two orders of magnitude faster than with BOA*. CH was also successfully applied to accelerate CSP [23, 13] as well PSP queries [12]. In [16], it was shown that filtering dominated points can be the bottleneck in bi-criteria CH construction as well as query answering. There, faster methods were proposed to compute Pareto-optimal path sets. But if the final set size remains large, the approach might still be too slow in practice. In all of these preprocessing-based techniques, sets of Pareto-optimal paths are precomputed and stored between selected pairs of nodes. While [12] allows to obtain approximate query results faster by only considering a subset of stored solutions on query time, non of the techniques apply filtering during the preprocessing, which results in data structures of substantial size.

We show how multi-criteria route planning can be integrated with regret minimization. Compared to existing filtering methods, regret-based filtering has the advantage that it works for an arbitrary number of objectives and provides the user with the power to decide how many Pareto-optimal solutions shall be maintained to not exceed memory or running time resources. We first prove new theoretical properties of regret minimizing sets that are crucial for their application to route planning. As one main result, we show that the regret value does not deteriorate if we concatenate paths and combine their (filtered) solutions. This is important for many preprocessing-based techniques, in which this operation frequently occurs, for example, in multi-criteria contraction hierarchies (CH).

We describe how to construct the CH data structure with regret-based filtering as part of the preprocessing step (and thus significantly reduced space consumption), such that CSP and PSP queries can be answered much faster but with almost no loss in solution quality. As computing the solution subset with smallest regret poses an NP-hard problem, we also propose a novel and very efficient divide & conquer heuristic to compute high-quality subsets. In our experimental evaluation, we demonstrate that our new heuristic significantly outperforms the prevailing algorithm in solution quality, with only a small increase in running time. Furthermore, we show that using this heuristic as a subroutine for multi-criteria route planning results in well-performing preprocessing and query algorithms, even for a large number of cost dimensions.

Next, we prove a crucial property of the regret measure, namely that it does not stack when we combine partial solutions. This allows us to guarantee a good output quality when integrating regret-based pruning into various route planning algorithms, even if they need to combine partial solutions frequently. To concisely phrase our result, we introduce the following notations: With $P_{ab}$ we refer to the set of cost vectors of Pareto-optimal paths from $a$ to $b$, and with $P_{ab}^{\prime }$ to a subset with regret $r_{ab}$. For two sets of cost vectors $P,Q$, we use $P\oplus Q:=\{p+q|p\in P,q\in Q\}$ to denote the set of elements derived from pairwise addition.

Contraction hierarchies (CH) were shown to be a very powerful technique for accelerating bi- and multi-objective route planning queries [9, 13, 12, 28, 16, 6, 3].

In the CH preprocessing phase, nodes are ordered by a ranking function $r:V\to [n]$. Then, so called shortcut edges are inserted between nodes $v,w$ if and there exists at least one Pareto-optimal path from $v$ to $w$ that does not contain a node of rank higher than $r(w)$. The shortcut edge $e=\{v,w\}$ represents all such Pareto-optimal paths from $v$ to $w$ and thus gets assigned the respective set of cost vectors $S(e)$. To obtain this shortcut set $E^{+}$ efficiently, a bottom-up approach is used. For original edges $e$, the set $S(e)$ initially only contains the cost vector associated with that edge. Then the nodes are considered in the order implied by the ranking and are contracted one-by-one. In the contraction step for node $v$, it is checked for all pairs of neighbors $u,w$ of $v$ whether $S(uv)\oplus S(vw)$ encodes Pareto-optimal paths from $u$ to $w$. If this is the case, a shortcut from $u$ to $w$ is added (if it not already exists) and $S(uw)$ is augmented with the relevant cost vectors from $S(uv)\oplus S(vw)$. Then, $v$ and its incident edges are temporarily deleted from the graph. Note that by construction it holds that after each contraction the Pareto-optimal path costs between the remaining nodes in the graph are the same as in the original graph. After all nodes have been contracted, all temporarily deleted nodes and edges are inserted back into the graph.

In the resulting CH-graph, queries are answered with a bi-directional run of the Pareto-Dijkstra algorithm (or a MOA* variant). Here, forward and backward search only relax edges $(v,w)$ incident to a node $v$ if $r(w)>r(v)$. This significantly reduces the search space but can be proven to nevertheless ensure correct query answering. To not only obtain the cost vectors of Pareto-optimal paths but also the paths themselves, a cost vector $c\in S(uw)$ stores references to $c_1\in S(uv)$ and $c_2\in S(vw)$ with $c_1+c_2=c$. This allows to recursively unpack a path that contains shortcut edges to a path that consists solely of original edges.

The memory consumption of the CH graph and the query performance crucially depend on the number of shortcut edges and especially the sizes of the cost vector sets $S(e)$ associated with them. A simple approach to reduce the set sizes is to apply regret-based filtering to all $S(e)$ independently with some fixed size upper bound $k$. By virtue of Theorem 1, the regret for the result of any FPS query is upper bounded by the maximum regret obtained for any shortcut. But if one is interested not only in the path costs but also the paths themselves, the approach is insufficient. This is because we can no longer guarantee that the path unpacking procedure is successful, as for $c\in S(uw)$ with $c_1+c_2=c$ and $c_1\in S(uv),c_2\in S(vw)$ either $c_1$ or $c_2$ (or both) could have been pruned from their respective sets. Therefore, we use the following bottom-up approach instead: We process the edges/shortcuts $e=\{u,w\}$ ordered by $\min \{r(u),r(w)\}$. For a shortcut $e=\{u,w\}$ we consider all pairs of edges $\{u,v\},\{v,w\}$ with and construct $S(e)$ as the union of $S(uv)\oplus S(vw)$. Then, we apply regret-based pruning to $S(e)$. In this way, we guarantee that each cost vector that remains in $S^{\prime }(e)$ is represented by two cost vectors in $S^{\prime }(uv)$ and $S^{\prime }(vw)$, respectively. Figure 2 demonstrates the difference of maintaining the Pareto-optimal cost vector sets versus applying regret-based pruning on the set of cost vectors with a fixed size $k=3$.

For PSP queries there is no need to apply label pruning on query time, as the personalized weight vector reduces the edge costs to scalar values of which only the minimum needs to be maintained. But for FPS and CSP queries, label sizes tend to become huge during the search. A simple way to integrate regret pruning into answering FPS queries is to apply it whenever forward and backward search meet in bi-directional search. For query answering with CH, bi-directional search is the standard and it is also used as a standalone to reduce query time and space consumption [2]. For a node $v$ with a forward label $P_{st}$ and a backward label $P_{vt}$, computing $P_{sv}\oplus P_{vt}$ can be very time consuming if both sets are large. First applying regret-based pruning to both sets to reduce them to a size of $k$, respectively, allows to restrict the number of relevant elements to inspect to $k^2$. According to Theorem 1, the resulting regret is upper bounded by the maximum of the individual regrets.

However, we can also use regret pruning within the forward or backward (or in unidirectional) search as follows. Whenever a node label size $|P_{sv}|$ exceeds a threshold $t$, e.g. $t=2k$, we apply pruning to reduce the size back to $k$ and then only proceed with the reduced label. Here, the regret might increase as shown in Lemma 2. However, this approach allows us to limit the space consumption of a query to $𝒪(tn)$ and the cost of an edge relaxation to $𝒪(t)$.

We propose a novel hierarchical regret minimizing algorithm HRMS that produces representative subsets of size $k$ for arbitrary dimension $d$. The divide and conquer approach partitions the input set into smaller subsets and applies any pre-existing regret minimizing algorithm on each of the subsets to obtain intermediate regret minimizing sets. These sets are then merged in a hierarchical manner until only the final regret minimizing set remains. The hierarchical regret minimizing algorithm allows for user-defined adjustments to its hierarchy in order to obtain desired trade-offs between running time and solution quality. Figure 3 illustrates the basic algorithmic concept. Algorithm 1 shows the respective pseudo-code.

Here, $\text{RMS}(P,k^{\prime })$ is supposed to return a subset of $P$ of size $k^{\prime }$ with (hopefully) small regret. In our implementation, we use the Cube algorithm [18] for this purpose, due to its simplicity and efficiency even for high dimensions. However, one could plug in any other RMS algorithm as well. $\text{Partition}(S,p)$ is supposed to partition $S$ into $p$ subsets, and $\text{Merge}(S_A^{\prime },S_B^{\prime },k^{\prime })$ to merge two point sets into one and to reduce the resulting set to the desired size. We next discuss sensible implementations of these two important routines.

The goal of the Partition method is to break the input set $S$ down into sufficiently small subsets of roughly similar size for efficient processing. A very simple partitioning method, is to randomly assign $\frac{n}{p}$ points to each of the $p$ subsets. However, it is advantageous to partition the input set in such way that the smaller subsets cover continuous parts of the multi-dimensional space. A good partition with regards to the HRMS algorithm yields subsets containing points from the Pareto front i.e. non-dominated points together with dominated points. During the conquer phase of the algorithm we handle each subset separately and reduce the number of overall points during the merging phase. In the worst case, all Pareto-optimal points are in one subset. Then, during the conquer phase we would exclude many such points in favor of dominated points from other subsets. Thus, it is ideal to have Pareto-optimal points in each of the $p$ subsets to ensure that the RMS algorithm is able to retrieve all of them. Our idea to achieve this is to divide the input space into $p$ equally-sized wedges between the x- and y- axes and to assign points to the wedges they are contained in. This likely ensures that each of the wedges covers a wide range of point values and also includes some Pareto-optimal points.

Figure 4 depicts an exemplarily partitioning of the input space in $d=2$ and $d=3$ dimensions.

The goal of the MERGE operation is to combine two point sets $S_A^{\prime }$ and $S_B^{\prime }$ but only keep the best $k$ points among them. A naive approach would again be to just randomly sample $k$ points from the union $S_A^{\prime }\cup S_B^{\prime }$. However, this method is unlikely to produce good results. Since we already use an RMS algorithm to obtain the intermediate sets $S_A^{\prime }$ and $S_B^{\prime }$, a natural way to merge would be to rerun said RMS algorithm on their union. In practice, this merging technique significantly increases the running time of the HRMS algorithm, though. A third method is to greedily remove points from the union until the desired output size is reached. Ideally, we would like to always select the point whose removal increases the regret the least. But computing the regret ratio requires to solve a linear program [18] and is thus also time intensive. As a compromise, we propose a sorted merge algorithm. It initially sorts $S_A^{\prime }$ and $S_B^{\prime }$ decreasingly in each of the $d$ dimensions. Then, the first $\lfloor \frac{k}{2d}\rfloor$ points from the sets $S_A^{\prime }$ and $S_B^{\prime }$ corresponding to the decreasing order in the first dimension are retrieved. This procedure is repeated for each dimension to obtain the output set of given size. In this way, we select the promising points in each dimension.

Considering the running time of the HRMS algorithm, we define $t_{\text{Part}}$ as the running time required by the partitioning method, $t_{\text{RMS}}$ as the maximum running time of the chosen RMS algorithm executed on a subset $S^{\prime }$, and $t_{\text{Merge}}$ be the running time of the chosen merging technique. With the partition method producing $p$ subsets, the total running time is in $𝒪(t_{\text{Part}}+p\cdot (t_{\text{RMS}}+t_{\text{Merge}}))$. Wedge-based partitioning takes $𝒪(nd)$. The Cube algorithm executed on a point subset $P$ with a desired output size of $k^{\prime }=kd$ takes $𝒪(k^{\prime }|P|d)$. Thus, the total time for processing all $p$ subsets $P\in 𝒫(S)$ is in $𝒪(kn{d}^2)$. The merging calls take $𝒪(dn\log n)$ to go from $p$ subsets to $p/2$ subsets. Thus, the total merging time is in $𝒪(dn\log n\log p)$. As we have $p\le n$, we get an overall running time in $𝒪(nd(dk+{\log }^{2}n))$ which is close to the theoretical running time of the Cube algorithm. We will see that the two algorithms indeed also have similar practical running times, while HRMS produces sets with significantly smaller regret than Cube.

First, we investigate the performance of our proposed HRMS algorithm and compare it to the Cube baseline. We chose the Cube algorithm since it scales well in arbitrary dimension and allows for a straightforward implementation. For our experiments, we use input sets $S$ consisting of $n$ points in $d$ dimensions and obtain subsets $S^{\prime }\subset S$ of size of $k=2d$. Generating the input sets is done by randomly sampling $d$ values from the uniform distribution in the range $[0,nd)$ for each point. Running times and regret ratios are always averaged over 100 generated instances per tested value of $n$.

In order to evaluate the solution quality of the HRMS algorithm, we need to obtain the regret $r(S,S^{\prime })$ of the solution subset $S^{\prime }$ which is defined by the most regretful user. To this end, we uniformly sample $1,000$ users represented by their weight vectors ${\alpha }_u\in {[0,1]}^d$. We approximate the regret of the solution subset $S^{\prime }$ by computing the regret $r_u(S,S^{\prime })$ for each sampled user $u$ and extract the maximum among them. A similar approach is done in [1] by randomly sampling $20,000$ user weight vectors. We experimentally explore the effect of the sample size of users in the set $U$ on the resulting solution quality in Figure 5. Comparing sample sizes ranging from $|U|={10}^2,\mathrm{\dots },{10}^6$ we conclude that the obtained regret ratios for the solution subsets $S^{\prime }$ are sufficiently similar among the sample sizes when ensuring that the extreme values $0.0$ and $1.0$ are represented at least once per dimension. Since computing the regret ratio for a given user weight vector ${\alpha }_u$ involves traversing the entire input set $S$, we use a sample size of $1,000$ to efficiently approximate the regret ratio for our experiments.

Prior to the experiments, we want to evaluate the geometric partitioning with respect to the resulting subset sizes and asses how close this angle-based partitioning comes to an ideal partitioning of the input space. The partitioning divides the input set into $p$ subsets based on the position of points in the $d$-dimensional space. For the statistical assessment in Figure 6 input sizes of $n={10}^2,\mathrm{\dots },{10}^6$ in $d=2$ dimensions and the output size $k=4$ and intermediate output size $k^{\prime }=8$ are used to obtain $p$ subsets. The value of $p$ is determined such that $\frac{n}{p}>k^{\prime }d=16$. Per tested value of $n$, the partitioning described in Section 3.2 is executed on $100$ instances. Figure 6 reports on the average distribution of resulting subset sizes with the minimum, maximum and median size of subsets $P\in 𝒫(S)$ in the partition of the input set. Additionally, the number of subsets $p$ is also provided for each input size. An ideal partitioning yields equally-sized subsets each containing exactly $\frac{n}{p}$ points. This value depending on $n$ and $p$ is denoted as ideal (red markers).

The difference between the minimum and maximum subset sizes is fairly small considering input sets of up to 1 million points being divided into $p=2^{15}$ subsets. The smallest subsets contain 2 points and the largest 72 points. However, most observations in the distribution are much closer to the ideal subset size. The interquartile range for all input sizes always encloses the ideal subset size and the ${25}^{\text{th}}$ percentile is 12 points below the ideal value and the ${75}^{\text{th}}$ percentile is 20 points above the ideal value. Moreover, the median of actual subset sizes from the partitioning is within $3$ points of the ideal value. For $n\ge 1000$ the variation reduces to one point or less. The median is closer to the lower quartile value thus more subsets are slightly smaller than the median subset size.

Overall, the distribution of subset sizes is consistent throughout all input sizes. As the value of $p$ is equal for some input sizes e.g. $n=6\cdot {10}^5,\mathrm{\dots },{10}^6$, the ideal subset size varies, consequently shifting the box plots to a slightly higher subset size.

In conclusion, the geometric partitioning based on angles to the $x$-axis produces subsets which are fairly equally-sized and close to the ideal subset size for a given value of $p$. Further, the advantages of dividing the input space geometrically in contrast to a random partitioning prevail as the former ensures an even coverage of the Pareto-optimal points among the subsets.

Figure 7 compares the regret ratios of the HRMS algorithm using the geometric partitioning and the random partitioning. The former divides the input space into equally-sized wedges between the x- and y-axes whereas the latter divides the input set into $p$ subsets using the indices of points within the set. The solution quality resulting from the geometric partitioning is clearly preferable compared to the random partitioning. In $d=2$ dimensions, the improvement in regret ratio is up to a factor of $227$ on average to the random partitioning. The beneficial behavior of the geometric approach was observed consistently up to $d=10$ dimensions. Only for higher dimensions both versions of HRMS provide similar regret ratios. Thus, we conclude that the geometric partitioning is indeed preferred over the random partitioning in practice matching the previous theoretical considerations.

Considering the dimensional scalability of the HRMS algorithm, we use input sets of up to $n={10}^6$ points in $d=2,\mathrm{\dots },50$ dimensions with the selection of $d=2,5,10,50$ being depicted in Figure 8 (running time) and Figure 9 (solution quality). For all tested dimensions, we observe the HRMS algorithm requiring slightly more time than the Cube algorithm executed directly on the input set which is in compliance with our theoretical analysis. However, as the number of dimensions increases, the practical running time of HRMS algorithm gets closer towards the running times of the Cube algorithm. In terms of the solution quality, the HRMS algorithm consistently outperforms the Cube algorithm by providing significantly lower regret ratios among all tested dimensions. The most significant improvement by the HRMS algorithm of up to a factor of $174$ on average is obtained in $d=2$ dimensions compared to Cube. In $d=5$, $d=10$ and $d=50$ dimensions, the average improvement of HRMS compared to Cube is by factors of $1.49$, $1.40$ and $1.48$, respectively. However, the HRMS algorithm optimizes for $50$ objectives simultaneously and provides small representing subsets that still ensure that the most regretful user is about $79\%$ happy with the provided solution instead of the full ${10}^6$ alternatives in the input set. Hence, we conclude that the geometric partitioning together with the hierarchical merging of the HRMS algorithm is consistently advantageous in terms of the solution quality as opposed to the state-of-the-art algorithm Cube.

Further, we evaluate the ratio of Pareto-optimal points in the solution subsets of the HRMS algorithm compared to the Cube algorithm in Figure 10 for $d=2$ and $d=3$ dimensions and up to $n={10}^6$ input points. In both dimensions, the HRMS algorithm retrieves more Pareto-optimal points in its output set than the Cube algorithm. More precisely, for two dimensions the HRMS provides a Pareto ratio of $87\%$ while the Cube only achieves $70\%$. In three dimensions, the Pareto ratios are $91\%$ for the HRMS and $77\%$ for the Cube algorithm. Hence, the improvement in solution quality provided by the HRMS algorithm is due to retrieving more Pareto-optimal points from the input set $S$ than the Cube algorithm. During the partitioning phase we emphasize on dividing the input space in such way that each subset ideally contains a small fraction of the Pareto frontier. Further, the sorted merge during the hierarchical merging ensures to select points having high values in each of the dimensions which corresponds to the concept of Pareto-optimality.

We now want to evaluate the HRMS algorithm on input sets following different distributions which are closer to realistic input scenarios. To this end, we execute the algorithms on Gaussian distributed input sets. For the Gaussian generator, we sample $d$ values from the normal distribution with mean $\mu =\frac{nd}{2}$ and standard deviation $\sigma =\frac{\mu }{4}$ ensuring that all values are positive integers. The corresponding regret ratios for the HRMS algorithm are displayed in Figure 11. Again, the HRMS algorithm consistently produces lower regret ratios than the Cube algorithm on all tested dimensions up to $50$. On average among the input sizes, we gain a maximal improvement factor of $2.6$ in $d=2$ dimensions compared to the Cube algorithm. Over all dimensions and input sizes, the average improvement of the HRMS algorithm is by a factor of $1.24$.

For studying the impact of regret-based filtering in multi-objective route planning, we used an established benchmark, namely the German road network with $d=10$ real cost dimensions²²2https://www.dropbox.com/s/tclrjdkfhabu27h/ger10.zip?dl=0 such as the distance, travel time, positive height difference and energy consumption for electric vehicles [12]. Each cost dimension was normalized to the interval $[0,1]$. To study the scalability of the different methods, we selected cutouts with the number of nodes ranging from 10000 to 3 million.