Keywords

1 Introduction

Shortest Path Problems (SPPs) represent one of the most significant and investigated family of problems in Operations Research. The formulations that describe members of this class are often intuitive and easily relatable to real-world scenarios, while their broad applicability implies that often SPPs need to be solved as sub-tasks in many other combinatorial problems, such as Maximum-Flow Minimum-Cost Problems or Vehicle Routing Problems.

While notably the classical SPPs can be optimally solved using polynomial algorithms, a more recent stream of research focused on the solution of either dynamic [12, 13] or constrained-SPPs [11, 14, 20], studying both exact and heuristic techniques. In this work, we define and formally state a novel problem: the k-Color Shortest Path Problem (k-CSPP), whose objective is to find a shortest path in a weighted edge-colored network, with a constraint on the maximum number of different colors that can be used. In the following we will use interchangeably the terms “colors” and “labels”.

Edge-colored networks received a fair share of attention in the scientific literature, given their aptness for the depiction of complex and diverse relations among nodes. This feature proved to be beneficial in a wide variety of application fields, such as: computational biology [9], telecommunications [23], as well as in the analysis of transportation networks [1], and conflicts resolution [21].

In [4], it is proven that to find a path from a source node s to a destination node t with maximum k colors is a NP-complete problem, by reduction from the 3-SAT problem. We observe how any instance of the decisional problem of finding an s − t path with at most k colors can be represented as an instance of k-CSPP, where each edge has null cost. Therefore, a polynomial algorithm for the k-CSPP would efficiently solve the decisional problem described in [4]. Consequently, k-CSPP is NP-hard.

In the study of edge-colored graphs, many works—of both theoretical and experimental interest—are concerned with the investigation of specific properly-colored edge structures, where a coloring is said to be proper whenever any two adjacent edges differ in color. These structures include for example: paths, trails, trees and cycles; see for example [17]. On the other hand, some classical optimization problems—such as the Minimum Spanning Tree (MST), the Traveling Salesman Problem (TSP), and the Longest Path Problem (LPP)—have all been extended to the case of edge-colored graphs, taking labels into account either in the objective function or in their constraints.

For example, the Minimum Label Spanning Tree is defined in [8] as a variant of the classical MST in which the cost of the spanning tree is given by the number of different edge-labels used. The authors of [8] describe a heuristic technique and an exact method based on the A* algorithm. The problem is further investigated in [6] which present a logarithmic approximation algorithm and a comparative study of several metaheuristic techniques, respectively. A strictly related generalization, the k-labeled Spanning Forest Problem, is studied in [7].

In [19], Jozefowiez et al. present an in-depth analysis of the Minimum Label Hamiltonian Cycle Problem (MLHCP). The MLHCP consists in the determination of an Hamiltonian cycle that presents the minimum total number of different edge-labels used. Moreover, in [19] two variations are introduced: the MLHP with length constraints and the Traveling Salesman Problem with label constraints (LCTSP). Aim of the LCTSP is to minimize the length of the tour—as in the classical TSP—while constraining the maximum number of different colors that can be used. The authors propose mathematical models and prove valid inequalities that are then included in branch-and-cut algorithms for the MLHCP and its two variants.

As an additional example, a special case of longest path on edge-colored graphs, the Orderly Colored Longest Path Problem, was recently studied in [5] by Carrabs et al. Suitably adapting existing formulations, the authors obtain several mathematical descriptions for the problem, that are then compared over a broad set of instances.

The main ground of interest for the k-CSPP arises in the field of telecommunications. While designing transmission networks, reliability is a crucial matter to ensure good performances and prevent data loss. As deeply discussed in [22] and [23], the robustness of a path-routed communication network can be achieved by means of path protection schemes, which make use of backup paths to ensure reachability in the case of single link failures. The backup path and the primary path are link-disjoint, and share the same source and destination. To prevent traffic loss, the backup path is activated whenever the primary path fails. On the other hand, often a single happening can cause the simultaneous failure of several links in the network. For instance, in WDM networks it is customary to bundle multiple fiber links in the same conduit. Consequently, even if these links are disjoint in the network layer, a damage to the conduit will cause the failure of all the links there bundled. The fibers sharing a common risk factor are said to be in the same Shared Risk Link Group, and are modeled with arcs of the same color. In [23], Yuan et al. address the failure minimization problem as a minimum-color path problem, in which each path is associated with one or more colors and each color is related to a given failure event. The authors support their approach arguing that by minimizing the number of colors involved in the path, the failure probability of the path can consequently be minimized. At the same time, while this argument handles different edge-labels, it does not include lengths in the comparison of different paths. Accordingly, a path with at most k different colors is connected if and only if failures do not occur in any of the k colors traversed in the path. If we make the assumption that color failures are mutually independent, and equiprobable—with probability p ∈ [0, 1]—, then the reliability of the path can be computed as (1 − p)k. Consequently, an upper bound on the number of different colors allows to have a probabilistic estimate on the reliability of the network. A similar argument can be repeated in the case of independent failure events with different probabilities.

With in mind a similar network reliability scenario, the k-CSPP handles risk adversity as a strict requirement, while optimizing path length. Hence, the mathematical models introduced in the present paper include distances in the objective function, while encompassing the use of few colors in a problem constraint.

The main contributions of this work are: (1) a first formal description of the k-CSPP and (2) the design of a branch and bound algorithm. The work is organized as follows: in Sect. 2 some related works on Constrained Shortest Path Problems are presented. The problem is formally introduced in Sect. 3, where a mathematical model is proposed. Section 4 describes the Branch and Bound implementation used to optimally solve the problem. Computational results and a comparative analysis of the performances of our Branch and Bound with respect to the CPLEX solver are presented in Sect. 5. Concluding remarks are given in Sect. 6.

2 A Brief Taxonomy of Shortest Path Problems with Edge Constraints

The goal of this section is to provide a brief classification of some Shortest Path Problem variants that include edge constraints, with the aim of pointing out their differences with the k-CSPP.

One of the most broad and notable classes of edge-constrained SPPs is given by Resource Constrained Shortest Path Problems (RCSPPs) [3, 20].

In RCSPPs, in addition to the customary directed graph G = (V, E) and edge-distance function , a L-dimensional vector of resources R is defined. Essentially, each resource is related to relevant link attributes that needs to be accounted in the planning of the path. Indeed, for each l = 1, …, L, to each (i, j) ∈ E is associated a resource attribute \(r_{ij}^l\). Accordingly, a path P ∗ is optimal whenever it is minimal w.r.t. the distance function d, and satisfies the restrictions enforced on the resources \(r_{ij}^l\).

As argued in [2], the resources and the subsequent constraints can be of multifold nature. In fact, resources can model both numerical (either cumulative or non-cumulative) and categorical (or index) attributes. Straightforward examples of cumulative numerical attributes are travel time or fuel consumption, whose total use in a path P is obtained adding up all the travel times or consumption along the edges belonging to P, as in [10].

On the other hand, road width is an example of numerical non-cumulative parameter; in cases like this the feasibility of a path P can be subject to average or bottleneck restrictions, in which either the average of the resource or its minimum (respectively maximum) has to respect some bounds. Finally, RCSPPs can include categorical attributes, that can be used to specify the type of connection among two nodes. Whenever the problem considers arcs with categorical attributes, the formulation can feature constraints such as: a feasible path cannot contain links whose attribute is equal to a specific value (or a set of specific values). For a more detailed discussion see [2, 18].

The fundamental difference between the k-CSPP and RCSPPs lies in the fact that the k-CSPP does not restricts color-sets a priori and there is a strong interdependence among arcs. In our scenario, indeed, the cost of a color as a resource is not constant during the exploration of the solution space: once that an arc with a certain color is traversed, all other arcs sharing the same colors turn free and thus can be inserted in the solution without placing additional burden on the color constraint.

Another related idea studied in path problems on edge colored graphs consists in the use of reload costs. For each couples of colors (b, c) a reload cost ρ b,c is the amount to be paid if in the path P an arc of color c is traversed after an arc of color b. Gourvès et al. [16] studied the problem of minimizing reload costs for walks, trails and paths, deriving the resulting computational complexities. On the other hand, [1] consider a general form of objective function that includes both distances and reload cost. Aside from their presence in the objective function rather than in the constraints, the main difference between reload costs and the modeling paradigm of the k-CSPP is that reload costs are fixed, and have to be taken into account any given time there is a change from a color to another. On the contrary, bounding the maximum number of different colors, as required in the k-CSPP, means to count just once a transition to a specific color, whatever the preceding color (if any) may be.

3 Mathematical Model

Let G = (V, E) be an undirected graph, with n nodes and m edges. Let the functions and be an edge-coloring and a non-negative distance function defined on E, respectively. The positive integer C(e), ∀e ∈ E, is said to be the color of edge e.

Let c(G) be the number of colors used to label the edges of G, for each color h ∈{1, …c(G)} all edges labeled with h are collected in color class C h, in a way that \(E = \bigcup _{h = 1}^{c(G)} C_h \).

The k-CSPP consists in finding a shortest path P ∗ = (v 1, v 2, …, v h) from a source node v 1 = s to a destination node v h = t, with s, t ∈ V , such that the number of different colors traversed in the path does not exceed k.

Introducing a Boolean decision variable x ij, for each edge [i, j] ∈ E, such that:

$$\displaystyle \begin{aligned} x_{ij} = \begin{cases} 1, & \text{if } \left[i,j\right] \text{ belongs to } P^*, \\ 0, & \text{otherwise,} \end{cases} \end{aligned}$$

and for each possible color h, a Boolean decision variable y h such that: y h = 1, if color h is traversed in P ∗, y h = 0 otherwise. Then, the problem can be formulated as follows:

$$\displaystyle \begin{aligned} & &z = \min \sum_{\left[i,j\right] \in E} d_{ij} x_{ij} {} \end{aligned} $$
(1a)
$$\displaystyle \begin{aligned} &\mbox{subject to:} & \notag\\ & &\sum_{j \in V \setminus \{i\}} x_{ji} - \sum_{j \in V \setminus \{i\}} x_{ij} = b_i, & &\forall i \in V {} \end{aligned} $$
(1b)
$$\displaystyle \begin{aligned} & &x_{ij}\leq y_h, & &\forall [i,j]\in C_h ,h = 1,\dots, c(G) {} \end{aligned} $$
(1c)
$$\displaystyle \begin{aligned} & &\sum_{h=1}^{c(G)} y_h \leq k {} \end{aligned} $$
(1d)
$$\displaystyle \begin{aligned} & &x_{ij} \in \{0,1\}, & &\left[i,j\right] \in E {} \end{aligned} $$
(1e)
$$\displaystyle \begin{aligned} & &y_h \in \{0,1\}, & &\forall h = 1,\dots, c(G) {} \end{aligned} $$
(1f)

with b i = −1 for i = s, b i = 1 for i = t, and b i = 0 otherwise.

The objective function (1a) minimizes the total cost d(p ∗) of the solution path p ∗. The constraints (1b) represent the flow balance constraint at each node. Constraints (1c) correlate arc traversal to color selection, and constraints (1d) impose the maximum number of colors that can be used in the path. Finally, the binary constraints are given in Eqs. (1e) and (1f).

4 Branch and Bound

The basic idea of the branch and bound here proposed consists in the observation that relaxing the color constraints (1d), the problem can be solved very efficiently by a classical shortest path algorithm. Consequently, at each node of the branching tree, a shortest path problem is solved on a given edge-colored graph G′ = (V, A′). Then, if \(p^*_{G'}\) is the optimal solution obtained, and \(c(p^*_{G'})\) is the number of different colors used in \(p^*_{G'}\), four cases can occur:

  • \(d(p^*_{G'}) = +\infty \): there is no path from s to d, the feasible region is empty, and the branching node becomes a leaf;

  • \(d(p^*_{G'}) \geq d(\hat {p})\): where \(\hat {p}\) is the incumbent solution. In this case, the branching node is fathomed due to the bounding criterion;

  • \(c(p^*_{G'}) \leq k\): the solution is feasible for the original problem, and the incumbent is updated if necessary;

  • \(c(p^*_{G'}) = l > k\): the solution is not feasible for the original problem.

In the last case, a branching operation is performed. Let C ∗ = {c 1, …, c l} be the colors used by the path \(p^*_{G'}\), for each i = 1, …, l a new branching node is generated on the graph G″ = (V, E″), where E″ = E′∖{e vw ∈ E′: C(e vw) = c i}.

Moreover, the strategy guiding the exploration of the branching tree is a depth-first mechanism, and the nodes of the tree are generated excluding colors according to their absolute frequencies in \(p^*_{G'}\). The lesser used the color, the earlier it is excluded from G′. The main target of this strategy is to obtain a feasible solution in the quickest way possible, in order exploit the bounding operation as much as possible. This aim is reflected by both the choice of the depth first strategy, and in the exclusion criterion considered for colors. The latter, indeed, tries to define a sub-problem favoring the constriction of colors that are less used in the computed path \(p^*_{G'}\).

5 Experimental Results

This section presents some computational experiments designed to compare the performances of the two exact solution strategies, the Branch and Bound technique described in Sect. 4, and the model presented in Sect. 3 and solved with ILOG CPLEX 12.9. Both the algorithms were coded in C++ using the flags -std=c++17 -O3 and compiled with g++ 8.2. The experiments were run on a INTEL i5-6400@2.70 GHz processor with 8GB of RAM. A time limit of 10 min has been used for both the algorithms.

The instances used in the experiments can be divided in two separate classes, both obtained with the a generator adapted from [15] to suitably introduce edge-colors. More specifically, the networks considered are either grid graphs or fully random networks. The total number of colors introduced in each graph amounts to either the 15% or 20% of the total number of edges.

Table 1 reports a summary of the instances included in the experimental phase. For each type, ten instances have been generated with different seeds.

Table 1 Instance parameters
Full size table

The computational results obtained by our Branch and Bound (B&B), and CPLEX—executed either with depth first (df) or breadth first (bf) strategy—are reported in Tables 2 and 3 for fully random and grid graphs, respectively. More specifically, for each instance type we report: the average time spent by the algorithms solving instances of that type (avg. time), and the number of instances of that type for which either an optimal (O) or feasible (F) solution has been found. This last information is collected in the column (O + F). Note that since each class is made up by 10 different instances, we have O + F ≤ 10; whenever the preceding inequality its strict, then for some of the instances not even a feasible solution could be found within the time limit.

Table 2 Results on random graphs
Full size table
Table 3 Results on grid graphs
Full size table

The results show how CPLEX is performing well on the smaller instances of the dataset, while the Branch and Bound approach is able to tackle larger instances, where the model becomes too large to be managed by CPLEX. For example, referring to graph types R15–R18, it is worthy to note that CPLEX can obtain just two feasible solutions—that happen to be optimal as well—within the required time limit. On the other hand, the branch and bound approach is able to obtain at least a feasible solution in 56 out of 60 total cases, guaranteeing optimality in 24.

Similarly, we can observe in Table 3 that even in the case of grid graphs our Branch and Bound outperforms CPLEX as the size of the network grows. Additionally, the results evidence higher computational times and a lower number of optimal solution found with respect to those reported in Table 2. For example, comparing the results obtained on instance classes G8 and R13—that have the same number of nodes—we can observe how the time spent by our Branch and Bound increased by 40%, and the number of optimal solution found within the time limit dropped by 50%. This behaviour is probably due to the greater sparsity of grid graphs, that implies increased difficulties in the construction of a feasible k-color path.

6 Conclusions and Future Work

This paper presented a new variant of constrained shortest path problem, the k-Color Shortest Path (k-CSPP). The problem is formally described and a Branch and Bound is proposed for its solution. The performances of the exact method here described are then compared to those achieved by CPLEX in the solution of the integer programming model. The results evidence how our Branch and Bound can manage larger instances with respect to CPLEX, achieving good performances in terms of both optimal and feasible solutions found.

As future research perspectives—inspired by classical constrained shortest path literature—we plan to investigate the use of an exact dynamic programming algorithm. Additionally, given the complexity of the problem, future investigation will exploit metaheuristic techniques to quickly obtain good sub-optimal solutions. Moreover, a larger set of instances will be generated to properly assess a comparison between the methods, and to establish a shareable benchmark for future works.