On the Shortest Path Problems with Edge Constraints

The goal of this work is to provide a brief classification of some Shortest Path Problem (SPP) variants that include edge constraints and that find applications in several different contexts, including optical networks, transportation and logistics. One of the most broad and notable classes of edge-constrained SPPs is given by Resource Constrained Shortest Path Problems (RCSPPs). In RCSPPs, in addition to the customary directed graph G=(V, A) and edge-distance function, a L-dimensional vector of resources R is defined. Essentially, each resource is related to relevant link attributes that need to be accounted for in the planning of the path. Accordingly, a path P* is optimal whenever it is minimal w.r.t. the distance function, and satisfies the restrictions enforced on the resources Other variants can involve colors assigned to the nodes and/or the edges of the graph and/or reload costs. These kinds of problems have relevant applications in network reliability. Particularly interesting is the so-called k-Color SPP, where a color is assigned to each edge and the minimum path from a given source node s to a target node t must not cross more than k differently colored edges. As for the use of reload cost, a reload cost r(b, c) is assigned to each pair of colors (b, c) and represents the amount to be paid if in a path P an arc of color c is traversed after an arc of color b.